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