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 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   };
00083 
00084 # define VCSN_MAKE_AUTOMATON_TRAITS(Type)                                       \
00085   template <typename Kind,                                                      \
00086             typename WordValue,                                                 \
00087             typename WeightValue,                                               \
00088             typename SeriesValue,                                               \
00089             typename Letter,                                                    \
00090             typename Tag,                                                       \
00091             typename GeometryCoords>                                            \
00092   struct automaton_traits<Type<Kind, WordValue, WeightValue, SeriesValue,       \
00093                           Letter, Tag, GeometryCoords> >                        \
00094   {                                                                             \
00095     typedef Type<Kind, WordValue, WeightValue, SeriesValue,                     \
00096                  Letter, Tag, GeometryCoords>           graph_t;                \
00097     typedef typename graph_t::semiring_elt_value_t      semiring_elt_value_t;   \
00098     typedef typename graph_t::monoid_elt_value_t        monoid_elt_value_t;     \
00099     typedef typename graph_t::word_value_t              word_value_t;           \
00100     typedef typename graph_t::series_set_elt_value_t    series_set_elt_value_t; \
00101     typedef typename graph_t::letter_t                  letter_t;               \
00102     typedef typename graph_t::tag_t                     tag_t;                  \
00103     typedef typename graph_t::geometry_t                geometry_t;             \
00104     typedef typename graph_t::label_t                   label_t;                \
00105     typedef typename graph_t::states_t                  states_t;               \
00106     typedef typename states_t::iterator                 state_iterator;         \
00107     typedef typename graph_t::hstate_t                  hstate_t;               \
00108     typedef typename graph_t::edges_t                   transitions_t;          \
00109     typedef typename transitions_t::iterator            transition_iterator;    \
00110     typedef typename graph_t::htransition_t             htransition_t;          \
00111     typedef typename graph_t::initial_t                 initial_t;              \
00112     typedef typename graph_t::initial_support_t         initial_support_t;      \
00113     typedef typename initial_support_t::iterator        initial_iterator;       \
00114     typedef typename graph_t::final_t                   final_t;                \
00115     typedef typename graph_t::final_support_t           final_support_t;        \
00116     typedef typename final_support_t::iterator          final_iterator;         \
00117   }
00118 
00119 
00120 
00121 
00122   /*-----------------------------------.
00123   | virtual_types<AutomataBase<Self> > |
00124   `-----------------------------------*/
00125   template <class S>
00126   struct virtual_types<AutomataBase<S> >
00127     : virtual_types<Structure<S> >
00128   { };
00129 
00130   /*------------------------------------.
00131   | dynamic_traits<AutomataBase<Self> > |
00132   `------------------------------------*/
00133   template <class S>
00134   struct dynamic_traits<AutomataBase<S> >
00135     : dynamic_traits<Structure<S> >
00136   { };
00137 
00138   /*-----------------------------------.
00139   | MetaElement<AutomataBase<Self>, T> |
00140   `-----------------------------------*/
00142 
00155   // FIXME: Use some of the TYPEDEF_IMPORT macros.
00156   template <typename Self, typename T>
00157   struct MetaElement<AutomataBase<Self>, T>
00158     : MetaElement<Structure<Self>, T>
00159   {
00161       typedef MetaElement<AutomataBase<Self>, T>        self_t;
00162 
00164       typedef typename AutomataBase<Self>::series_set_t series_set_t;
00165 
00167       typedef typename automaton_traits<T>::series_set_elt_value_t
00168       series_set_elt_value_t;
00169 
00171       typedef Element<series_set_t, series_set_elt_value_t> series_set_elt_t;
00172 
00174       typedef typename series_set_t::monoid_t           monoid_t;
00175 
00177       typedef typename series_set_elt_t::monoid_elt_t   monoid_elt_t;
00178 
00180       typedef typename monoid_elt_t::value_t            monoid_elt_value_t;
00181 
00183       typedef typename monoid_t::letter_t               letter_t;
00184 
00186       typedef typename series_set_t::semiring_t         semiring_t;
00187 
00189       typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t;
00190 
00192       typedef typename series_set_elt_t::semiring_elt_value_t
00193       semiring_elt_value_t;
00194 
00196       typedef typename automaton_traits<T>::tag_t               tag_t;
00197 
00199       typedef typename automaton_traits<T>::label_t     label_t;
00200 
00202       typedef typename automaton_traits<T>::states_t    states_t;
00203 
00205       typedef typename automaton_traits<T>::state_iterator state_iterator;
00206 
00208       typedef typename automaton_traits<T>::transitions_t transitions_t;
00209 
00211       typedef typename automaton_traits<T>::transition_iterator transition_iterator;
00212 
00214       typedef typename automaton_traits<T>::initial_support_t initial_support_t;
00215 
00217       typedef typename automaton_traits<T>::initial_iterator initial_iterator;
00218 
00220       typedef typename automaton_traits<T>::final_support_t final_support_t;
00221 
00223       typedef typename automaton_traits<T>::final_iterator final_iterator;
00224 
00226       typedef typename automaton_traits<T>::geometry_t  geometry_t;
00227 
00229       typedef typename automaton_traits<T>::geometry_t::coords_t geometry_coords_t;
00230 
00232       typedef typename automaton_traits<T>::hstate_t hstate_t;
00233       typedef typename automaton_traits<T>::htransition_t htransition_t;
00234 
00236       const series_set_t& series() const;
00237 
00239       tag_t& tag();
00240 
00242       const tag_t& tag() const;
00243 
00245       geometry_t& geometry();
00246 
00248       const geometry_t& geometry() const;
00249 
00251       bool exists() const;
00252 
00254       states_t states() const;
00255 
00257       transitions_t transitions() const;
00258 
00260       initial_support_t initial() const;
00261 
00263       final_support_t final() const;
00264 
00267       bool is_initial(const hstate_t& state) const;
00268       bool is_initial(unsigned state) const;
00269 
00271       bool is_final(const hstate_t& state) const;
00272       bool is_final(unsigned state) const;
00273 
00275       void set_initial(const hstate_t& state);
00276       void set_initial(unsigned state);
00277 
00279       void set_initial(const hstate_t& state, const series_set_elt_t& m);
00280       void set_initial(unsigned state, const series_set_elt_t& m);
00281 
00283       void set_final(const hstate_t& state);
00284       void set_final(unsigned state);
00285 
00287       void set_final(const hstate_t& state, const series_set_elt_t& m);
00288       void set_final(unsigned state, const series_set_elt_t& m);
00289 
00291       void unset_initial(const hstate_t& state);
00292       void unset_initial(unsigned state);
00293 
00295       void unset_final(const hstate_t& state);
00296       void unset_final(unsigned state);
00297 
00299       void clear_initial();
00300 
00302       void clear_final();
00303 
00305       Element<series_set_t, series_set_elt_value_t>
00306       get_initial(const hstate_t& state) const;
00307       Element<series_set_t, series_set_elt_value_t>
00308       get_initial(unsigned state) const;
00309 
00311       Element<series_set_t, series_set_elt_value_t>
00312       get_final(const hstate_t& state) const;
00313       Element<series_set_t, series_set_elt_value_t>
00314       get_final(unsigned state) const;
00315 
00317       hstate_t add_state();
00318 
00320       hstate_t get_state(unsigned state) const;
00321 
00324       hstate_t choose_state() const;
00325 
00327       htransition_t add_transition(const hstate_t& src, const hstate_t& dst,
00328                                    const label_t& label);
00329       htransition_t add_transition(unsigned src, unsigned dst,
00330                                    const label_t& label);
00331 
00334       htransition_t add_weighted_transition(const hstate_t& src, const hstate_t& dst,
00335                                             const semiring_elt_t& w,
00336                                             const monoid_elt_value_t& m);
00337       htransition_t add_weighted_transition(unsigned src, unsigned dst,
00338                                             const semiring_elt_t& w,
00339                                             const monoid_elt_value_t& m);
00340 
00342 
00345       htransition_t add_series_transition(const hstate_t& src, const hstate_t& dst,
00346                                           const series_set_elt_t& e);
00347       htransition_t add_series_transition(unsigned src, unsigned dst,
00348                                           const series_set_elt_t& e);
00349 
00351       htransition_t add_spontaneous(const hstate_t& src, const hstate_t& dst,
00352                                     const semiring_elt_t& w);
00353 
00354       htransition_t add_spontaneous(const hstate_t& src, const hstate_t& dst);
00355 
00356       htransition_t add_spontaneous(unsigned src, unsigned dst,
00357                                     const semiring_elt_t& w);
00358 
00359       htransition_t add_spontaneous(unsigned src, unsigned dst);
00360 
00362       htransition_t add_letter_transition(const hstate_t& src, const hstate_t& dst,
00363                                           const letter_t& l);
00364       htransition_t add_letter_transition(unsigned src, unsigned dst,
00365                                           const letter_t& l);
00366 
00368       void update(const htransition_t& e, const label_t& l);
00369 
00371       void del_state(const hstate_t& state);
00372       void del_state(unsigned state);
00373 
00375       void del_transition(const htransition_t& e);
00376 
00378       bool has_state(const hstate_t& state) const;
00379       bool has_state(unsigned state) const;
00380 
00382       bool has_transition(const htransition_t& e) const;
00383 
00385       hstate_t src_of(const htransition_t& e) const;
00386 
00388       hstate_t dst_of(const htransition_t& e) const;
00389 
00391       typename automaton_traits<T>::label_t label_of(const htransition_t& e) const;
00392 
00394       series_set_elt_t series_of(const htransition_t& e) const;
00395 
00397       series_set_elt_value_t series_value_of(const htransition_t& e) const;
00398 
00400       bool is_spontaneous(const htransition_t& e) const;
00401 
00403       monoid_elt_t word_of(const htransition_t& e) const;
00404 
00406       semiring_elt_t weight_of(const htransition_t& e) const;
00407 
00409       monoid_elt_value_t word_value_of(const htransition_t& e) const;
00410 
00412 
00415       letter_t letter_of(const htransition_t& e) const;
00416 
00417       /*---------.
00418       | Deltas.  |
00419       `---------*/
00420 
00423       template <typename OutputIterator, typename Kind>
00424       void delta(OutputIterator res,
00425                  const hstate_t& src,
00426                  delta_kind::kind<Kind> k) const;
00427       template <typename OutputIterator, typename Kind>
00428       void delta(OutputIterator res,
00429                  unsigned src,
00430                  delta_kind::kind<Kind> k) const;
00431 
00432 
00433 
00436       template <typename OutputIterator, typename L, typename Kind>
00437       void delta(OutputIterator res,
00438                  const hstate_t& src,
00439                  const L& query,
00440                  delta_kind::kind<Kind> k) const;
00441       template <typename OutputIterator, typename L, typename Kind>
00442       void delta(OutputIterator res,
00443                  unsigned src,
00444                  const L& query,
00445                  delta_kind::kind<Kind> k) const;
00446 
00449       template <typename OutputIterator, typename L, typename Kind>
00450       void letter_delta(OutputIterator res,
00451                         const hstate_t& src,
00452                         const L& letter,
00453                         delta_kind::kind<Kind> k) const;
00454       template <typename OutputIterator, typename L, typename Kind>
00455       void letter_delta(OutputIterator res,
00456                         unsigned src,
00457                         const L& letter,
00458                         delta_kind::kind<Kind> k) const;
00459 
00462       template <typename OutputIterator, typename Kind>
00463       void spontaneous_delta(OutputIterator res,
00464                              const hstate_t& src,
00465                              delta_kind::kind<Kind> k) const;
00466       template <typename OutputIterator, typename Kind>
00467       void spontaneous_delta(OutputIterator res,
00468                              unsigned src,
00469                              delta_kind::kind<Kind> k) const;
00470 
00471       /*----------.
00472       | Deltacs.  |
00473       `----------*/
00474 
00477       template <typename Container, typename Kind>
00478       void deltac(Container& res, const hstate_t& src, delta_kind::kind<Kind> k) const;
00479       template <typename Container, typename Kind>
00480       void deltac(Container& res, unsigned src, delta_kind::kind<Kind> k) const;
00481 
00485       template <typename Container, typename L, typename Kind>
00486       void deltac(Container& res,
00487                   const hstate_t& src,
00488                   const L& query,
00489                   delta_kind::kind<Kind> k) const;
00490       template <typename Container, typename L, typename Kind>
00491       void deltac(Container& res,
00492                   unsigned src,
00493                   const L& query,
00494                   delta_kind::kind<Kind> k) const;
00495 
00498       template <typename Container, typename L, typename Kind>
00499       void letter_deltac(Container& res,
00500                          const hstate_t& src,
00501                          const L& letter,
00502                          delta_kind::kind<Kind> k) const;
00503       template <typename Container, typename L, typename Kind>
00504       void letter_deltac(Container& res,
00505                          unsigned src,
00506                          const L& letter,
00507                          delta_kind::kind<Kind> k) const;
00508 
00511       template <typename Container, typename Kind>
00512       void spontaneous_deltac(Container& res,
00513                               const hstate_t& src,
00514                               delta_kind::kind<Kind> k) const;
00515       template <typename Container, typename Kind>
00516       void spontaneous_deltac(Container& res,
00517                               unsigned src,
00518                               delta_kind::kind<Kind> k) const;
00519 
00520 
00521       /*----------.
00522       | Deltafs.  |
00523       `----------*/
00524 
00528       template <typename Functor, typename Kind>
00529       void deltaf(Functor& fun, const hstate_t& src, delta_kind::kind<Kind> k) const;
00530       template <typename Functor, typename Kind>
00531       void deltaf(Functor& fun, unsigned src, delta_kind::kind<Kind> k) const;
00532 
00536       template <typename Functor, typename L, typename Kind>
00537       void deltaf(Functor& fun,
00538                   const hstate_t& src,
00539                   const L& query,
00540                   delta_kind::kind<Kind> k) const;
00541       template <typename Functor, typename L, typename Kind>
00542       void deltaf(Functor& fun,
00543                   unsigned src,
00544                   const L& query,
00545                   delta_kind::kind<Kind> k) const;
00546 
00551       template <typename Functor, typename L, typename Kind>
00552       void letter_deltaf(Functor& fun,
00553                          const hstate_t& src,
00554                          const L& letter,
00555                          delta_kind::kind<Kind> k) const;
00556       template <typename Functor, typename L, typename Kind>
00557       void letter_deltaf(Functor& fun,
00558                          unsigned src,
00559                          const L& letter,
00560                          delta_kind::kind<Kind> k) const;
00561 
00566       template <typename Functor, typename Kind>
00567       void spontaneous_deltaf(Functor& fun,
00568                               const hstate_t& src,
00569                               delta_kind::kind<Kind> k) const;
00570       template <typename Functor, typename Kind>
00571       void spontaneous_deltaf(Functor& fun,
00572                               unsigned src,
00573                               delta_kind::kind<Kind> k) const;
00574 
00575       /*-----------------.
00576       | Reverse deltas.  |
00577       `-----------------*/
00578 
00581       template <typename OutputIterator, typename Kind>
00582       void rdelta(OutputIterator res,
00583                   const hstate_t& src,
00584                   delta_kind::kind<Kind> k) const;
00585       template <typename OutputIterator, typename Kind>
00586       void rdelta(OutputIterator res,
00587                   unsigned src,
00588                   delta_kind::kind<Kind> k) const;
00589 
00592       template <typename OutputIterator, typename L, typename Kind>
00593       void rdelta(OutputIterator res,
00594                   const hstate_t& src,
00595                   const L& query,
00596                   delta_kind::kind<Kind> k) const;
00597       template <typename OutputIterator, typename L, typename Kind>
00598       void rdelta(OutputIterator res,
00599                   unsigned src,
00600                   const L& query,
00601                   delta_kind::kind<Kind> k) const;
00602 
00605       template <typename OutputIterator, typename L, typename Kind>
00606       void letter_rdelta(OutputIterator res,
00607                          const hstate_t& src,
00608                          const L& letter,
00609                          delta_kind::kind<Kind> k) const;
00610       template <typename OutputIterator, typename L, typename Kind>
00611       void letter_rdelta(OutputIterator res,
00612                          unsigned src,
00613                          const L& letter,
00614                          delta_kind::kind<Kind> k) const;
00615 
00618       template <typename OutputIterator, typename Kind>
00619       void spontaneous_rdelta(OutputIterator res,
00620                               const hstate_t& src,
00621                               delta_kind::kind<Kind> k) const;
00622       template <typename OutputIterator, typename Kind>
00623       void spontaneous_rdelta(OutputIterator res,
00624                               unsigned src,
00625                               delta_kind::kind<Kind> k) const;
00626 
00627       /*------------------.
00628       | Reverse deltacs.  |
00629       `------------------*/
00630 
00633       template <typename Container, typename Kind>
00634       void rdeltac(Container& res, const hstate_t& src, delta_kind::kind<Kind> k) const;
00635       template <typename Container, typename Kind>
00636       void rdeltac(Container& res, unsigned src, delta_kind::kind<Kind> k) const;
00637 
00641       template <typename Container, typename L, typename Kind>
00642       void rdeltac(Container& res,
00643                    const hstate_t& src,
00644                    const L& query,
00645                    delta_kind::kind<Kind> k) const;
00646       template <typename Container, typename L, typename Kind>
00647       void rdeltac(Container& res,
00648                   unsigned src,
00649                   const L& query,
00650                   delta_kind::kind<Kind> k) const;
00651 
00654       template <typename Container, typename L, typename Kind>
00655       void letter_rdeltac(Container& res,
00656                           const hstate_t& src,
00657                           const L& letter,
00658                           delta_kind::kind<Kind> k) const;
00659       template <typename Container, typename L, typename Kind>
00660       void letter_rdeltac(Container& res,
00661                           unsigned src,
00662                           const L& letter,
00663                           delta_kind::kind<Kind> k) const;
00664 
00667       template <typename Container, typename Kind>
00668       void spontaneous_rdeltac(Container& res,
00669                                const hstate_t& src,
00670                                delta_kind::kind<Kind> k) const;
00671       template <typename Container, typename Kind>
00672       void spontaneous_rdeltac(Container& res,
00673                                unsigned src,
00674                                delta_kind::kind<Kind> k) const;
00675 
00676 
00677       /*------------------.
00678       | Reverse deltafs.  |
00679       `------------------*/
00680 
00683       template <typename Functor, typename Kind>
00684       void rdeltaf(Functor& fun, const hstate_t& src, delta_kind::kind<Kind> k) const;
00685       template <typename Functor, typename Kind>
00686       void rdeltaf(Functor& fun, unsigned src, delta_kind::kind<Kind> k) const;
00687 
00690       template <typename Functor, typename L, typename Kind>
00691       void rdeltaf(Functor& fun,
00692                    const hstate_t& src,
00693                    const L& query,
00694                    delta_kind::kind<Kind> k) const;
00695       template <typename Functor, typename L, typename Kind>
00696       void rdeltaf(Functor& fun,
00697                    unsigned src,
00698                    const L& query,
00699                    delta_kind::kind<Kind> k) const;
00700 
00703       template <typename Functor, typename L, typename Kind>
00704       void letter_rdeltaf(Functor& fun,
00705                           const hstate_t& src,
00706                           const L& letter,
00707                           delta_kind::kind<Kind> k) const;
00708       template <typename Functor, typename L, typename Kind>
00709       void letter_rdeltaf(Functor& fun,
00710                           unsigned src,
00711                           const L& letter,
00712                           delta_kind::kind<Kind> k) const;
00713 
00716       template <typename Functor, typename Kind>
00717       void spontaneous_rdeltaf(Functor& fun,
00718                                const hstate_t& src,
00719                                delta_kind::kind<Kind> k) const;
00720       template <typename Functor, typename Kind>
00721       void spontaneous_rdeltaf(Functor& fun,
00722                                unsigned src,
00723                                delta_kind::kind<Kind> k) const;
00724     protected:
00725       MetaElement();
00726       MetaElement(const MetaElement& other);
00727   };
00728 
00731 
00732   template <typename S, typename St, typename T>
00733   St& op_rout(const AutomataBase<S>& s, St& st, const T& r);
00734 
00735 } // vcsn
00736 
00737 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00738 #  include <vaucanson/automata/concept/automata_base.hxx>
00739 # endif // VCSN_USE_INTERFACE_ONLY
00740 
00741 #endif // ! VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH