Vaucanson: polynoms.hxx Source File

00001 // polynoms.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, 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_POLYNOMS_HXX
00018 # define VCSN_ALGEBRA_IMPLEMENTATION_SERIES_POLYNOMS_HXX
00019 
00020 # include <sstream>
00021 
00022 # include <vaucanson/algebra/implementation/series/polynoms.hh>
00023 # include <vaucanson/algebra/concept/freemonoid_base.hh>
00024 
00025 # include <vaucanson/misc/contract.hh>
00026 # include <vaucanson/misc/escaper.hh>
00027 
00028 namespace vcsn {
00029 
00030   namespace algebra {
00031 
00032     /*----------------.
00033       | polynom<Tm, Tw> |
00034       `----------------*/
00035 
00036     template<typename Tm, typename Tw>
00037     template<typename M, typename W>
00038     polynom<Tm, Tw>::polynom(SELECTOR(M), SELECTOR(W))
00039     {
00040       map_.insert(std::make_pair(identity_value(SELECT(M), SELECT(Tm)),
00041                                  identity_value(SELECT(W), SELECT(Tw))));
00042     }
00043 
00044     template<typename Tm, typename Tw>
00045     polynom<Tm, Tw>::polynom(const polynom& other) : map_(other.map_)
00046     {}
00047 
00048     template<typename Tm, typename Tw>
00049     polynom<Tm, Tw>::polynom() : map_()
00050     {}
00051 
00052     template<typename Tm, typename Tw>
00053     size_t
00054     polynom<Tm, Tw>::size() const
00055     {
00056       return map_.size();
00057     }
00058 
00059     template<typename Tm, typename Tw>
00060     bool polynom<Tm, Tw>::empty() const
00061     {
00062       return map_.empty();
00063     }
00064 
00065     template<typename Tm, typename Tw>
00066     typename polynom<Tm, Tw>::iterator
00067     polynom<Tm, Tw>::begin()
00068     {
00069       return map_.begin();
00070     }
00071 
00072     template<typename Tm, typename Tw>
00073     typename polynom<Tm, Tw>::const_iterator
00074     polynom<Tm, Tw>::begin() const
00075     {
00076       return map_.begin();
00077     }
00078 
00079     template<typename Tm, typename Tw>
00080     typename polynom<Tm, Tw>::iterator
00081     polynom<Tm, Tw>::end()
00082     {
00083       return map_.end();
00084     }
00085 
00086     template<typename Tm, typename Tw>
00087     typename polynom<Tm, Tw>::const_iterator
00088     polynom<Tm, Tw>::end() const
00089     {
00090       return map_.end();
00091     }
00092 
00093     template<typename Tm, typename Tw>
00094     typename polynom<Tm, Tw>::iterator
00095     polynom<Tm, Tw>::find(const Tm& m)
00096     {
00097       return map_.find(m);
00098     }
00099 
00100     template<typename Tm, typename Tw>
00101     typename polynom<Tm, Tw>::const_iterator
00102     polynom<Tm, Tw>::find(const Tm& m) const
00103     {
00104       return map_.find(m);
00105     }
00106 
00107     template<typename Tm, typename Tw>
00108     template<typename W>
00109     Tw& polynom<Tm, Tw>::make_get(SELECTOR(W), const Tm& m)
00110     {
00111       std::pair<iterator, bool> i =
00112         map_.insert(std::make_pair(m, zero_value(SELECT(W), SELECT(Tw))));
00113       return i.first->second;
00114     }
00115 
00116     template<typename Tm, typename Tw>
00117     template<typename W>
00118     Tw polynom<Tm, Tw>::get(SELECTOR(W), const Tm& m) const
00119     {
00120       const_iterator i;
00121       if ((i = map_.find(m)) == map_.end())
00122         return zero_value(SELECT(W), SELECT(Tw));
00123       return i->second;
00124     }
00125 
00126     template<typename Tm, typename Tw>
00127     void polynom<Tm, Tw>::insert(const Tm& m, const Tw& w)
00128     {
00129       map_.insert(std::make_pair(m, w));
00130     }
00131 
00132     template<typename Tm, typename Tw>
00133     template<typename W>
00134     void polynom<Tm, Tw>::add(const W& semiring, const Tm& m, const Tw& w)
00135     {
00136       Tw& o = make_get(SELECT(W), m);
00137       op_in_add(semiring, o, w);
00138     }
00139 
00140     template<typename Tm, typename Tw>
00141     void polynom<Tm, Tw>::erase(iterator i)
00142     {
00143       map_.erase(i);
00144     }
00145 
00146     template<typename Tm, typename Tw>
00147     void polynom<Tm, Tw>::clear()
00148     {
00149       map_.clear();
00150     }
00151 
00152     template<typename Tm, typename Tw>
00153     void polynom<Tm, Tw>::swap(polynom<Tm, Tw>& other)
00154     {
00155       map_.swap(other.map_);
00156     }
00157 
00158     template<typename Tm, typename Tw>
00159     const std::map<Tm, Tw>&
00160     polynom<Tm, Tw>::as_map() const
00161     {
00162       return map_;
00163     }
00164 
00165     template<typename Tm, typename Tw>
00166     const Tw&
00167     polynom<Tm, Tw>::operator [] (const Tm& m) const
00168     {
00169       const_iterator i = map_.find(m);
00170 
00171       postcondition_ (i != map_.end(),
00172                       "Word is not in the support");
00173 
00174       return i->second;
00175     }
00176 
00177     template<typename Tm, typename Tw>
00178     Tw&
00179     polynom<Tm, Tw>::operator [] (const Tm& m)
00180     {
00181       return map_[m];
00182     }
00183 
00184     template <class Series, class Tm, class Tw>
00185     polynom<Tm,Tw>
00186     DefaultTransposeFun<Series, polynom<Tm,Tw> >::
00187     operator()(const Series& s,const polynom<Tm,Tw>& t) const
00188     {
00189       typedef typename polynom<Tm, Tw>::const_iterator  const_iterator;
00190       typedef typename Series::monoid_t                 monoid_t;
00191       typedef Element<monoid_t, Tm>                     monoid_elt_t;
00192 
00193       polynom<Tm, Tw> p;
00194 
00195       for (const_iterator i = t.begin(); i != t.end(); ++i)
00196         {
00197           monoid_elt_t m (s.monoid(), i->first);
00198           m.mirror();
00199           p[m.value()] = transpose(s.semiring(), i->second);
00200         }
00201       return p;
00202     }
00203 
00204     template <class Series, class Tm, class Tw>
00205     template <class S>
00206     Tw
00207     DefaultTransposeFun<Series, polynom<Tm,Tw> >::
00208     transpose(const SeriesBase<S>& s, const Tw& t)
00209     {
00210       Element<S, Tw> e (s.self(), t);
00211       e.transpose();
00212       return e.value();
00213     }
00214 
00215     template <class Series, class Tm, class Tw>
00216     template <class S>
00217     Tw
00218     DefaultTransposeFun<Series, polynom<Tm,Tw> >::
00219     transpose(const SemiringBase<S>&, const Tw& t)
00220     {
00221       return t;
00222     }
00223 
00224 
00225     template <class Tm, class Tw>
00226     bool operator==(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs)
00227     {
00228       return lhs.as_map() == rhs.as_map();
00229     }
00230 
00231     template <class Tm, class Tw>
00232     bool operator!=(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs)
00233     {
00234       return !(lhs == rhs);
00235     }
00236 
00237 
00238     template <class Tm, class Tw>
00239     bool operator<(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs)
00240     {
00241       return lhs.as_map() < rhs.as_map();
00242     }
00243 
00244     template <class Tm, class Tw>
00245     bool operator>(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs)
00246     {
00247       return lhs.as_map() > rhs.as_map();
00248     }
00249 
00250     template <class Tm, class Tw>
00251     bool operator<=(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs)
00252     {
00253       return lhs.as_map() <= rhs.as_map();
00254     }
00255 
00256     template <class Tm, class Tw>
00257     bool operator>=(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs)
00258     {
00259       return lhs.as_map() >= rhs.as_map();
00260     }
00261 
00262 
00263   } // algebra
00264 
00265 
00266   /*-------------------.
00267     | External functions |
00268     `-------------------*/
00269 
00270   template<typename W, typename M, typename Tm, typename Tw>
00271   bool op_contains(const algebra::Series<W, M>& s, const algebra::polynom<Tm, Tw>& m)
00272   {
00273     for (typename algebra::polynom<Tm, Tw>::const_iterator i = m.begin();
00274          i != m.end();
00275          ++i)
00276       if (!s.monoid().contains(i->first) || !s.semiring().contains(i->second))
00277         return false;
00278     return true;
00279   }
00280 
00281   template<typename Self, typename Tm, typename Tw>
00282   void op_in_star(const algebra::SeriesBase<Self>&,
00283                   algebra::polynom<Tm, Tw>& m)
00284   {
00285     if (m.size() == 0)
00286       {
00287         Tw val (0);
00288         op_in_star(SELECT(typename Self::semiring_t), val);
00289         m.insert(identity_value(SELECT(typename Self::monoid_t), SELECT(Tm)),
00290                  val);
00291       }
00292     else
00293       {
00294         typename std::pair<Tm, Tw> elt = *m.as_map().begin();
00295         assertion_ (!(m.size() > 1 ||
00296                     elt.first != identity_value(SELECT(typename Self::monoid_t),
00297                                                 SELECT(Tm))),
00298                     "Support is not empty, star cannot be computed.");
00299 
00300         op_in_star(SELECT(typename Self::semiring_t), elt.second);
00301         m.clear();
00302         m.insert(elt.first, elt.second);
00303       }
00304   }
00305 
00306   template<typename W, typename M, typename Tm, typename Tw>
00307   bool op_is_finite_app(const algebra::Series<W, M>&, const algebra::polynom<Tm, Tw>&)
00308   {
00309     return true;
00310   }
00311 
00312   template<typename W, typename M, typename Tm, typename Tw>
00313   typename algebra::series_traits<algebra::polynom<Tm, Tw> >::support_t
00314   op_support(const algebra::Series<W, M>&, const algebra::polynom<Tm, Tw>& m)
00315   {
00316     return typename algebra::series_traits<algebra::polynom<Tm, Tw> >::support_t(m.as_map());
00317   }
00318 
00319   template<typename W, typename M, typename Tm, typename Tw>
00320   const algebra::polynom<Tm, Tw>& identity_value(SELECTOR2(algebra::Series<W, M>),
00321                                                  SELECTOR2(algebra::polynom<Tm, Tw>))
00322   {
00323     static const algebra::polynom<Tm, Tw> instance =
00324       algebra::polynom<Tm, Tw>(SELECT(M), SELECT(W));
00325     return instance;
00326   }
00327 
00328   template<typename W, typename M, typename Tm, typename Tw>
00329   const algebra::polynom<Tm, Tw>& zero_value(SELECTOR2(algebra::Series<W, M>),
00330                                              SELECTOR2(algebra::polynom<Tm, Tw>))
00331   {
00332     static const algebra::polynom<Tm, Tw> instance;
00333     return instance;
00334   }
00335 
00336   template<typename W, typename M, typename Tm, typename Tw>
00337   void op_in_add(const algebra::Series<W, M>& s,
00338                  algebra::polynom<Tm, Tw>& dst,
00339                  const algebra::polynom<Tm, Tw>& arg)
00340   {
00341     typename algebra::polynom<Tm, Tw>::iterator p;
00342     Tw zero = zero_value(SELECT(W), SELECT(Tw));
00343     Tw w;
00344 
00345     for (typename algebra::polynom<Tm, Tw>::const_iterator i = arg.begin();
00346          i != arg.end();
00347          ++i)
00348       if (i->second != zero)
00349         {
00350           p = dst.find(i->first);
00351           if (p != dst.end())
00352             {
00353               w = i->second;
00354               op_in_add(s.semiring(), w, p->second);
00355               if (w == zero_value(SELECT(W), SELECT(Tw)))
00356                 dst.erase(p);
00357               else
00358                 p->second = w;
00359             }
00360           else
00361             dst.insert(i->first, i->second);
00362         }
00363   }
00364 
00365   template<typename W, typename M, typename Tm, typename Tw>
00366   algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00367                                   const algebra::polynom<Tm, Tw>& a,
00368                                   const algebra::polynom<Tm, Tw>& b)
00369   {
00370     algebra::polynom<Tm, Tw> ret(a);
00371     op_in_add(s, ret, b);
00372     return ret;
00373   }
00374 
00375   /*-----------------.
00376     | cauchy's product |
00377     `-----------------*/
00378   template<typename W, typename M, typename Tm, typename Tw>
00379   algebra::polynom<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00380                                   const algebra::polynom<Tm, Tw>& a,
00381                                   const algebra::polynom<Tm, Tw>& b)
00382   {
00383     algebra::polynom<Tm, Tw> ret;
00384     for (typename algebra::polynom<Tm, Tw>::const_iterator i = a.begin();
00385          i != a.end();
00386          ++i)
00387       for (typename algebra::polynom<Tm, Tw>::const_iterator j = b.begin();
00388            j != b.end();
00389            ++j)
00390         {
00391           Tw w = op_mul(s.semiring(), i->second, j->second);
00392           if (w != zero_value(SELECT(W), SELECT(Tw)))
00393             ret.add(s.semiring(),
00394                     op_mul(s.monoid(), i->first, j->first),
00395                     w);
00396         }
00397     return ret;
00398   }
00399 
00400   template<typename W, typename M, typename Tm, typename Tw>
00401   void op_in_mul(const algebra::Series<W, M>& s,
00402                  algebra::polynom<Tm, Tw>& dst,
00403                  const algebra::polynom<Tm, Tw>& arg)
00404   {
00405     op_assign(s, dst, op_mul(s, dst, arg));
00406   }
00407 
00408   /*---------------------.
00409     | foreign constructors |
00410     `---------------------*/
00411 
00412   template <typename Tm, typename Tw, typename W, typename M>
00413   algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00414                                       SELECTOR2(algebra::polynom<Tm, Tw>),
00415                                       const Tm& m_value)
00416   {
00417     algebra::polynom<Tm, Tw> p(SELECT(M), SELECT(W));
00418     p.insert(m_value, identity_value(SELECT(W), SELECT(Tw)));
00419     return p;
00420   }
00421 
00422   template<typename Tm, typename Tw, typename W, typename M, typename oTm>
00423   algebra::polynom<Tm, Tw> op_convert(const algebra::Series<W, M>& s,
00424                                       SELECTOR2(algebra::polynom<Tm, Tw>),
00425                                       SELECTOR(algebra::MonoidBase<M>),
00426                                       const oTm& m_value)
00427   {
00428     const M&    monoid = s.monoid();
00429     const W&    semiring = s.semiring();
00430 
00431     algebra::polynom<Tm, Tw> ret;
00432     ret.insert(op_convert(monoid, SELECT(Tm), m_value),
00433                identity_value(semiring, SELECT(Tw)));
00434     return ret;
00435   }
00436 
00437   template<typename Tm, typename Tw, typename W, typename M, typename oTw>
00438   algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00439                                       SELECTOR2(algebra::polynom<Tm, Tw>),
00440                                       SELECTOR(algebra::SemiringBase<W>),
00441                                       const oTw& w_value)
00442   {
00443     algebra::polynom<Tm, Tw> ret;
00444     if (w_value != zero_value(SELECT(W), SELECT(oTw)))
00445       ret.insert(identity_value(SELECT(M), SELECT(Tm)),
00446                  op_convert(SELECT(W), SELECT(Tw), w_value));
00447     return ret;
00448   }
00449 
00450   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00451   void op_assign(const algebra::Series<W, M>&,
00452                  const algebra::MonoidBase<M>&,
00453                  algebra::polynom<Tm, Tw>& dst,
00454                  const oTm& src)
00455   {
00456     dst.clear();
00457     dst.insert(op_convert(SELECT(M), SELECT(Tm), src),
00458                identity_value(SELECT(W), SELECT(Tw)));
00459   }
00460 
00461   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00462   void op_assign(const algebra::Series<W, M>& s,
00463                  const algebra::SemiringBase<W>&,
00464                  algebra::polynom<Tm, Tw>& dst,
00465                  const oTw& src)
00466   {
00467     dst.clear();
00468     if (src != zero_value(SELECT(W), SELECT(oTw)))
00469       dst.insert(identity_value(SELECT(M), SELECT(Tm)),
00470                  op_convert(SELECT(W), SELECT(Tw), src));
00471   }
00472 
00473   /*--------------------------------------.
00474     | foreign addition with monoid elements |
00475     `--------------------------------------*/
00476 
00477   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00478   void op_in_add(const algebra::Series<W, M>& s,
00479                  const algebra::MonoidBase<M>& monoid,
00480                  algebra::polynom<Tm, Tw>& dst,
00481                  const oTm& src)
00482   {
00483     precondition(& s.monoid() == & monoid);
00484     dst.add(s.semiring(),
00485             op_convert(SELECT(M), SELECT(Tm), src),
00486             identity_value(SELECT(W), SELECT(Tw)));
00487   }
00488 
00489   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00490   algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00491                                   const algebra::MonoidBase<M>& monoid,
00492                                   const algebra::polynom<Tm, Tw>& a,
00493                                   const oTm& b)
00494   {
00495     algebra::polynom<Tm, Tw> ret(a);
00496     op_in_add(s, monoid, ret, b);
00497     return ret;
00498   }
00499 
00500   template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00501   algebra::polynom<Tm, Tw> op_add(const algebra::MonoidBase<M>& monoid,
00502                                   const algebra::Series<W, M>& s,
00503                                   const oTm& a,
00504                                   const algebra::polynom<Tm, Tw>& b)
00505   {
00506     algebra::polynom<Tm, Tw> ret(b);
00507     op_in_add(s, monoid, ret, a);
00508     return ret;
00509   }
00510 
00511   /*---------------------------------------.
00512     | foreign addition with semiring elements |
00513     `---------------------------------------*/
00514 
00515   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00516   void op_in_add(const algebra::Series<W, M>& s,
00517                  const algebra::SemiringBase<W>& semiring,
00518                  algebra::polynom<Tm, Tw>& dst,
00519                  const oTw& src)
00520   {
00521     precondition(& s.semiring() == & semiring);
00522     if (src != zero_value(SELECT(W), SELECT(oTw)))
00523       dst.add(s.semiring(),
00524               identity_value(SELECT(M), SELECT(Tm)),
00525               op_convert(SELECT(W), SELECT(Tw), src));
00526   }
00527 
00528   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00529   algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00530                                   const algebra::SemiringBase<W>& semiring,
00531                                   const algebra::polynom<Tm, Tw>& a,
00532                                   const oTw& b)
00533   {
00534     algebra::polynom<Tm, Tw> ret(a);
00535     op_in_add(s, semiring, ret, b);
00536     return ret;
00537   }
00538 
00539   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00540   algebra::polynom<Tm, Tw> op_add(const algebra::SemiringBase<W>& semiring,
00541                                   const algebra::Series<W, M>& s,
00542                                   const oTw& a,
00543                                   const algebra::polynom<Tm, Tw>& b)
00544   {
00545     algebra::polynom<Tm, Tw> ret(b);
00546     op_in_add(s, semiring, ret, a);
00547     return ret;
00548   }
00549 
00550   /*-------------------------------------------.
00551     | foreign multiplication by semiring elements |
00552     `-------------------------------------------*/
00553 
00554   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00555   void op_in_mul(const algebra::Series<W, M>& s,
00556                  const algebra::SemiringBase<W>& semiring,
00557                  algebra::polynom<Tm, Tw>& dst,
00558                  const oTw& src)
00559   {
00560     precondition(& s.semiring() == & semiring);
00561     (void) s; (void) semiring;
00562 
00563     typename algebra::polynom<Tm, Tw>::iterator p;
00564     for (typename algebra::polynom<Tm, Tw>::iterator i = dst.begin();
00565          i != dst.end();
00566          )
00567       {
00568         p = i++;
00569         op_in_mul(s.semiring(), p->second, src);
00570         if (p->second == zero_value(SELECT(W), SELECT(Tw)))
00571           dst.erase(p);
00572       }
00573   }
00574 
00575   template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00576   algebra::polynom<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00577                                   const algebra::SemiringBase<W>& semiring,
00578                                   const algebra::polynom<Tm, Tw>& a,
00579                                   const oTw& b)
00580   {
00581     algebra::polynom<Tm, Tw> ret(a);
00582     op_in_mul(s, semiring, ret, b);
00583     return ret;
00584   }
00585 
00586   template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00587   algebra::polynom<Tm, Tw> op_mul(const algebra::SemiringBase<W>& semiring,
00588                                   const algebra::Series<W, M>& s,
00589                                   const oTw& a,
00590                                   const algebra::polynom<Tm, Tw>& b)
00591   {
00592     precondition(& s.semiring() == & semiring);
00593     (void) s; (void) semiring;
00594 
00595     algebra::polynom<Tm, Tw> ret(b);
00596 
00597     typename algebra::polynom<Tm, Tw>::iterator p;
00598     for (typename algebra::polynom<Tm, Tw>::iterator i = ret.begin();
00599          i != ret.end();)
00600       {
00601         p = i++;
00602         p->second = op_mul(s.semiring(), a, p->second);
00603         if (p->second == zero_value(SELECT(W), SELECT(Tw)))
00604           ret.erase(p);
00605       }
00606     return ret;
00607   }
00608 
00609     /*-------------.
00610     | input-output |
00611     `-------------*/
00612 
00613   template<typename W, typename M, typename St, typename Tm, typename Tw>
00614   St& op_rout(const algebra::Series<W, M>& s,
00615               St& st,
00616               const algebra::polynom<Tm, Tw>& p)
00617   {
00618     typename algebra::polynom<Tm, Tw>::const_iterator i = p.begin();
00619 
00620     while(i != p.end())
00621       {
00622         if (i != p.begin())
00623           st << "+";
00624 
00625         if (i->second != identity_value(SELECT(W), SELECT(Tw)))
00626         {
00627           st << "(";
00628           op_rout(s.semiring(), st, i->second);
00629           st << " ";
00630         }
00631 
00632         if (i->first != identity_value(SELECT(M), SELECT(Tm)))
00633           op_rout(s.monoid(), st, i->first);
00634         else
00635           st << "1";
00636 
00637         if (i->second != identity_value(SELECT(W), SELECT(Tw)))
00638           st << ")";
00639 
00640         ++i;
00641       }
00642     if (i == p.begin()) /* case zero */
00643       op_rout(s.semiring(), st, zero_value(SELECT(W), SELECT(Tw)));
00644     return st;
00645   }
00646 
00647   /*---------------.
00648     | specialization |
00649     `---------------*/
00650 
00651   /*------------------------------.
00652     | design_pattern series operations |
00653     `------------------------------*/
00654 
00655 
00656   template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00657   Tw op_series_get(const algebra::Series<W, M>& s,
00658                    const algebra::polynom<Tm, Tw>& p,
00659                    const oTm& m)
00660   {
00661     return p.get(s.semiring(), op_convert(s.semiring(), SELECT(Tm), m));
00662   }
00663 
00664   template <typename W, typename M,
00665             typename Tm, typename Tw,
00666             typename oTm, typename oTw>
00667   void op_series_set(const algebra::Series<W, M>& s,
00668                      algebra::polynom<Tm, Tw>& p,
00669                      const oTm& m,
00670                      const oTw& w)
00671   {
00672     const M&    monoid = s.monoid();
00673     const W&    semiring = s.semiring();
00674 
00675     typename utility::static_if
00676       <utility::static_eq<Tm, oTm>::value, const Tm&, Tm>::t
00677       new_m = op_convert(monoid, SELECT(Tm), m);
00678     typename utility::static_if
00679       <utility::static_eq<Tw, oTw>::value, const Tw&, Tw>::t
00680       new_w = op_convert(semiring, SELECT(Tw), w);
00681 
00682     typename algebra::polynom<Tm, Tw>::iterator i = p.find(new_m);
00683     if (new_w == zero_value(semiring, new_w))
00684       {
00685         if (i != p.end())
00686           p.erase(i);
00687       }
00688     else
00689       if (i == p.end())
00690         p.insert(new_m, new_w);
00691       else
00692         i->second = new_w;
00693   }
00694 
00695 
00696   template <class W, class M, class Tm, class Tw>
00697   Tm op_choose_from_supp(const algebra::Series<W, M>&,
00698                          const algebra::polynom<Tm, Tw>& p)
00699   {
00700     typedef typename algebra::polynom<Tm, Tw>::const_iterator const_iterator;
00701 
00702     if (p.size() == 0)
00703       return Tm();
00704 
00705     unsigned       index = rand() * p.size() / RAND_MAX;
00706     const_iterator i = p.begin();
00707     while ((index > 0) && (i != p.end()))
00708       {
00709         --index;
00710         ++i;
00711       }
00712     return (*i).first;
00713   }
00714 
00715 
00716   template <class W, class M, class Tm, class Tw>
00717   Element<algebra::Series<W,M>, algebra::polynom<Tm,Tw> >
00718   op_choose(const algebra::Series<W,M>& s,
00719             SELECTOR2(algebra::polynom<Tm,Tw>))
00720   {
00721     algebra::polynom<Tm, Tw> p;
00722     // FIXME: add global constants to define this !
00723     unsigned nb_monome = rand() * 10 / RAND_MAX;
00724     for (unsigned i = 0; i < nb_monome; ++i)
00725       p[s.monoid().choose()] = s.semiring().choose();
00726     return Element<algebra::Series<W,M>, algebra::polynom<Tm,Tw> >(s, p);
00727   }
00728 
00729   /*----------.
00730     | transpose |
00731     `----------*/
00732   template <typename W, typename M, typename Tm, typename Tw>
00733   void  op_in_transpose(const algebra::Series<W, M>& s,
00734                         algebra::polynom<Tm, Tw>& t)
00735   {
00736     algebra::DefaultTransposeFun<algebra::Series<W, M>,
00737                                  algebra::polynom<Tm, Tw> > f;
00738     t = f(s, t);
00739   }
00740 
00741 } // vcsn
00742 
00743 namespace std {
00744 
00745   // FIXME: Must this operator exist ?
00746   template <class Tm, class Tw>
00747   std::ostream& operator<<(std::ostream& out,
00748                            const vcsn::algebra::polynom<Tm, Tw>& p)
00749   {
00750     typename vcsn::algebra::polynom<Tm, Tw>::const_iterator i = p.begin();
00751 
00752     while (i != p.end())
00753       {
00754         if (i != p.begin())
00755           out << "+";
00756         out << "(" << i->second << " "
00757             << utility::make_escaper(i->first) << ")";
00758         ++i;
00759       }
00760 
00761     if (i == p.begin()) /* case zero */
00762       out << "0";
00763 
00764     return out;
00765   }
00766 
00767 } // std
00768 
00769 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_POLYNOMS_HXX