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