krat_exp_derivation.hxx

00001 // krat_exp_derivation.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 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_KRAT_EXP_DERIVATION_HXX
00018 # define VCSN_ALGORITHMS_KRAT_EXP_DERIVATION_HXX
00019 
00020 # include <vaucanson/algorithms/krat_exp_derivation.hh>
00021 
00022 # include <vaucanson/algebra/implementation/series/krat_exp_pattern.hh>
00023 # include <vaucanson/algorithms/krat_exp_constant_term.hh>
00024 
00025 namespace vcsn {
00026 
00027   template <class Series, class T, class Dispatch>
00028   struct KRatExpDerivation : algebra::KRatExpMatcher<
00029     KRatExpDerivation<Series, T, Dispatch>,
00030     T,
00031     Element<Series, T>,
00032     Dispatch
00033     >
00034   {
00035     typedef KRatExpDerivation<Series, T, Dispatch>    self_t;
00036     typedef Element<Series, T>                        return_type;
00037     typedef typename Element<Series, T>::semiring_elt_t     semiring_elt_t;
00038     typedef typename semiring_elt_t::value_t                  semiring_elt_value_t;
00039     typedef typename Element<Series, T>::monoid_elt_t monoid_elt_t;
00040     typedef typename monoid_elt_t::value_t            monoid_elt_value_t;
00041     typedef typename monoid_elt_t::set_t              monoid_t;
00042     typedef typename monoid_t::alphabet_t             alphabet_t;
00043     typedef typename alphabet_t::letter_t             letter_t;
00044     INHERIT_CONSTRUCTORS(self_t, T, semiring_elt_t, Dispatch);
00045 
00046     KRatExpDerivation(const Element<Series, T>& exp,
00047                    letter_t                  a) :
00048       undefined(false),
00049       exp_(exp),
00050       a_(a)
00051     {}
00052 
00053     Element<Series, T> series(const T& e)
00054     {
00055       return Element<Series, T>(exp_.structure(), e);
00056     }
00057 
00058     MATCH__(Product, lhs, rhs)
00059     {
00060       std::pair<semiring_elt_t, bool> ret = constant_term(series(lhs));
00061       if (ret.second == false)
00062         {
00063           undefined = true;
00064           return return_type(exp_.structure());
00065         }
00066       return (match(lhs) * rhs) + ret.first * match(rhs);
00067     }
00068     END
00069 
00070     MATCH__(Sum, lhs, rhs)
00071     {
00072       return match(lhs) + match(rhs);
00073     }
00074     END
00075 
00076     MATCH_(Star, e)
00077     {
00078       std::pair<semiring_elt_t, bool> ret = constant_term(series(e));
00079       if ((ret.second == false) || (ret.first.starable() == false))
00080         {
00081           undefined = true;
00082           return return_type(exp_.structure());
00083         }
00084       return ret.first.star() * match(e) * e.clone().star();
00085     }
00086     END
00087 
00088     MATCH__(LeftWeight, w, e)
00089     {
00090       return semiring_elt_t(w) * match(e);
00091     }
00092     END
00093 
00094     MATCH__(RightWeight, e, w)
00095     {
00096       return match(e) * semiring_elt_t(w);
00097     }
00098     END
00099 
00100     MATCH_(Constant, m)
00101     {
00102       if (m[0] == a_)
00103         {
00104           if (m.length() == 1)
00105             return algebra::identity_as<T>::of(exp_.structure());
00106           else
00107             return Element<Series, T> (exp_.structure(), m.substr(1));
00108         }
00109       else
00110         return algebra::zero_as<T>::of(exp_.structure());
00111     }
00112     END
00113 
00114     MATCH(Zero)
00115     {
00116       return algebra::zero_as<T>::of(exp_.structure());
00117     }
00118     END
00119 
00120     MATCH(One)
00121     {
00122       return algebra::zero_as<T>::of(exp_.structure());
00123     }
00124     END
00125 
00126     bool undefined;
00127 
00128   private:
00129     Element<Series, T>  exp_;
00130     letter_t            a_;
00131   };
00132 
00133   template <class Series, class T, class Letter>
00134   std::pair<Element<Series, T>, bool>
00135   derivate(const Element<Series, T>& exp,
00136            Letter a)
00137   {
00138     KRatExpDerivation<Series, T, algebra::DispatchFunction<T> >
00139       matcher(exp, a);
00140     Element<Series, T> ret = matcher.match(exp.value());
00141     if (matcher.undefined)
00142       return std::make_pair(ret, false);
00143     return std::make_pair(ret, true);
00144   }
00145 
00146   template <class Series, class T, class Word>
00147   std::pair<Element<Series, T>, bool>
00148   word_derivate(const Element<Series, T>& exp,
00149                 Word w)
00150   {
00151     Element<Series, T> ret(exp);
00152     for (typename Word::reverse_iterator a = w.rbegin();
00153          a != w.rend(); ++a)
00154       {
00155         KRatExpDerivation<Series, T, algebra::DispatchFunction<T> >
00156           matcher(exp, *a);
00157         ret = matcher.match(ret.value());
00158         if (matcher.undefined)
00159           return std::make_pair(ret, false);
00160       }
00161     return std::make_pair(ret, true);
00162   }
00163 
00164 } // vcsn
00165 
00166 #endif // ! VCSN_ALGORITHMS_KRAT_EXP_DERIVATION_HXX

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