Vaucanson 1.4
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, 2006, 2011 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/misc/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             Exp 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 linearize_element<S, T>::element_t   linear_exp_t;
00138     typedef typename linearize_element<S, T>::alphabet_t  linear_alphabet_t;
00139     typedef typename linearize_element<S, T>::letter_t    etiq_t;
00141     // Common types.
00142     AUTOMATON_TYPES(T_auto);
00143     AUTOMATON_FREEMONOID_TYPES(T_auto);
00144 
00157     BerrySethiAlgo(const series_set_t& series, const exp_t& exp):
00158       MathAutomataConstructor <BerrySethiAlgo, T_auto, etiq_t>
00159         (series, linearized_alphabet(exp)),
00160       linear_exp(linearize(exp)),
00161       linear_alpha(linear_exp.structure().monoid().alphabet())
00162     {
00163       linear_alpha.insert(etiq_t(0, 0));
00164     }
00165 
00167 
00168     bool is_initial(const etiq_t& e) const
00169     {
00170       return (e == etiq_t(0, 0));
00171     }
00172 
00173     bool is_final(const etiq_t& e) const
00174     {
00175       return constant_term(linear_exp_continuation(linear_exp, e)).first
00176         != linear_exp.structure().semiring().zero(SELECT(semiring_elt_value_t));
00177     }
00180 
00181     std::set<etiq_t> delta(const etiq_t& e, const letter_t& l)
00182     {
00183       typedef typename linear_alphabet_t::iterator      iterator;
00184       std::set<etiq_t>  result;
00185       linear_exp_t      continuation_e = linear_exp_continuation(linear_exp, e);
00186 
00187       for (iterator i = linear_alpha.begin(); i != linear_alpha.end(); ++i)
00188         if (i->first == l
00189             && (derivation(continuation_e, *i)
00190                 == linear_exp_continuation(linear_exp, *i)))
00191           result.insert(*i);
00192       return result;
00193     }
00194 
00195   private:
00197     linear_exp_t        derivation(const linear_exp_t& exp, const etiq_t& e)
00198     {
00199       if (e == etiq_t(0, 0))
00200         return exp;
00201       else
00202         return derivate(exp, e).first;
00203     }
00204 
00206     linear_exp_t        linear_exp;
00208     linear_alphabet_t   linear_alpha;
00209   };
00210 
00211   template<typename T_auto, typename S, typename T>
00212   T_auto*
00213   do_berry_sethi(const T_auto& out, const Element<S, T>& kexp)
00214   {
00215     BerrySethiAlgo<T_auto, S, T> berrysethi_algo(out.series(), kexp);
00216     berrysethi_algo.run();
00217     return berrysethi_algo.get();
00218   }
00219 
00220   template<typename A, typename T, typename Exp>
00221   void
00222   berry_sethi(Element<A, T>& out, const Exp& kexp)
00223   {
00224     BENCH_TASK_SCOPED("berry_sethi");
00225     Element<A, T>* tmp = do_berry_sethi(out, kexp);
00226     out = *tmp;
00227     delete tmp;
00228   }
00229 
00230 } // vcsn
00231 
00232 #endif // ! VCSN_ALGORITHMS_BERRY_SETHI_HXX