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 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     void op_in_star(const algebra::SeriesBase<Self>&,
00278                     algebra::polynom<Tm, Tw>& m)
00279     {
00280       if (m.size() == 0)
00281       {
00282         Tw val (zero_value(SELECT(typename Self::semiring_t), SELECT(Tw)));
00283         op_in_star(SELECT(typename Self::semiring_t), val);
00284         m.insert(identity_value(SELECT(typename Self::monoid_t), SELECT(Tm)),
00285                  val);
00286       }
00287       else
00288       {
00289         typename std::pair<Tm, Tw> elt = *m.as_map().begin();
00290         assertion_ (!(m.size() > 1 ||
00291                       elt.first != identity_value(SELECT(typename
00292                                                          Self::monoid_t),
00293                                                   SELECT(Tm))),
00294                     "Support is not empty, star cannot be computed.");
00295 
00296         op_in_star(SELECT(typename Self::semiring_t), elt.second);
00297         m.clear();
00298         m.insert(elt.first, elt.second);
00299       }
00300     }
00301 
00302     template<typename W, typename M, typename Tm, typename Tw>
00303     bool op_is_finite_app(const algebra::Series<W, M>&,
00304                           const algebra::polynom<Tm, Tw>&)
00305     {
00306       return true;
00307     }
00308 
00309     template<typename W, typename M, typename Tm, typename Tw>
00310     typename algebra::series_traits<algebra::polynom<Tm, Tw> >::support_t
00311     op_support(const algebra::Series<W, M>&,
00312                const algebra::polynom<Tm, Tw>& m)
00313     {
00314       return typename algebra::series_traits<algebra::polynom<Tm, Tw> >::
00315       support_t(m.as_map());
00316     }
00317 
00318     template<typename W, typename M, typename Tm, typename Tw>
00319     const algebra::polynom<Tm, Tw>&
00320     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>&
00330     zero_value(SELECTOR2(algebra::Series<W, M>),
00331                SELECTOR2(algebra::polynom<Tm, Tw>))
00332     {
00333       static const algebra::polynom<Tm, Tw> instance;
00334       return instance;
00335     }
00336 
00337     template<typename W, typename M, typename Tm, typename Tw>
00338     void op_in_add(const algebra::Series<W, M>& s,
00339                    algebra::polynom<Tm, Tw>& dst,
00340                    const algebra::polynom<Tm, Tw>& arg)
00341     {
00342       typename algebra::polynom<Tm, Tw>::iterator p;
00343       Tw zero = zero_value(SELECT(W), SELECT(Tw));
00344       Tw w;
00345 
00346       for (typename algebra::polynom<Tm, Tw>::const_iterator i = arg.begin();
00347            i != arg.end();
00348            ++i)
00349         if (i->second != zero)
00350         {
00351           p = dst.find(i->first);
00352           if (p != dst.end())
00353           {
00354             w = i->second;
00355             op_in_add(s.semiring(), w, p->second);
00356             if (w == zero_value(SELECT(W), SELECT(Tw)))
00357               dst.erase(p);
00358             else
00359               p->second = w;
00360           }
00361           else
00362             dst.insert(i->first, i->second);
00363         }
00364     }
00365 
00366     template<typename W, typename M, typename Tm, typename Tw>
00367     algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00368                                     const algebra::polynom<Tm, Tw>& a,
00369                                     const algebra::polynom<Tm, Tw>& b)
00370     {
00371       algebra::polynom<Tm, Tw> ret(a);
00372       op_in_add(s, ret, b);
00373       return ret;
00374     }
00375 
00376     /*-----------------.
00377     | cauchy's product |
00378     `-----------------*/
00379 
00380     template<typename W, typename M, typename Tm, typename Tw>
00381     algebra::polynom<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00382                                     const algebra::polynom<Tm, Tw>& a,
00383                                     const algebra::polynom<Tm, Tw>& b)
00384     {
00385       algebra::polynom<Tm, Tw> ret;
00386       for (typename algebra::polynom<Tm, Tw>::const_iterator i = a.begin();
00387            i != a.end();
00388            ++i)
00389         for (typename algebra::polynom<Tm, Tw>::const_iterator j = b.begin();
00390              j != b.end();
00391              ++j)
00392         {
00393           Tw w = op_mul(s.semiring(), i->second, j->second);
00394           if (w != zero_value(SELECT(W), SELECT(Tw)))
00395             ret.add(s.semiring(),
00396                     op_mul(s.monoid(), i->first, j->first),
00397                     w);
00398         }
00399       return ret;
00400     }
00401 
00402     template<typename W, typename M, typename Tm, typename Tw>
00403     void op_in_mul(const algebra::Series<W, M>& s,
00404                    algebra::polynom<Tm, Tw>& dst,
00405                    const algebra::polynom<Tm, Tw>& arg)
00406     {
00407       op_assign(s, dst, op_mul(s, dst, arg));
00408     }
00409 
00410     /*---------------------.
00411     | foreign constructors |
00412     `---------------------*/
00413 
00414     template <typename Tm, typename Tw, typename W, typename M>
00415     algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00416                                         SELECTOR2(algebra::polynom<Tm, Tw>),
00417                                         const Tm& m_value)
00418     {
00419       algebra::polynom<Tm, Tw> p(SELECT(M), SELECT(W));
00420       p.insert(m_value, identity_value(SELECT(W), SELECT(Tw)));
00421       return p;
00422     }
00423 
00424     template<typename Tm, typename Tw, typename W, typename M, typename oTm>
00425     algebra::polynom<Tm, Tw> op_convert(const algebra::Series<W, M>& s,
00426                                         SELECTOR2(algebra::polynom<Tm, Tw>),
00427                                         SELECTOR(algebra::MonoidBase<M>),
00428                                         const oTm& m_value)
00429     {
00430       const M&  monoid = s.monoid();
00431       const W&  semiring = s.semiring();
00432 
00433       algebra::polynom<Tm, Tw> ret;
00434       ret.insert(op_convert(monoid, SELECT(Tm), m_value),
00435                  identity_value(semiring, SELECT(Tw)));
00436       return ret;
00437     }
00438 
00439     template<typename Tm, typename Tw, typename W, typename M, typename oTw>
00440     algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
00441                                         SELECTOR2(algebra::polynom<Tm, Tw>),
00442                                         SELECTOR(algebra::SemiringBase<W>),
00443                                         const oTw& w_value)
00444     {
00445       algebra::polynom<Tm, Tw> ret;
00446       if (w_value != zero_value(SELECT(W), SELECT(oTw)))
00447         ret.insert(identity_value(SELECT(M), SELECT(Tm)),
00448                    op_convert(SELECT(W), SELECT(Tw), w_value));
00449       return ret;
00450     }
00451 
00452     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00453     void op_assign(const algebra::Series<W, M>&,
00454                    const algebra::MonoidBase<M>&,
00455                    algebra::polynom<Tm, Tw>& dst,
00456                    const oTm& src)
00457     {
00458       dst.clear();
00459       dst.insert(op_convert(SELECT(M), SELECT(Tm), src),
00460                  identity_value(SELECT(W), SELECT(Tw)));
00461     }
00462 
00463     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00464     void op_assign(const algebra::Series<W, M>& s,
00465                    const algebra::SemiringBase<W>&,
00466                    algebra::polynom<Tm, Tw>& dst,
00467                    const oTw& src)
00468     {
00469       dst.clear();
00470       if (src != zero_value(SELECT(W), SELECT(oTw)))
00471         dst.insert(identity_value(SELECT(M), SELECT(Tm)),
00472                    op_convert(SELECT(W), SELECT(Tw), src));
00473     }
00474 
00475     /*--------------------------------------.
00476     | foreign addition with monoid elements |
00477     `--------------------------------------*/
00478 
00479     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00480     void op_in_add(const algebra::Series<W, M>& s,
00481                    const algebra::MonoidBase<M>& monoid,
00482                    algebra::polynom<Tm, Tw>& dst,
00483                    const oTm& src)
00484     {
00485       precondition(& s.monoid() == & monoid);
00486       dst.add(s.semiring(),
00487               op_convert(SELECT(M), SELECT(Tm), src),
00488               identity_value(SELECT(W), SELECT(Tw)));
00489     }
00490 
00491     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00492     algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00493                                     const algebra::MonoidBase<M>& monoid,
00494                                     const algebra::polynom<Tm, Tw>& a,
00495                                     const oTm& b)
00496     {
00497       algebra::polynom<Tm, Tw> ret(a);
00498       op_in_add(s, monoid, ret, b);
00499       return ret;
00500     }
00501 
00502     template<typename M, typename W, typename oTm, typename Tm, typename Tw>
00503     algebra::polynom<Tm, Tw> op_add(const algebra::MonoidBase<M>& monoid,
00504                                     const algebra::Series<W, M>& s,
00505                                     const oTm& a,
00506                                     const algebra::polynom<Tm, Tw>& b)
00507     {
00508       algebra::polynom<Tm, Tw> ret(b);
00509       op_in_add(s, monoid, ret, a);
00510       return ret;
00511     }
00512 
00513     /*----------------------------------------.
00514     | foreign addition with semiring elements |
00515     `----------------------------------------*/
00516 
00517     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00518     void op_in_add(const algebra::Series<W, M>& s,
00519                    const algebra::SemiringBase<W>& semiring,
00520                    algebra::polynom<Tm, Tw>& dst,
00521                    const oTw& src)
00522     {
00523       precondition(& s.semiring() == & semiring);
00524       if (src != zero_value(SELECT(W), SELECT(oTw)))
00525         dst.add(s.semiring(),
00526                 identity_value(SELECT(M), SELECT(Tm)),
00527                 op_convert(SELECT(W), SELECT(Tw), src));
00528     }
00529 
00530     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00531     algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
00532                                     const algebra::SemiringBase<W>& semiring,
00533                                     const algebra::polynom<Tm, Tw>& a,
00534                                     const oTw& b)
00535     {
00536       algebra::polynom<Tm, Tw> ret(a);
00537       op_in_add(s, semiring, ret, b);
00538       return ret;
00539     }
00540 
00541     template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00542     algebra::polynom<Tm, Tw> op_add(const algebra::SemiringBase<W>& semiring,
00543                                     const algebra::Series<W, M>& s,
00544                                     const oTw& a,
00545                                     const algebra::polynom<Tm, Tw>& b)
00546     {
00547       algebra::polynom<Tm, Tw> ret(b);
00548       op_in_add(s, semiring, ret, a);
00549       return ret;
00550     }
00551 
00552     /*--------------------------------------------.
00553     | foreign multiplication by semiring elements |
00554     `--------------------------------------------*/
00555 
00556     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00557     void op_in_mul(const algebra::Series<W, M>& s,
00558                    const algebra::SemiringBase<W>& semiring,
00559                    algebra::polynom<Tm, Tw>& dst,
00560                    const oTw& src)
00561     {
00562       precondition(& s.semiring() == & semiring);
00563       (void) s; (void) semiring;
00564 
00565       typename algebra::polynom<Tm, Tw>::iterator p;
00566       for (typename algebra::polynom<Tm, Tw>::iterator i = dst.begin();
00567            i != dst.end();
00568           )
00569       {
00570         p = i++;
00571         op_in_mul(s.semiring(), p->second, src);
00572         if (p->second == zero_value(SELECT(W), SELECT(Tw)))
00573           dst.erase(p);
00574       }
00575     }
00576 
00577     template<typename W, typename M, typename Tm, typename Tw, typename oTw>
00578     algebra::polynom<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
00579                                     const algebra::SemiringBase<W>& semiring,
00580                                     const algebra::polynom<Tm, Tw>& a,
00581                                     const oTw& b)
00582     {
00583       algebra::polynom<Tm, Tw> ret(a);
00584       op_in_mul(s, semiring, ret, b);
00585       return ret;
00586     }
00587 
00588     template<typename W, typename M, typename oTw, typename Tm, typename Tw>
00589     algebra::polynom<Tm, Tw> op_mul(const algebra::SemiringBase<W>& semiring,
00590                                     const algebra::Series<W, M>& s,
00591                                     const oTw& a,
00592                                     const algebra::polynom<Tm, Tw>& b)
00593     {
00594       precondition(& s.semiring() == & semiring);
00595       (void) s; (void) semiring;
00596 
00597       algebra::polynom<Tm, Tw> ret(b);
00598 
00599       typename algebra::polynom<Tm, Tw>::iterator p;
00600       for (typename algebra::polynom<Tm, Tw>::iterator i = ret.begin();
00601            i != ret.end();)
00602       {
00603         p = i++;
00604         p->second = op_mul(s.semiring(), a, p->second);
00605         if (p->second == zero_value(SELECT(W), SELECT(Tw)))
00606           ret.erase(p);
00607       }
00608       return ret;
00609     }
00610 
00611     /*-------------.
00612     | input-output |
00613     `-------------*/
00614 
00615     template<typename W, typename M, typename St, typename Tm, typename Tw>
00616     St& op_rout(const algebra::Series<W, M>& s,
00617                 St& st,
00618                 const algebra::polynom<Tm, Tw>& p)
00619     {
00620       typename algebra::polynom<Tm, Tw>::const_iterator i = p.begin();
00621 
00622       while (i != p.end())
00623       {
00624         if (i != p.begin())
00625           st << s.representation()->plus;
00626 
00627         if (i->second != identity_value(SELECT(W), SELECT(Tw)))
00628         {
00629           st << s.representation()->open_par
00630              << s.representation()->open_weight;
00631           op_rout(s.semiring(), st, i->second);
00632           st << s.representation()->close_weight
00633              << s.representation()->spaces.front();
00634         }
00635 
00636         op_rout(s.monoid(), st, i->first);
00637 
00638         if (i->second != identity_value(SELECT(W), SELECT(Tw)))
00639           st << s.representation()->close_par;
00640 
00641         ++i;
00642       }
00643 
00644       if (i == p.begin()) /* case zero */
00645         op_rout(s.semiring(), st, zero_value(SELECT(W), SELECT(Tw)));
00646 
00647       return st;
00648     }
00649 
00650     /*---------------------------------.
00651     | design_pattern series operations |
00652     `---------------------------------*/
00653 
00654     template<typename W, typename M, typename Tm, typename Tw, typename oTm>
00655     Tw op_series_get(const algebra::Series<W, M>& s,
00656                      const algebra::polynom<Tm, Tw>& p,
00657                      const oTm& m)
00658     {
00659       return p.get(s.semiring(), op_convert(s.semiring(), SELECT(Tm), m));
00660     }
00661 
00662     template <typename W, typename M,
00663               typename Tm, typename Tw,
00664               typename oTm, typename oTw>
00665     void op_series_set(const algebra::Series<W, M>& s,
00666                        algebra::polynom<Tm, Tw>& p,
00667                        const oTm& m,
00668                        const oTw& w)
00669     {
00670       const M&  monoid = s.monoid();
00671       const W&  semiring = s.semiring();
00672 
00673       typename misc::static_if
00674         <misc::static_eq<Tm, oTm>::value, const Tm&, Tm>::t
00675         new_m = op_convert(monoid, SELECT(Tm), m);
00676       typename misc::static_if
00677         <misc::static_eq<Tw, oTw>::value, const Tw&, Tw>::t
00678         new_w = op_convert(semiring, SELECT(Tw), w);
00679 
00680       typename algebra::polynom<Tm, Tw>::iterator i = p.find(new_m);
00681       if (new_w == zero_value(semiring, new_w))
00682       {
00683         if (i != p.end())
00684           p.erase(i);
00685       }
00686       else if (i == p.end())
00687         p.insert(new_m, new_w);
00688       else
00689         i->second = new_w;
00690     }
00691 
00692     template <class W, class M, class Tm, class Tw>
00693     Tm op_choose_from_supp(const algebra::Series<W, M>&,
00694                            const algebra::polynom<Tm, Tw>& p)
00695     {
00696       typedef typename algebra::polynom<Tm, Tw>::const_iterator const_iterator;
00697 
00698       const unsigned size = p.size();
00699 
00700       if (size == 0)
00701         return Tm();
00702 
00703       const_iterator i = p.begin();
00704 
00705       // No need to call rand in this case
00706       if (size == 1)
00707         return i->first;
00708 
00709       unsigned index = rand() % size;
00710       while (index > 0)
00711       {
00712         --index;
00713         ++i;
00714       }
00715       return i->first;
00716     }
00717 
00718     template <class W, class M, class Tm, class Tw>
00719     Element<algebra::Series<W,M>, algebra::polynom<Tm,Tw> >
00720     op_choose(const algebra::Series<W,M>& s,
00721               SELECTOR2(algebra::polynom<Tm,Tw>))
00722     {
00723       algebra::polynom<Tm, Tw> p;
00724       // FIXME: add global constants to define this !
00725       unsigned nb_monome = rand() * 10 / RAND_MAX;
00726       for (unsigned i = 0; i < nb_monome; ++i)
00727         p[s.monoid().choose()] = s.semiring().choose();
00728       return Element<algebra::Series<W,M>, algebra::polynom<Tm,Tw> >(s, p);
00729     }
00730 
00731     /*----------.
00732     | transpose |
00733     `----------*/
00734 
00735     template <typename W, typename M, typename Tm, typename Tw>
00736     void  op_in_transpose(const algebra::Series<W, M>& s,
00737                           algebra::polynom<Tm, Tw>& t)
00738     {
00739       algebra::DefaultTransposeFun<algebra::Series<W, M>,
00740                                    algebra::polynom<Tm, Tw> > f;
00741       t = f(s, t);
00742     }
00743 
00744   } // ! algebra
00745 
00746 } // ! vcsn
00747 
00748 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_POLYNOMS_HXX