partial_rat_exp_derivation.hxx

00001 // partial_rat_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, 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_INTERNAL_PARTIAL_RAT_EXP_DERIVATION_HXX
00018 # define VCSN_ALGORITHMS_INTERNAL_PARTIAL_RAT_EXP_DERIVATION_HXX
00019 
00020 # include <vaucanson/algebra/implementation/series/krat_exp_pattern.hh>
00021 # include <vaucanson/algorithms/krat_exp_constant_term.hh>
00022 # include <vaucanson/algebra/implementation/series/krat.hh>
00023 # include <vaucanson/misc/contract.hh>
00024 
00025 namespace vcsn {
00026 
00027   template <typename T>
00028   void list_fusion_here(std::list<T>& dst, std::list<T>& src)
00029   {
00030     typedef typename std::list<T>::iterator             iterator;
00031     typedef typename T::series_set_t                    series_set_t;
00032     typedef typename T::series_set_elt_value_t          series_set_elt_value_t;
00033     typedef typename T::semiring_elt_t::value_t         semiring_elt_value_t;
00034 
00035     src.sort(unweighted_inf<series_set_t, series_set_elt_value_t>);
00036     dst.sort(unweighted_inf<series_set_t, series_set_elt_value_t>);
00037     dst.merge(src, unweighted_inf<series_set_t, series_set_elt_value_t>);
00038     iterator i = dst.begin();
00039     while (i != dst.end())
00040     {
00041       iterator next = i;
00042       if (++next != dst.end() and unweighted_eq(*next, *i))
00043       {
00044         i->begin().semiring_elt() += next->begin().semiring_elt();
00045         dst.erase(next);
00046         if (i->begin().semiring_elt() ==
00047             i->begin().semiring_elt().structure().zero(
00048               SELECT(semiring_elt_value_t)))
00049         {
00050           next = i++;
00051           dst.erase(next);
00052           continue ;
00053         }
00054       }
00055       ++i;
00056     }
00057   }
00058 
00059   template <typename S, typename T>
00060   void list_multiply_here_left(std::list<PartialExp<S, T> >& l,
00061                                const typename PartialExp<S, T>::semiring_elt_t& w)
00062   {
00063     typedef std::list<PartialExp<S, T> >        list_t;
00064     for (typename list_t::iterator i = l.begin(); i != l.end(); ++i)
00065       *i >>= w;
00066   }
00067 
00068   template <typename S, typename T>
00069   void list_multiply_here_right(std::list<PartialExp<S, T> >& l,
00070                                const typename PartialExp<S, T>::semiring_elt_t& w)
00071   {
00072     typedef std::list<PartialExp<S, T> >        list_t;
00073     for (typename list_t::iterator i = l.begin(); i != l.end(); ++i)
00074       *i <<= w;
00075   }
00076 
00077   template <typename S, typename T>
00078   void list_insert_here(std::list<PartialExp<S, T> >& l,
00079                         const typename PartialExp<S,T>::node_t* elm)
00080   {
00081     typedef std::list<PartialExp<S, T> >        list_t;
00082     for (typename list_t::iterator i = l.begin(); i != l.end(); ++i)
00083       i->insert(elm);
00084   }
00085 
00092   template <typename Series, typename T>
00093   class PRatExpDerivationVisitor :
00094     public rat::ConstNodeVisitor<typename T::monoid_elt_value_t,
00095                                  typename T::semiring_elt_value_t>
00096   {
00097   public:
00098     typedef Element<Series, T>                          exp_t;
00099     typedef T                                           series_set_elt_value_t;
00100     typedef typename T::node_t                          node_t;
00101     typedef typename std::list<PartialExp<Series, T> >  return_type;
00102     typedef typename Element<Series, T>::semiring_elt_t semiring_elt_t;
00103     typedef typename semiring_elt_t::value_t            semiring_elt_value_t;
00104     typedef typename Element<Series, T>::monoid_elt_t   monoid_elt_t;
00105     typedef typename monoid_elt_t::value_t              monoid_elt_value_t;
00106     typedef typename monoid_elt_t::set_t                monoid_t;
00107     typedef typename monoid_t::alphabet_t               alphabet_t;
00108     typedef typename alphabet_t::letter_t               letter_t;
00109 
00110   public:
00111     PRatExpDerivationVisitor(const exp_t&       exp,
00112                              const letter_t&    a) :
00113       undefined(false),
00114       exp_(exp),
00115       a_(a),
00116       father_(NULL)
00117     {}
00118 
00119     virtual
00120     ~PRatExpDerivationVisitor()
00121     {}
00122 
00123     void match(const node_t* node)
00124     {
00125       father_ = node;
00126       node->accept(*this);
00127     }
00128 
00129   private:
00130     Element<Series, T> series(const T& e)
00131     {
00132       return Element<Series, T>(exp_.structure(), e);
00133     }
00134 
00135   public:
00136     virtual void
00137     product(const node_t* lhs, const node_t* rhs)
00138     {
00139       std::pair<semiring_elt_t, bool> ret =
00140         constant_term(series(series_set_elt_value_t(lhs)));
00141       if (ret.second == false)
00142       {
00143         undefined = true;
00144         return ;
00145       }
00146 
00147       return_type tmp;
00148       if ( ret.first !=
00149            exp_.structure().semiring().zero(SELECT(semiring_elt_value_t)))
00150       {
00151         match(rhs);
00152         list_multiply_here_left(result, ret.first);
00153         tmp = result;
00154       }
00155 
00156       match(lhs);
00157       list_insert_here(result, rhs);
00158       list_fusion_here(result, tmp);
00159     }
00160 
00161     virtual void
00162     sum(const node_t* lhs, const node_t* rhs)
00163     {
00164       match(rhs);
00165       return_type tmp = result;
00166       match(lhs);
00167       list_fusion_here(result, tmp);
00168     }
00169 
00170     virtual void
00171     star(const node_t* node)
00172     {
00173       assertion(father_ != NULL);
00174       const typename T::node_t* father = father_;
00175 
00176       std::pair<semiring_elt_t, bool> ret =
00177         constant_term(series(series_set_elt_value_t(node)));
00178       if ((ret.second == false) || (ret.first.starable() == false))
00179       {
00180         undefined = true;
00181         return;
00182       }
00183 
00184       match(node);
00185       list_insert_here(result, father);
00186       list_multiply_here_left(result, ret.first.star());
00187     }
00188 
00189     virtual void
00190     left_weight(const semiring_elt_value_t& w, const node_t* node)
00191     {
00192       match(node);
00193       list_multiply_here_left(result, semiring_elt_t(w));
00194     }
00195 
00196     virtual void
00197     right_weight(const semiring_elt_value_t& w, const node_t* node)
00198     {
00199       match(node);
00200       list_multiply_here_right(result, semiring_elt_t(w));
00201     }
00202 
00203     virtual void
00204     constant(const monoid_elt_value_t& m)
00205     {
00206       result = return_type();
00207       if (m.length() != 1)
00208       {
00209         WARNING("PartialExp base is not realtime.");
00210         undefined = true;
00211         return;
00212       }
00213       if (m[0] == a_)
00214         result.push_back(PartialExp<Series, T>(exp_));
00215     }
00216 
00217     virtual void
00218     zero()
00219     {
00220       result = return_type();
00221     }
00222 
00223     virtual void
00224     one()
00225     {
00226       result = return_type();
00227     }
00228 
00229   public:
00230     bool                        undefined;
00231     return_type                 result;
00232 
00233   private:
00234     const exp_t&                exp_;
00235     const letter_t&             a_;
00236     const typename T::node_t*   father_;
00237   };
00238 
00239 
00240 /*****************************************************************************/
00241 /***************************** User's functions ******************************/
00242 /*****************************************************************************/
00243 
00244   template <class Series, class T, class Letter>
00245   std::pair<std::list<PartialExp<Series, T> >, bool>
00246   prat_exp_derivate(const Element<Series, T>& exp,
00247                     Letter a)
00248   {
00249     PRatExpDerivationVisitor<Series, T> visitor(exp, a);
00250     visitor.match(exp.value().base());
00251     return std::make_pair(visitor.result, !visitor.undefined);
00252   }
00253 
00254   template <class Series, class T, class Letter>
00255   std::pair<std::list<PartialExp<Series, T> >, bool>
00256   prat_exp_derivate(const PartialExp<Series, T>& exp,
00257                     Letter a)
00258   {
00259     typedef PartialExp<Series, T>                       exp_t;
00260     typedef std::list<PartialExp<Series, T> >           exp_list_t;
00261     typedef std::pair<exp_list_t, bool>                 return_type;
00262     typedef typename exp_t::const_iterator              const_iterator;
00263     typedef typename Element<Series, T>::semiring_elt_t semiring_elt_t;
00264     typedef typename semiring_elt_t::value_t            semiring_elt_value_t;
00265     typedef T                                           series_set_elt_value_t;
00266 
00267     // Save the first weight, and go to the first expression
00268     const_iterator i = exp.begin();
00269     semiring_elt_t w = i.semiring_elt();
00270     i++;
00271 
00272     // Check if the exp is not empty
00273     if (i == exp.end())
00274       return std::make_pair(exp_list_t(), true);
00275 
00276     // Visit the first element of the exp
00277     PRatExpDerivationVisitor<Series, T> visitor(exp.exp(), a);
00278     const typename exp_t::node_t*       n = i.node();
00279     visitor.match(n);
00280 
00281     // Insert other pointers and values into the result
00282     for (i++; i != exp.end(); ++i)
00283       if (i.on_node())
00284         list_insert_here(visitor.result, i.node());
00285       else
00286         list_multiply_here_right(visitor.result, i.semiring_elt());
00287 
00288     // Calculate the constant term
00289     std::pair<semiring_elt_t, bool> cterm =
00290       constant_term(Element<Series, T>(exp.exp_structure(), series_set_elt_value_t(n)));
00291     if (cterm.second == false)
00292       return std::make_pair(exp_list_t(), false);
00293 
00294     // --------  If cterm != 0, look at the rest of the list  ---------------
00295     if (cterm.first !=
00296         exp.exp_structure().semiring().zero(SELECT(semiring_elt_value_t)) )
00297     {
00298       // Build an exp from the orignal, without the head
00299       exp_t new_exp(exp);
00300       new_exp.nodes().pop_front();
00301       new_exp.weights().pop_front();
00302 
00303       // Recall prat_exp_derivate on it
00304       return_type ret = prat_exp_derivate(new_exp, a);
00305 
00306       // Multiply by constant term
00307       list_multiply_here_left(ret.first, cterm.first);
00308 
00309       // Fusion results
00310       visitor.undefined = visitor.undefined || !ret.second;
00311       list_fusion_here(visitor.result, ret.first);
00312     }
00313     //------------------------------------------------------------------------
00314 
00315     // Multiply by the weight of exp
00316     list_multiply_here_left(visitor.result, w);
00317 
00318     // Return the final result
00319     return std::make_pair(visitor.result, !visitor.undefined);
00320   }
00321 
00322 } // vcsn
00323 
00324 #endif // ! VCSN_ALGORITHMS_INTERNAL_PARTIAL_RAT_EXP_DERIVATION_HXX

Generated on Sun Jul 29 19:35:28 2007 for Vaucanson by  doxygen 1.5.2