Vaucanson 1.4
build_pattern.hxx
00001 // build_pattern.hxx: 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_HXX
00018 # define VCSN_ALGORITHMS_INTERNAL_BUILD_PATTERN_HXX
00019 
00020 namespace vcsn
00021 {
00022   namespace algorithm_patterns
00023   {
00024 
00025     // The ordered function called by maps
00026     template <typename Self, typename Etiq>
00027     bool
00028     Comparator<Self, Etiq>::operator()(const Etiq& e1, const Etiq& e2) const
00029     {
00030       return Self::compare(e1, e2);
00031     }
00032 
00033     /*-----------------------.
00034     | IncAutomataConstructor |
00035     `-----------------------*/
00036 
00037     // The constructor
00038     template <typename Self, typename T_auto, typename Etiq>
00039     IncAutomataConstructor<Self, T_auto, Etiq>::IncAutomataConstructor
00040     (
00041       const series_set_t& series, const Etiq& etiq
00042       )
00043     {
00044       automata_set_t a_set(series);
00045       auto_p = new T_auto(a_set);
00046       unvisited = 0;
00047       auto_p->set_initial(add_state(etiq));
00048       current_state = states_map.end();
00049     }
00050 
00051     // The constructor with list
00052     template <typename Self, typename T_auto, typename Etiq>
00053     IncAutomataConstructor<Self, T_auto, Etiq>::IncAutomataConstructor
00054     (
00055       const series_set_t& series, const std::list<Etiq>& listexp
00056       )
00057     {
00058       automata_set_t a_set(series);
00059       auto_p = new T_auto(a_set);
00060       unvisited = 0;
00061 
00062       for (typename std::list<Etiq>::const_iterator it = listexp.begin();
00063            it != listexp.end(); ++it)
00064         auto_p->set_initial(add_state(*it));
00065 
00066       current_state = states_map.end();
00067     }
00068 
00069 
00070     // To get the result
00071     template <typename Self, typename T_auto, typename Etiq>
00072     T_auto*
00073     IncAutomataConstructor<Self, T_auto, Etiq>::get() const
00074     {
00075       return auto_p;
00076     }
00077 
00078     // To run the algorithm
00079     template <typename Self, typename T_auto, typename Etiq>
00080     void
00081     IncAutomataConstructor<Self, T_auto, Etiq>::run()
00082     {
00083       while (unvisited > 0)
00084       {
00085         for (current_state = states_map.begin();
00086              current_state != states_map.end();
00087              ++current_state)
00088         {
00089           if (!(current_state->second.second))
00090           {
00091             on_state_caller(current_state->first);
00092             unvisited -= 1;
00093             current_state->second.second = true;
00094           }
00095         }
00096       }
00097     }
00098 
00099     // Link current state to another, which can be created
00100     template <typename Self, typename T_auto, typename Etiq>
00101     void
00102     IncAutomataConstructor<Self, T_auto, Etiq>::link_to
00103     (
00104       const Etiq& etiq, const letter_t& l
00105       )
00106     {
00107       typename T_auto::hstate_t s;
00108       iterator  i = states_map.find(etiq);
00109 
00110       if (i == states_map.end())
00111         s = add_state(etiq);
00112       else
00113         s = i->second.first;
00114       auto_p->add_letter_transition(current_state->second.first, s, l);
00115     }
00116 
00117     template <typename Self, typename T_auto, typename Etiq>
00118     void
00119     IncAutomataConstructor<Self, T_auto, Etiq>::link_to
00120     (
00121       const Etiq& etiq, const series_set_elt_t& el
00122       )
00123     {
00124       typename T_auto::hstate_t s;
00125       iterator  i = states_map.find(etiq);
00126 
00127       if (i == states_map.end())
00128         s = add_state(etiq);
00129       else
00130         s = i->second.first;
00131       auto_p->add_series_transition(current_state->second.first, s, el);
00132     }
00133 
00134     // A tool to add a state in the set and the automaton
00135     template <typename Self, typename T_auto, typename Etiq>
00136     typename T_auto::hstate_t
00137     IncAutomataConstructor<Self, T_auto, Etiq>::add_state(const Etiq& etiq)
00138     {
00139       typename T_auto::hstate_t res = auto_p->add_state();
00140       states_map[etiq] = std::pair<typename T_auto::hstate_t, bool>(res, false);
00141       unvisited += 1;
00142       return res;
00143     }
00144 
00145     // To make the current state final
00146     template <typename Self, typename T_auto, typename Etiq>
00147     void
00148     IncAutomataConstructor<Self, T_auto, Etiq>::set_final()
00149     {
00150       auto_p->set_final(current_state->second.first);
00151     }
00152 
00153     // To make the current state final
00154     template <typename Self, typename T_auto, typename Etiq>
00155     void
00156     IncAutomataConstructor<Self, T_auto, Etiq>::set_final
00157     (const series_set_elt_t& el)
00158     {
00159       auto_p->set_final(current_state->second.first, el);
00160     }
00161 
00162 
00163     // The function called on each state :
00164     // it just call the on_each_state function, which must be defined
00165     // by user.
00166     template <typename Self, typename T_auto, typename Etiq>
00167     void
00168     IncAutomataConstructor<Self, T_auto, Etiq>::on_state_caller(const Etiq& e)
00169     {
00170       static_cast<Self&>(*this).on_state(e);
00171     }
00172 
00173     // The default function which will compare 2 Etiq
00174     template <typename Self, typename T_auto, typename Etiq>
00175     bool
00176     IncAutomataConstructor<Self, T_auto, Etiq>::compare
00177     (
00178       const Etiq& e1, const Etiq& e2
00179       )
00180     {
00181       return e1 < e2;
00182     }
00183 
00184     /*------------------------.
00185     | MathAutomataConstructor |
00186     `------------------------*/
00187 
00188     // The constructor.
00189     // It takes a container, which must contain the labels of states
00190     template <typename Self, typename T_auto, typename Etiq>
00191     template <typename Container>
00192     MathAutomataConstructor<Self, T_auto, Etiq>::MathAutomataConstructor
00193     (
00194       const series_set_t& series, const Container container
00195       )
00196     {
00197       typedef typename Container::iterator      c_iterator;
00198 
00199       automata_set_t a_set(series);
00200       auto_p = new T_auto(a_set);
00201 
00202       for (c_iterator i = container.begin(); i != container.end(); ++i)
00203         states_map[*i] = auto_p->add_state();
00204     }
00205 
00206     // The function used to get the result
00207     template <typename Self, typename T_auto, typename Etiq>
00208     T_auto*
00209     MathAutomataConstructor<Self, T_auto, Etiq>::get() const
00210     {
00211       return auto_p;
00212     }
00213 
00214     // The building function.
00215     // It calls the templated function link_to() in order to
00216     // allow user not to declare the return type of delta()
00217     // (That's why delta_caller() does not exist)
00218     template <typename Self, typename T_auto, typename Etiq>
00219     void
00220     MathAutomataConstructor<Self, T_auto, Etiq>::run()
00221     {
00222       alphabet_t alpha = get()->series().monoid().alphabet();
00223       for (iterator i = states_map.begin(); i != states_map.end(); ++i)
00224       {
00225         if (is_initial_caller(i->first))
00226           auto_p->set_initial(i->second);
00227         if (is_final_caller(i->first))
00228           auto_p->set_final(i->second);
00229         for (alphabet_iterator a = alpha.begin(); a != alpha.end(); ++a)
00230           link_to(i->second, *a, static_cast<Self&>(*this).delta(i->first, *a));
00231       }
00232     }
00233 
00234     // The two following funtions just call the appropriate function
00235     // of daughter class
00236     template <typename Self, typename T_auto, typename Etiq>
00237     bool
00238     MathAutomataConstructor<Self, T_auto, Etiq>::is_initial_caller
00239     (
00240       const Etiq& e
00241       ) const
00242     {
00243       return static_cast<const Self&>(*this).is_initial(e);
00244     }
00245 
00246     template <typename Self, typename T_auto, typename Etiq>
00247     bool
00248     MathAutomataConstructor<Self, T_auto, Etiq>::is_final_caller
00249     (
00250       const Etiq& e
00251       ) const
00252     {
00253       return static_cast<const Self&>(*this).is_final(e);
00254     }
00255 
00256     // Function which build transitions between a state
00257     // and a set of states
00258     template <typename Self, typename T_auto, typename Etiq>
00259     template <typename Container>
00260     void
00261     MathAutomataConstructor<Self, T_auto, Etiq>::link_to
00262     (
00263       const typename T_auto::hstate_t& state, const letter_t& letter, const Container container
00264       )
00265     {
00266       typedef typename Container::iterator      c_iterator;
00267       for (c_iterator j = container.begin(); j != container.end(); ++j)
00268       {
00269         iterator tmp = states_map.find(*j);
00270         if (tmp != states_map.end())
00271           auto_p->add_letter_transition(state, tmp->second, letter);
00272       }
00273     }
00274 
00275     // The default function which will compare 2 Etiq
00276     template <typename Self, typename T_auto, typename Etiq>
00277     bool
00278     MathAutomataConstructor<Self, T_auto, Etiq>::compare
00279     (
00280       const Etiq& e1, const Etiq& e2
00281       )
00282     {
00283       return e1 < e2;
00284     }
00285 
00286   }
00287 }
00288 
00289 #endif // ! VCSN_ALGORITHMS_INTERNAL_BUILD_PATTERN_HXX