Vaucanson  1.4.1
invert.hxx
1 // invert.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 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 
18 #ifndef VCSN_ALGORITHMS_INVERT_HXX
19 # define VCSN_ALGORITHMS_INVERT_HXX
20 
21 # include <map>
22 
23 # include <vaucanson/automata/concept/automata_base.hh>
24 # include <vaucanson/automata/concept/transducer.hh>
25 # include <vaucanson/algebra/concept/freemonoid_product.hh>
26 # include <vaucanson/algebra/implementation/series/series.hh>
27 
28 # include <vaucanson/misc/usual_macros.hh>
29 
30 # include <vaucanson/algorithms/standard_of.hh>
31 # include <vaucanson/algorithms/realtime.hh>
32 
33 namespace vcsn
34 {
35 
36  /*------------------------------------.
37  | Specialization for RW transducers. |
38  `------------------------------------*/
39 
40  template<typename S, typename T>
41  Element<S, T>&
42  do_invert_rw(Element<S, T>& t,
43  Element<S, T>& u)
44  {
45  typedef Element<S, T> Trans_t;
46  typedef typename output_projection_helper<S, T>::ret Auto_t;
47  AUTOMATON_TYPES(Trans_t);
48 
49  normalize_here(t);
50 
51  std::map<hstate_t, hstate_t> map_t_u;
52  for_all_const_states (p, t)
53  map_t_u[*p] = u.add_state ();
54 
55  initial_iterator i_it;
56  for (initial_iterator next = t.initial().begin(), next_end = t.initial().end();
57  next != next_end;)
58  {
59  //We need to store the next iterator before using the current one
60  //to avoid an invalid iterator after having called set_final.
61  //Indeed, set_final can delete the iterator if its second parameter
62  //is the zero of the serie.
63  i_it = next;
64  next++;
65  u.set_initial (map_t_u[*i_it]);
66  }
67 
68  final_iterator f_it;
69  for (final_iterator next = t.final().begin(), next_end = t.final().end();
70  next != next_end;)
71  {
72  //We need to store the next iterator before using the current one
73  //to avoid an invalid iterator after having called set_final.
74  //Indeed, set_final can delete the iterator if its second parameter
75  //is the zero of the serie.
76  f_it = next;
77  next++;
78  u.set_final (map_t_u[*f_it]);
79  }
80 
81  for_all_const_transitions (e, t)
82  {
83  semiring_elt_t exp = t.output_of(*e);
84 
85  typename Auto_t::set_t auto_structure
86  (typename Auto_t::set_t::series_set_t
87  (t.structure().series().semiring()));
88  Auto_t auto_tmp(auto_structure);
89 
90  // As the output of each transition is not supposed to be
91  // realtime we build the standard automaton corresponding to
92  // this expression
93  standard_of(auto_tmp, exp.value());
94 
95  std::map<hstate_t, hstate_t> map_auto_u;
96 
97  for_all_const_states (p, auto_tmp)
98  if (auto_tmp.is_initial (*p))
99  map_auto_u[*p] = map_t_u[t.src_of(*e)];
100  else
101  map_auto_u[*p] = u.add_state();
102 
103  typename semiring_elt_t::semiring_elt_t
104  o_sm_zero (u.structure().series().semiring().semiring());
105  monoid_elt_t monoid_identity = u.series().monoid().VCSN_EMPTY_;
106 
107  monoid_elt_t a (u.structure().series().monoid());
108  semiring_elt_t sm (u.structure().series().semiring());
109  series_set_elt_t s (u.structure().series());
110 
111  for (typename Auto_t::transition_iterator f =
112  auto_tmp.transitions().begin();
113  f != auto_tmp.transitions().end();
114  ++f)
115  {
116  a = auto_tmp.word_of (*f);
117 
118  s.assoc (a, algebra::identity_as<semiring_elt_value_t>
119  ::of(u.series().semiring()));
120 
121  u.add_series_transition (map_auto_u[auto_tmp.src_of(*f)],
122  map_auto_u[auto_tmp.dst_of(*f)],
123  s);
124  }
125 
126  a = t.input_of (*e);
127  for (typename Auto_t::final_iterator q = auto_tmp.final().begin();
128  q != auto_tmp.final().end();
129  ++q)
130  {
131  typedef typename semiring_elt_t::semiring_elt_t output_sm_t;
132  typedef typename output_sm_t::value_t output_sm_value_t;
133 
134  sm.assoc (a, algebra::identity_as<output_sm_value_t>
135  ::of(u.series().semiring().semiring()));
136  s.assoc(monoid_identity, sm);
137  u.add_series_transition(map_auto_u[*q],
138  map_t_u[t.dst_of(*e)],
139  s);
140  }
141  }
142 
143  realtime_here(u);
144 
145  return u;
146  }
147 
148 
149  /*-------------------------------------.
150  | Specialization for FMP transducers. |
151  `-------------------------------------*/
152 
153 
154  // Invert `label' and store the result in `res'.
155  template<typename S, typename T,
156  typename SS, typename TT>
157  static void invert_label(const Element<S, T>& label,
158  Element<SS, TT>& res)
159  {
160  typedef Element<S, T> series_set_elt_t;
161  typedef typename series_set_elt_t::monoid_elt_t::value_t
162  res_monoid_elt_value_t;
163 
164  // Invert each pair
165  for_all_const_(series_set_elt_t::support_t, w, label.supp())
166  // (u,v) -> (v,u)
167  res.assoc(res_monoid_elt_value_t((*w).second, (*w).first),
168  label.get(*w));
169  }
170 
171 
172  template<typename S, typename T,
173  typename SS, typename TT>
174  Element<SS, TT>&
175  do_invert_tdc(const Element<S, T>& t,
176  Element<SS, TT>& u)
177  {
178  typedef Element<S, T> Trans_t;
179  typedef Element<SS, TT> res_t;
180  AUTOMATON_TYPES(Trans_t);
181  AUTOMATON_TYPES_(res_t, res_);
182 
183  std::map<hstate_t, hstate_t> map_t_u;
184  for_all_const_states (p, t)
185  map_t_u[*p] = u.add_state ();
186 
187  // Proceed initial and final states
188  for_all_const_initial_states (p, t)
189  {
190  res_series_set_elt_t s (u.structure().series());
191  invert_label(t.get_initial(*p), s);
192  u.set_initial (map_t_u[*p], s);
193  }
194 
195  for_all_const_final_states (p, t)
196  {
197  res_series_set_elt_t s (u.structure().series());
198  invert_label(t.get_final(*p), s);
199  u.set_final (map_t_u[*p], s);
200  }
201 
202 
203  for_all_const_transitions (e, t)
204  {
205  res_series_set_elt_t s (u.structure().series());
206  res_monoid_elt_t a (u.structure().series().monoid());
207 
208  // Get the label of the current transition
209  series_set_elt_t label(t.structure().series());
210  label = t.series_of(*e);
211 
212  invert_label(label, s);
213 
214  u.add_series_transition(map_t_u[t.src_of(*e)],
215  map_t_u[t.dst_of(*e)],
216  s);
217  }
218 
219  return u;
220  }
221 
222 
223 
224  /*------------------------------.
225  | Dispatch for FMP tranducers. |
226  `------------------------------*/
227 
228  template<typename S, typename T,
229  typename M1, typename M2>
230  Element<S, T>&
231  do_invert_fmp(const algebra::FreeMonoidProduct<M1, M2>&,
232  const Element<S, T>& t)
233  {
234  // Declaration of the inverted transducer
235  typedef Element<S, T> trans_t;
236  AUTOMATON_TYPES(trans_t);
237 
238  typedef algebra::FreeMonoidProduct<
239  typename trans_t::series_set_t::monoid_t::second_monoid_t,
240  typename trans_t::series_set_t::monoid_t::first_monoid_t>
241  res_monoid_t;
242 
243  typedef algebra::Series<typename trans_t::series_set_t::semiring_t,
244  res_monoid_t>
245  res_series_set_t;
246 
247  res_monoid_t monoid(t.structure().series().monoid().second_monoid(),
248  t.structure().series().monoid().first_monoid());
249 
250 
251  res_series_set_t series(t.structure().series().semiring(), monoid);
252 
253  Automata<series_set_t, kind_t> trans_set(series);
254 
255  typedef Element< Automata<series_set_t, kind_t>, T> res_trans_t;
256  res_trans_t* res = new res_trans_t(trans_set);
257 
258  return do_invert_tdc(t, *res);
259  }
260 
261 
262  template<typename S, typename T,
263  typename SS, typename TT,
264  typename M1, typename M2>
265  Element<SS, TT>&
266  do_invert_fmp(const algebra::FreeMonoidProduct<M1, M2>&,
267  const Element<S, T>& t,
268  Element<SS, TT>& res)
269  {
270  return do_invert_tdc(t, res);
271  }
272 
273 
274  template<typename S, typename T>
275  Element<S, T>&
276  do_invert(const AutomataBase<S>&,
277  const Element<S, T>& t)
278  {
279  return do_invert_fmp(t.structure().series().monoid(), t);
280  }
281 
282  template<typename S, typename T>
283  Element<S, T>&
284  do_invert(const AutomataBase<S>&,
285  const Element<S, T>& t,
286  Element<S, T>& res)
287  {
288  return do_invert_fmp(t.structure().series().monoid(), t, res);
289 
290  }
291 
292  /*-----------------------------.
293  | Dispatch for RW tranducers. |
294  `-----------------------------*/
295 
296  template<typename S, typename T>
297  Element<S, T>&
298  do_invert(const TransducerBase<S>&,
299  const Element<S, T>& t)
300  {
301  // Building the structure of the inverted transducer
302  typedef Element<S, T> Trans_t;
303  AUTOMATON_TYPES(Trans_t);
304 
305  monoid_t o_mon_structure
306  (t.structure().series().monoid());
307  typename semiring_t::semiring_t sm_sm_structure
308  (t.structure().series().semiring().semiring());
309  typename semiring_t::monoid_t i_mon_structure
310  (t.structure().series().semiring().monoid());
311 
312  semiring_t sm_structure (sm_sm_structure, o_mon_structure);
313  series_set_t ss_structure(sm_structure, i_mon_structure);
314 
315  automata_set_t auto_structure(ss_structure);
316 
317  Trans_t* res = new Trans_t(auto_structure);
318  Trans_t src(t);
319 
320  do_invert_rw(src, *res);
321  return *res;
322  }
323 
324 
325  template<typename S, typename T>
326  Element<S, T>&
327  do_invert(const TransducerBase<S>&,
328  const Element<S, T>& t,
329  Element<S, T>& res)
330  {
331  Element<S, T> src(t);
332  return do_invert_rw(src, res);
333  }
334 
335 
336 
337 
338  /*----------.
339  | Facades. |
340  `----------*/
341 
342  template<typename S, typename T>
343  Element<S, T>&
344  invert(const Element<S, T>& t)
345  {
346  BENCH_TASK_SCOPED("invert");
347  return do_invert(t.structure(), t);
348  }
349 
350  template<typename S, typename T>
351  void
352  invert(const Element<S, T>& t,
353  Element<S, T>& res)
354  {
355  BENCH_TASK_SCOPED("invert");
356  do_invert(t.structure(), t, res);
357  }
358 }
359 
360 #endif // !VCSN_ALGORITHMS_INVERT_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1