Vaucanson  1.4.1
image.hxx
1 // image.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, 2011 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_IMAGE_HXX
19 # define VCSN_ALGORITHMS_IMAGE_HXX
20 
21 # include <vaucanson/algorithms/image.hh>
22 # include <vaucanson/algorithms/cut_up.hh>
23 # include <vaucanson/algorithms/projection.hh>
24 
25 namespace vcsn
26 {
27  template <typename auto_t, typename trans_t>
28  static void
29  do_fmp_image(const trans_t& input, auto_t& res, bool weighted)
30  {
31  BENCH_TASK_SCOPED("image");
32  AUTOMATON_TYPES_(trans_t, trans_);
33  AUTOMATON_TYPES(auto_t);
34 
35  trans_t fmp_trans = cut_up(input);
36 
37  typedef typename trans_series_set_elt_t::support_t trans_support_t;
38  std::map<trans_hstate_t, hstate_t> stmap;
39 
40  const series_set_t& series = res.structure().series();
41  const monoid_t& monoid = res.structure().series().monoid();
42  const semiring_elt_t& unit = res.structure().series().semiring().wone_;
43  const trans_monoid_t& trans_monoid =
44  fmp_trans.structure().series().monoid();
45 
46  for_all_const_states(fmp_s, fmp_trans)
47  {
48  hstate_t s = res.add_state();
49  stmap[*fmp_s] = s;
50 
51  if (fmp_trans.is_initial(*fmp_s))
52  {
53  const trans_series_set_elt_t trans_series_elt =
54  fmp_trans.get_initial(*fmp_s);
55  trans_support_t trans_supp = trans_series_elt.supp();
56  const trans_monoid_elt_t trans_monoid_elt(trans_monoid,
57  *(trans_supp.begin()));
58 
59  const monoid_elt_value_t word(trans_monoid_elt.value().second);
60 
61  series_set_elt_t series_elt(series);
62 
63  series_elt.assoc(monoid_elt_t(monoid, word),
64  weighted ?
65  trans_series_elt.get(trans_monoid_elt) : unit);
66 
67  res.set_initial(s, series_elt);
68  }
69  if (fmp_trans.is_final(*fmp_s))
70  {
71  const trans_series_set_elt_t trans_series_elt =
72  fmp_trans.get_final(*fmp_s);
73  trans_support_t trans_supp = trans_series_elt.supp();
74  const trans_monoid_elt_t trans_monoid_elt(trans_monoid,
75  *(trans_supp.begin()));
76 
77  const monoid_elt_value_t word(trans_monoid_elt.value().second);
78 
79  series_set_elt_t series_elt(series);
80 
81  series_elt.assoc(monoid_elt_t(monoid, word),
82  weighted ? trans_series_elt.get(trans_monoid_elt)
83  : unit);
84  res.set_final(s, series_elt);
85  }
86  }
87 
88  for_all_const_transitions_(trans_, fmp_e, fmp_trans)
89  {
90  const trans_series_set_elt_t trans_series_elt =
91  fmp_trans.series_of(*fmp_e);
92  trans_support_t trans_supp = trans_series_elt.supp();
93  for_all_const_(trans_support_t, trans_value, trans_supp)
94  {
95  const trans_monoid_elt_t trans_monoid_elt(trans_monoid,
96  *trans_value);
97 
98  const monoid_elt_value_t word(trans_monoid_elt.value().second);
99 
100  series_set_elt_t series_elt(series);
101 
102  series_elt.assoc(monoid_elt_t(monoid, word),
103  weighted ? trans_series_elt.get(trans_monoid_elt)
104  : unit);
105 
106  res.add_series_transition(stmap[fmp_trans.src_of(*fmp_e)],
107  stmap[fmp_trans.dst_of(*fmp_e)], series_elt);
108  }
109  }
110  }
111 
112 
113  template<typename Trans_t, typename Auto_t>
114  static void
115  do_rw_image(const Trans_t& t,
116  Auto_t& ret)
117  {
118  BENCH_TASK_SCOPED("image (transducer to automaton)");
119  AUTOMATON_TYPES(Trans_t);
120  AUTOMATON_TYPES_(Auto_t, auto_);
121  std::map<hstate_t, auto_hstate_t> m;
122 
123  for_all_const_states(p, t)
124  m[*p] = ret.add_state();
125 
126  monoid_elt_t empty =
127  algebra::identity_as<monoid_elt_value_t>::of(t.series().monoid());
128  typename Trans_t::series_set_elt_t id_series(t.structure().series());
129  id_series = vcsn::algebra::
130  identity_as<typename Trans_t::series_set_elt_value_t>::
131  of(t.structure().series());
132 
133  for_all_const_initial_states(p, t)
134  {
135  if (t.get_initial(*p) != id_series)
136  {
137  auto_hstate_t tmp = ret.add_state();
138  ret.set_initial(tmp);
139  ret.add_series_transition(tmp, m[*p], t.get_initial(*p).get(empty));
140  }
141  else
142  ret.set_initial(m[*p], t.get_initial(*p).get(empty));
143  }
144 
145  for_all_const_final_states(p, t)
146  {
147  if (t.get_final(*p) != id_series)
148  {
149  auto_hstate_t tmp = ret.add_state();
150  ret.set_final(tmp);
151  ret.add_series_transition(m[*p], tmp, t.get_final(*p).get(empty));
152  }
153  else
154  ret.set_final(m[*p], t.get_final(*p).get(empty));
155  }
156 
157  for_all_const_transitions(e, t)
158  {
159  ret.add_series_transition(m[t.src_of(*e)],
160  m[t.dst_of(*e)],
161  t.output_of(*e));
162  }
163  }
164 
165 
166  template <typename S, typename T, typename Auto_t>
167  static
168  typename output_projection_helper<S, T>::ret
169  do_rw_image(const Element<S, T>& t,
170  Auto_t& ret,
171  std::map<typename Auto_t::hstate_t, typename T::hstate_t>& m_)
172  {
173  BENCH_TASK_SCOPED("image (transducer to automaton)");
174  typedef Element<S, T> Trans_t;
175  AUTOMATON_TYPES(Trans_t);
176 
177  monoid_elt_t empty = t.series().monoid().VCSN_EMPTY_;
178  std::map<hstate_t, hstate_t> m;
179 
180  for_all_const_states(p, t)
181  {
182  m[*p] = ret.add_state();
183  m_[m[*p]] = *p;
184  }
185 
186  for_all_const_initial_states(p, t)
187  ret.set_initial(m[*p], t.get_initial(*p).get(empty));
188 
189  for_all_const_final_states(p, t)
190  ret.set_final(m[*p], t.get_final(*p).get(empty));
191 
192  for_all_const_transitions(e, t)
193  ret.add_series_transition(m[t.src_of(*e)], m[t.dst_of(*e)],
194  t.output_of(*e));
195 
196  return ret;
197  }
198 
199 
200 
201  /*-------------.
202  | DISPATCHERS. |
203  `-------------*/
204 
205  // Dispatchers for RW transducers.
206  template <typename S, typename S2,
207  typename T, typename T2,
208  typename ST, typename M1>
209  static void
210  image_dispatch(const Element<S,T>& src,
211  const TransducerBase<ST>&,
212  const algebra::FreeMonoidBase<M1>&,
213  Element<S2, T2>& dst, bool)
214  {
215  do_rw_image(src, dst);
216  }
217 
218  template <typename S, typename S2,
219  typename T, typename T2,
220  typename ST, typename M1>
221  static void
222  image_dispatch(const Element<S,T>& src,
223  const TransducerBase<ST>&,
224  const algebra::FreeMonoidBase<M1>&,
225  Element<S2, T2>& dst,
226  std::map<typename T::hstate_t, typename T2::hstate_t>& m)
227  {
228  do_rw_image(src, dst, m);
229  }
230 
231  // Dispatch and build returned object for RW transducers. A map between
232  // states of the resulting automaton and the tranducer is filled.
233  template <typename S, typename T, typename ST>
234  static
235  typename output_projection_helper<S, T>::ret
236  image_dispatch2(const Element<S,T>& src,
237  const TransducerBase<ST>&,
238  std::map<typename T::hstate_t, typename T::hstate_t>& m)
239  {
240  typename output_projection_helper<S, T>::ret dst =
241  output_projection_helper<S, T>::make_output_projection_automaton(src);
242 
243  image_dispatch(src, src.structure(),
244  src.structure().series().monoid(), dst, m);
245  return dst;
246  }
247 
248  // Dispatch and build returned object for RW transducers
249  template <typename S, typename T, typename ST>
250  static
251  typename output_projection_helper<S, T>::ret
252  image_dispatch2(const Element<S,T>& src,
253  const TransducerBase<ST>&)
254  {
255  typename output_projection_helper<S, T>::ret dst =
256  output_projection_helper<S, T>::make_output_projection_automaton(src);
257 
258  image_dispatch(src, src.structure(),
259  src.structure().series().monoid(), dst, true);
260  return dst;
261  }
262 
263  // Dispatcher for transducers
264  template <typename S, typename S2,
265  typename T, typename T2,
266  typename ST, typename M1>
267  static void
268  image_dispatch(const Element<S,T>& src,
269  const AutomataBase<ST>&,
270  const algebra::FreeMonoidProductBase<M1>&,
271  Element<S2, T2>& dst, bool weighted)
272  {
273  do_fmp_image(src, dst, weighted);
274  }
275 
276  /*---------------.
277  | IMAGE FACADES. |
278  `---------------*/
279 
280  template <typename S, typename T>
281  void
282  image(const Element<S, T>& src,
283  typename output_projection_helper<S, T>::ret& dst,
284  bool weighted)
285  {
286  image_dispatch(src, src.structure(),
287  src.structure().series().monoid(),
288  dst, weighted);
289  }
290 
291  template <typename S, typename T>
292  typename output_projection_helper<S, T>::ret
293  image(const Element<S, T>& src)
294  {
295  return image_dispatch2(src, src.structure());
296  }
297 
298  template <typename S, typename T>
299  typename output_projection_helper<S, T>::ret
300  image(const Element<S, T>& src,
301  std::map<typename T::hstate_t, typename T::hstate_t>& m)
302  {
303  return image_dispatch2(src, src.structure(), m);
304  }
305 
306 } // End of namespace vcsn.
307 
308 #endif /* !VCSN_ALGORITHMS_IMAGE_HXX */
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1