build_pattern.hh

00001 // build_pattern.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 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_ALGORITHMS_INTERNAL_BUILD_PATTERN_HH
00018 # define VCSN_ALGORITHMS_INTERNAL_BUILD_PATTERN_HH
00019 
00020 # include <map>
00021 # include <vaucanson/automata/concept/automata_base.hh>
00022 # include <vaucanson/algorithms/standard.hh>
00023 # include <vaucanson/misc/usual_macros.hh>
00024 
00025 namespace vcsn {
00026   namespace algorithm_patterns
00027   {
00028 
00029     // This is the structure given to the map, which will
00030     // call the appropriate function
00031     template <typename Self, typename Etiq>
00032     struct Comparator
00033     {
00034       bool operator()(const Etiq& e1, const Etiq& e2) const;
00035     };
00036 
00037     /*-----------------------.
00038     | IncAutomataConstructor |
00039     `-----------------------*/
00040 
00041     // This is a pattern for algorithm which build automaton in
00042     // an incremental way :
00043     // it starts with one state, and with this state, it builds
00044     // other states. New states are used to build more and
00045     // more states.
00046     // It needs the function applied on each state,
00047     // and the order used by the map (a default one can be used).
00048     template <typename Self, typename T_auto, typename Etiq>
00049     class IncAutomataConstructor
00050     {
00051     public:
00052       // Useful types :))
00053       typedef T_auto*                                           T_auto_p;
00054       AUTOMATON_TYPES(T_auto);
00055       AUTOMATON_FREEMONOID_TYPES(T_auto);
00056       // Types for the list
00057       // It uses a map with an ordered function which can be
00058       // redefined in Self
00059       typedef
00060       std::pair<hstate_t, bool>                                 StateMarked;
00061       typedef
00062       std::map<Etiq, StateMarked, Comparator<Self, Etiq> >      StateMap;
00063       typedef typename StateMap::iterator                       iterator;
00064 
00065       // To run the algorithm
00066       void      run();
00067       // To get the result
00068       T_auto_p  get() const;
00069       // The function which will compare 2 Etiq
00070       // User may redefine it !
00071       static bool compare(const Etiq& e1, const Etiq& e2);
00072     protected:
00073       // The constructors (protected in order to not instance the class)
00074       IncAutomataConstructor(const series_set_t& series, const Etiq& etiq);
00075       IncAutomataConstructor(const series_set_t& series,
00076                              const std::list<Etiq>& listexp);
00077       // Add a link from current state to indicated state
00078       void      link_to(const Etiq& etiq, const letter_t& l);
00079       void      link_to(const Etiq& etiq, const series_set_elt_t& el);
00080       // To make the current state final
00081       void      set_final();
00082       void      set_final(const series_set_elt_t& el);
00083     private:
00084       // Function to apply on each state (call on_state function)
00085       void on_state_caller(const Etiq& e);
00086       // Method to add properly a state
00087       hstate_t  add_state(const Etiq& etiq);
00088       // Attributes
00089       int                               unvisited;
00090       T_auto_p                          auto_p;
00091       StateMap                          states_map;
00092       iterator                          current_state;
00093     };
00094 
00095     /*------------------------.
00096     | MathAutomataConstructor |
00097     `------------------------*/
00098 
00099     // This  Algorithm builder takes a struture
00100     // which contains different functions (like IncAutomataConstructor)
00101     // but the functions needed are mathematical definitions
00102     // of the automaton, i.e. :
00103     // function which return the set of final state,
00104     // etc.
00105     // FIXME: make it compatible with multiplicity
00106     template <typename Self, typename T_auto, typename Etiq>
00107     class MathAutomataConstructor
00108     {
00109     public:
00110       // Types used. The map make link between Etiq and hstate_t.
00111       AUTOMATON_TYPES(T_auto);
00112       AUTOMATON_FREEMONOID_TYPES(T_auto);
00113       typedef T_auto*                                           T_auto_p;
00114       typedef std::map<Etiq, hstate_t, Comparator<Self, Etiq> > StateMap;
00115       typedef typename StateMap::iterator                       iterator;
00116 
00117       // To run the algorithm and build the entire automaton
00118       void      run();
00119       // To get the result
00120       T_auto_p  get() const;
00121       // The function which will compare 2 Etiq
00122       // User may redefine it !
00123       static bool compare(const Etiq& e1, const Etiq& e2);
00124     protected:
00125       // The constructor
00126       template <typename Container>
00127       MathAutomataConstructor(const series_set_t& series,
00128                               const Container container);
00129     private:
00130       // Function which will call those which are defined by user
00131       bool is_initial_caller(const Etiq& e) const;
00132       bool is_final_caller(const Etiq& e) const;
00133       // Function which will link a state to a set of states
00134       template <typename Container>
00135       void link_to(const hstate_t& state,
00136                    const letter_t& letter,
00137                    const Container container);
00138       // Attributes
00139       T_auto_p                          auto_p;
00140       StateMap                          states_map;
00141     };
00142 
00143   }
00144 }
00145 
00146 
00147 # if !defined VCSN_USE_INTERFACE_ONLY && !defined VCSN_USE_LIB
00148 #include <vaucanson/algorithms/internal/build_pattern.hxx>
00149 #endif // VCSN_USE_INTERFACE_ONLY
00150 
00151 
00152 #endif // ! VCSN_ALGORITHMS_INTERNAL_BUILD_PATTERN_HH

Generated on Wed Jun 13 17:00:21 2007 for Vaucanson by  doxygen 1.5.1