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