krat.hxx

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

Generated on Fri Jul 28 12:18:35 2006 for Vaucanson by  doxygen 1.4.6