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_state_iterator;
00087 typedef undefined_type delta_transition_iterator;
00088 typedef undefined_type rdelta_state_iterator;
00089 typedef undefined_type rdelta_transition_iterator;
00090 };
00091
00092 # define VCSN_MAKE_AUTOMATON_TRAITS(Type) \
00093 template <typename Kind, \
00094 typename WordValue, \
00095 typename WeightValue, \
00096 typename SeriesValue, \
00097 typename Letter, \
00098 typename Tag, \
00099 typename GeometryCoords> \
00100 struct automaton_traits<Type<Kind, WordValue, WeightValue, SeriesValue, \
00101 Letter, Tag, GeometryCoords> > \
00102 { \
00103 typedef Type<Kind, WordValue, WeightValue, SeriesValue, \
00104 Letter, Tag, GeometryCoords> graph_t; \
00105 typedef typename graph_t::semiring_elt_value_t semiring_elt_value_t; \
00106 typedef typename graph_t::monoid_elt_value_t monoid_elt_value_t; \
00107 typedef typename graph_t::word_value_t word_value_t; \
00108 typedef typename graph_t::series_set_elt_value_t series_set_elt_value_t; \
00109 typedef typename graph_t::letter_t letter_t; \
00110 typedef typename graph_t::tag_t tag_t; \
00111 typedef typename graph_t::geometry_t geometry_t; \
00112 typedef typename graph_t::label_t label_t; \
00113 typedef typename graph_t::states_t states_t; \
00114 typedef typename states_t::iterator state_iterator; \
00115 typedef typename graph_t::hstate_t hstate_t; \
00116 typedef typename graph_t::edges_t transitions_t; \
00117 typedef typename transitions_t::iterator transition_iterator; \
00118 typedef typename graph_t::htransition_t htransition_t; \
00119 typedef typename graph_t::initial_t initial_t; \
00120 typedef typename graph_t::initial_support_t initial_support_t; \
00121 typedef typename initial_support_t::iterator initial_iterator; \
00122 typedef typename graph_t::final_t final_t; \
00123 typedef typename graph_t::final_support_t final_support_t; \
00124 typedef typename final_support_t::iterator final_iterator; \
00125 typedef typename graph_t::delta_state_iterator delta_state_iterator; \
00126 typedef typename graph_t::delta_transition_iterator delta_transition_iterator; \
00127 typedef typename graph_t::rdelta_state_iterator rdelta_state_iterator; \
00128 typedef typename graph_t::rdelta_transition_iterator rdelta_transition_iterator; \
00129 }
00130
00131
00132 template <typename Auto>
00133 struct generalized_traits
00134 {
00135 typedef undefined_type automaton_t;
00136 };
00137
00138 # define VCSN_MAKE_GENERALIZED_AUTOMATON_TRAITS(Type) \
00139 template <typename Struct, \
00140 typename Kind, \
00141 typename WordValue, \
00142 typename WeightValue, \
00143 typename SeriesValue, \
00144 typename Letter, \
00145 typename Tag, \
00146 typename GeometryCoords> \
00147 struct generalized_traits<Element<Struct, Type<Kind, WordValue, \
00148 WeightValue, SeriesValue, Letter, \
00149 Tag, GeometryCoords> > > \
00150 { \
00151 typedef Element<Struct, Type<Kind, WordValue, WeightValue, SeriesValue, \
00152 Letter, Tag, GeometryCoords> > Auto_; \
00153 typedef typename Auto_::series_set_t series_set_t; \
00154 typedef typename Auto_::kind_t kind_t; \
00155 typedef typename series_set_t::monoid_t monoid_t; \
00156 typedef typename Auto_::series_set_elt_t series_set_elt_t; \
00157 typedef typename series_set_elt_t::monoid_elt_t monoid_elt_t; \
00158 typedef typename monoid_elt_t::value_t monoid_elt_value_t; \
00159 typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t; \
00160 typedef typename semiring_elt_t::value_t semiring_elt_value_t; \
00161 typedef typename Auto_::value_t::geometry_t geometry_t; \
00162 typedef vcsn::Element<vcsn::Automata<series_set_t, Kind>, \
00163 Type<labels_are_series, \
00164 monoid_elt_value_t, \
00165 semiring_elt_value_t, \
00166 rat::exp<monoid_elt_value_t, semiring_elt_value_t>, \
00167 typename monoid_t::letter_t, \
00168 NoTag, \
00169 typename geometry_t::coords_t> \
00170 > automaton_t; \
00171 typedef typename automaton_t::hstate_t hstate_t; \
00172 typedef typename automaton_t::htransition_t htransition_t; \
00173 }
00174
00175
00176
00177
00178
00179
00180
00181 template <typename Struct, typename Ratexp>
00182 struct standard_of_traits
00183 {
00184 typedef undefined_type automaton_t;
00185 };
00186
00187 # define VCSN_MAKE_STANDARD_OF_TRAITS(Type) \
00188 template <typename W, \
00189 typename M, \
00190 typename Tm, \
00191 typename Tw> \
00192 struct standard_of_traits<algebra::Series<W, M>, rat::exp<Tm, Tw> > \
00193 { \
00194 typedef typename algebra::Series<W, M> series_set_t; \
00195 typedef typename algebra::polynom<Tm, Tw> \
00196 series_set_elt_value_t; \
00197 typedef typename M::letter_t letter_t; \
00198 typedef typename Type<labels_are_series, Tm, Tw, \
00199 series_set_elt_value_t, letter_t, \
00200 NoTag, std::pair<double, double> > \
00201 automaton_impl_t; \
00202 typedef Element<Automata<series_set_t, labels_are_series>, automaton_impl_t> \
00203 automaton_t; \
00204 }
00205
00206
00207
00208 template <typename S, typename T>
00209 struct projection_traits
00210 {
00212 typedef undefined_type first_projection_t;
00213
00215 typedef undefined_type second_projection_t;
00216 };
00217
00218
00219
00220
00221 template <typename T, typename TT>
00222 struct mute_graph_impl_traits
00223 {
00225 typedef undefined_type first_projection_t;
00226
00228 typedef undefined_type second_projection_t;
00229 };
00230
00231 # define VCSN_MAKE_MUTE_GRAPH_IMPL_TRAITS(Type) \
00232 template <typename Kind, \
00233 typename WordValue, \
00234 typename WeightValue, \
00235 typename SeriesValue, \
00236 typename Letter, \
00237 typename Tag, \
00238 typename GeometryCoords, \
00239 typename TT> \
00240 struct mute_graph_impl_traits<Type<Kind, \
00241 WordValue, \
00242 WeightValue, \
00243 SeriesValue, \
00244 Letter, \
00245 Tag, \
00246 GeometryCoords>, TT> \
00247 { \
00248 typedef Type<Kind, WordValue, WeightValue, SeriesValue, \
00249 Letter, Tag, GeometryCoords> graph_t; \
00250 typedef typename algebra::letter_traits<Letter>:: \
00251 first_projection_t first_letter_t; \
00252 typedef typename algebra::letter_traits<Letter>:: \
00253 second_projection_t second_letter_t; \
00254 typedef typename TT::first_projection_t::value_t \
00255 first_monoid_elt_value_t; \
00256 typedef typename TT::second_projection_t::value_t \
00257 second_monoid_elt_value_t; \
00258 typedef typename algebra::mute_series_impl<SeriesValue, WeightValue, \
00259 first_monoid_elt_value_t>::ret \
00260 first_series_impl_t; \
00261 typedef typename algebra::mute_series_impl<SeriesValue, WeightValue, \
00262 second_monoid_elt_value_t>::ret \
00263 second_series_impl_t; \
00264 typedef Type<Kind, first_monoid_elt_value_t, \
00265 WeightValue, first_series_impl_t, \
00266 first_letter_t, Tag, GeometryCoords> first_projection_t; \
00267 typedef Type<Kind, second_monoid_elt_value_t, \
00268 WeightValue, second_series_impl_t, \
00269 second_letter_t, Tag, GeometryCoords> second_projection_t; \
00270 }
00271
00272
00273
00274
00275 template <typename G, typename W, typename L>
00276 struct mute_graph_impl_monoid_traits
00277 {
00279 typedef undefined_type ret;
00280 };
00281
00282 # define VCSN_MAKE_MUTE_GRAPH_IMPL_MONOID_TRAITS(Type) \
00283 template <typename Kind, \
00284 typename WordValue, \
00285 typename WeightValue, \
00286 typename SeriesValue, \
00287 typename Letter, \
00288 typename Tag, \
00289 typename GeometryCoords, \
00290 typename W, \
00291 typename L> \
00292 struct mute_graph_impl_monoid_traits<Type<Kind, \
00293 WordValue, \
00294 WeightValue, \
00295 SeriesValue, \
00296 Letter, \
00297 Tag, \
00298 GeometryCoords>, W, L> \
00299 { \
00300 typedef Type<Kind, WordValue, WeightValue, SeriesValue, \
00301 Letter, Tag, GeometryCoords> graph_t; \
00302 typedef typename algebra::mute_series_impl<SeriesValue, WeightValue, \
00303 W>::ret \
00304 series_impl_t; \
00305 typedef Type<Kind, W, \
00306 WeightValue, series_impl_t, \
00307 L, Tag, GeometryCoords> ret; \
00308 }
00309
00310
00311
00312
00313
00314 template <class S>
00315 struct virtual_types<AutomataBase<S> >
00316 : virtual_types<Structure<S> >
00317 { };
00318
00319
00320
00321
00322 template <class S>
00323 struct dynamic_traits<AutomataBase<S> >
00324 : dynamic_traits<Structure<S> >
00325 { };
00326
00327
00328
00329
00331
00344
00345 template <typename Self, typename T>
00346 struct MetaElement<AutomataBase<Self>, T>
00347 : MetaElement<Structure<Self>, T>
00348 {
00350 typedef MetaElement<AutomataBase<Self>, T> self_t;
00351
00353 typedef typename AutomataBase<Self>::series_set_t series_set_t;
00354
00356 typedef typename AutomataBase<Self>::kind_t kind_t;
00357
00359 typedef typename automaton_traits<T>::series_set_elt_value_t
00360 series_set_elt_value_t;
00361
00363 typedef Element<series_set_t, series_set_elt_value_t> series_set_elt_t;
00364
00366 typedef typename series_set_t::monoid_t monoid_t;
00367
00369 typedef typename series_set_elt_t::monoid_elt_t monoid_elt_t;
00370
00372 typedef typename monoid_elt_t::value_t monoid_elt_value_t;
00373
00375 typedef typename monoid_t::letter_t letter_t;
00376
00378 typedef typename series_set_t::semiring_t semiring_t;
00379
00381 typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t;
00382
00384 typedef typename series_set_elt_t::semiring_elt_value_t
00385 semiring_elt_value_t;
00386
00388 typedef typename automaton_traits<T>::tag_t tag_t;
00389
00391 typedef typename automaton_traits<T>::label_t label_t;
00392
00394 typedef typename automaton_traits<T>::states_t states_t;
00395
00397 typedef typename automaton_traits<T>::state_iterator state_iterator;
00398
00400 typedef typename automaton_traits<T>::transitions_t transitions_t;
00401
00403 typedef typename automaton_traits<T>::transition_iterator transition_iterator;
00404
00406 typedef typename automaton_traits<T>::initial_support_t initial_support_t;
00407
00409 typedef typename automaton_traits<T>::initial_iterator initial_iterator;
00410
00412 typedef typename automaton_traits<T>::final_support_t final_support_t;
00413
00415 typedef typename automaton_traits<T>::final_iterator final_iterator;
00416
00418 typedef typename automaton_traits<T>::geometry_t geometry_t;
00419
00421 typedef typename automaton_traits<T>::geometry_t::coords_t geometry_coords_t;
00422
00424 typedef typename automaton_traits<T>::hstate_t hstate_t;
00425 typedef typename automaton_traits<T>::htransition_t htransition_t;
00426
00428 typedef typename automaton_traits<T>::delta_state_iterator delta_state_iterator;
00429 typedef typename automaton_traits<T>::delta_transition_iterator delta_transition_iterator;
00430 typedef typename automaton_traits<T>::rdelta_state_iterator rdelta_state_iterator;
00431 typedef typename automaton_traits<T>::rdelta_transition_iterator rdelta_transition_iterator;
00432
00434 const series_set_t& series() const;
00435
00437 tag_t& tag();
00438
00440 const tag_t& tag() const;
00441
00443 geometry_t& geometry();
00444
00446 const geometry_t& geometry() const;
00447
00449 bool exists() const;
00450
00453
00455 states_t states() const;
00456
00458 transitions_t transitions() const;
00459
00461 initial_support_t initial() const;
00462
00464 final_support_t final() const;
00465
00467 bool is_initial(const hstate_t& state) const;
00468 bool is_initial(unsigned state) const;
00469
00471 bool is_final(const hstate_t& state) const;
00472 bool is_final(unsigned state) const;
00473
00475 void set_initial(const hstate_t& state);
00476 void set_initial(unsigned state);
00477
00479 void set_initial(const hstate_t& state, const series_set_elt_t& m);
00480 void set_initial(unsigned state, const series_set_elt_t& m);
00481
00483 void set_final(const hstate_t& state);
00484 void set_final(unsigned state);
00485
00487 void set_final(const hstate_t& state, const series_set_elt_t& m);
00488 void set_final(unsigned state, const series_set_elt_t& m);
00489
00491 void unset_initial(const hstate_t& state);
00492 void unset_initial(unsigned state);
00493
00495 void unset_final(const hstate_t& state);
00496 void unset_final(unsigned state);
00497
00499 void clear_initial();
00500
00502 void clear_final();
00503
00505 Element<series_set_t, series_set_elt_value_t>
00506 get_initial(const hstate_t& state) const;
00507 Element<series_set_t, series_set_elt_value_t>
00508 get_initial(unsigned state) const;
00509
00511 Element<series_set_t, series_set_elt_value_t>
00512 get_final(const hstate_t& state) const;
00513 Element<series_set_t, series_set_elt_value_t>
00514 get_final(unsigned state) const;
00515
00517 hstate_t add_state();
00518
00520 hstate_t get_state(unsigned state) const;
00521
00524 hstate_t choose_state() const;
00525
00527 htransition_t add_transition(const hstate_t& src, const hstate_t& dst,
00528 const label_t& label);
00529 htransition_t add_transition(unsigned src, unsigned dst,
00530 const label_t& label);
00531
00534 htransition_t add_weighted_transition(const hstate_t& src, const hstate_t& dst,
00535 const semiring_elt_t& w,
00536 const monoid_elt_value_t& m);
00537 htransition_t add_weighted_transition(unsigned src, unsigned dst,
00538 const semiring_elt_t& w,
00539 const monoid_elt_value_t& m);
00540
00542
00545 htransition_t add_series_transition(const hstate_t& src, const hstate_t& dst,
00546 const series_set_elt_t& e);
00547 htransition_t add_series_transition(unsigned src, unsigned dst,
00548 const series_set_elt_t& e);
00549
00551 htransition_t add_spontaneous(const hstate_t& src, const hstate_t& dst,
00552 const semiring_elt_t& w);
00553
00554 htransition_t add_spontaneous(const hstate_t& src, const hstate_t& dst);
00555
00556 htransition_t add_spontaneous(unsigned src, unsigned dst,
00557 const semiring_elt_t& w);
00558
00559 htransition_t add_spontaneous(unsigned src, unsigned dst);
00560
00562 htransition_t add_letter_transition(const hstate_t& src, const hstate_t& dst,
00563 const letter_t& l);
00564 htransition_t add_letter_transition(unsigned src, unsigned dst,
00565 const letter_t& l);
00566
00569 htransition_t add_letter_transition(const hstate_t& src, const hstate_t& dst,
00570 const std::string& l);
00571 htransition_t add_letter_transition(unsigned src, unsigned dst,
00572 const std::string& l);
00573
00575 void update(const htransition_t& e, const label_t& l);
00576
00578 void del_state(const hstate_t& state);
00579 void del_state(unsigned state);
00580
00582 void del_transition(const htransition_t& e);
00583
00585 bool has_state(const hstate_t& state) const;
00586 bool has_state(unsigned state) const;
00587
00589 bool has_transition(const htransition_t& e) const;
00590
00592 hstate_t src_of(const htransition_t& e) const;
00593
00595 hstate_t dst_of(const htransition_t& e) const;
00596
00598 typename automaton_traits<T>::label_t label_of(const htransition_t& e) const;
00599
00601 series_set_elt_t series_of(const htransition_t& e) const;
00602
00604 series_set_elt_value_t series_value_of(const htransition_t& e) const;
00605
00607 bool is_spontaneous(const htransition_t& e) const;
00608
00610 monoid_elt_t word_of(const htransition_t& e) const;
00611
00613 semiring_elt_t weight_of(const htransition_t& e) const;
00614
00616 monoid_elt_value_t word_value_of(const htransition_t& e) const;
00617
00619
00622 letter_t letter_of(const htransition_t& e) const;
00623
00624
00625
00626
00627
00630 template <typename Container, typename Kind>
00631 void deltac(Container& res, const hstate_t& src, delta_kind::kind<Kind> k) const;
00632 template <typename Container, typename Kind>
00633 void deltac(Container& res, unsigned src, delta_kind::kind<Kind> k) const;
00634
00638 template <typename Container, typename L, typename Kind>
00639 void deltac(Container& res,
00640 const hstate_t& src,
00641 const L& query,
00642 delta_kind::kind<Kind> k) const;
00643 template <typename Container, typename L, typename Kind>
00644 void deltac(Container& res,
00645 unsigned src,
00646 const L& query,
00647 delta_kind::kind<Kind> k) const;
00648
00651 template <typename Container, typename L, typename Kind>
00652 void letter_deltac(Container& res,
00653 const hstate_t& src,
00654 const L& letter,
00655 delta_kind::kind<Kind> k) const;
00656 template <typename Container, typename L, typename Kind>
00657 void letter_deltac(Container& res,
00658 unsigned src,
00659 const L& letter,
00660 delta_kind::kind<Kind> k) const;
00661
00664 template <typename Container, typename Kind>
00665 void spontaneous_deltac(Container& res,
00666 const hstate_t& src,
00667 delta_kind::kind<Kind> k) const;
00668 template <typename Container, typename Kind>
00669 void spontaneous_deltac(Container& res,
00670 unsigned src,
00671 delta_kind::kind<Kind> k) const;
00672
00673
00674
00675
00676
00677
00681 template <typename Functor, typename Kind>
00682 void deltaf(Functor& fun, const hstate_t& src, delta_kind::kind<Kind> k) const;
00683 template <typename Functor, typename Kind>
00684 void deltaf(Functor& fun, unsigned src, delta_kind::kind<Kind> k) const;
00685
00689 template <typename Functor, typename L, typename Kind>
00690 void deltaf(Functor& fun,
00691 const hstate_t& src,
00692 const L& query,
00693 delta_kind::kind<Kind> k) const;
00694 template <typename Functor, typename L, typename Kind>
00695 void deltaf(Functor& fun,
00696 unsigned src,
00697 const L& query,
00698 delta_kind::kind<Kind> k) const;
00699
00704 template <typename Functor, typename L, typename Kind>
00705 void letter_deltaf(Functor& fun,
00706 const hstate_t& src,
00707 const L& letter,
00708 delta_kind::kind<Kind> k) const;
00709 template <typename Functor, typename L, typename Kind>
00710 void letter_deltaf(Functor& fun,
00711 unsigned src,
00712 const L& letter,
00713 delta_kind::kind<Kind> k) const;
00714
00719 template <typename Functor, typename Kind>
00720 void spontaneous_deltaf(Functor& fun,
00721 const hstate_t& src,
00722 delta_kind::kind<Kind> k) const;
00723 template <typename Functor, typename Kind>
00724 void spontaneous_deltaf(Functor& fun,
00725 unsigned src,
00726 delta_kind::kind<Kind> k) const;
00727
00728
00729
00730
00731
00732
00735 template <typename Container, typename Kind>
00736 void rdeltac(Container& res, const hstate_t& src, delta_kind::kind<Kind> k) const;
00737 template <typename Container, typename Kind>
00738 void rdeltac(Container& res, unsigned src, delta_kind::kind<Kind> k) const;
00739
00743 template <typename Container, typename L, typename Kind>
00744 void rdeltac(Container& res,
00745 const hstate_t& src,
00746 const L& query,
00747 delta_kind::kind<Kind> k) const;
00748 template <typename Container, typename L, typename Kind>
00749 void rdeltac(Container& res,
00750 unsigned src,
00751 const L& query,
00752 delta_kind::kind<Kind> k) const;
00753
00756 template <typename Container, typename L, typename Kind>
00757 void letter_rdeltac(Container& res,
00758 const hstate_t& src,
00759 const L& letter,
00760 delta_kind::kind<Kind> k) const;
00761 template <typename Container, typename L, typename Kind>
00762 void letter_rdeltac(Container& res,
00763 unsigned src,
00764 const L& letter,
00765 delta_kind::kind<Kind> k) const;
00766
00769 template <typename Container, typename Kind>
00770 void spontaneous_rdeltac(Container& res,
00771 const hstate_t& src,
00772 delta_kind::kind<Kind> k) const;
00773 template <typename Container, typename Kind>
00774 void spontaneous_rdeltac(Container& res,
00775 unsigned src,
00776 delta_kind::kind<Kind> k) const;
00777
00778
00779 protected:
00780 MetaElement();
00781 MetaElement(const MetaElement& other);
00782 };
00783
00786
00787 template <typename S, typename St, typename T>
00788 St& op_rout(const AutomataBase<S>& s, St& st, const T& r);
00789
00790 template <typename Auto_>
00791 typename generalized_traits<Auto_>::automaton_t
00792 generalized(const Auto_& from);
00793 }
00794
00795 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00796 # include <vaucanson/automata/concept/automata_base.hxx>
00797 # endif // VCSN_USE_INTERFACE_ONLY
00798
00799 #endif // ! VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH
