Vaucanson  1.4.1
automata_ops.hxx
1 // automata_ops.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 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_AUTOMATA_CONCEPT_AUTOMATA_OPS_HXX
18 # define VCSN_AUTOMATA_CONCEPT_AUTOMATA_OPS_HXX
19 
20 # include <iterator>
21 # include <set>
22 # include <vaucanson/misc/random.hh>
23 # include <vaucanson/misc/contract.hh>
24 # include <vaucanson/algebra/concept/series_base.hh>
25 
26 namespace vcsn {
27 
28 #define AutoType(Type) \
29  typename Element<S, T>::Type
30 
31  template<typename S, typename T, typename U>
32  void
33  op_assign(const AutomataBase<S>& concept, T& dst, const U& src)
34  {
35  dst = op_convert(concept, dst, src);
36  }
37 
38  template<typename S, typename T>
39  void
40  op_assign(const AutomataBase<S>&, T& dst, const T& src)
41  {
42  dst = src;
43  }
44 
45  template<typename S, typename T>
46  const T& op_convert(const AutomataBase<S>&,
47  SELECTOR(T), const T& from_data)
48  {
49  return from_data;
50  }
51 
52  template<typename S, typename R, typename T>
53  R op_convert(const AutomataBase<S>& concept,
54  SELECTOR(R), const T& src)
55  {
56  typedef typename automaton_traits<R>::hstate_t dst_hstate_t;
57  typedef typename automaton_traits<T>::hstate_t src_hstate_t;
58  typedef typename automaton_traits<T>::transition_iterator transition_iterator;
59  typedef typename automaton_traits<T>::final_iterator final_iterator;
60  typedef typename automaton_traits<T>::initial_iterator initial_iterator;
61  typedef typename automaton_traits<T>::state_iterator state_iterator;
62 
63  R dst;
64  std::map<src_hstate_t, dst_hstate_t> states_map;
65 
66  //Mapping src's states to dst's states
67  for (state_iterator s = op_states(concept, src).begin(),
68  s_end = op_states(concept, src).end(); s != s_end; ++s)
69  states_map[*s] = op_add_state(concept, dst);
70 
71  //Adding all transitions
72  for (transition_iterator t = op_transitions(concept, src).begin(),
73  t_end = op_transitions(concept, src).end(); t != t_end; ++t)
74  op_add_series_transition(concept,
75  dst,
76  states_map[op_src_of(concept, src, *t)],
77  states_map[op_dst_of(concept, src, *t)],
78  op_label_of(concept, src, *t));
79 
80  //Adding initial states
81  for (initial_iterator i = op_initial(concept, src).begin(),
82  i_end = op_initial(concept, src).end(); i != i_end; ++i)
83  op_set_initial(concept,
84  dst,
85  states_map[*i],
86  op_get_initial(concept, src, *i));
87 
88  //Adding final states
89  for (final_iterator f = op_final(concept, src).begin(),
90  f_end = op_final(concept, src).end(); f != f_end; ++f)
91  op_set_final(concept,
92  dst,
93  states_map[*f],
94  op_get_final(concept, src, *f));
95 
96  //FIXME: geometry isn't preserved during this conversion.
97 
98  return dst;
99  }
100 
101 
102  template <class S, class T>
103  const typename automaton_traits<T>::tag_t&
104  op_get_tag(const AutomataBase<S>&, const T& v)
105  {
106  return v.tag();
107  }
108 
109  template <class S, class T>
110  typename automaton_traits<T>::tag_t&
111  op_get_tag(const AutomataBase<S>&, T& v)
112  {
113  return v.tag();
114  }
115 
116  template <class S, class T>
117  const typename automaton_traits<T>::geometry_t&
118  op_get_geometry(const AutomataBase<S>&, const T& v)
119  {
120  return v.geometry();
121  }
122 
123  template <class S, class T>
124  typename automaton_traits<T>::geometry_t&
125  op_get_geometry(const AutomataBase<S>&, T& v)
126  {
127  return v.geometry();
128  }
129 
130  template <class S, class T>
131  bool
132  op_exists(const AutomataBase<S>& s, const T& v)
133  {
134  return v.exists(s);
135  }
136 
137  template <class S, class T>
138  typename automaton_traits<T>::states_t
139  op_states(const AutomataBase<S>&, const T& v)
140  {
141  return v.states();
142  }
143 
144  template <class S, class T>
145  typename automaton_traits<T>::hstate_t
146  op_get_state(const AutomataBase<S>&, const T& v, int state)
147  {
148  return v.get_state(state);
149  }
150 
151  template <class S, class T>
152  typename automaton_traits<T>::transitions_t
153  op_transitions(const AutomataBase<S>&, const T& v)
154  {
155  return v.edges();
156  }
157 
158  template <class S, class T>
159  typename automaton_traits<T>::initial_support_t
160  op_initial(const AutomataBase<S>&, const T& v)
161  {
162  return v.initial();
163  }
164 
165  template <class S, class T>
166  typename automaton_traits<T>::final_support_t
167  op_final(const AutomataBase<S>&, const T& v)
168  {
169  return v.final();
170  }
171 
172  template <class S, class T>
173  void
174  op_set_initial(const AutomataBase<S>& ss, T& v,
175  const typename automaton_traits<T>::hstate_t& state,
176  const AutoType(series_set_elt_t)& s)
177  {
178  typedef
179  typename Element<S, T>::series_set_elt_value_t series_set_elt_value_t;
180  v.set_initial(state,
181  s.value(),
182  zero_value(ss.series(),
183  SELECT(series_set_elt_value_t)));
184  }
185 
186  template <class S, class T>
187  typename Element<S, T>::series_set_elt_t
188  op_get_initial(const AutomataBase<S>& s,
189  const T& v,
190  const typename automaton_traits<T>::hstate_t& state)
191  {
192  return typename Element<S, T>::series_set_elt_t
193  (s.series(),
194  v.get_initial(state,
195  zero_value(s.series(),
196  SELECT(AutoType(series_set_elt_value_t)))));
197  }
198 
199  template <class S, class T>
200  bool
201  op_is_initial(const AutomataBase<S>& s,
202  const T& v,
203  const typename automaton_traits<T>::hstate_t& state)
204  {
205  return v.is_initial(state, zero_value(s.series(),
206  SELECT(AutoType(series_set_elt_value_t))));
207  }
208 
209  template <class S, class T>
210  void
211  op_set_final(const AutomataBase<S>& ss, T& v,
212  const typename automaton_traits<T>::hstate_t& state,
213  const typename Element<S, T>::series_set_elt_t& s)
214  {
215  v.set_final(state,
216  s.value(),
217  zero_value(ss.series(),
218  SELECT(AutoType(series_set_elt_value_t))));
219  }
220 
221  template <class S, class T>
222  void
223  op_set_initial(const AutomataBase<S>& ss, T& v,
224  int state,
225  const AutoType(series_set_elt_t)& s)
226  {
227  op_set_initial(ss, v, op_get_state(ss, v, state), s);
228  }
229 
230  template <class S, class T>
231  typename Element<S, T>::series_set_elt_t
232  op_get_initial(const AutomataBase<S>& s,
233  const T& v,
234  int state)
235  {
236  return op_get_initial(s, v, op_get_state(s, v, state));
237  }
238 
239  template <class S, class T>
240  bool
241  op_is_initial(const AutomataBase<S>& s,
242  const T& v,
243  int state)
244  {
245  return op_is_initial(s, v, op_get_state(s, v, state));
246  }
247 
248  template <class S, class T>
249  void
250  op_set_final(const AutomataBase<S>& ss, T& v,
251  int state,
252  const typename Element<S, T>::series_set_elt_t& s)
253  {
254  op_set_final(ss, v, op_get_state(ss, v, state), s);
255  }
256 
257  template <class S, class T>
258  typename Element<S, T>::series_set_elt_t
259  op_get_final(const AutomataBase<S>& s,
260  const T& v,
261  const typename automaton_traits<T>::hstate_t& state)
262  {
263  return typename Element<S, T>::series_set_elt_t
264  (s.series(),
265  v.get_final(state,
266  zero_value(s.series(),
267  SELECT(AutoType(series_set_elt_value_t)))));
268  }
269 
270  template <class S, class T>
271  typename Element<S, T>::series_set_elt_t
272  op_get_final(const AutomataBase<S>& s,
273  const T& v,
274  int state)
275  {
276  return op_get_final(s, v, op_get_state(s, v, state));
277  }
278 
279  template <class S, class T>
280  bool
281  op_is_final(const AutomataBase<S>& s,
282  const T& v,
283  const typename automaton_traits<T>::hstate_t& state)
284  {
285  return v.is_final(state, zero_value(s.series(),
286  SELECT(AutoType(series_set_elt_value_t))));
287  }
288 
289  template <class S, class T>
290  bool
291  op_is_final(const AutomataBase<S>& s,
292  const T& v,
293  int state)
294  {
295  return op_is_final(s, v, op_get_state(s, v, state));
296  }
297 
298  template <class S, class T>
299  void
300  op_clear_initial(const AutomataBase<S>&, T& v)
301  {
302  return v.clear_initial();
303  }
304 
305  template <class S, class T>
306  void
307  op_clear_final(const AutomataBase<S>&, T& v)
308  {
309  return v.clear_final();
310  }
311 
312  template <class S, class T>
313  typename automaton_traits<T>::hstate_t
314  op_add_state(const AutomataBase<S>&, T& v)
315  {
316  return v.add_state();
317  }
318 
319  template <class S, class T>
320  typename automaton_traits<T>::hstate_t
321  op_choose_state(const AutomataBase<S>& s, const T& v)
322  {
323  typedef typename automaton_traits<T>::states_t states_t;
324  typedef typename states_t::const_iterator state_iterator;
325  const states_t& st = op_states(s, v);
326  assertion(st.size() > 0);
327  int n = misc::random::generate(0, int(st.size() - 1));
328  state_iterator ss = st.begin();
329  for (; n > 0; --n)
330  ++ss;
331  return *ss;
332  }
333 
334  template <class S, class T>
335  typename automaton_traits<T>::htransition_t
336  op_add_transition(const AutomataBase<S>&, T& v,
337  const typename automaton_traits<T>::hstate_t& from,
338  const typename automaton_traits<T>::hstate_t& to,
339  const typename Element<S, T>::label_t& label)
340  {
341  return v.add_edge(from, to, label);
342  }
343 
344  template <class S, class T>
345  typename automaton_traits<T>::htransition_t
346  op_add_transition(const AutomataBase<S>& s, T& v,
347  int from,
348  int to,
349  const typename Element<S, T>::label_t& label)
350  {
351  return op_add_transition(s, v, op_get_state(s, v, from),
352  op_get_state(s, v, to), label);
353  }
354 
355  template<class S, class T>
356  typename automaton_traits<T>::htransition_t
357  op_add_weighted_transition(const AutomataBase<S>& s, T& v,
358  const typename automaton_traits<T>::hstate_t& from,
359  const typename automaton_traits<T>::hstate_t& to,
360  const typename Element<S, T>::semiring_elt_t& w,
361  const typename Element<S, T>::monoid_elt_value_t& m)
362  {
363  typename Element<S, T>::series_set_elt_t series (s.series());
364  series.assoc(m, w.value());
365  return op_add_series_transition(s, v, from, to, series);
366  }
367 
368  template<class S, class T>
369  typename automaton_traits<T>::htransition_t
370  op_add_weighted_transition(const AutomataBase<S>& s, T& v,
371  int from,
372  int to,
373  const typename Element<S, T>::semiring_elt_t& w,
374  const typename Element<S, T>::monoid_elt_value_t& m)
375  {
376  return op_add_weighted_transition(s, v, op_get_state(s, v, from),
377  op_get_state(s, v, to), w, m);
378  }
379 
380  template <class S, class T>
381  typename automaton_traits<T>::htransition_t
382  op_add_series_transition(const AutomataBase<S>& s, T& v,
383  const typename automaton_traits<T>::hstate_t& from,
384  const typename automaton_traits<T>::hstate_t& to,
385  const typename Element<S, T>::series_set_elt_t& l)
386  {
387  return op_add_transition(s, v, from, to, l.value());
388  }
389 
390  template <class S, class T>
391  typename automaton_traits<T>::htransition_t
392  op_add_series_transition(const AutomataBase<S>& s, T& v,
393  int from,
394  int to,
395  const typename Element<S, T>::series_set_elt_t& l)
396  {
397  return op_add_series_transition(s, v, op_get_state(s, v, from),
398  op_get_state(s, v, to), l);
399  }
400 
401  template <class S, class T>
402  typename automaton_traits<T>::htransition_t
403  op_add_spontaneous(const AutomataBase<S>& s, T& v,
404  const typename automaton_traits<T>::hstate_t& from,
405  const typename automaton_traits<T>::hstate_t& to,
406  const typename Element<S, T>::semiring_elt_t& w)
407  {
408  AutoType(series_set_elt_t) ss(s.series());
409  ss.assoc(algebra::identity_as<AutoType(monoid_elt_value_t)>::
410  of(s.series().monoid()), w);
411  return op_add_series_transition(s, v, from, to, ss);
412  }
413 
414  template <class S, class T>
415  typename automaton_traits<T>::htransition_t
416  op_add_spontaneous(const AutomataBase<S>& s, T& v,
417  int from,
418  int to,
419  const typename Element<S, T>::semiring_elt_t& w)
420  {
421  return op_add_spontaneous(s, v, op_get_state(s, v, from),
422  op_get_state(s, v, to), w);
423  }
424 
425  template <class S, class T>
426  typename automaton_traits<T>::htransition_t
427  op_add_letter_transition(const AutomataBase<S>& s, T& v,
428  const typename automaton_traits<T>::hstate_t& from,
429  const typename automaton_traits<T>::hstate_t& to,
430  const typename Element<S, T>::letter_t& l)
431  {
432  return op_add_transition(s, v, from, to, l);
433  }
434 
435  template <class S, class T>
436  typename automaton_traits<T>::htransition_t
437  op_add_letter_transition(const AutomataBase<S>& s, T& v,
438  int from,
439  int to,
440  const typename Element<S, T>::letter_t& l)
441  {
442  return op_add_letter_transition(s, v, op_get_state(s, v, from),
443  op_get_state(s, v, to), l);
444  }
445 
446  template <class S, class T>
447  void
448  op_update(const AutomataBase<S>&, T& v,
449  const typename automaton_traits<T>::htransition_t& e,
450  const AutoType(label_t)& l)
451  {
452  // FIXME: test that l != 0.
453  v.update(e, l);
454  }
455 
456  template <class S, class T>
457  void
458  op_del_state(const AutomataBase<S>&, T& v,
459  const typename automaton_traits<T>::hstate_t& s)
460  {
461  v.del_state(s);
462  }
463 
464  template <class S, class T>
465  void
466  op_del_state(const AutomataBase<S>& s, T& v,
467  int state)
468  {
469  op_del_state(s, v, op_get_state(s, v, state));
470  }
471 
472  template <class S, class T>
473  void
474  op_del_transition(const AutomataBase<S>&, T& v,
475  const typename automaton_traits<T>::htransition_t& e)
476  {
477  v.del_edge(e);
478  }
479 
480  template <class S, class T>
481  bool
482  op_has_state(const AutomataBase<S>&, const T& v,
483  const typename automaton_traits<T>::hstate_t& s)
484  {
485  return v.has_state(s);
486  }
487 
488  template <class S, class T>
489  bool
490  op_has_state(const AutomataBase<S>& s, const T& v,
491  int state)
492  {
493  return op_has_state(s, v, op_get_state(s, v, state));
494  }
495 
496  template <class S, class T>
497  bool
498  op_has_transition(const AutomataBase<S>&, const T& v,
499  const typename automaton_traits<T>::htransition_t& e)
500  {
501  return v.has_edge(e);
502  }
503 
504  template <class S, class T>
505  typename automaton_traits<T>::hstate_t
506  op_src_of(const AutomataBase<S>&, const T& v,
507  const typename automaton_traits<T>::htransition_t& e)
508  {
509  return v.src_of(e);
510  }
511 
512  template <class S, class T>
513  typename automaton_traits<T>::hstate_t
514  op_dst_of(const AutomataBase<S>&, const T& v,
515  const typename automaton_traits<T>::htransition_t& e)
516  {
517  return v.dst_of(e);
518  }
519 
520  template <class S, class T>
521  typename Element<S, T>::label_t
522  op_label_of(const AutomataBase<S>&, const T& v,
523  const typename automaton_traits<T>::htransition_t& e)
524  {
525  return v.label_of(e);
526  }
527 
528  template <class S, class T>
529  const typename Element<S, T>::series_set_elt_t
530  op_series_of(const AutomataBase<S>& s, const T& v,
531  const typename automaton_traits<T>::htransition_t& e)
532  {
533  return typename Element<S, T>::series_set_elt_t
534  (s.series(),
535  v.label_of(e));
536  }
537 
538  template <class S, class T>
539  typename Element<S, T>::series_set_elt_value_t
540  op_series_value_of(const AutomataBase<S>& s, const T& v,
541  const typename automaton_traits<T>::htransition_t& e)
542  {
543  return op_series_of(s, v, e).value();
544  }
545 
546  template <class S, class T>
547  typename Element<S, T>::monoid_elt_t
548  op_word_of(const AutomataBase<S>& s, const T& v,
549  const typename automaton_traits<T>::htransition_t& e)
550  {
551  return typename Element<S, T>::monoid_elt_t
552  (s.series().monoid(),
553  v.label_of(e));
554  }
555 
556  template <class S, class T>
557  typename Element<S, T>::semiring_elt_t
558  op_weight_of(const AutomataBase<S>& s, const T& v,
559  const typename automaton_traits<T>::htransition_t& e)
560  {
561  return op_series_of(s, v, e).get(op_word_of(s, v, e));
562  }
563 
564  template <class S, class T>
565  typename Element<S, T>::monoid_elt_value_t
566  op_word_value_of(const AutomataBase<S>& s, const T& v,
567  const typename automaton_traits<T>::htransition_t& e)
568  {
569  return op_word_of(s, v, e).value();
570  }
571 
572  template <class S, class T>
573  typename Element<S, T>::letter_t
574  op_letter_of(const AutomataBase<S>&, const T& v,
575  const typename automaton_traits<T>::htransition_t& e)
576  {
577  return v.label_of(e);
578  }
579 
580  template <class S, class T>
581  bool
582  op_is_spontaneous(const AutomataBase<S>& s, const T& v,
583  const typename automaton_traits<T>::htransition_t& e)
584  {
585  return (op_series_of(s, v, e) ==
586  algebra::identity_as<AutoType(series_set_elt_value_t)>::of(s.series()));
587  }
588 
589 } // vcsn
590 
591 # undef AutoType
592 
593 #endif // ! VCSN_AUTOMATA_CONCEPT_AUTOMATA_OPS_HXX
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1