Vaucanson  1.4.1
automata_base.hh
1 // automata_base.hh: 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, 2007, 2008 The Vaucanson
6 // Group.
7 //
8 // This program is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU General Public License
10 // as published by the Free Software Foundation; either version 2
11 // of the License, or (at your option) any later version.
12 //
13 // The complete GNU General Public Licence Notice can be found as the
14 // `COPYING' file in the root directory.
15 //
16 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
17 //
18 #ifndef VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH
19 # define VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH
20 
21 # include <iterator>
22 # include <vaucanson/design_pattern/design_pattern.hh>
23 # include <vaucanson/automata/concept/handlers.hh>
24 # include <vaucanson/automata/concept/delta_kind.hh>
25 # include <vaucanson/algebra/concept/series_base.hh>
26 
27 namespace vcsn {
28 
32  /*-------------------.
33  | AutomataBase<Self> |
34  `-------------------*/
36 
40  template <typename Self>
41  struct AutomataBase
42  : Structure<Self>
43  {
44  public:
46  typedef typename virtual_types<Self>::series_set_t series_set_t;
48  typedef typename virtual_types<Self>::kind_t kind_t;
49 
50  protected:
52  AutomataBase();
53 
55  AutomataBase(const AutomataBase& other);
56 
57  public:
59  const series_set_t& series() const;
60  };
61 
62  // FIXME: it must be renamed to automaton_impl_traits
63  // traits for automaton implementation.
64  template <typename T>
65  struct automaton_traits
66  {
67  typedef undefined_type label_t;
68  typedef undefined_type series_set_elt_value_t;
69  typedef undefined_type word_value_t;
70  typedef undefined_type semiring_elt_value_t;
71  typedef undefined_type letter_t;
72  typedef undefined_type tag_t;
73  typedef undefined_type states_t;
74  typedef undefined_type state_iterator;
75  typedef undefined_type transitions_t;
76  typedef undefined_type transition_iterator;
77  typedef undefined_type initial_iterator;
78  typedef undefined_type initial_t;
79  typedef undefined_type initial_support_t;
80  typedef undefined_type final_iterator;
81  typedef undefined_type final_t;
82  typedef undefined_type final_support_t;
83  typedef undefined_type geometry_t;
84  typedef undefined_type hstate_t;
85  typedef undefined_type htransition_t;
86  typedef undefined_type delta_iterator;
87  typedef undefined_type rdelta_iterator;
88  };
89 
90 # define VCSN_MAKE_AUTOMATON_TRAITS(Type) \
91  template <typename Kind, \
92  typename WordValue, \
93  typename WeightValue, \
94  typename SeriesValue, \
95  typename Letter, \
96  typename Tag, \
97  typename GeometryCoords> \
98  struct automaton_traits<Type<Kind, WordValue, WeightValue, SeriesValue, \
99  Letter, Tag, GeometryCoords> > \
100  { \
101  typedef Type<Kind, WordValue, WeightValue, SeriesValue, \
102  Letter, Tag, GeometryCoords> graph_t; \
103  typedef typename graph_t::semiring_elt_value_t semiring_elt_value_t; \
104  typedef typename graph_t::monoid_elt_value_t monoid_elt_value_t; \
105  typedef typename graph_t::word_value_t word_value_t; \
106  typedef typename graph_t::series_set_elt_value_t series_set_elt_value_t; \
107  typedef typename graph_t::letter_t letter_t; \
108  typedef typename graph_t::tag_t tag_t; \
109  typedef typename graph_t::geometry_t geometry_t; \
110  typedef typename graph_t::label_t label_t; \
111  typedef typename graph_t::states_t states_t; \
112  typedef typename states_t::iterator state_iterator; \
113  typedef typename graph_t::hstate_t hstate_t; \
114  typedef typename graph_t::edges_t transitions_t; \
115  typedef typename transitions_t::iterator transition_iterator; \
116  typedef typename graph_t::htransition_t htransition_t; \
117  typedef typename graph_t::initial_t initial_t; \
118  typedef typename graph_t::initial_support_t initial_support_t; \
119  typedef typename initial_support_t::iterator initial_iterator; \
120  typedef typename graph_t::final_t final_t; \
121  typedef typename graph_t::final_support_t final_support_t; \
122  typedef typename final_support_t::iterator final_iterator; \
123  typedef typename graph_t::delta_iterator delta_iterator; \
124  typedef typename graph_t::rdelta_iterator rdelta_iterator; \
125  }
126 
127  // traits for generalized automaton implementation.
128  template <typename Auto>
129  struct generalized_traits
130  {
131  typedef undefined_type automaton_t;
132  };
133 
134 # define VCSN_MAKE_GENERALIZED_AUTOMATON_TRAITS(Type) \
135  template <typename Struct, \
136  typename Kind, \
137  typename WordValue, \
138  typename WeightValue, \
139  typename SeriesValue, \
140  typename Letter, \
141  typename Tag, \
142  typename GeometryCoords> \
143  struct generalized_traits<Element<Struct, Type<Kind, WordValue, \
144  WeightValue, SeriesValue, Letter, \
145  Tag, GeometryCoords> > > \
146  { \
147  typedef Element<Struct, Type<Kind, WordValue, WeightValue, SeriesValue, \
148  Letter, Tag, GeometryCoords> > Auto_; \
149  typedef typename Auto_::series_set_t series_set_t; \
150  typedef typename Auto_::kind_t kind_t; \
151  typedef typename series_set_t::monoid_t monoid_t; \
152  typedef typename Auto_::series_set_elt_t series_set_elt_t; \
153  typedef typename series_set_elt_t::monoid_elt_t monoid_elt_t; \
154  typedef typename monoid_elt_t::value_t monoid_elt_value_t; \
155  typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t; \
156  typedef typename semiring_elt_t::value_t semiring_elt_value_t; \
157  typedef typename Auto_::value_t::geometry_t geometry_t; \
158  typedef vcsn::Element<vcsn::Automata<series_set_t, Kind>, \
159  Type<labels_are_series, \
160  monoid_elt_value_t, \
161  semiring_elt_value_t, \
162  rat::exp<monoid_elt_value_t, semiring_elt_value_t>, \
163  typename monoid_t::letter_t, \
164  NoTag, \
165  typename geometry_t::coords_t> \
166  > automaton_t; \
167  typedef typename automaton_t::hstate_t hstate_t; \
168  typedef typename automaton_t::htransition_t htransition_t; \
169  }
170 
171  // traits to construct an automaton type from a rational expression type,
172  // with a given structural type.
173  // (the automaton type must be able to hold the value returned by
174  // standard_of)
175  // FIXME: there is no rat exp concept, so we put the code here. (maybe it
176  // should be put here anyway)
177  template <typename Struct, typename Ratexp>
178  struct standard_of_traits
179  {
180  typedef undefined_type automaton_t;
181  };
182 
183 # define VCSN_MAKE_STANDARD_OF_TRAITS(Type) \
184  template <typename W, \
185  typename M, \
186  typename Tm, \
187  typename Tw> \
188  struct standard_of_traits<algebra::Series<W, M>, rat::exp<Tm, Tw> > \
189  { \
190  typedef typename algebra::Series<W, M> series_set_t; \
191  typedef typename algebra::polynom<Tm, Tw> \
192  series_set_elt_value_t; \
193  typedef typename M::letter_t letter_t; \
194  typedef typename Type<labels_are_series, Tm, Tw, \
195  series_set_elt_value_t, letter_t, \
196  NoTag, std::pair<double, double> > \
197  automaton_impl_t; \
198  typedef Element<Automata<series_set_t, labels_are_series>, automaton_impl_t> \
199  automaton_t; \
200  }
201 
202  // Traits to construct misc projections from a structural type and
203  // an implementation.
204  template <typename S, typename T>
205  struct projection_traits
206  {
208  typedef undefined_type first_projection_t;
209 
211  typedef undefined_type second_projection_t;
212  };
213 
214  // Traits to mute an existing graph implementation into a projection
215  // implementation with TT.
216  // FIXME: rename to mute_graph_impl_projection_traits
217  template <typename T, typename TT>
218  struct mute_graph_impl_traits
219  {
221  typedef undefined_type first_projection_t;
222 
224  typedef undefined_type second_projection_t;
225  };
226 
227 # define VCSN_MAKE_MUTE_GRAPH_IMPL_TRAITS(Type) \
228  template <typename Kind, \
229  typename WordValue, \
230  typename WeightValue, \
231  typename SeriesValue, \
232  typename Letter, \
233  typename Tag, \
234  typename GeometryCoords, \
235  typename TT> \
236  struct mute_graph_impl_traits<Type<Kind, \
237  WordValue, \
238  WeightValue, \
239  SeriesValue, \
240  Letter, \
241  Tag, \
242  GeometryCoords>, TT> \
243  { \
244  typedef Type<Kind, WordValue, WeightValue, SeriesValue, \
245  Letter, Tag, GeometryCoords> graph_t; \
246  typedef typename algebra::letter_traits<Letter>:: \
247  first_projection_t first_letter_t; \
248  typedef typename algebra::letter_traits<Letter>:: \
249  second_projection_t second_letter_t; \
250  typedef typename TT::first_projection_t::value_t \
251  first_monoid_elt_value_t; \
252  typedef typename TT::second_projection_t::value_t \
253  second_monoid_elt_value_t; \
254  typedef typename algebra::mute_series_impl<SeriesValue, WeightValue, \
255  first_monoid_elt_value_t>::ret \
256  first_series_impl_t; \
257  typedef typename algebra::mute_series_impl<SeriesValue, WeightValue, \
258  second_monoid_elt_value_t>::ret \
259  second_series_impl_t; \
260  typedef Type<Kind, first_monoid_elt_value_t, \
261  WeightValue, first_series_impl_t, \
262  first_letter_t, Tag, GeometryCoords> first_projection_t; \
263  typedef Type<Kind, second_monoid_elt_value_t, \
264  WeightValue, second_series_impl_t, \
265  second_letter_t, Tag, GeometryCoords> second_projection_t; \
266  }
267 
268  // Traits to mute an existing graph implementation into another
269  // graph implementation with a different word implementation and letter
270  // implementation.
271  template <typename G, typename W, typename L>
272  struct mute_graph_impl_monoid_traits
273  {
275  typedef undefined_type ret;
276  };
277 
278 # define VCSN_MAKE_MUTE_GRAPH_IMPL_MONOID_TRAITS(Type) \
279  template <typename Kind, \
280  typename WordValue, \
281  typename WeightValue, \
282  typename SeriesValue, \
283  typename Letter, \
284  typename Tag, \
285  typename GeometryCoords, \
286  typename W, \
287  typename L> \
288  struct mute_graph_impl_monoid_traits<Type<Kind, \
289  WordValue, \
290  WeightValue, \
291  SeriesValue, \
292  Letter, \
293  Tag, \
294  GeometryCoords>, W, L> \
295  { \
296  typedef Type<Kind, WordValue, WeightValue, SeriesValue, \
297  Letter, Tag, GeometryCoords> graph_t; \
298  typedef typename algebra::mute_series_impl<SeriesValue, WeightValue, \
299  W>::ret \
300  series_impl_t; \
301  typedef Type<Kind, W, \
302  WeightValue, series_impl_t, \
303  L, Tag, GeometryCoords> ret; \
304  }
305 
306  /*-----------------------------------.
307  | virtual_types<AutomataBase<Self> > |
308  `-----------------------------------*/
309 
310  template <class S>
311  struct virtual_types<AutomataBase<S> >
312  : virtual_types<Structure<S> >
313  { };
314 
315  /*------------------------------------.
316  | dynamic_traits<AutomataBase<Self> > |
317  `------------------------------------*/
318  template <class S>
319  struct dynamic_traits<AutomataBase<S> >
320  : dynamic_traits<Structure<S> >
321  { };
322 
323  /*-----------------------------------.
324  | MetaElement<AutomataBase<Self>, T> |
325  `-----------------------------------*/
327 
340  // FIXME: Use some of the TYPEDEF_IMPORT macros.
341  template <typename Self, typename T>
342  struct MetaElement<AutomataBase<Self>, T>
343  : MetaElement<Structure<Self>, T>
344  {
346  typedef MetaElement<AutomataBase<Self>, T> self_t;
347 
349  typedef typename AutomataBase<Self>::series_set_t series_set_t;
350 
352  typedef typename AutomataBase<Self>::kind_t kind_t;
353 
355  typedef typename automaton_traits<T>::series_set_elt_value_t
356  series_set_elt_value_t;
357 
359  typedef Element<series_set_t, series_set_elt_value_t> series_set_elt_t;
360 
362  typedef typename series_set_t::monoid_t monoid_t;
363 
365  typedef typename series_set_elt_t::monoid_elt_t monoid_elt_t;
366 
368  typedef typename monoid_elt_t::value_t monoid_elt_value_t;
369 
371  typedef typename monoid_t::letter_t letter_t;
372 
374  typedef typename series_set_t::semiring_t semiring_t;
375 
377  typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t;
378 
380  typedef typename series_set_elt_t::semiring_elt_value_t
381  semiring_elt_value_t;
382 
384  typedef typename automaton_traits<T>::tag_t tag_t;
385 
387  typedef typename automaton_traits<T>::label_t label_t;
388 
390  typedef typename automaton_traits<T>::states_t states_t;
391 
393  typedef typename automaton_traits<T>::state_iterator state_iterator;
394 
396  typedef typename automaton_traits<T>::transitions_t transitions_t;
397 
399  typedef typename automaton_traits<T>::transition_iterator transition_iterator;
400 
402  typedef typename automaton_traits<T>::initial_support_t initial_support_t;
403 
405  typedef typename automaton_traits<T>::initial_iterator initial_iterator;
406 
408  typedef typename automaton_traits<T>::final_support_t final_support_t;
409 
411  typedef typename automaton_traits<T>::final_iterator final_iterator;
412 
414  typedef typename automaton_traits<T>::geometry_t geometry_t;
415 
417  typedef typename automaton_traits<T>::geometry_t::coords_t geometry_coords_t;
418 
420  typedef typename automaton_traits<T>::hstate_t hstate_t;
421  typedef typename automaton_traits<T>::htransition_t htransition_t;
422 
424  typedef typename automaton_traits<T>::delta_iterator delta_iterator;
425  typedef typename automaton_traits<T>::rdelta_iterator rdelta_iterator;
426 
428  const series_set_t& series() const;
429 
431  tag_t& tag();
432 
434  const tag_t& tag() const;
435 
437  geometry_t& geometry();
438 
440  const geometry_t& geometry() const;
441 
443  bool exists() const;
444 
447 
449  states_t states() const;
450 
452  transitions_t transitions() const;
453 
455  initial_support_t initial() const;
456 
458  final_support_t final() const;
459 
461  bool is_initial(const hstate_t& state) const;
462  bool is_initial(unsigned state) const;
463 
465  bool is_final(const hstate_t& state) const;
466  bool is_final(unsigned state) const;
467 
469  void set_initial(const hstate_t& state);
470  void set_initial(unsigned state);
471 
473  void set_initial(const hstate_t& state, const series_set_elt_t& m);
474  void set_initial(unsigned state, const series_set_elt_t& m);
475 
477  void set_final(const hstate_t& state);
478  void set_final(unsigned state);
479 
481  void set_final(const hstate_t& state, const series_set_elt_t& m);
482  void set_final(unsigned state, const series_set_elt_t& m);
483 
485  void unset_initial(const hstate_t& state);
486  void unset_initial(unsigned state);
487 
489  void unset_final(const hstate_t& state);
490  void unset_final(unsigned state);
491 
493  void clear_initial();
494 
496  void clear_final();
497 
499  Element<series_set_t, series_set_elt_value_t>
500  get_initial(const hstate_t& state) const;
501  Element<series_set_t, series_set_elt_value_t>
502  get_initial(unsigned state) const;
503 
505  Element<series_set_t, series_set_elt_value_t>
506  get_final(const hstate_t& state) const;
507  Element<series_set_t, series_set_elt_value_t>
508  get_final(unsigned state) const;
509 
511  hstate_t add_state();
512 
514  hstate_t get_state(unsigned state) const;
515 
518  hstate_t choose_state() const;
519 
521  htransition_t add_transition(const hstate_t& src, const hstate_t& dst,
522  const label_t& label);
523  htransition_t add_transition(unsigned src, unsigned dst,
524  const label_t& label);
525 
528  htransition_t add_weighted_transition(const hstate_t& src, const hstate_t& dst,
529  const semiring_elt_t& w,
530  const monoid_elt_value_t& m);
531  htransition_t add_weighted_transition(unsigned src, unsigned dst,
532  const semiring_elt_t& w,
533  const monoid_elt_value_t& m);
534 
536 
539  htransition_t add_series_transition(const hstate_t& src, const hstate_t& dst,
540  const series_set_elt_t& e);
541  htransition_t add_series_transition(unsigned src, unsigned dst,
542  const series_set_elt_t& e);
543 
545  htransition_t add_spontaneous(const hstate_t& src, const hstate_t& dst,
546  const semiring_elt_t& w);
547 
548  htransition_t add_spontaneous(const hstate_t& src, const hstate_t& dst);
549 
550  htransition_t add_spontaneous(unsigned src, unsigned dst,
551  const semiring_elt_t& w);
552 
553  htransition_t add_spontaneous(unsigned src, unsigned dst);
554 
556  htransition_t add_letter_transition(const hstate_t& src, const hstate_t& dst,
557  const letter_t& l);
558  htransition_t add_letter_transition(unsigned src, unsigned dst,
559  const letter_t& l);
560 
563  htransition_t add_letter_transition(const hstate_t& src, const hstate_t& dst,
564  const std::string& l);
565  htransition_t add_letter_transition(unsigned src, unsigned dst,
566  const std::string& l);
567 
569  void update(const htransition_t& e, const label_t& l);
570 
572  void del_state(const hstate_t& state);
573  void del_state(unsigned state);
574 
576  void del_transition(const htransition_t& e);
577 
579  bool has_state(const hstate_t& state) const;
580  bool has_state(unsigned state) const;
581 
583  bool has_transition(const htransition_t& e) const;
584 
586  hstate_t src_of(const htransition_t& e) const;
587 
589  hstate_t dst_of(const htransition_t& e) const;
590 
592  typename automaton_traits<T>::label_t label_of(const htransition_t& e) const;
593 
595  series_set_elt_t series_of(const htransition_t& e) const;
596 
598  series_set_elt_value_t series_value_of(const htransition_t& e) const;
599 
601  bool is_spontaneous(const htransition_t& e) const;
602 
604  monoid_elt_t word_of(const htransition_t& e) const;
605 
607  semiring_elt_t weight_of(const htransition_t& e) const;
608 
610  monoid_elt_value_t word_value_of(const htransition_t& e) const;
611 
613 
616  letter_t letter_of(const htransition_t& e) const;
617 
618 
619  protected:
620  MetaElement();
621  MetaElement(const MetaElement& other);
622  };
623 
626 
627  template <typename S, typename St, typename T>
628  St& op_rout(const AutomataBase<S>& s, St& st, const T& r);
629 
630  template <typename Auto_>
631  typename generalized_traits<Auto_>::automaton_t
632  generalized(const Auto_& from);
633 } // vcsn
634 
635 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
636 # include <vaucanson/automata/concept/automata_base.hxx>
637 # endif // VCSN_USE_INTERFACE_ONLY
638 
639 #endif // ! VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH
Generated on Sat Jul 14 2012 18:46:39 for Vaucanson by   doxygen 1.8.1.1