berry_sethi.hxx

00001 // berry_sethi.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 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_BERRY_SETHI_HXX
00018 # define VCSN_ALGORITHMS_BERRY_SETHI_HXX
00019 
00020 # include <list>
00021 
00022 # include <vaucanson/algorithms/berry_sethi.hh>
00023 
00024 # include <vaucanson/algorithms/internal/build_pattern.hh>
00025 # include <vaucanson/automata/concept/automata_base.hh>
00026 
00027 # include <vaucanson/algorithms/krat_exp_constant_term.hh>
00028 # include <vaucanson/algorithms/krat_exp_derivation.hh>
00029 # include <vaucanson/algorithms/krat_exp_linearize.hh>
00030 # include <vaucanson/tools/usual_macros.hh>
00031 
00032 namespace vcsn {
00033 
00034   using namespace algorithm_patterns;
00035 
00047   template <typename S, typename T>
00048   typename linearize_element<S, T>::alphabet_t
00049   linearized_alphabet(const Element<S, T>& exp)
00050   {
00051     typedef typename linearize_element<S, T>::alphabet_t        alphabet_t;
00052     typedef typename linearize_element<S, T>::letter_t          letter_t;
00053 
00054     alphabet_t result = linearize(exp).structure().monoid().alphabet();
00055     result.insert(letter_t(0, 0));
00056     return result;
00057   }
00058 
00069   template <typename Exp, typename Letter>
00070   Exp
00071   linear_exp_continuation(const Exp& exp, const Letter& l)
00072   {
00073     typedef typename Exp::set_t::monoid_t::alphabet_t   alphabet_t;
00074     typedef typename alphabet_t::iterator               iterator;
00075     typedef typename Exp::value_t                       value_t;
00076 
00077     if (l == Letter(0,0))
00078       return exp;
00079 
00080     alphabet_t          alpha = exp.structure().monoid().alphabet();
00081     Exp                 zero = exp.structure().zero(SELECT(value_t));
00082     std::list<Exp>      exp_list;
00083 
00084     exp_list.push_back(exp);
00085 
00086     while (!exp_list.empty())
00087     {
00088       Exp       exp = exp_list.front();
00089       exp_list.pop_front();
00090       Exp       deriv = derivate(exp, l).first;
00091 
00092       if (deriv != zero)
00093         return deriv;
00094       else
00095         for (iterator i = alpha.begin(); i != alpha.end(); ++i)
00096           if (*i != l)
00097           {
00098             deriv = derivate(exp, *i).first;
00099             if (deriv != zero && deriv != exp)
00100               exp_list.push_back(deriv);
00101           }
00102     }
00103     return zero;
00104   }
00105 
00125   template <typename T_auto, typename S, typename T>
00126   struct BerrySethiAlgo : public MathAutomataConstructor <
00127     BerrySethiAlgo<T_auto, S, T>,
00128     T_auto,
00129     typename linearize_element<S, T>::letter_t >
00130   {
00131   public:
00133     typedef
00134     Element<S, T>                                       exp_t;
00136 
00137     typedef typename
00138     linearize_element<S, T>::element_t                  linear_exp_t;
00139     typedef typename
00140     linearize_element<S, T>::alphabet_t                 linear_alphabet_t;
00141     typedef typename
00142     linearize_element<S, T>::letter_t                   etiq_t;
00144     // Common types.
00145     AUTOMATON_TYPES(T_auto);
00146     AUTOMATON_FREEMONOID_TYPES(T_auto);
00147 
00160     BerrySethiAlgo(const series_set_t& series, const exp_t& exp):
00161       MathAutomataConstructor <BerrySethiAlgo, T_auto, etiq_t>
00162         (series, linearized_alphabet(exp)),
00163       linear_exp(linearize(exp)),
00164       linear_alpha(linear_exp.structure().monoid().alphabet())
00165     {
00166       linear_alpha.insert(etiq_t(0, 0));
00167     }
00168 
00170 
00171     bool is_initial(const etiq_t& e) const
00172     {
00173       return (e == etiq_t(0, 0));
00174     }
00175 
00176     bool is_final(const etiq_t& e) const
00177     {
00178       return constant_term(linear_exp_continuation(linear_exp, e)).first
00179         != linear_exp.structure().semiring().zero(SELECT(semiring_elt_value_t));
00180     }
00183 
00184     std::set<etiq_t> delta(const etiq_t& e, const letter_t& l)
00185     {
00186       typedef typename linear_alphabet_t::iterator      iterator;
00187       std::set<etiq_t>  result;
00188       linear_exp_t      continuation_e = linear_exp_continuation(linear_exp, e);
00189 
00190       for (iterator i = linear_alpha.begin(); i != linear_alpha.end(); ++i)
00191         if ((i->first == l) && (derivation(continuation_e, *i)
00192                                 == linear_exp_continuation(linear_exp, *i)))
00193           result.insert(*i);
00194       return result;
00195     }
00196 
00197   private:
00199     linear_exp_t        derivation(const linear_exp_t& exp, const etiq_t& e)
00200     {
00201       if (e == etiq_t(0, 0))
00202         return exp;
00203       else
00204         return derivate(exp, e).first;
00205     }
00206 
00208     linear_exp_t        linear_exp;
00210     linear_alphabet_t   linear_alpha;
00211   };
00212 
00213   template<typename T_auto, typename S, typename T>
00214   T_auto*
00215   do_berry_sethi(const T_auto& out, const Element<S, T>& kexp)
00216   {
00217     BerrySethiAlgo<T_auto, S, T> berrysethi_algo(out.series(), kexp);
00218     berrysethi_algo.run();
00219     return berrysethi_algo.get();
00220   }
00221 
00222   template<typename A, typename T, typename Exp>
00223   void
00224   berry_sethi(Element<A, T>& out, const Exp& kexp)
00225   {
00226     Element<A, T>* tmp = do_berry_sethi(out, kexp);
00227     out = *tmp;
00228     delete tmp;
00229   }
00230 
00231 } // vcsn
00232 
00233 #endif // ! VCSN_ALGORITHMS_BERRY_SETHI_HXX

Generated on Fri Jul 28 12:18:30 2006 for Vaucanson by  doxygen 1.4.6