|
Vaucanson 1.4
|
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
1.7.4