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