krat_exp_cderivation.hxx

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

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