00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH
00018 # define VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH
00019
00020 # include <iterator>
00021 # include <vaucanson/design_pattern/design_pattern.hh>
00022 # include <vaucanson/automata/concept/handlers.hh>
00023 # include <vaucanson/automata/concept/delta_kind.hh>
00024 # include <vaucanson/algebra/concept/series_base.hh>
00025
00026 namespace vcsn {
00027
00031
00032
00033
00035
00039 template <typename Self>
00040 struct AutomataBase
00041 : Structure<Self>
00042 {
00043 public:
00045 typedef typename virtual_types<Self>::series_set_t series_set_t;
00046
00047 protected:
00049 AutomataBase();
00050
00052 AutomataBase(const AutomataBase& other);
00053
00054 public:
00056 const series_set_t& series() const;
00057 };
00058
00059
00060 template <typename T>
00061 struct automaton_traits
00062 {
00063 typedef undefined_type label_t;
00064 typedef undefined_type series_set_elt_value_t;
00065 typedef undefined_type word_value_t;
00066 typedef undefined_type semiring_elt_value_t;
00067 typedef undefined_type letter_t;
00068 typedef undefined_type tag_t;
00069 typedef undefined_type states_t;
00070 typedef undefined_type state_iterator;
00071 typedef undefined_type transitions_t;
00072 typedef undefined_type transition_iterator;
00073 typedef undefined_type initial_iterator;
00074 typedef undefined_type initial_t;
00075 typedef undefined_type initial_support_t;
00076 typedef undefined_type final_iterator;
00077 typedef undefined_type final_t;
00078 typedef undefined_type final_support_t;
00079 typedef undefined_type geometry_t;
00080 typedef undefined_type hstate_t;
00081 typedef undefined_type htransition_t;
00082 typedef undefined_type delta_state_iterator;
00083 typedef undefined_type delta_transition_iterator;
00084 typedef undefined_type rdelta_state_iterator;
00085 typedef undefined_type rdelta_transition_iterator;
00086 };
00087
00088 # define VCSN_MAKE_AUTOMATON_TRAITS(Type) \
00089 template <typename Kind, \
00090 typename WordValue, \
00091 typename WeightValue, \
00092 typename SeriesValue, \
00093 typename Letter, \
00094 typename Tag, \
00095 typename GeometryCoords> \
00096 struct automaton_traits<Type<Kind, WordValue, WeightValue, SeriesValue, \
00097 Letter, Tag, GeometryCoords> > \
00098 { \
00099 typedef Type<Kind, WordValue, WeightValue, SeriesValue, \
00100 Letter, Tag, GeometryCoords> graph_t; \
00101 typedef typename graph_t::semiring_elt_value_t semiring_elt_value_t; \
00102 typedef typename graph_t::monoid_elt_value_t monoid_elt_value_t; \
00103 typedef typename graph_t::word_value_t word_value_t; \
00104 typedef typename graph_t::series_set_elt_value_t series_set_elt_value_t; \
00105 typedef typename graph_t::letter_t letter_t; \
00106 typedef typename graph_t::tag_t tag_t; \
00107 typedef typename graph_t::geometry_t geometry_t; \
00108 typedef typename graph_t::label_t label_t; \
00109 typedef typename graph_t::states_t states_t; \
00110 typedef typename states_t::iterator state_iterator; \
00111 typedef typename graph_t::hstate_t hstate_t; \
00112 typedef typename graph_t::edges_t transitions_t; \
00113 typedef typename transitions_t::iterator transition_iterator; \
00114 typedef typename graph_t::htransition_t htransition_t; \
00115 typedef typename graph_t::initial_t initial_t; \
00116 typedef typename graph_t::initial_support_t initial_support_t; \
00117 typedef typename initial_support_t::iterator initial_iterator; \
00118 typedef typename graph_t::final_t final_t; \
00119 typedef typename graph_t::final_support_t final_support_t; \
00120 typedef typename final_support_t::iterator final_iterator; \
00121 typedef typename graph_t::delta_state_iterator delta_state_iterator; \
00122 typedef typename graph_t::delta_transition_iterator delta_transition_iterator; \
00123 typedef typename graph_t::rdelta_state_iterator rdelta_state_iterator; \
00124 typedef typename graph_t::rdelta_transition_iterator rdelta_transition_iterator; \
00125 }
00126
00127
00128
00129
00130
00131
00132
00133 template <class S>
00134 struct virtual_types<AutomataBase<S> >
00135 : virtual_types<Structure<S> >
00136 { };
00137
00138
00139
00140
00141 template <class S>
00142 struct dynamic_traits<AutomataBase<S> >
00143 : dynamic_traits<Structure<S> >
00144 { };
00145
00146
00147
00148
00150
00163
00164 template <typename Self, typename T>
00165 struct MetaElement<AutomataBase<Self>, T>
00166 : MetaElement<Structure<Self>, T>
00167 {
00169 typedef MetaElement<AutomataBase<Self>, T> self_t;
00170
00172 typedef typename AutomataBase<Self>::series_set_t series_set_t;
00173
00175 typedef typename automaton_traits<T>::series_set_elt_value_t
00176 series_set_elt_value_t;
00177
00179 typedef Element<series_set_t, series_set_elt_value_t> series_set_elt_t;
00180
00182 typedef typename series_set_t::monoid_t monoid_t;
00183
00185 typedef typename series_set_elt_t::monoid_elt_t monoid_elt_t;
00186
00188 typedef typename monoid_elt_t::value_t monoid_elt_value_t;
00189
00191 typedef typename monoid_t::letter_t letter_t;
00192
00194 typedef typename series_set_t::semiring_t semiring_t;
00195
00197 typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t;
00198
00200 typedef typename series_set_elt_t::semiring_elt_value_t
00201 semiring_elt_value_t;
00202
00204 typedef typename automaton_traits<T>::tag_t tag_t;
00205
00207 typedef typename automaton_traits<T>::label_t label_t;
00208
00210 typedef typename automaton_traits<T>::states_t states_t;
00211
00213 typedef typename automaton_traits<T>::state_iterator state_iterator;
00214
00216 typedef typename automaton_traits<T>::transitions_t transitions_t;
00217
00219 typedef typename automaton_traits<T>::transition_iterator transition_iterator;
00220
00222 typedef typename automaton_traits<T>::initial_support_t initial_support_t;
00223
00225 typedef typename automaton_traits<T>::initial_iterator initial_iterator;
00226
00228 typedef typename automaton_traits<T>::final_support_t final_support_t;
00229
00231 typedef typename automaton_traits<T>::final_iterator final_iterator;
00232
00234 typedef typename automaton_traits<T>::geometry_t geometry_t;
00235
00237 typedef typename automaton_traits<T>::geometry_t::coords_t geometry_coords_t;
00238
00240 typedef typename automaton_traits<T>::hstate_t hstate_t;
00241 typedef typename automaton_traits<T>::htransition_t htransition_t;
00242
00244 typedef typename automaton_traits<T>::delta_state_iterator delta_state_iterator;
00245 typedef typename automaton_traits<T>::delta_transition_iterator delta_transition_iterator;
00246 typedef typename automaton_traits<T>::rdelta_state_iterator rdelta_state_iterator;
00247 typedef typename automaton_traits<T>::rdelta_transition_iterator rdelta_transition_iterator;
00248
00250 const series_set_t& series() const;
00251
00253 tag_t& tag();
00254
00256 const tag_t& tag() const;
00257
00259 geometry_t& geometry();
00260
00262 const geometry_t& geometry() const;
00263
00265 bool exists() const;
00266
00268 states_t states() const;
00269
00271 transitions_t transitions() const;
00272
00274 initial_support_t initial() const;
00275
00277 final_support_t final() const;
00278
00281 bool is_initial(const hstate_t& state) const;
00282 bool is_initial(unsigned state) const;
00283
00285 bool is_final(const hstate_t& state) const;
00286 bool is_final(unsigned state) const;
00287
00289 void set_initial(const hstate_t& state);
00290 void set_initial(unsigned state);
00291
00293 void set_initial(const hstate_t& state, const series_set_elt_t& m);
00294 void set_initial(unsigned state, const series_set_elt_t& m);
00295
00297 void set_final(const hstate_t& state);
00298 void set_final(unsigned state);
00299
00301 void set_final(const hstate_t& state, const series_set_elt_t& m);
00302 void set_final(unsigned state, const series_set_elt_t& m);
00303
00305 void unset_initial(const hstate_t& state);
00306 void unset_initial(unsigned state);
00307
00309 void unset_final(const hstate_t& state);
00310 void unset_final(unsigned state);
00311
00313 void clear_initial();
00314
00316 void clear_final();
00317
00319 Element<series_set_t, series_set_elt_value_t>
00320 get_initial(const hstate_t& state) const;
00321 Element<series_set_t, series_set_elt_value_t>
00322 get_initial(unsigned state) const;
00323
00325 Element<series_set_t, series_set_elt_value_t>
00326 get_final(const hstate_t& state) const;
00327 Element<series_set_t, series_set_elt_value_t>
00328 get_final(unsigned state) const;
00329
00331 hstate_t add_state();
00332
00334 hstate_t get_state(unsigned state) const;
00335
00338 hstate_t choose_state() const;
00339
00341 htransition_t add_transition(const hstate_t& src, const hstate_t& dst,
00342 const label_t& label);
00343 htransition_t add_transition(unsigned src, unsigned dst,
00344 const label_t& label);
00345
00348 htransition_t add_weighted_transition(const hstate_t& src, const hstate_t& dst,
00349 const semiring_elt_t& w,
00350 const monoid_elt_value_t& m);
00351 htransition_t add_weighted_transition(unsigned src, unsigned dst,
00352 const semiring_elt_t& w,
00353 const monoid_elt_value_t& m);
00354
00356
00359 htransition_t add_series_transition(const hstate_t& src, const hstate_t& dst,
00360 const series_set_elt_t& e);
00361 htransition_t add_series_transition(unsigned src, unsigned dst,
00362 const series_set_elt_t& e);
00363
00365 htransition_t add_spontaneous(const hstate_t& src, const hstate_t& dst,
00366 const semiring_elt_t& w);
00367
00368 htransition_t add_spontaneous(const hstate_t& src, const hstate_t& dst);
00369
00370 htransition_t add_spontaneous(unsigned src, unsigned dst,
00371 const semiring_elt_t& w);
00372
00373 htransition_t add_spontaneous(unsigned src, unsigned dst);
00374
00376 htransition_t add_letter_transition(const hstate_t& src, const hstate_t& dst,
00377 const letter_t& l);
00378 htransition_t add_letter_transition(unsigned src, unsigned dst,
00379 const letter_t& l);
00380
00383 htransition_t add_letter_transition(const hstate_t& src, const hstate_t& dst,
00384 const std::string& l);
00385 htransition_t add_letter_transition(unsigned src, unsigned dst,
00386 const std::string& l);
00387
00389 void update(const htransition_t& e, const label_t& l);
00390
00392 void del_state(const hstate_t& state);
00393 void del_state(unsigned state);
00394
00396 void del_transition(const htransition_t& e);
00397
00399 bool has_state(const hstate_t& state) const;
00400 bool has_state(unsigned state) const;
00401
00403 bool has_transition(const htransition_t& e) const;
00404
00406 hstate_t src_of(const htransition_t& e) const;
00407
00409 hstate_t dst_of(const htransition_t& e) const;
00410
00412 typename automaton_traits<T>::label_t label_of(const htransition_t& e) const;
00413
00415 series_set_elt_t series_of(const htransition_t& e) const;
00416
00418 series_set_elt_value_t series_value_of(const htransition_t& e) const;
00419
00421 bool is_spontaneous(const htransition_t& e) const;
00422
00424 monoid_elt_t word_of(const htransition_t& e) const;
00425
00427 semiring_elt_t weight_of(const htransition_t& e) const;
00428
00430 monoid_elt_value_t word_value_of(const htransition_t& e) const;
00431
00433
00436 letter_t letter_of(const htransition_t& e) const;
00437
00438
00439
00440
00441
00444 template <typename OutputIterator, typename Kind>
00445 void delta(OutputIterator res,
00446 const hstate_t& src,
00447 delta_kind::kind<Kind> k) const;
00448 template <typename OutputIterator, typename Kind>
00449 void delta(OutputIterator res,
00450 unsigned src,
00451 delta_kind::kind<Kind> k) const;
00452
00453
00454
00457 template <typename OutputIterator, typename L, typename Kind>
00458 void delta(OutputIterator res,
00459 const hstate_t& src,
00460 const L& query,
00461 delta_kind::kind<Kind> k) const;
00462 template <typename OutputIterator, typename L, typename Kind>
00463 void delta(OutputIterator res,
00464 unsigned src,
00465 const L& query,
00466 delta_kind::kind<Kind> k) const;
00467
00470 template <typename OutputIterator, typename L, typename Kind>
00471 void letter_delta(OutputIterator res,
00472 const hstate_t& src,
00473 const L& letter,
00474 delta_kind::kind<Kind> k) const;
00475 template <typename OutputIterator, typename L, typename Kind>
00476 void letter_delta(OutputIterator res,
00477 unsigned src,
00478 const L& letter,
00479 delta_kind::kind<Kind> k) const;
00480
00483 template <typename OutputIterator, typename Kind>
00484 void spontaneous_delta(OutputIterator res,
00485 const hstate_t& src,
00486 delta_kind::kind<Kind> k) const;
00487 template <typename OutputIterator, typename Kind>
00488 void spontaneous_delta(OutputIterator res,
00489 unsigned src,
00490 delta_kind::kind<Kind> k) const;
00491
00492
00493
00494
00495
00498 template <typename Container, typename Kind>
00499 void deltac(Container& res, const hstate_t& src, delta_kind::kind<Kind> k) const;
00500 template <typename Container, typename Kind>
00501 void deltac(Container& res, unsigned src, delta_kind::kind<Kind> k) const;
00502
00506 template <typename Container, typename L, typename Kind>
00507 void deltac(Container& res,
00508 const hstate_t& src,
00509 const L& query,
00510 delta_kind::kind<Kind> k) const;
00511 template <typename Container, typename L, typename Kind>
00512 void deltac(Container& res,
00513 unsigned src,
00514 const L& query,
00515 delta_kind::kind<Kind> k) const;
00516
00519 template <typename Container, typename L, typename Kind>
00520 void letter_deltac(Container& res,
00521 const hstate_t& src,
00522 const L& letter,
00523 delta_kind::kind<Kind> k) const;
00524 template <typename Container, typename L, typename Kind>
00525 void letter_deltac(Container& res,
00526 unsigned src,
00527 const L& letter,
00528 delta_kind::kind<Kind> k) const;
00529
00532 template <typename Container, typename Kind>
00533 void spontaneous_deltac(Container& res,
00534 const hstate_t& src,
00535 delta_kind::kind<Kind> k) const;
00536 template <typename Container, typename Kind>
00537 void spontaneous_deltac(Container& res,
00538 unsigned src,
00539 delta_kind::kind<Kind> k) const;
00540
00541
00542
00543
00544
00545
00549 template <typename Functor, typename Kind>
00550 void deltaf(Functor& fun, const hstate_t& src, delta_kind::kind<Kind> k) const;
00551 template <typename Functor, typename Kind>
00552 void deltaf(Functor& fun, unsigned src, delta_kind::kind<Kind> k) const;
00553
00557 template <typename Functor, typename L, typename Kind>
00558 void deltaf(Functor& fun,
00559 const hstate_t& src,
00560 const L& query,
00561 delta_kind::kind<Kind> k) const;
00562 template <typename Functor, typename L, typename Kind>
00563 void deltaf(Functor& fun,
00564 unsigned src,
00565 const L& query,
00566 delta_kind::kind<Kind> k) const;
00567
00572 template <typename Functor, typename L, typename Kind>
00573 void letter_deltaf(Functor& fun,
00574 const hstate_t& src,
00575 const L& letter,
00576 delta_kind::kind<Kind> k) const;
00577 template <typename Functor, typename L, typename Kind>
00578 void letter_deltaf(Functor& fun,
00579 unsigned src,
00580 const L& letter,
00581 delta_kind::kind<Kind> k) const;
00582
00587 template <typename Functor, typename Kind>
00588 void spontaneous_deltaf(Functor& fun,
00589 const hstate_t& src,
00590 delta_kind::kind<Kind> k) const;
00591 template <typename Functor, typename Kind>
00592 void spontaneous_deltaf(Functor& fun,
00593 unsigned src,
00594 delta_kind::kind<Kind> k) const;
00595
00596
00597
00598
00599
00600
00603 template <typename OutputIterator, typename Kind>
00604 void rdelta(OutputIterator res,
00605 const hstate_t& src,
00606 delta_kind::kind<Kind> k) const;
00607 template <typename OutputIterator, typename Kind>
00608 void rdelta(OutputIterator res,
00609 unsigned src,
00610 delta_kind::kind<Kind> k) const;
00611
00614 template <typename OutputIterator, typename L, typename Kind>
00615 void rdelta(OutputIterator res,
00616 const hstate_t& src,
00617 const L& query,
00618 delta_kind::kind<Kind> k) const;
00619 template <typename OutputIterator, typename L, typename Kind>
00620 void rdelta(OutputIterator res,
00621 unsigned src,
00622 const L& query,
00623 delta_kind::kind<Kind> k) const;
00624
00627 template <typename OutputIterator, typename L, typename Kind>
00628 void letter_rdelta(OutputIterator res,
00629 const hstate_t& src,
00630 const L& letter,
00631 delta_kind::kind<Kind> k) const;
00632 template <typename OutputIterator, typename L, typename Kind>
00633 void letter_rdelta(OutputIterator res,
00634 unsigned src,
00635 const L& letter,
00636 delta_kind::kind<Kind> k) const;
00637
00640 template <typename OutputIterator, typename Kind>
00641 void spontaneous_rdelta(OutputIterator res,
00642 const hstate_t& src,
00643 delta_kind::kind<Kind> k) const;
00644 template <typename OutputIterator, typename Kind>
00645 void spontaneous_rdelta(OutputIterator res,
00646 unsigned src,
00647 delta_kind::kind<Kind> k) const;
00648
00649
00650
00651
00652
00655 template <typename Container, typename Kind>
00656 void rdeltac(Container& res, const hstate_t& src, delta_kind::kind<Kind> k) const;
00657 template <typename Container, typename Kind>
00658 void rdeltac(Container& res, unsigned src, delta_kind::kind<Kind> k) const;
00659
00663 template <typename Container, typename L, typename Kind>
00664 void rdeltac(Container& res,
00665 const hstate_t& src,
00666 const L& query,
00667 delta_kind::kind<Kind> k) const;
00668 template <typename Container, typename L, typename Kind>
00669 void rdeltac(Container& res,
00670 unsigned src,
00671 const L& query,
00672 delta_kind::kind<Kind> k) const;
00673
00676 template <typename Container, typename L, typename Kind>
00677 void letter_rdeltac(Container& res,
00678 const hstate_t& src,
00679 const L& letter,
00680 delta_kind::kind<Kind> k) const;
00681 template <typename Container, typename L, typename Kind>
00682 void letter_rdeltac(Container& res,
00683 unsigned src,
00684 const L& letter,
00685 delta_kind::kind<Kind> k) const;
00686
00689 template <typename Container, typename Kind>
00690 void spontaneous_rdeltac(Container& res,
00691 const hstate_t& src,
00692 delta_kind::kind<Kind> k) const;
00693 template <typename Container, typename Kind>
00694 void spontaneous_rdeltac(Container& res,
00695 unsigned src,
00696 delta_kind::kind<Kind> k) const;
00697
00698
00699
00700
00701
00702
00705 template <typename Functor, typename Kind>
00706 void rdeltaf(Functor& fun, const hstate_t& src, delta_kind::kind<Kind> k) const;
00707 template <typename Functor, typename Kind>
00708 void rdeltaf(Functor& fun, unsigned src, delta_kind::kind<Kind> k) const;
00709
00712 template <typename Functor, typename L, typename Kind>
00713 void rdeltaf(Functor& fun,
00714 const hstate_t& src,
00715 const L& query,
00716 delta_kind::kind<Kind> k) const;
00717 template <typename Functor, typename L, typename Kind>
00718 void rdeltaf(Functor& fun,
00719 unsigned src,
00720 const L& query,
00721 delta_kind::kind<Kind> k) const;
00722
00725 template <typename Functor, typename L, typename Kind>
00726 void letter_rdeltaf(Functor& fun,
00727 const hstate_t& src,
00728 const L& letter,
00729 delta_kind::kind<Kind> k) const;
00730 template <typename Functor, typename L, typename Kind>
00731 void letter_rdeltaf(Functor& fun,
00732 unsigned src,
00733 const L& letter,
00734 delta_kind::kind<Kind> k) const;
00735
00738 template <typename Functor, typename Kind>
00739 void spontaneous_rdeltaf(Functor& fun,
00740 const hstate_t& src,
00741 delta_kind::kind<Kind> k) const;
00742 template <typename Functor, typename Kind>
00743 void spontaneous_rdeltaf(Functor& fun,
00744 unsigned src,
00745 delta_kind::kind<Kind> k) const;
00746 protected:
00747 MetaElement();
00748 MetaElement(const MetaElement& other);
00749 };
00750
00753
00754 template <typename S, typename St, typename T>
00755 St& op_rout(const AutomataBase<S>& s, St& st, const T& r);
00756
00757 }
00758
00759 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00760 # include <vaucanson/automata/concept/automata_base.hxx>
00761 # endif // VCSN_USE_INTERFACE_ONLY
00762
00763 #endif // ! VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH