Vaucanson  1.4.1
rw_to_fmp.hxx
1 // rw_to_fmp.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2005, 2006, 2008 The Vaucanson Group.
6 //
7 // This program is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU General Public License
9 // as published by the Free Software Foundation; either version 2
10 // of the License, or (at your option) any later version.
11 //
12 // The complete GNU General Public Licence Notice can be found as the
13 // `COPYING' file in the root directory.
14 //
15 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
16 //
17 #ifndef VCSN_ALGORITHMS_RW_TO_FMP_HXX
18 # define VCSN_ALGORITHMS_RW_TO_FMP_HXX
19 
20 # include <vaucanson/algebra/concept/freemonoid_product.hh>
21 # include <vaucanson/automata/concept/transducer.hh>
22 # include <vaucanson/automata/concept/automata.hh>
23 # include <map>
24 
25 namespace vcsn
26 {
27  template<typename S, typename T,
28  typename SS, typename TT,
29  typename Self>
30  void
31  do_rw_to_fmp(const vcsn::TransducerBase<S>&,
34  const vcsn::Element<S, T>& trans,
36  {
37  typedef typename T::hstate_t hstate_t;
38  //Map source states with result states
39  std::map<hstate_t, hstate_t> m;
40 
41  //Input transducer type
42  typedef vcsn::Element<S, T> Trans_t;
43 
44  //Output FMP Automaton type
45  typedef vcsn::Element<SS, TT> FMP_t;
46 
47  typename FMP_t::monoid_t fmp(trans.structure().series().monoid(),
48  trans.structure().series().monoid());
49  typename FMP_t::semiring_t sg;
50  typename FMP_t::series_set_t ss(sg, fmp);
51 
52  typedef vcsn::Element<typename FMP_t::monoid_t::first_monoid_t,
53  typename FMP_t::monoid_elt_value_t::first_type>
54  first_monoid_elt_t;
55  typedef vcsn::Element<typename FMP_t::monoid_t::second_monoid_t,
56  typename FMP_t::monoid_elt_value_t::second_type>
57  second_monoid_elt_t;
58  typedef vcsn::Element<typename Trans_t::series_set_t,
59  typename Trans_t::series_set_elt_value_t>
60  mult_elt_t;
61 
62 
63  /*----------------------------.
64  | Creating the FMP automaton. |
65  `----------------------------*/
66 
67  // Adding states
68  for (typename Trans_t::state_iterator St = trans.states().begin();
69  St != trans.states().end();
70  ++St)
71  m[*St] = res.add_state();
72 
73  typename Trans_t::series_set_elt_t id_series(trans.structure().series());
74  id_series = vcsn::algebra::
75  identity_as<typename Trans_t::series_set_elt_value_t>::
76  of(trans.structure().series());
77 
78 
79  /*------------------------.
80  | Setting initial states. |
81  `------------------------*/
82 
83  for (typename Trans_t::initial_iterator St, next = trans.initial().begin();
84  next != trans.initial().end();)
85  {
86  //We need to store the next iterator before using the current one
87  //to avoid an invalid iterator after having called set_final.
88  //Indeed, set_final can delete the iterator if its second parameter
89  //is the zero of the serie.
90  St = next;
91  next++;
92 
93  typename FMP_t::series_set_elt_t s(ss);
94  typename FMP_t::monoid_elt_t mon(res.structure().series().monoid());
95  first_monoid_elt_t
96  first(res.structure().series().monoid().first_monoid());
97  second_monoid_elt_t
98  second(res.structure().series().monoid().second_monoid());
99  typename FMP_t::semiring_elt_t
100  weight(res.structure().series().semiring());
101 
102  mult_elt_t mult = trans.get_initial(*St);
103  if (mult != id_series)
104  {
105  hstate_t tmp = res.add_state();
106  typename mult_elt_t::support_t mult_supp = mult.supp();
107  for_all_const_(mult_elt_t::support_t, i, mult_supp)
108  {
109  first = *i;
110 
111  typename Trans_t::semiring_elt_t
112  output(trans.structure().series().semiring(), mult.get(*i));
113  typename Trans_t::semiring_elt_t::support_t
114  output_supp = output.supp();
115  for_all_const_(Trans_t::semiring_elt_t::support_t,
116  j,
117  output_supp)
118  {
119  second = *j;
120  weight = output.get(*j);
121  mon = typename FMP_t::monoid_elt_value_t(first.value(),
122  second.value());
123  s.assoc(mon, weight);
124  }
125  }
126  res.add_series_transition(tmp, m[*St], s);
127  res.set_initial(tmp);
128  }
129  else
130  res.set_initial(m[*St]);
131  }
132 
133 
134  /*----------------------.
135  | Setting final states. |
136  `----------------------*/
137 
138  for (typename Trans_t::final_iterator St, next = trans.final().begin();
139  next != trans.final().end();)
140  {
141  //We need to store the next iterator before using the current one
142  //to avoid an invalid iterator after having called set_final.
143  //Indeed, set_final can delete the iterator if its second parameter
144  //is the zero of the serie.
145  St = next;
146  next++;
147 
148  typename FMP_t::series_set_elt_t s(ss);
149  typename FMP_t::monoid_elt_t mon(res.structure().series().monoid());
150  first_monoid_elt_t
151  first(res.structure().series().monoid().first_monoid());
152  second_monoid_elt_t
153  second(res.structure().series().monoid().second_monoid());
154  typename FMP_t::semiring_elt_t
155  weight(res.structure().series().semiring());
156 
157  mult_elt_t mult = trans.get_final(*St);
158  if (mult != id_series)
159  {
160  hstate_t tmp = res.add_state();
161 
162  typename mult_elt_t::support_t mult_supp = mult.supp();
163  for_all_const_(mult_elt_t::support_t, i, mult_supp)
164  {
165  first = *i;
166 
167  typename Trans_t::semiring_elt_t
168  output(trans.structure().series().semiring(), mult.get(*i));
169  typename Trans_t::semiring_elt_t::support_t
170  output_supp = output.supp();
171  for_all_const_(Trans_t::semiring_elt_t::support_t,
172  j,
173  output_supp)
174  {
175  second = *j;
176  weight = output.get(*j);
177  mon = typename FMP_t::monoid_elt_value_t(first.value(),
178  second.value());
179  s.assoc(mon, weight);
180  }
181  }
182  res.add_series_transition(m[*St], tmp, s);
183  res.set_final(tmp);
184  }
185  else
186  res.set_final(m[*St]);
187  }
188 
189 
190  /*-----------------------.
191  | Creating transitions. |
192  `-----------------------*/
193 
194  for (typename Trans_t::transition_iterator Ed = trans.transitions().begin();
195  Ed != trans.transitions().end();
196  ++Ed)
197  {
198  typename FMP_t::series_set_elt_t s(ss);
199 
200  first_monoid_elt_t first(trans.structure().series().monoid());
201  second_monoid_elt_t
202  second(trans.structure().series().semiring().monoid());
203  typename FMP_t::monoid_elt_t
204  mon(res.structure().series().monoid());
205 
206  typename Trans_t::series_set_elt_t
207  series_elt(trans.structure().series());
208  series_elt = trans.series_of(*Ed);
209 
210  for (typename Trans_t::series_set_elt_t::support_t::const_iterator
211  i = series_elt.supp().begin();
212  i != series_elt.supp().end();
213  ++i)
214  {
215  first = *i;
216 
217  typename Trans_t::semiring_elt_t
218  mult(trans.structure().series().semiring());
219  mult = series_elt.get(first);
220 
221  //FIXME
222  //If we don't use a copy of the support we don't get ALL the
223  //element of the series when card(mult) > 1.
224  typename Trans_t::semiring_elt_t::support_t
225  mult_supp = mult.supp();
226  for (typename Trans_t::semiring_elt_t::support_t::const_iterator
227  j = mult_supp.begin();
228  j != mult_supp.end();
229  ++j)
230  {
231  second = *j;
232 
233  mon = typename FMP_t::monoid_elt_value_t(first.value(),
234  second.value());
235  s.assoc(mon, trans.output_of(*Ed).get(second));
236  }
237  }
238  res.add_series_transition(m[trans.src_of(*Ed)],
239  m[trans.dst_of(*Ed)],
240  s);
241  }
242  }
243 
244  template<typename S, typename T,
245  typename SS, typename TT>
248  {
249  do_rw_to_fmp(trans.structure(), res.structure(),
250  res.structure().series().monoid(),
251  trans, res);
252  return res;
253  }
254 }
255 
256 #endif // ! VCSN_ALGORITHMS_RW_TO_FMP_HXX