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       if (m_value == identity_value(SELECT(M), SELECT(oTm)))
00283         return rat::exp<Tm, Tw>::one();
00284 
00285       return rat::exp<Tm, Tw>::constant(op_convert(s.monoid(), SELECT(Tm),
00286                                                    m_value));
00287     }
00288 
00289     template<typename Tm, typename Tw, typename W, typename M, typename oTw>
00290     rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00291                                 SELECTOR2(rat::exp<Tm, Tw>),
00292                                 SELECTOR(W),
00293                                 const oTw& w_value)
00294     {
00295       if (w_value == identity_value(SELECT(W), SELECT(oTw)))
00296         return rat::exp<Tm, Tw>::one();
00297       if (w_value == zero_value(SELECT(W), SELECT(oTw)))
00298         return rat::exp<Tm, Tw>::zero();
00299       rat::exp<Tm, Tw> ret = rat::exp<Tm, Tw>::one();
00300       ret.base() = new rat::LeftWeighted<Tm, Tw>
00301       (op_convert(SELECT(W), SELECT(Tw),
00302                   w_value), ret.base());
00303       return ret;
00304     }
00305 
00306     template <typename W, typename M, typename Tm, typename Tw, typename oTm>
00307     void op_assign(SELECTOR2(algebra::Series<W, M>) s,
00308                    SELECTOR(M),
00309                    rat::exp<Tm, Tw>& dst,
00310                    const oTm& src)
00311     {
00312       dst = op_convert(s,
00313                        SELECT2(rat::exp<Tm, Tw>),
00314                        SELECT(M), src);
00315     }
00316 
00317     template <typename W, typename M, typename Tm, typename Tw, typename oTw>
00318     void op_assign(SELECTOR2(algebra::Series<W, M>) s,
00319                    SELECTOR(W),
00320                    rat::exp<Tm, Tw>& dst,
00321                    const oTw& src)
00322     {
00323       dst = op_convert(s,
00324                        SELECT2(rat::exp<Tm, Tw>),
00325                        SELECT(W), src);
00326     }
00327 
00328     /*-----.
00329     | star |
00330     `-----*/
00331 
00332     template<typename W, typename M, typename Tm, typename Tw>
00333     bool op_starable(const algebra::Series<W, M>&,
00334                      const rat::exp<Tm, Tw>&)
00335     {
00336       return true;
00337     }
00338 
00339     template<typename W, typename M, typename Tm, typename Tw>
00340     void op_in_star(const algebra::Series<W, M>&,
00341                     rat::exp<Tm, Tw>& dst)
00342     {
00343       // rewrite 0* as 1
00344       if (dst.base()->what() == rat::Node<Tm, Tw>::zero)
00345         dst = rat::exp<Tm, Tw>::one();
00346       else
00347         dst.base() = new rat::Star<Tm, Tw>(dst.base());
00348     }
00349 
00350     template<typename W, typename M, typename Tm, typename Tw>
00351     rat::exp<Tm, Tw>
00352     op_star(const algebra::Series<W, M>& s,
00353             const rat::exp<Tm, Tw>& src)
00354     {
00355       rat::exp<Tm, Tw> ret(src);
00356       op_in_star(s, ret);
00357       return ret;
00358     }
00359 
00360     /*--------------------------------------.
00361     | foreign addition with monoid elements |
00362     `--------------------------------------*/
00363 
00364     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00365     void op_in_add(const algebra::Series<W, M>& s,
00366                    const M& monoid,
00367                    rat::exp<Tm, Tw>& dst,
00368                    const oTm& src)
00369     {
00370       op_in_add(s, dst, op_convert(s,
00371                                    SELECT2(rat::exp<Tm, Tw>),
00372                                    SELECT(M),
00373                                    src));
00374     }
00375 
00376     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00377     rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00378                             const M& monoid,
00379                             const rat::exp<Tm, Tw>& a,
00380                             const oTm& b)
00381     {
00382       rat::exp<Tm, Tw> ret(a);
00383       op_in_add(s, monoid, ret, b);
00384       return ret;
00385     }
00386 
00387     template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00388     rat::exp<Tm, Tw> op_add(const M& monoid,
00389                             const algebra::Series<W, M>& s,
00390                             const oTm& a,
00391                             const rat::exp<Tm, Tw>& b)
00392     {
00393       rat::exp<Tm, Tw> ret(b);
00394       op_in_add(s, monoid, ret, a);
00395       return ret;
00396     }
00397 
00398     /*----------------------------------------.
00399     | foreign addition with semiring elements |
00400     `----------------------------------------*/
00401 
00402     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00403     void op_in_add(const algebra::Series<W, M>& s,
00404                    const W& semiring,
00405                    rat::exp<Tm, Tw>& dst,
00406                    const oTw& src)
00407     {
00408       precondition(& s.semiring() == & semiring);
00409       op_in_add(s, dst, op_convert(s,
00410                                    SELECT2(rat::exp<Tm, Tw>),
00411                                    SELECT(W),
00412                                    src));
00413     }
00414 
00415     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00416     rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00417                             const W& semiring,
00418                             const rat::exp<Tm, Tw>& a,
00419                             const oTw& b)
00420     {
00421       rat::exp<Tm, Tw> ret(a);
00422       op_in_add(s, semiring, ret, b);
00423       return ret;
00424     }
00425 
00426     template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00427     rat::exp<Tm, Tw> op_add(const W& semiring,
00428                             const algebra::Series<W, M>& s,
00429                             const oTw& a,
00430                             const rat::exp<Tm, Tw>& b)
00431     {
00432       rat::exp<Tm, Tw> ret(b);
00433       op_in_add(s, semiring, ret, a);
00434       return ret;
00435     }
00436 
00437     /*--------------------------------------------.
00438     | foreign multiplication by semiring elements |
00439     `--------------------------------------------*/
00440 
00441     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00442     void op_in_mul(const algebra::Series<W, M>& s,
00443                    const W& semiring,
00444                    rat::exp<Tm, Tw>& ret,
00445                    const oTw& w)
00446     {
00447       precondition(& s.semiring() == & semiring);
00448       (void) s; (void) semiring;
00449 
00450       typedef rat::Node<Tm, Tw>                         node_t;
00451       typedef typename rat::Node<Tm, Tw>::type          type;
00452       typedef rat::One<Tm, Tw>                          n_one_t;
00453       typedef rat::Constant<Tm, Tw>                     n_const_t;
00454       typedef rat::Zero<Tm, Tw>                         n_zero_t;
00455       typedef rat::Star<Tm, Tw>                         n_star_t;
00456       typedef rat::LeftWeighted<Tm, Tw>                 n_lweight_t;
00457       typedef rat::RightWeighted<Tm, Tw>                n_rweight_t;
00458       typedef rat::Sum<Tm, Tw>                          n_sum_t;
00459       typedef rat::Product<Tm, Tw>                      n_prod_t;
00460 
00461       type this_type = ret.base()->what();
00462 
00463       // case 0 {k} -> 0
00464       if (this_type == node_t::zero)
00465         return;
00466 
00467       // case E {1} -> E
00468       if (w == identity_value(SELECT(W), SELECT(oTw)))
00469         return;
00470 
00471       // case E {0} -> 0
00472       if (w == zero_value(SELECT(W), SELECT(oTw)))
00473       {
00474         delete ret.base();
00475         ret.base() = new n_zero_t;
00476         return;
00477       }
00478 
00479       // case 1 {k} -> {k} 1
00480       if (this_type == node_t::one)
00481       {
00482         ret.base() = new n_lweight_t
00483         (op_convert(SELECT(W), SELECT(Tw), w), ret.base());
00484         return;
00485       }
00486 
00487       // case c {k} -> {k} c  (where c is a letter, not a word)
00488       if (this_type == node_t::constant)
00489       {
00490         n_const_t* c = dynamic_cast<n_const_t*>(ret.base());
00491         if (c->value_.size() == 1)
00492           {
00493             ret.base() = new n_lweight_t
00494               (op_convert(SELECT(W), SELECT(Tw), w), ret.base());
00495             return;
00496           }
00497       }
00498 
00499       // case (E {k'}) {k} -> E {k'k}
00500       if (this_type == node_t::rweight)
00501       {
00502         op_in_mul(s.semiring(),
00503                   dynamic_cast<n_rweight_t* >(ret.base())->weight_,
00504                   op_convert(SELECT(W), SELECT(Tw), w));
00505         return;
00506       }
00507 
00508       // [1] case ({k'} E) {k} -> {k'} (E {k})
00509       // [2] case ({k'} c) {k} -> {k'k} c  if c is a letter
00510       // (Note: case [2] is like if you had applied case [1]
00511       // followed by the c {k} -> {k} c, and then the
00512       // {k'} (E  {k}) -> {k'k} E rewritings.)
00513       if (this_type == node_t::lweight)
00514       {
00515         n_lweight_t* p = dynamic_cast<n_lweight_t*>(ret.base());
00516         if (p->child_->what() == node_t::constant
00517             && dynamic_cast<n_const_t*>(p->child_)->value_.size() == 1)
00518           {
00519             p->weight_ = op_mul (s.semiring(), p->weight_,
00520                                  op_convert(SELECT(W), SELECT(Tw), w));
00521           }
00522         else
00523           {
00524             p->child_ = new n_rweight_t(op_convert(SELECT(W), SELECT(Tw), w),
00525                                         p->child_);
00526           }
00527         return;
00528       }
00529 
00530       // case ({k'} E) {k} -> general case
00531       ret.base() =
00532       new n_rweight_t(op_convert(SELECT(W), SELECT(Tw), w), ret.base());
00533       return;
00534     }
00535 
00536     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00537     rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00538                             const W& semiring,
00539                             const rat::exp<Tm, Tw>& a,
00540                             const oTw& w)
00541     {
00542       rat::exp<Tm, Tw> ret(a);
00543       op_in_mul(s, semiring, ret, w);
00544       return ret;
00545     }
00546 
00547     template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00548     rat::exp<Tm, Tw> op_mul(const W& semiring,
00549                             const algebra::Series<W, M>& s,
00550                             const oTw& w,
00551                             const rat::exp<Tm, Tw>& b)
00552     {
00553       precondition(& s.semiring() == & semiring);
00554       (void) s; (void) semiring;
00555 
00556       typedef rat::Node<Tm, Tw>                         node_t;
00557       typedef typename rat::Node<Tm, Tw>::type          type;
00558       typedef rat::One<Tm, Tw>                          n_one_t;
00559       typedef rat::Constant<Tm, Tw>                     n_const_t;
00560       typedef rat::Zero<Tm, Tw>                         n_zero_t;
00561       typedef rat::Star<Tm, Tw>                         n_star_t;
00562       typedef rat::LeftWeighted<Tm, Tw>                 n_lweight_t;
00563       typedef rat::RightWeighted<Tm, Tw>                n_rweight_t;
00564       typedef rat::Sum<Tm, Tw>                          n_sum_t;
00565       typedef rat::Product<Tm, Tw>                      n_prod_t;
00566 
00567       rat::exp<Tm, Tw> ret(b);
00568 
00569       type this_type = ret.base()->what();
00570 
00571       // case {k} 0 -> 0
00572       if (this_type == node_t::zero)
00573         return ret;
00574 
00575       // case {k} 1 -> general case
00576 
00577       // case {0} E -> 0
00578       if (w == zero_value(SELECT(W), SELECT(oTw)))
00579       { return rat::exp<Tm, Tw>::zero(); }
00580 
00581       // case {1} E -> E
00582       if (w == identity_value(SELECT(W), SELECT(oTw)))
00583         return ret;
00584 
00585       // case {k} ({k'} E) -> {k k'} E
00586       if (this_type == node_t::lweight)
00587       {
00588         n_lweight_t* p = dynamic_cast<n_lweight_t*>(ret.base());
00589         p->weight_ = op_mul
00590           (s.semiring(), op_convert(SELECT(W), SELECT(Tw), w), p->weight_);
00591         return ret;
00592       }
00593 
00594       // general case {k} E
00595       ret.base() = new n_lweight_t(w, ret.base());
00596       return ret;
00597     }
00598 
00599     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00600     Tw op_series_get(const algebra::Series<W, M>& s,
00601                      const rat::exp<Tm, Tw>& p,
00602                      const oTm& m)
00603     {
00604       typedef typename standard_of_traits<algebra::Series<W, M>,
00605                                           rat::exp<Tm, Tw> >::
00606                                           automaton_t automaton_t;
00607 
00608       typename automaton_t::set_t       automata (s);
00609       automaton_t                       a (automata);
00610       standard_of(a, p);
00611       return eval(a, m).value();
00612     }
00613 
00614     template<typename W, typename M, typename Tm, typename Tw,
00615     typename oTm, typename oTw>
00616     void op_series_set(const algebra::Series<W, M>& s,
00617                        rat::exp<Tm, Tw>& p,
00618                        const oTm& m,
00619                        const oTw& w)
00620     {
00621       if ((m == algebra::identity_as<oTm>::of(s.monoid())) &&
00622           (w == algebra::identity_as<oTw>::of(s.semiring())) &&
00623           (p == algebra::zero_as<rat::exp<Tm, Tw> >::of(s)))
00624       {
00625         p = algebra::identity_as<rat::exp<Tm, Tw> >::of(s).value();
00626         return ;
00627       }
00628 
00629       typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> > series_set_elt_t;
00630       typedef typename series_set_elt_t::monoid_elt_t           monoid_elt_t;
00631       typedef typename monoid_elt_t::value_t                    monoid_elt_value_t;
00632       typedef std::list<monoid_elt_value_t>                     support_t;
00633 
00634       rat::exp<Tm, Tw> pp = p;
00635       p = algebra::zero_as<rat::exp<Tm, Tw> >::of(s).value();
00636 
00637       // FIXME Should not rebuild the serie from stratch
00638       // Should use some kind of visitor and update the tree
00639       support_t supp = op_support(s, pp);
00640       oTw sw;
00641       bool exist = false;
00642       for_all_const_(support_t, e, supp)
00643       {
00644         rat::exp<Tm, Tw> ret = op_convert(s,
00645                                           SELECT2(rat::exp<Tm, Tw>),
00646                                           SELECT(M), *e);
00647         if (*e == m)
00648         {
00649           exist = true;
00650           sw = w;
00651         }
00652         else
00653           sw = op_series_get(s, pp, *e);
00654 
00655         op_in_add(s, p, op_mul(s.semiring(), s, sw, ret));
00656       }
00657       if (!exist)
00658         op_in_add(s, p, op_mul(s.semiring(), s, w,
00659                                op_convert(s,
00660                                           SELECT2(rat::exp<Tm, Tw>),
00661                                           SELECT(M), m)));
00662     }
00663 
00664   } // ! algebra
00665 
00666   /*----------------------------------------------------------------------------.
00667   | MetaElement<algebra::SeriesBase<algebra::Series<W, M> >, rat::exp<Tm, Tw> > |
00668   `----------------------------------------------------------------------------*/
00669 
00670   template <typename W, typename M, typename Tm, typename Tw>
00671   void
00672   MetaElement<algebra::Series<W, M>, rat::exp<Tm, Tw> >::accept
00673   (const rat::ConstNodeVisitor<Tm, Tw>& v) const
00674   {
00675     this->value().accept(v);
00676   }
00677 
00678   template <typename W, typename M, typename Tm, typename Tw>
00679   size_t
00680   MetaElement<algebra::Series<W, M>, rat::exp<Tm, Tw> >::depth() const
00681   {
00682     return this->value().depth();
00683   }
00684 
00685   namespace algebra
00686   {
00687     template <class W, class M, class Tm, class Tw>
00688     Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >
00689     op_choose(const algebra::Series<W,M>& s,
00690               SELECTOR2(rat::exp<Tm,Tw>))
00691     {
00692       Element<algebra::Series<W,M>, rat::exp<Tm, Tw> > e(s);
00693       // FIXME : add global constants to do this !
00694       unsigned nb = RAND___(10);
00695       while (nb != 0)
00696       {
00697         --nb;
00698         unsigned t = RAND___(3);
00699         switch (t)
00700         {
00701           // star
00702           case 0 :
00703             {
00704               e = e.star();
00705               continue;
00706             }
00707             // plus
00708           case 1 :
00709             {
00710               Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >
00711                       ep(s, s.monoid().choose(SELECT(Tm)));
00712               ep = ep * s.semiring().choose(SELECT(Tw));
00713               unsigned t = RAND___(2);
00714               if (t < 1)
00715                 e = e + ep;
00716               else
00717                 e = ep + e;
00718               continue;
00719             }
00720             // mult
00721           case 2 :
00722             {
00723               Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >
00724                       ep(s, s.monoid().choose(SELECT(Tm)));
00725               ep = ep * s.semiring().choose(SELECT(Tw));
00726               unsigned t = RAND___(2);
00727               if (t < 1)
00728                 e = e * ep;
00729               else
00730                 e = ep * e;
00731               continue;
00732             }
00733         }
00734       }
00735       return Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >(s, e);
00736     }
00737 
00738   } // ! algebra
00739 
00740 } // ! vcsn
00741 
00742 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_HXX