automata_base.hh

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_data_t;
00071       typedef undefined_type state_iterator;
00072       typedef undefined_type transitions_t;
00073       typedef undefined_type transition_data_t;
00074       typedef undefined_type transition_iterator;
00075       typedef undefined_type initial_iterator;
00076       typedef undefined_type initial_support_t;
00077       typedef undefined_type final_iterator;
00078       typedef undefined_type final_support_t;
00079       typedef undefined_type geometry_t;
00080   };
00081 
00082   /*-----------------------------------.
00083   | virtual_types<AutomataBase<Self> > |
00084   `-----------------------------------*/
00085   template <class S>
00086   struct virtual_types<AutomataBase<S> >
00087     : virtual_types<Structure<S> >
00088   { };
00089 
00090   /*------------------------------------.
00091   | dynamic_traits<AutomataBase<Self> > |
00092   `------------------------------------*/
00093   template <class S>
00094   struct dynamic_traits<AutomataBase<S> >
00095     : dynamic_traits<Structure<S> >
00096   { };
00097 
00098   /*-----------------------------------.
00099   | MetaElement<AutomataBase<Self>, T> |
00100   `-----------------------------------*/
00102 
00115   // FIXME: Use some of the TYPEDEF_IMPORT macros.
00116   template <typename Self, typename T>
00117   struct MetaElement<AutomataBase<Self>, T>
00118     : MetaElement<Structure<Self>, T>
00119   {
00121       typedef MetaElement<AutomataBase<Self>, T>        self_t;
00122 
00124       typedef typename AutomataBase<Self>::series_set_t series_set_t;
00125 
00127       typedef typename automaton_traits<T>::series_set_elt_value_t
00128       series_set_elt_value_t;
00129 
00131       typedef Element<series_set_t, series_set_elt_value_t> series_set_elt_t;
00132 
00134       typedef typename series_set_t::monoid_t           monoid_t;
00135 
00137       typedef typename series_set_elt_t::monoid_elt_t   monoid_elt_t;
00138 
00140       typedef typename monoid_elt_t::value_t            monoid_elt_value_t;
00141 
00143       typedef typename monoid_t::letter_t               letter_t;
00144 
00146       typedef typename series_set_t::semiring_t         semiring_t;
00147 
00149       typedef typename series_set_elt_t::semiring_elt_t semiring_elt_t;
00150 
00152       typedef typename series_set_elt_t::semiring_elt_value_t
00153       semiring_elt_value_t;
00154 
00156       typedef typename automaton_traits<T>::tag_t               tag_t;
00157 
00159       typedef typename automaton_traits<T>::label_t     label_t;
00160 
00162       typedef typename automaton_traits<T>::states_t    states_t;
00163 
00165       typedef typename automaton_traits<T>::state_iterator state_iterator;
00166 
00168       typedef typename automaton_traits<T>::transitions_t transitions_t;
00169 
00171       typedef typename automaton_traits<T>::transition_iterator transition_iterator;
00172 
00174       typedef typename automaton_traits<T>::initial_support_t initial_support_t;
00175 
00177       typedef typename automaton_traits<T>::initial_iterator initial_iterator;
00178 
00180       typedef typename automaton_traits<T>::final_support_t final_support_t;
00181 
00183       typedef typename automaton_traits<T>::final_iterator final_iterator;
00184 
00186       typedef typename automaton_traits<T>::geometry_t  geometry_t;
00187 
00189       const series_set_t& series() const;
00190 
00192       tag_t& tag();
00193 
00195       const tag_t& tag() const;
00196 
00198       geometry_t& geometry();
00199 
00201       const geometry_t& geometry() const;
00202 
00204       bool exists() const;
00205 
00207       states_t states() const;
00208 
00210       transitions_t transitions() const;
00211 
00213       initial_support_t initial() const;
00214 
00216       final_support_t final() const;
00217 
00220       bool is_initial(hstate_t state) const;
00221 
00223       bool is_final(hstate_t state) const;
00224 
00226       void set_initial(hstate_t state);
00227 
00229       void set_initial(hstate_t state, const series_set_elt_t& m);
00230 
00232       void set_final(hstate_t state);
00233 
00235       void set_final(hstate_t state, const series_set_elt_t& m);
00236 
00238       void unset_initial(hstate_t state);
00239 
00241       void unset_final(hstate_t state);
00242 
00244       void clear_initial();
00245 
00247       void clear_final();
00248 
00250       Element<series_set_t, series_set_elt_value_t>
00251       get_initial(hstate_t state) const;
00252 
00254       Element<series_set_t, series_set_elt_value_t>
00255       get_final(hstate_t what) const;
00256 
00258       hstate_t add_state();
00259 
00262       hstate_t choose_state() const;
00263 
00265       htransition_t add_transition(hstate_t src, hstate_t dst,
00266                                    const label_t& label);
00267 
00270       htransition_t add_weighted_transition(hstate_t src, hstate_t dst,
00271                                             const semiring_elt_t& w,
00272                                             const monoid_elt_value_t& m);
00273 
00275 
00278       htransition_t add_series_transition(hstate_t src, hstate_t dst,
00279                                           const series_set_elt_t& e);
00280 
00282       htransition_t add_spontaneous(hstate_t src, hstate_t dst,
00283                                     const semiring_elt_t& w);
00284 
00285       htransition_t add_spontaneous(hstate_t src, hstate_t dst);
00286 
00288       htransition_t add_letter_transition(hstate_t src, hstate_t dst,
00289                                           const letter_t& l);
00290 
00292       void update(htransition_t e, const label_t& l);
00293 
00295       void del_state(hstate_t s);
00296 
00298       void del_transition(htransition_t e);
00299 
00301       bool has_state(hstate_t s) const;
00302 
00304       bool has_transition(htransition_t e) const;
00305 
00307       hstate_t src_of(htransition_t e) const;
00308 
00310       hstate_t dst_of(htransition_t e) const;
00311 
00313       typename automaton_traits<T>::label_t label_of(htransition_t e) const;
00314 
00316       series_set_elt_t series_of(htransition_t e) const;
00317 
00319       series_set_elt_value_t series_value_of(htransition_t e) const;
00320 
00322       bool is_spontaneous(htransition_t e) const;
00323 
00325       monoid_elt_t word_of(htransition_t e) const;
00326 
00328       semiring_elt_t weight_of(htransition_t e) const;
00329 
00331       monoid_elt_value_t word_value_of(htransition_t e) const;
00332 
00334 
00337       letter_t letter_of(htransition_t e) const;
00338 
00339       /*---------.
00340       | Deltas.  |
00341       `---------*/
00342 
00345       template <typename OutputIterator, typename Kind>
00346       void delta(OutputIterator res,
00347                  hstate_t src,
00348                  delta_kind::kind<Kind> k) const;
00349 
00352       template <typename OutputIterator, typename L, typename Kind>
00353       void delta(OutputIterator res,
00354                  hstate_t src,
00355                  const L& query,
00356                  delta_kind::kind<Kind> k) const;
00357 
00360       template <typename OutputIterator, typename L, typename Kind>
00361       void letter_delta(OutputIterator res,
00362                         hstate_t src,
00363                         const L& letter,
00364                         delta_kind::kind<Kind> k) const;
00365 
00368       template <typename OutputIterator, typename Kind>
00369       void spontaneous_delta(OutputIterator res,
00370                              hstate_t src,
00371                              delta_kind::kind<Kind> k) const;
00372 
00373       /*----------.
00374       | Deltacs.  |
00375       `----------*/
00376 
00379       template <typename Container, typename Kind>
00380       void deltac(Container& res, hstate_t src, delta_kind::kind<Kind> k) const;
00381 
00385       template <typename Container, typename L, typename Kind>
00386       void deltac(Container& res,
00387                   hstate_t src,
00388                   const L& query,
00389                   delta_kind::kind<Kind> k) const;
00390 
00393       template <typename Container, typename L, typename Kind>
00394       void letter_deltac(Container& res,
00395                          hstate_t src,
00396                          const L& letter,
00397                          delta_kind::kind<Kind> k) const;
00398 
00401       template <typename Container, typename Kind>
00402       void spontaneous_deltac(Container& res,
00403                               hstate_t src,
00404                               delta_kind::kind<Kind> k) const;
00405 
00406 
00407       /*----------.
00408       | Deltafs.  |
00409       `----------*/
00410 
00414       template <typename Functor, typename Kind>
00415       void deltaf(Functor& fun, hstate_t src, delta_kind::kind<Kind> k) const;
00416 
00420       template <typename Functor, typename L, typename Kind>
00421       void deltaf(Functor& fun,
00422                   hstate_t src,
00423                   const L& query,
00424                   delta_kind::kind<Kind> k) const;
00425 
00430       template <typename Functor, typename L, typename Kind>
00431       void letter_deltaf(Functor& fun,
00432                          hstate_t src,
00433                          const L& letter,
00434                          delta_kind::kind<Kind> k) const;
00435 
00440       template <typename Functor, typename Kind>
00441       void spontaneous_deltaf(Functor& fun,
00442                               hstate_t src,
00443                               delta_kind::kind<Kind> k) const;
00444 
00445       /*-----------------.
00446       | Reverse deltas.  |
00447       `-----------------*/
00448 
00451       template <typename OutputIterator, typename Kind>
00452       void rdelta(OutputIterator res,
00453                   hstate_t src,
00454                   delta_kind::kind<Kind> k) const;
00455 
00458       template <typename OutputIterator, typename L, typename Kind>
00459       void rdelta(OutputIterator res,
00460                   hstate_t src,
00461                   const L& query,
00462                   delta_kind::kind<Kind> k) const;
00463 
00466       template <typename OutputIterator, typename L, typename Kind>
00467       void letter_rdelta(OutputIterator res,
00468                          hstate_t src,
00469                          const L& letter,
00470                          delta_kind::kind<Kind> k) const;
00471 
00474       template <typename OutputIterator, typename Kind>
00475       void spontaneous_rdelta(OutputIterator res,
00476                               hstate_t src,
00477                               delta_kind::kind<Kind> k) const;
00478 
00479       /*------------------.
00480       | Reverse deltacs.  |
00481       `------------------*/
00482 
00485       template <typename Container, typename Kind>
00486       void rdeltac(Container& res, hstate_t src, delta_kind::kind<Kind> k) const;
00487 
00491       template <typename Container, typename L, typename Kind>
00492       void rdeltac(Container& res,
00493                    hstate_t src,
00494                    const L& query,
00495                    delta_kind::kind<Kind> k) const;
00496 
00499       template <typename Container, typename L, typename Kind>
00500       void letter_rdeltac(Container& res,
00501                           hstate_t src,
00502                           const L& letter,
00503                           delta_kind::kind<Kind> k) const;
00504 
00507       template <typename Container, typename Kind>
00508       void spontaneous_rdeltac(Container& res,
00509                                hstate_t src,
00510                                delta_kind::kind<Kind> k) const;
00511 
00512       /*------------------.
00513       | Reverse deltafs.  |
00514       `------------------*/
00515 
00518       template <typename Functor, typename Kind>
00519       void rdeltaf(Functor& fun, hstate_t src, delta_kind::kind<Kind> k) const;
00520 
00523       template <typename Functor, typename L, typename Kind>
00524       void rdeltaf(Functor& fun,
00525                    hstate_t src,
00526                    const L& query,
00527                    delta_kind::kind<Kind> k) const;
00528 
00531       template <typename Functor, typename L, typename Kind>
00532       void letter_rdeltaf(Functor& fun,
00533                           hstate_t src,
00534                           const L& letter,
00535                           delta_kind::kind<Kind> k) const;
00536 
00539       template <typename Functor, typename Kind>
00540       void spontaneous_rdeltaf(Functor& fun,
00541                                hstate_t src,
00542                                delta_kind::kind<Kind> k) const;
00543 
00544     protected:
00545       MetaElement();
00546       MetaElement(const MetaElement& other);
00547   };
00548 
00551 
00552   template <typename S, typename St, typename T>
00553   St& op_rout(const AutomataBase<S>& s, St& st, const T& r);
00554 
00555 } // vcsn
00556 
00557 # if !defined VCSN_USE_INTERFACE_ONLY || defined VCSN_USE_LIB
00558 #  include <vaucanson/automata/concept/automata_base.hxx>
00559 # endif // VCSN_USE_INTERFACE_ONLY
00560 
00561 #endif // ! VCSN_AUTOMATA_CONCEPT_AUTOMATA_BASE_HH

Generated on Sun Jul 29 19:35:17 2007 for Vaucanson by  doxygen 1.5.2