Vaucanson: automata_base.hh Source File

00001 // automata_base.hh: this file is part of the Vaucanson project.
00002 //
00003 // Vaucanson, a generic library for finite state machines.
00004 //
00005 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 The Vaucanson Group.
00006 //
00007 // This program is free software; you can redistribute it and/or
00008 // modify it under the terms of the GNU General Public License
00009 // as published by the Free Software Foundation; either version 2
00010 // of the License, or (at your option) any later version.
00011 //
00012 // The complete GNU General Public Licence Notice can be found as the
00013 // `COPYING' file in the root directory.
00014 //
00015 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
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   | AutomataBase<Self> |
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   // traits for automaton implementation.
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   | virtual_types<AutomataBase<Self> > |
00132   `-----------------------------------*/
00133   template <class S>
00134   struct virtual_types<AutomataBase<S> >
00135     : virtual_types<Structure<S> >
00136   { };
00137 
00138   /*------------------------------------.
00139   | dynamic_traits<AutomataBase<Self> > |
00140   `------------------------------------*/
00141   template <class S>
00142   struct dynamic_traits<AutomataBase<S> >
00143     : dynamic_traits<Structure<S> >
00144   { };
00145 
00146   /*-----------------------------------.
00147   | MetaElement<AutomataBase<Self>, T> |
00148   `-----------------------------------*/
00150 
00163   // FIXME: Use some of the TYPEDEF_IMPORT macros.
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       | Deltas.  |
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       | Deltacs.  |
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       | Deltafs.  |
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       | Reverse deltas.  |
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       | Reverse deltacs.  |
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       | Reverse deltafs.  |
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 } // vcsn
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