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