00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018 #ifndef VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH
00019 # define VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH
00020
00021 # include <iterator>
00022 # include <vaucanson/design_pattern/design_pattern.hh>
00023 # include <vaucanson/automata/concept/handlers.hh>
00024 # include <vaucanson/automata/concept/delta_kind.hh>
00025 # include <vaucanson/algebra/concept/series_base.hh>
00026
00027 namespace vcsn {
00028
00032
00033
00034
00036
00040 template <typename Self>
00041 struct AutomataBase
00042 : Structure<Self>
00043 {
00044 public:
00046 typedef typename virtual_types<Self>::series_set_t series_set_t;
00048 typedef typename virtual_types<Self>::kind_t kind_t;
00049
00050 protected:
00052 AutomataBase();
00053
00055 AutomataBase(const AutomataBase& other);
00056
00057 public:
00059 const series_set_t& series() const;
00060 };
00061
00062
00063
00064 template <typename T>
00065 struct automaton_traits
00066 {
00067 typedef undefined_type label_t;
00068 typedef undefined_type series_set_elt_value_t;
00069 typedef undefined_type word_value_t;
00070 typedef undefined_type semiring_elt_value_t;
00071 typedef undefined_type letter_t;
00072 typedef undefined_type tag_t;
00073 typedef undefined_type states_t;
00074 typedef undefined_type state_iterator;
00075 typedef undefined_type transitions_t;
00076 typedef undefined_type transition_iterator;
00077 typedef undefined_type initial_iterator;
00078 typedef undefined_type initial_t;
00079 typedef undefined_type initial_support_t;
00080 typedef undefined_type final_iterator;
00081 typedef undefined_type final_t;
00082 typedef undefined_type final_support_t;
00083 typedef undefined_type geometry_t;
00084 typedef undefined_type hstate_t;
00085 typedef undefined_type htransition_t;
00086 typedef undefined_type delta_iterator;
00087 typedef undefined_type rdelta_iterator;
00088 };
00089
00090 # define VCSN_MAKE_AUTOMATON_TRAITS(Type) \
00091 template <typename Kind, \
00092 typename WordValue, \
00093 typename WeightValue, \
00094 typename SeriesValue, \
00095 typename Letter, \
00096 typename Tag, \
00097 typename GeometryCoords> \
00098 struct automaton_traits<Type<Kind, WordValue, WeightValue, SeriesValue, \
00099 Letter, Tag, GeometryCoords> > \
00100 { \
00101 typedef Type<Kind, WordValue, WeightValue, SeriesValue, \
00102 Letter, Tag, GeometryCoords> graph_t; \
00103 typedef typename graph_t::semiring_elt_value_t semiring_elt_value_t; \
00104 typedef typename graph_t::monoid_elt_value_t monoid_elt_value_t; \
00105 typedef typename graph_t::word_value_t word_value_t; \
00106 typedef typename graph_t::series_set_elt_value_t series_set_elt_value_t; \
00107 typedef typename graph_t::letter_t letter_t; \
00108 typedef typename graph_t::tag_t tag_t; \
00109 typedef typename graph_t::geometry_t geometry_t; \
00110 typedef typename graph_t::label_t label_t; \
00111 typedef typename graph_t::states_t states_t; \
00112 typedef typename states_t::iterator state_iterator; \
00113 typedef typename graph_t::hstate_t hstate_t; \
00114 typedef typename graph_t::edges_t transitions_t; \
00115 typedef typename transitions_t::iterator transition_iterator; \
00116 typedef typename graph_t::htransition_t htransition_t; \
00117 typedef typename graph_t::initial_t initial_t; \
00118 typedef typename graph_t::initial_support_t initial_support_t; \
00119 typedef typename initial_support_t::iterator initial_iterator; \
00120 typedef typename graph_t::final_t final_t; \
00121 typedef typename graph_t::final_support_t final_support_t; \
00122 typedef typename final_support_t::iterator final_iterator; \
00123 typedef typename graph_t::delta_iterator delta_iterator; \
00124 typedef typename graph_t::rdelta_iterator rdelta_iterator; \
00125 }
00126
00127
00128 template <typename Auto>
00129 struct generalized_traits
00130 {
00131 typedef undefined_type automaton_t;
00132 };
00133
00134 # define VCSN_MAKE_GENERALIZED_AUTOMATON_TRAITS(Type) \
00135 template <typename Struct, \
00136 typename Kind, \
00137 typename WordValue, \
00138 typename WeightValue, \
00139 typename SeriesValue, \
00140 typename Letter, \
00141 typename Tag, \
00142 typename GeometryCoords> \
00143 struct generalized_traits<Element<Struct, Type<Kind, WordValue, \
00144 WeightValue, SeriesValue, Letter, \
00145 Tag, GeometryCoords> > > \
00146 { \
00147 typedef Element<Struct, Type<Kind, WordValue, WeightValue, SeriesValue, \
00148 Letter, Tag, GeometryCoords> > Auto_; \
00149 typedef typename Auto_::series_set_t series_set_t; \
00150 typedef typename Auto_::kind_t kind_t; \
00151 typedef typename series_set_t::monoid_t monoid_t; \
00152 typedef typename Auto_::series_set_elt_t series_set_elt_t; \
00153 typedef typename series_set_elt_t::monoid_elt_t monoid_elt_t; \
00154 typedef typename monoid_elt_t::value_t monoid_elt_value_t; \
00155 typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t; \
00156 typedef typename semiring_elt_t::value_t semiring_elt_value_t; \
00157 typedef typename Auto_::value_t::geometry_t geometry_t; \
00158 typedef vcsn::Element<vcsn::Automata<series_set_t, Kind>, \
00159 Type<labels_are_series, \
00160 monoid_elt_value_t, \
00161 semiring_elt_value_t, \
00162 rat::exp<monoid_elt_value_t, semiring_elt_value_t>, \
00163 typename monoid_t::letter_t, \
00164 NoTag, \
00165 typename geometry_t::coords_t> \
00166 > automaton_t; \
00167 typedef typename automaton_t::hstate_t hstate_t; \
00168 typedef typename automaton_t::htransition_t htransition_t; \
00169 }
00170
00171
00172
00173
00174
00175
00176
00177 template <typename Struct, typename Ratexp>
00178 struct standard_of_traits
00179 {
00180 typedef undefined_type automaton_t;
00181 };
00182
00183 # define VCSN_MAKE_STANDARD_OF_TRAITS(Type) \
00184 template <typename W, \
00185 typename M, \
00186 typename Tm, \
00187 typename Tw> \
00188 struct standard_of_traits<algebra::Series<W, M>, rat::exp<Tm, Tw> > \
00189 { \
00190 typedef typename algebra::Series<W, M> series_set_t; \
00191 typedef typename algebra::polynom<Tm, Tw> \
00192 series_set_elt_value_t; \
00193 typedef typename M::letter_t letter_t; \
00194 typedef typename Type<labels_are_series, Tm, Tw, \
00195 series_set_elt_value_t, letter_t, \
00196 NoTag, std::pair<double, double> > \
00197 automaton_impl_t; \
00198 typedef Element<Automata<series_set_t, labels_are_series>, automaton_impl_t> \
00199 automaton_t; \
00200 }
00201
00202
00203
00204 template <typename S, typename T>
00205 struct projection_traits
00206 {
00208 typedef undefined_type first_projection_t;
00209
00211 typedef undefined_type second_projection_t;
00212 };
00213
00214
00215
00216
00217 template <typename T, typename TT>
00218 struct mute_graph_impl_traits
00219 {
00221 typedef undefined_type first_projection_t;
00222
00224 typedef undefined_type second_projection_t;
00225 };
00226
00227 # define VCSN_MAKE_MUTE_GRAPH_IMPL_TRAITS(Type) \
00228 template <typename Kind, \
00229 typename WordValue, \
00230 typename WeightValue, \
00231 typename SeriesValue, \
00232 typename Letter, \
00233 typename Tag, \
00234 typename GeometryCoords, \
00235 typename TT> \
00236 struct mute_graph_impl_traits<Type<Kind, \
00237 WordValue, \
00238 WeightValue, \
00239 SeriesValue, \
00240 Letter, \
00241 Tag, \
00242 GeometryCoords>, TT> \
00243 { \
00244 typedef Type<Kind, WordValue, WeightValue, SeriesValue, \
00245 Letter, Tag, GeometryCoords> graph_t; \
00246 typedef typename algebra::letter_traits<Letter>:: \
00247 first_projection_t first_letter_t; \
00248 typedef typename algebra::letter_traits<Letter>:: \
00249 second_projection_t second_letter_t; \
00250 typedef typename TT::first_projection_t::value_t \
00251 first_monoid_elt_value_t; \
00252 typedef typename TT::second_projection_t::value_t \
00253 second_monoid_elt_value_t; \
00254 typedef typename algebra::mute_series_impl<SeriesValue, WeightValue, \
00255 first_monoid_elt_value_t>::ret \
00256 first_series_impl_t; \
00257 typedef typename algebra::mute_series_impl<SeriesValue, WeightValue, \
00258 second_monoid_elt_value_t>::ret \
00259 second_series_impl_t; \
00260 typedef Type<Kind, first_monoid_elt_value_t, \
00261 WeightValue, first_series_impl_t, \
00262 first_letter_t, Tag, GeometryCoords> first_projection_t; \
00263 typedef Type<Kind, second_monoid_elt_value_t, \
00264 WeightValue, second_series_impl_t, \
00265 second_letter_t, Tag, GeometryCoords> second_projection_t; \
00266 }
00267
00268
00269
00270
00271 template <typename G, typename W, typename L>
00272 struct mute_graph_impl_monoid_traits
00273 {
00275 typedef undefined_type ret;
00276 };
00277
00278 # define VCSN_MAKE_MUTE_GRAPH_IMPL_MONOID_TRAITS(Type) \
00279 template <typename Kind, \
00280 typename WordValue, \
00281 typename WeightValue, \
00282 typename SeriesValue, \
00283 typename Letter, \
00284 typename Tag, \
00285 typename GeometryCoords, \
00286 typename W, \
00287 typename L> \
00288 struct mute_graph_impl_monoid_traits<Type<Kind, \
00289 WordValue, \
00290 WeightValue, \
00291 SeriesValue, \
00292 Letter, \
00293 Tag, \
00294 GeometryCoords>, W, L> \
00295 { \
00296 typedef Type<Kind, WordValue, WeightValue, SeriesValue, \
00297 Letter, Tag, GeometryCoords> graph_t; \
00298 typedef typename algebra::mute_series_impl<SeriesValue, WeightValue, \
00299 W>::ret \
00300 series_impl_t; \
00301 typedef Type<Kind, W, \
00302 WeightValue, series_impl_t, \
00303 L, Tag, GeometryCoords> ret; \
00304 }
00305
00306
00307
00308
00309
00310 template <class S>
00311 struct virtual_types<AutomataBase<S> >
00312 : virtual_types<Structure<S> >
00313 { };
00314
00315
00316
00317
00318 template <class S>
00319 struct dynamic_traits<AutomataBase<S> >
00320 : dynamic_traits<Structure<S> >
00321 { };
00322
00323
00324
00325
00327
00340
00341 template <typename Self, typename T>
00342 struct MetaElement<AutomataBase<Self>, T>
00343 : MetaElement<Structure<Self>, T>
00344 {
00346 typedef MetaElement<AutomataBase<Self>, T> self_t;
00347
00349 typedef typename AutomataBase<Self>::series_set_t series_set_t;
00350
00352 typedef typename AutomataBase<Self>::kind_t kind_t;
00353
00355 typedef typename automaton_traits<T>::series_set_elt_value_t
00356 series_set_elt_value_t;
00357
00359 typedef Element<series_set_t, series_set_elt_value_t> series_set_elt_t;
00360
00362 typedef typename series_set_t::monoid_t monoid_t;
00363
00365 typedef typename series_set_elt_t::monoid_elt_t monoid_elt_t;
00366
00368 typedef typename monoid_elt_t::value_t monoid_elt_value_t;
00369
00371 typedef typename monoid_t::letter_t letter_t;
00372
00374 typedef typename series_set_t::semiring_t semiring_t;
00375
00377 typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t;
00378
00380 typedef typename series_set_elt_t::semiring_elt_value_t
00381 semiring_elt_value_t;
00382
00384 typedef typename automaton_traits<T>::tag_t tag_t;
00385
00387 typedef typename automaton_traits<T>::label_t label_t;
00388
00390 typedef typename automaton_traits<T>::states_t states_t;
00391
00393 typedef typename automaton_traits<T>::state_iterator state_iterator;
00394
00396 typedef typename automaton_traits<T>::transitions_t transitions_t;
00397
00399 typedef typename automaton_traits<T>::transition_iterator transition_iterator;
00400
00402 typedef typename automaton_traits<T>::initial_support_t initial_support_t;
00403
00405 typedef typename automaton_traits<T>::initial_iterator initial_iterator;
00406
00408 typedef typename automaton_traits<T>::final_support_t final_support_t;
00409
00411 typedef typename automaton_traits<T>::final_iterator final_iterator;
00412
00414 typedef typename automaton_traits<T>::geometry_t geometry_t;
00415
00417 typedef typename automaton_traits<T>::geometry_t::coords_t geometry_coords_t;
00418
00420 typedef typename automaton_traits<T>::hstate_t hstate_t;
00421 typedef typename automaton_traits<T>::htransition_t htransition_t;
00422
00424 typedef typename automaton_traits<T>::delta_iterator delta_iterator;
00425 typedef typename automaton_traits<T>::rdelta_iterator rdelta_iterator;
00426
00428 const series_set_t& series() const;
00429
00431 tag_t& tag();
00432
00434 const tag_t& tag() const;
00435
00437 geometry_t& geometry();
00438
00440 const geometry_t& geometry() const;
00441
00443 bool exists() const;
00444
00447
00449 states_t states() const;
00450
00452 transitions_t transitions() const;
00453
00455 initial_support_t initial() const;
00456
00458 final_support_t final() const;
00459
00461 bool is_initial(const hstate_t& state) const;
00462 bool is_initial(unsigned state) const;
00463
00465 bool is_final(const hstate_t& state) const;
00466 bool is_final(unsigned state) const;
00467
00469 void set_initial(const hstate_t& state);
00470 void set_initial(unsigned state);
00471
00473 void set_initial(const hstate_t& state, const series_set_elt_t& m);
00474 void set_initial(unsigned state, const series_set_elt_t& m);
00475
00477 void set_final(const hstate_t& state);
00478 void set_final(unsigned state);
00479
00481 void set_final(const hstate_t& state, const series_set_elt_t& m);
00482 void set_final(unsigned state, const series_set_elt_t& m);
00483
00485 void unset_initial(const hstate_t& state);
00486 void unset_initial(unsigned state);
00487
00489 void unset_final(const hstate_t& state);
00490 void unset_final(unsigned state);
00491
00493 void clear_initial();
00494
00496 void clear_final();
00497
00499 Element<series_set_t, series_set_elt_value_t>
00500 get_initial(const hstate_t& state) const;
00501 Element<series_set_t, series_set_elt_value_t>
00502 get_initial(unsigned state) const;
00503
00505 Element<series_set_t, series_set_elt_value_t>
00506 get_final(const hstate_t& state) const;
00507 Element<series_set_t, series_set_elt_value_t>
00508 get_final(unsigned state) const;
00509
00511 hstate_t add_state();
00512
00514 hstate_t get_state(unsigned state) const;
00515
00518 hstate_t choose_state() const;
00519
00521 htransition_t add_transition(const hstate_t& src, const hstate_t& dst,
00522 const label_t& label);
00523 htransition_t add_transition(unsigned src, unsigned dst,
00524 const label_t& label);
00525
00528 htransition_t add_weighted_transition(const hstate_t& src, const hstate_t& dst,
00529 const semiring_elt_t& w,
00530 const monoid_elt_value_t& m);
00531 htransition_t add_weighted_transition(unsigned src, unsigned dst,
00532 const semiring_elt_t& w,
00533 const monoid_elt_value_t& m);
00534
00536
00539 htransition_t add_series_transition(const hstate_t& src, const hstate_t& dst,
00540 const series_set_elt_t& e);
00541 htransition_t add_series_transition(unsigned src, unsigned dst,
00542 const series_set_elt_t& e);
00543
00545 htransition_t add_spontaneous(const hstate_t& src, const hstate_t& dst,
00546 const semiring_elt_t& w);
00547
00548 htransition_t add_spontaneous(const hstate_t& src, const hstate_t& dst);
00549
00550 htransition_t add_spontaneous(unsigned src, unsigned dst,
00551 const semiring_elt_t& w);
00552
00553 htransition_t add_spontaneous(unsigned src, unsigned dst);
00554
00556 htransition_t add_letter_transition(const hstate_t& src, const hstate_t& dst,
00557 const letter_t& l);
00558 htransition_t add_letter_transition(unsigned src, unsigned dst,
00559 const letter_t& l);
00560
00563 htransition_t add_letter_transition(const hstate_t& src, const hstate_t& dst,
00564 const std::string& l);
00565 htransition_t add_letter_transition(unsigned src, unsigned dst,
00566 const std::string& l);
00567
00569 void update(const htransition_t& e, const label_t& l);
00570
00572 void del_state(const hstate_t& state);
00573 void del_state(unsigned state);
00574
00576 void del_transition(const htransition_t& e);
00577
00579 bool has_state(const hstate_t& state) const;
00580 bool has_state(unsigned state) const;
00581
00583 bool has_transition(const htransition_t& e) const;
00584
00586 hstate_t src_of(const htransition_t& e) const;
00587
00589 hstate_t dst_of(const htransition_t& e) const;
00590
00592 typename automaton_traits<T>::label_t label_of(const htransition_t& e) const;
00593
00595 series_set_elt_t series_of(const htransition_t& e) const;
00596
00598 series_set_elt_value_t series_value_of(const htransition_t& e) const;
00599
00601 bool is_spontaneous(const htransition_t& e) const;
00602
00604 monoid_elt_t word_of(const htransition_t& e) const;
00605
00607 semiring_elt_t weight_of(const htransition_t& e) const;
00608
00610 monoid_elt_value_t word_value_of(const htransition_t& e) const;
00611
00613
00616 letter_t letter_of(const htransition_t& e) const;
00617
00618
00619 protected:
00620 MetaElement();
00621 MetaElement(const MetaElement& other);
00622 };
00623
00626
00627 template <typename S, typename St, typename T>
00628 St& op_rout(const AutomataBase<S>& s, St& st, const T& r);
00629
00630 template <typename Auto_>
00631 typename generalized_traits<Auto_>::automaton_t
00632 generalized(const Auto_& from);
00633 }
00634
00635 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00636 # include <vaucanson/automata/concept/automata_base.hxx>
00637 # endif // VCSN_USE_INTERFACE_ONLY
00638
00639 #endif // ! VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH
