Vaucanson: krat.hxx Source File

00001 // krat.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 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_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_HXX
00018 # define VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_HXX
00019 
00020 # include <utility>
00021 # include <list>
00022 
00023 # include <vaucanson/algebra/implementation/series/series.hh>
00024 # include <vaucanson/algebra/implementation/series/rat/exp.hh>
00025 # include <vaucanson/algebra/implementation/series/rat/random_visitor.hh>
00026 # include <vaucanson/misc/usual_macros.hh>
00027 
00028 # include <vaucanson/algebra/implementation/series/krat_exp_is_finite_app.hxx>
00029 # include <vaucanson/algebra/implementation/series/krat_exp_support.hxx>
00030 # include <vaucanson/algebra/implementation/series/krat_exp_transpose.hxx>
00031 
00032 # include <vaucanson/algorithms/eval.hh>
00033 # include <vaucanson/algorithms/standard_of.hh>
00034 
00035 # include <vaucanson/algebra/implementation/series/polynoms.hh>
00036 # include <vaucanson/automata/concept/automata.hh>
00037 
00038 # ifdef VCSN_GRAPH_IMPL
00039 #
00040 #  include GRAPH_IMPL_HEADER
00041 #
00042 # else
00043 #
00044 #  include <vaucanson/config/pconf.hh>
00045 #  define VCSN_GRAPH_IMPL_INCLUDE_PATH vaucanson/automata/implementation
00046 #  define VCSN_CONTEXT_INCLUDE_PATH vaucanson/contexts
00047 #  include GRAPH_DEFAULT_IMPL_HEADER
00048 #
00049 #  define VCSN_GRAPH_IMPL VCSN_DEFAULT_GRAPH_IMPL
00050 #  define UNDEF_VCSN_GRAPH_IMPL
00051 #
00052 # endif
00053 # include <vaucanson/misc/contract.hh>
00054 
00055 
00056 namespace vcsn {
00057   namespace algebra {
00072   template<typename W, typename M, typename Tm, typename Tw>
00073   bool op_contains(const algebra::Series<W, M>&, const rat::exp<Tm, Tw>&)
00074   {
00075     pure_service_call ("default version of op_contains(Series<W,M>, exp<Tm,Tw>)");
00076     return true;
00077   }
00078 
00079   template<typename W, typename M, typename Tm, typename Tw>
00080   bool op_is_finite_app(const algebra::Series<W, M>&,
00081                         const rat::exp<Tm, Tw>& m)
00082   {
00083     vcsn::IsFiniteAppMatcher<algebra::Series<W, M>,
00084       vcsn::rat::exp<Tm, Tw>,
00085       algebra::DispatchFunction<vcsn::rat::exp<Tm, Tw> > > matcher;
00086     return matcher.match(m);
00087   }
00088 
00089   template<typename W, typename M, typename Tm, typename Tw>
00090   typename algebra::series_traits<rat::exp<Tm, Tw> >::support_t
00091   op_support(const algebra::Series<W, M>& s, const rat::exp<Tm, Tw>& m)
00092   {
00093     vcsn::SupportMatcher<algebra::Series<W, M>, rat::exp<Tm, Tw>,
00094       algebra::DispatchFunction<rat::exp<Tm, Tw> > > matcher(s);
00095     matcher.match(m);
00096     return matcher.get();
00097   }
00098 
00099   template <typename W, typename M, typename Tm, typename Tw>
00100   Tm op_choose_from_supp(const algebra::Series<W, M>&,
00101                          const rat::exp<Tm, Tw>& m)
00102   {
00103     rat::RandomVisitor<Tm, Tw> v;
00104     m.accept(v);
00105     return v.get();
00106   }
00107 
00108   template<typename W, typename M, typename Tm, typename Tw>
00109   const rat::exp<Tm, Tw>& identity_value(SELECTOR2(algebra::Series<W, M>),
00110                                          SELECTOR2(rat::exp<Tm, Tw>))
00111   {
00112     static const rat::exp<Tm, Tw> instance = rat::exp<Tm, Tw>::one();
00113     return instance;
00114   }
00115 
00116   template<typename W, typename M, typename Tm, typename Tw>
00117   const rat::exp<Tm, Tw>& zero_value(SELECTOR2(algebra::Series<W, M>),
00118                                      SELECTOR2(rat::exp<Tm, Tw>))
00119   {
00120     static const rat::exp<Tm, Tw> instance = rat::exp<Tm, Tw>::zero();
00121     return instance;
00122   }
00123 
00124   template <typename W, typename M, typename Tm, typename Tw>
00125   void op_in_transpose(const algebra::Series<W, M>& s,
00126                        rat::exp<Tm, Tw>& exp)
00127   {
00128     Element<algebra::Series<W, M>,
00129       rat::exp<Tm, Tw> > elt(s, exp);
00130 
00131     vcsn::algebra::KRatExpTranspose<
00132       algebra::Series<W, M>,
00133       rat::exp<Tm, Tw>,
00134       algebra::DispatchFunction<vcsn::rat::exp<Tm, Tw> >
00135       > matcher(elt);
00136 
00137     elt = matcher.match(exp);
00138     exp = elt.value();
00139   }
00140 
00141 
00142   template<typename W, typename M, typename Tm, typename Tw>
00143   void op_in_add(const algebra::Series<W, M>&,
00144                  rat::exp<Tm, Tw>& dst,
00145                  const rat::exp<Tm, Tw>& arg)
00146   {
00147     // case any + 0
00148     if (arg.base()->what() == rat::Node<Tm, Tw>::zero)
00149       return ;
00150 
00151     // case 0 + any
00152     if (dst.base()->what() == rat::Node<Tm, Tw>::zero)
00153       {
00154         delete dst.base();
00155         dst.base() = arg.base()->clone();
00156         return;
00157       }
00158 
00159     dst.base() = new rat::Sum<Tm, Tw>(dst.base(), arg.base()->clone());
00160   }
00161 
00162   template<typename W, typename M, typename Tm, typename Tw>
00163   rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00164                           const rat::exp<Tm, Tw>& a,
00165                           const rat::exp<Tm, Tw>& b)
00166   {
00167     rat::exp<Tm, Tw> ret(a);
00168     op_in_add(s, ret, b);
00169     return ret;
00170   }
00171 
00172   template<typename W, typename M, typename Tm, typename Tw>
00173   void op_in_mul(const algebra::Series<W, M>& s,
00174                  rat::exp<Tm, Tw>& dst,
00175                  const rat::exp<Tm, Tw>& arg)
00176   {
00177     typedef rat::Node<Tm, Tw>                   node_t;
00178     typedef typename  rat::Node<Tm, Tw>::type   type;
00179     typedef rat::One<Tm, Tw>                    n_one_t;
00180     typedef rat::Constant<Tm, Tw>               n_const_t;
00181     typedef rat::Zero<Tm, Tw>                   n_zero_t;
00182     typedef rat::Star<Tm, Tw>                   n_star_t;
00183     typedef rat::LeftWeighted<Tm, Tw>           n_lweight_t;
00184     typedef rat::RightWeighted<Tm, Tw>          n_rweight_t;
00185     typedef rat::Sum<Tm, Tw>                    n_sum_t;
00186     typedef rat::Product<Tm, Tw>                n_prod_t;
00187 
00188     type this_type = dst.base()->what();
00189     type arg_type  = arg.base()->what();
00190 
00191     // case 0 * E -> 0
00192     if (this_type == node_t::zero)
00193       return;
00194 
00195     // case E * 0 -> 0
00196     if (arg_type == node_t::zero)
00197       {
00198         delete dst.base();
00199         dst.base() = new n_zero_t;
00200         return;
00201       }
00202 
00203     // case 1 * E -> E
00204     if (this_type == node_t::one)
00205       {
00206         delete dst.base();
00207         dst.base() = arg.base()->clone();
00208         return;
00209       }
00210 
00211     // case E * 1 -> E
00212     if (arg_type == node_t::one)
00213       {
00214         return;
00215       }
00216 
00217     // case E * (k' 1) -> E k'
00218     if (arg_type == node_t::lweight)
00219     {
00220       n_lweight_t *p = dynamic_cast<n_lweight_t*>(arg.base());
00221       if (p->child_->what() == node_t::one)
00222       {
00223         op_in_mul(s, s.semiring(), dst, p->weight_);
00224         return;
00225       }
00226     }
00227 
00229     /*
00230     // case (k E) * E' -> k (E * E')
00231     // it manages case (k 1) * E' -> k E'
00232     if (this_type == node_t::lweight)
00233     {
00234       n_lweight_t *p = dynamic_cast<n_lweight_t*>(dst.base());
00235       if (p->child_->what() == node_t::one)
00236         // case (k 1) * E' -> k E'
00237         dst = op_mul(s.semiring(), s, p->weight_, arg);
00238       else
00239         // case (k E) * E' -> k (E * E')
00240         p->child_ = new n_prod_t(p->child_, arg.base()->clone());
00241       return;
00242     }
00243 
00244     // case E * (E' k') -> (E * E') k'
00245     if (arg_type == node_t::rweight)
00246     {
00247       n_rweight_t *p = dynamic_cast<n_rweight_t*>(arg.base());
00248       dst.base() = new n_rweight_t(p->weight_,
00249         new n_prod_t(dst.base(), p->child_->clone()));
00250       return;
00251     }
00252     */
00253 
00254     // case (k 1) * E' -> k E'
00255     if (this_type == node_t::lweight)
00256     {
00257       n_lweight_t *p = dynamic_cast<n_lweight_t*>(dst.base());
00258       if (p->child_->what() == node_t::one)
00259       {
00260         dst = op_mul(s.semiring(), s, p->weight_, arg);
00261         return;
00262       }
00263     }
00264 
00265     // general case
00266     dst.base() = new n_prod_t(dst.base(), arg.base()->clone());
00267     return;
00268   }
00269 
00270   template<typename W, typename M, typename Tm, typename Tw>
00271   rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00272                           const rat::exp<Tm, Tw>& a,
00273                           const rat::exp<Tm, Tw>& b)
00274   {
00275     rat::exp<Tm, Tw> ret(a);
00276     op_in_mul(s, ret, b);
00277     return ret;
00278   }
00279 
00280 
00281   /*---------------------.
00282     | foreign constructors |
00283     `---------------------*/
00284 
00285   template<typename Tm, typename Tw, typename M, typename W>
00286   rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<M, W>),
00287                               SELECTOR2(rat::exp<Tm, Tw>),
00288                               const Tm& m_value)
00289   {
00290     return new rat::Constant<Tm, Tw>(m_value);
00291   }
00292 
00293   template<typename Tm, typename Tw, typename M, typename W>
00294   rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<M, W>),
00295                               SELECTOR2(rat::exp<Tm, Tw>),
00296                               char m_value)
00297   {
00298     const char str[] = {m_value, '\0'};
00299     return new rat::Constant<Tm, Tw>(str);
00300   }
00301 
00302   template<typename Tm, typename Tw, typename W, typename M, typename oTm>
00303   rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>) s,
00304                               SELECTOR2(rat::exp<Tm, Tw>),
00305                               SELECTOR(M),
00306                               const oTm& m_value)
00307   {
00308     // FIXME: this is completely broken. It should break up m_value
00309     // into letters.
00310     if (m_value == identity_value(SELECT(M), SELECT(oTm)))
00311       return rat::exp<Tm, Tw>::one();
00312     return rat::exp<Tm, Tw>::constant(op_convert(s.monoid(), SELECT(Tm),
00313                                                  m_value));
00314   }
00315 
00316   template<typename Tm, typename Tw, typename W, typename M, typename oTw>
00317   rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00318                               SELECTOR2(rat::exp<Tm, Tw>),
00319                               SELECTOR(W),
00320                               const oTw& w_value)
00321   {
00322     if (w_value == identity_value(SELECT(W), SELECT(oTw)))
00323       return rat::exp<Tm, Tw>::one();
00324     if (w_value == zero_value(SELECT(W), SELECT(oTw)))
00325       return rat::exp<Tm, Tw>::zero();
00326     rat::exp<Tm, Tw> ret = rat::exp<Tm, Tw>::one();
00327     ret.base() = new rat::LeftWeighted<Tm, Tw>
00328       (op_convert(SELECT(W), SELECT(Tw),
00329                   w_value), ret.base());
00330     return ret;
00331   }
00332 
00333   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00334   void op_assign(const algebra::Series<W, M>&,
00335                  const M&,
00336                  rat::exp<Tm, Tw>& dst,
00337                  const oTm& src)
00338   {
00339     // FIXME: this is completely broken also.
00340 
00341     if (src == identity_value(SELECT(M), SELECT(oTm)))
00342       dst = rat::exp<Tm, Tw>::one();
00343     else
00344       dst = rat::exp<Tm, Tw>::constant(src);
00345   }
00346 
00347   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00348   void op_assign(const algebra::Series<W, M>&,
00349                  const W& semiring,
00350                  rat::exp<Tm, Tw>& dst,
00351                  const oTw& src)
00352   {
00353     dst = op_convert
00354       (SELECT2(algebra::Series<W, M>), SELECT2(rat::exp<Tm, Tw>), SELECT(W), src);
00355   }
00356 
00357   /*-----.
00358     | star |
00359     `-----*/
00360 
00361   template<typename W, typename M, typename Tm, typename Tw>
00362   bool op_starable(const algebra::Series<W, M>&,
00363                     const rat::exp<Tm, Tw>&)
00364   {
00365     return true;
00366   }
00367 
00368   template<typename W, typename M, typename Tm, typename Tw>
00369   void op_in_star(const algebra::Series<W, M>&,
00370                   rat::exp<Tm, Tw>& dst)
00371   {
00372     if (dst.base()->what() == rat::Node<Tm, Tw>::zero)
00373       dst = rat::exp<Tm, Tw>::one();
00374     else
00375       dst.base() = new rat::Star<Tm, Tw>(dst.base());
00376   }
00377 
00378   template<typename W, typename M, typename Tm, typename Tw>
00379   rat::exp<Tm, Tw>
00380   op_star(const algebra::Series<W, M>&,
00381           const rat::exp<Tm, Tw>& src)
00382   {
00383     if (src.base()->what() == rat::Node<Tm, Tw>::zero)
00384       return rat::exp<Tm, Tw>::one();
00385     rat::exp<Tm, Tw> ret(src);
00386     ret.base() = new rat::Star<Tm, Tw>(ret.base());
00387     return ret;
00388   }
00389 
00390 
00391   /*--------------------------------------.
00392     | foreign addition with monoid elements |
00393     `--------------------------------------*/
00394 
00395   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00396   void op_in_add(const algebra::Series<W, M>& s,
00397                  const M& monoid,
00398                  rat::exp<Tm, Tw>& dst,
00399                  const oTm& src)
00400   {
00401     op_in_add(s, dst, op_convert(SELECT2(algebra::Series<W, M>),
00402                                  SELECT2(rat::exp<Tm, Tw>),
00403                                  SELECT(M),
00404                                  src));
00405   }
00406 
00407   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00408   rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00409                           const M& monoid,
00410                           const rat::exp<Tm, Tw>& a,
00411                           const oTm& b)
00412   {
00413     rat::exp<Tm, Tw> ret(a);
00414     op_in_add(s, monoid, ret, b);
00415     return ret;
00416   }
00417 
00418   template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00419   rat::exp<Tm, Tw> op_add(const M& monoid,
00420                           const algebra::Series<W, M>& s,
00421                           const oTm& a,
00422                           const rat::exp<Tm, Tw>& b)
00423   {
00424     rat::exp<Tm, Tw> ret(b);
00425     op_in_add(s, monoid, ret, a);
00426     return ret;
00427   }
00428 
00429   /*---------------------------------------.
00430     | foreign addition with semiring elements |
00431     `---------------------------------------*/
00432 
00433   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00434   void op_in_add(const algebra::Series<W, M>& s,
00435                  const W& semiring,
00436                  rat::exp<Tm, Tw>& dst,
00437                  const oTw& src)
00438   {
00439     precondition(& s.semiring() == & semiring);
00440     op_in_add(s, dst, op_convert(SELECT2(algebra::Series<W, M>),
00441                                  SELECT2(rat::exp<Tm, Tw>),
00442                                  SELECT(W),
00443                                  src));
00444   }
00445 
00446   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00447   rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00448                           const W& semiring,
00449                           const rat::exp<Tm, Tw>& a,
00450                           const oTw& b)
00451   {
00452     rat::exp<Tm, Tw> ret(a);
00453     op_in_add(s, semiring, ret, b);
00454     return ret;
00455   }
00456 
00457   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00458   rat::exp<Tm, Tw> op_add(const W& semiring,
00459                           const algebra::Series<W, M>& s,
00460                           const oTw& a,
00461                           const rat::exp<Tm, Tw>& b)
00462   {
00463     rat::exp<Tm, Tw> ret(b);
00464     op_in_add(s, semiring, ret, a);
00465     return ret;
00466   }
00467 
00468   /*-------------------------------------------.
00469     | foreign multiplication by semiring elements |
00470     `-------------------------------------------*/
00471 
00472   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00473   void op_in_mul(const algebra::Series<W, M>& s,
00474                  const W& semiring,
00475                  rat::exp<Tm, Tw>& ret,
00476                  const oTw& w)
00477   {
00478     precondition(& s.semiring() == & semiring);
00479     (void) s; (void) semiring;
00480 
00481     typedef rat::Node<Tm, Tw>                           node_t;
00482     typedef typename rat::Node<Tm, Tw>::type            type;
00483     typedef rat::One<Tm, Tw>                            n_one_t;
00484     typedef rat::Constant<Tm, Tw>                       n_const_t;
00485     typedef rat::Zero<Tm, Tw>                           n_zero_t;
00486     typedef rat::Star<Tm, Tw>                           n_star_t;
00487     typedef rat::LeftWeighted<Tm, Tw>                   n_lweight_t;
00488     typedef rat::RightWeighted<Tm, Tw>                  n_rweight_t;
00489     typedef rat::Sum<Tm, Tw>                            n_sum_t;
00490     typedef rat::Product<Tm, Tw>                        n_prod_t;
00491 
00492     type this_type = ret.base()->what();
00493 
00494     // case 0 * k -> 0
00495     if (this_type == node_t::zero)
00496       return;
00497 
00498     // case E * 1 -> E
00499     if (w == identity_value(SELECT(W), SELECT(oTw)))
00500       return;
00501 
00502     // case E * 0 -> 0
00503     if (w == zero_value(SELECT(W), SELECT(oTw)))
00504       {
00505         delete ret.base();
00506         ret.base() = new n_zero_t;
00507         return;
00508       }
00509 
00510     // case 1 * k -> k * 1
00511     if (this_type == node_t::one)
00512       {
00513         ret.base() = new n_lweight_t
00514           (op_convert(SELECT(W), SELECT(Tw), w), ret.base());
00515         return;
00516       }
00517 
00519     /*
00520     // case (k' 1) * k -> [k' k] 1
00521     if (this_type == node_t::lweight)
00522       {
00523         n_lweight_t* p = dynamic_cast<n_lweight_t*>(ret.base());
00524         type child_type = p->child_->what();
00525 
00526         if (child_type == node_t::one)
00527           {
00528             op_in_mul
00529               (s.semiring(), p->weight_, op_convert(SELECT(W), SELECT(Tw), w));
00530             return;
00531           }
00532       }
00533 
00534     // case (k' E) * k -> general case
00535 
00536     // case (E k') * k -> E [k' k]
00537     if (this_type == node_t::rweight)
00538       {
00539         op_in_mul(s.semiring(),
00540                   dynamic_cast<n_rweight_t* >(ret.base())
00541                   ->weight_, op_convert(SELECT(W), SELECT(Tw), w));
00542         return;
00543       }
00544     */
00545 
00546     // general case
00547     ret.base() =
00548       new n_rweight_t(op_convert(SELECT(W), SELECT(Tw), w), ret.base());
00549     return;
00550   }
00551 
00552   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00553   rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00554                           const W& semiring,
00555                           const rat::exp<Tm, Tw>& a,
00556                           const oTw& w)
00557   {
00558     rat::exp<Tm, Tw> ret(a);
00559     op_in_mul(s, semiring, ret, w);
00560     return ret;
00561   }
00562 
00563   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00564   rat::exp<Tm, Tw> op_mul(const W& semiring,
00565                           const algebra::Series<W, M>& s,
00566                           const oTw& w,
00567                           const rat::exp<Tm, Tw>& b)
00568   {
00569     precondition(& s.semiring() == & semiring);
00570     (void) s; (void) semiring;
00571 
00572     typedef rat::Node<Tm, Tw>                           node_t;
00573     typedef typename rat::Node<Tm, Tw>::type            type;
00574     typedef rat::One<Tm, Tw>                            n_one_t;
00575     typedef rat::Constant<Tm, Tw>                       n_const_t;
00576     typedef rat::Zero<Tm, Tw>                           n_zero_t;
00577     typedef rat::Star<Tm, Tw>                           n_star_t;
00578     typedef rat::LeftWeighted<Tm, Tw>                   n_lweight_t;
00579     typedef rat::RightWeighted<Tm, Tw>                  n_rweight_t;
00580     typedef rat::Sum<Tm, Tw>                            n_sum_t;
00581     typedef rat::Product<Tm, Tw>                        n_prod_t;
00582 
00583     rat::exp<Tm, Tw> ret(b);
00584 
00585     type this_type = ret.base()->what();
00586 
00587     // case k * 0 -> 0
00588     if (this_type == node_t::zero)
00589       return ret;
00590 
00591     // case k * 1 -> general case
00592 
00593     // case 0 * E -> 0
00594     if (w == zero_value(SELECT(W), SELECT(oTw)))
00595       { return rat::exp<Tm, Tw>::zero(); }
00596 
00597     // case 1 * E -> E
00598     if (w == identity_value(SELECT(W), SELECT(oTw)))
00599       return ret;
00600 
00602     /*
00603     // case k * (k' E) -> [k k'] E
00604     if (this_type == node_t::lweight)
00605       {
00606         n_lweight_t* p = dynamic_cast<n_lweight_t*>(ret.base());
00607         p->weight_ = op_mul
00608           (s.semiring(), op_convert(SELECT(W), SELECT(Tw), w), p->weight_);
00609         return ret;
00610       }
00611 
00612     // case k * (E k') -> (k E) k'
00613     if (this_type == node_t::rweight)
00614       {
00615         n_rweight_t* p = dynamic_cast<n_rweight_t*>(ret.base());
00616         p->child_ =
00617           new n_lweight_t(op_convert(SELECT(W), SELECT(Tw), w), p->child_);
00618         return ret;
00619       }
00620     */
00621 
00622     // general case
00623     ret.base() = new n_lweight_t(w, ret.base());
00624     return ret;
00625   }
00626 
00627   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00628   Tw op_series_get(const algebra::Series<W, M>& s,
00629                    const rat::exp<Tm, Tw>& p,
00630                    const oTm& m)
00631   {
00632     typedef typename algebra::Series<W,M>               series_set_t;
00633     typedef typename algebra::polynom<Tm, Tw>           series_set_elt_value_t;
00634     typedef typename rat::exp<Tm, Tw>                   exp_t;
00635     typedef VCSN_GRAPH_IMPL::Graph
00636       <
00637       labels_are_series,
00638       Tm,
00639       Tw,
00640       series_set_elt_value_t,
00641       Tm,
00642       NoTag,
00643       NoTag
00644       >
00645       automaton_impl_t;
00646     typedef Element<Automata<series_set_t>, automaton_impl_t>   automaton_t;
00647 
00648     typename automaton_t::set_t automata (s);
00649     automaton_t                 a (automata);
00650     standard_of(a, p);
00651     return eval(a, m).value();
00652   }
00653 
00654   template<typename W, typename M, typename Tm, typename Tw,
00655            typename oTm, typename oTw>
00656   void op_series_set(const algebra::Series<W, M>& s,
00657                      rat::exp<Tm, Tw>& p,
00658                      const oTm& m,
00659                      const oTw& w)
00660   {
00661     if ((m == algebra::identity_as<oTm>::of(s.monoid())) &&
00662         (w == algebra::identity_as<oTw>::of(s.semiring())) &&
00663         (p == algebra::zero_as<rat::exp<Tm, Tw> >::of(s)))
00664       {
00665         p = algebra::identity_as<rat::exp<Tm, Tw> >::of(s).value();
00666         return ;
00667       }
00668 
00669     typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> >   series_set_elt_t;
00670     typedef typename series_set_elt_t::monoid_elt_t             monoid_elt_t;
00671     typedef typename monoid_elt_t::value_t                      monoid_elt_value_t;
00672     typedef std::list<monoid_elt_value_t>                       support_t;
00673 
00674     rat::exp<Tm, Tw> pp = p;
00675     p = algebra::zero_as<rat::exp<Tm, Tw> >::of(s).value();
00676 
00677     // FIXME Should not rebuild the serie from stratch
00678     // Should use some kind of visitor and update the tree
00679     support_t supp = op_support(s, pp);
00680     oTw sw;
00681     bool exist = false;
00682     for_all_const_(support_t, e, supp)
00683     {
00684       rat::exp<Tm, Tw> ret =
00685         rat::exp<Tm, Tw>::constant(op_convert(s.monoid(),
00686                                               SELECT(Tm),
00687                                               *e));
00688       if (*e == m)
00689       {
00690         exist = true;
00691         sw = w;
00692       }
00693       else
00694         sw = op_series_get(s, pp, *e);
00695       op_in_add(s, p, op_mul(s.semiring(), s, sw, ret));
00696     }
00697     if (!exist)
00698       op_in_add(s, p, op_mul(s.semiring(), s, w,
00699                 rat::exp<Tm, Tw>::constant(op_convert(s.monoid(),
00700                                                       SELECT(Tm),
00701                                                       m))));
00702   }
00703   }//algebra
00704 
00705   /*----------------------------------------------------------.
00706     | MetaElement<algebra::SeriesBase<algebra::Series<W, M> >, rat::exp<Tm, Tw> > |
00707     `----------------------------------------------------------*/
00708 
00709   template <typename W, typename M, typename Tm, typename Tw>
00710   void
00711   MetaElement<algebra::Series<W, M>, rat::exp<Tm, Tw> >::accept
00712   (const rat::ConstNodeVisitor<Tm, Tw>& v) const
00713   {
00714     this->value().accept(v);
00715   }
00716 
00717   template <typename W, typename M, typename Tm, typename Tw>
00718   size_t
00719   MetaElement<algebra::Series<W, M>, rat::exp<Tm, Tw> >::depth() const
00720   {
00721     return this->value().depth();
00722   }
00723 
00724   namespace algebra {
00725 
00726     template <class W, class M, class Tm, class Tw>
00727     Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >
00728     op_choose(const algebra::Series<W,M>& s,
00729         SELECTOR2(rat::exp<Tm,Tw>))
00730     {
00731       Element<algebra::Series<W,M>, rat::exp<Tm, Tw> > e(s);
00732       // FIXME : add global constants to do this !
00733       unsigned nb = RAND___(10);
00734       while (nb != 0)
00735       {
00736         --nb;
00737         unsigned t = RAND___(3);
00738         switch (t)
00739         {
00740           // star
00741           case 0 :
00742             {
00743               e = e.star();
00744               continue;
00745             }
00746             // plus
00747           case 1 :
00748             {
00749               Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >
00750                 ep(s, s.monoid().choose(SELECT(Tm)));
00751               ep = ep * s.semiring().choose(SELECT(Tw));
00752               unsigned t = RAND___(2);
00753               if (t < 1)
00754                 e = e + ep;
00755               else
00756                 e = ep + e;
00757               continue;
00758             }
00759             // mult
00760           case 2 :
00761             {
00762               Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >
00763                 ep(s, s.monoid().choose(SELECT(Tm)));
00764               ep = ep * s.semiring().choose(SELECT(Tw));
00765               unsigned t = RAND___(2);
00766               if (t < 1)
00767                 e = e * ep;
00768               else
00769                 e = ep * e;
00770               continue;
00771             }
00772         }
00773       }
00774       return Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >(s, e);
00775     }
00776   } //algebra
00777 } // vcsn
00778 
00779 #ifdef UNDEF_VCSN_GRAPH_IMPL
00780 # undef VCSN_GRAPH_IMPL
00781 # undef UNDEF_VCSN_GRAPH_IMPL
00782 #endif
00783 
00784 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_HXX