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