krat_exp_partial_derivation.hxx

00001 // krat_exp_partial_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, 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_PARTIAL_DERIVATION_HXX
00018 # define VCSN_ALGORITHMS_KRAT_EXP_PARTIAL_DERIVATION_HXX
00019 
00020 # include <vaucanson/algorithms/krat_exp_partial_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   namespace algebra {
00028 
00029     // Some operators are defined in order to make algorithm clearer
00030     // and efficient
00031 
00032     // operator^ apply * between each element of the set and the other
00033     // argument
00034     template <typename T, typename U>
00035     std::set<T> operator^ (std::set<T> set, U other)
00036     {
00037       typedef typename std::set<T>::iterator    iterator;
00038       std::set<T>       result;
00039       for (iterator i = set.begin(); i != set.end(); ++i)
00040         result.insert(*i * other);
00041       return result;
00042     }
00043 
00044     template <typename T, typename U>
00045     std::set<T> operator^ (U other, std::set<T> set)
00046     {
00047       typedef typename std::set<T>::iterator    iterator;
00048       std::set<T>       result;
00049       for (iterator i = set.begin(); i != set.end(); ++i)
00050         result.insert(other * *i);
00051       return result;
00052     }
00053 
00054     // operator+ make the union of two set
00055     template <typename T>
00056     std::set<T> operator+ (std::set<T> s1, std::set<T> s2)
00057     {
00058       std::set<T>       result;
00059       merge(s1.begin(), s1.end(),
00060             s2.begin(), s2.end(),
00061             inserter(result, result.begin()));
00062       return result;
00063     }
00064 
00065     // It is a first implementation of partial derivate.
00066     // It simply apply the definition of partial derivates.
00067     template <class Series, class T, class Dispatch>
00068     struct KRatExpPartialDerivation : algebra::KRatExpMatcher<
00069       KRatExpPartialDerivation<Series, T, Dispatch>,
00070       T,
00071       std::set<Element<Series, T> >,
00072       Dispatch
00073       >
00074     {
00075       typedef KRatExpPartialDerivation<Series, T, Dispatch>     self_t;
00076       typedef Element<Series, T>                                        exp_t;
00077       typedef std::set<exp_t>                                   set_t;
00078       typedef set_t                                             return_type;
00079       typedef typename set_t::iterator  iterator;
00080       typedef typename Element<Series, T>::semiring_elt_t               semiring_elt_t;
00081       typedef typename semiring_elt_t::value_t                          semiring_elt_value_t;
00082       typedef typename Element<Series, T>::monoid_elt_t         monoid_elt_t;
00083       typedef typename monoid_elt_t::value_t                    monoid_elt_value_t;
00084       typedef typename monoid_elt_t::set_t                      monoid_t;
00085       typedef typename monoid_t::alphabet_t                     alphabet_t;
00086       typedef typename alphabet_t::letter_t                     letter_t;
00087       INHERIT_CONSTRUCTORS(self_t, T, semiring_elt_t, Dispatch);
00088 
00089       KRatExpPartialDerivation(const Element<Series, T>& exp,
00090                                letter_t                  a) :
00091         undefined(false),
00092         exp_(exp),
00093         a_(a)
00094       {}
00095 
00096       Element<Series, T> series(const T& e)
00097       {
00098         return Element<Series, T>(exp_.structure(), e);
00099       }
00100 
00101       MATCH__(Product, lhs, rhs)
00102       {
00103         std::pair<semiring_elt_t, bool> ret = constant_term(series(lhs));
00104         if (ret.second == false)
00105           {
00106             undefined = true;
00107             return return_type();
00108           }
00109         if (ret.first !=
00110             exp_.structure().semiring().zero(SELECT(semiring_elt_value_t)))
00111           return (match(lhs) ^ rhs) + (ret.first ^ match(rhs));
00112         else
00113           return (match(lhs) ^ rhs);
00114       }
00115       END
00116 
00117       MATCH__(Sum, lhs, rhs)
00118       {
00119         return match(lhs) + match(rhs);
00120       }
00121       END
00122 
00123       MATCH_(Star, e)
00124       {
00125         std::pair<semiring_elt_t, bool> ret = constant_term(series(e));
00126         if ((ret.second == false) || (ret.first.starable() == false))
00127           {
00128             undefined = true;
00129             return return_type();
00130           }
00131         return ret.first.star() ^ (match(e) ^ e.clone().star());
00132       }
00133       END
00134 
00135       MATCH__(LeftWeight, w, e)
00136       {
00137         return semiring_elt_t(w) ^ match(e);
00138       }
00139       END
00140 
00141       MATCH__(RightWeight, e, w)
00142       {
00143         return match(e) ^ semiring_elt_t(w);
00144       }
00145       END
00146 
00147       MATCH_(Constant, m)
00148       {
00149         return_type     res;
00150         if (m[0] == a_)
00151           {
00152             if (m.length() == 1)
00153               res.insert(algebra::identity_as<T>::of(exp_.structure()));
00154             else
00155               res.insert(Element<Series, T> (exp_.structure(), m.substr(1)));
00156           }
00157         return res;
00158       }
00159       END
00160 
00161       MATCH(Zero)
00162       {
00163         return return_type();
00164       }
00165       END
00166 
00167       MATCH(One)
00168       {
00169         return return_type();
00170       }
00171       END
00172 
00173       bool undefined;
00174 
00175     private:
00176       Element<Series, T>  exp_;
00177       letter_t          a_;
00178     };
00179 
00180   } // algebra
00181 
00182   template <class Series, class T, class Letter>
00183   std::pair<std::set<Element<Series, T> >, bool>
00184   partial_derivate(const Element<Series, T>& exp,
00185                    Letter a)
00186   {
00187     algebra::KRatExpPartialDerivation<Series, T, algebra::DispatchFunction<T> >
00188       matcher(exp, a);
00189     std::set<Element<Series, T> > ret = matcher.match(exp.value());
00190     if (matcher.undefined)
00191       return std::make_pair(ret, false);
00192     return std::make_pair(ret, true);
00193   }
00194 
00195 } // vcsn
00196 
00197 #endif // ! VCSN_ALGORITHMS_KRAT_EXP_PARTIAL_DERIVATION_HXX

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