Vaucanson  1.4.1
polynoms.hxx
1 // polynoms.hxx: this file is part of the Vaucanson project.
2 //
3 // Vaucanson, a generic library for finite state machines.
4 //
5 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010, 2011 The
6 // Vaucanson Group.
7 //
8 // This program is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU General Public License
10 // as published by the Free Software Foundation; either version 2
11 // of the License, or (at your option) any later version.
12 //
13 // The complete GNU General Public Licence Notice can be found as the
14 // `COPYING' file in the root directory.
15 //
16 // The Vaucanson Group consists of people listed in the `AUTHORS' file.
17 //
18 #ifndef VCSN_ALGEBRA_IMPLEMENTATION_SERIES_POLYNOMS_HXX
19 # define VCSN_ALGEBRA_IMPLEMENTATION_SERIES_POLYNOMS_HXX
20 
21 # include <vaucanson/algebra/implementation/series/polynoms.hh>
22 # include <vaucanson/algebra/concept/freemonoid_base.hh>
23 
24 # include <vaucanson/misc/contract.hh>
25 # include <vaucanson/misc/escaper.hh>
26 
27 namespace vcsn
28 {
29  namespace algebra
30  {
31  /*----------------.
32  | polynom<Tm, Tw> |
33  `----------------*/
34 
35  template<typename Tm, typename Tw>
36  template<typename M, typename W>
37  polynom<Tm, Tw>::polynom(SELECTOR(M), SELECTOR(W))
38  {
39  map_.insert(std::make_pair(identity_value(SELECT(M), SELECT(Tm)),
40  identity_value(SELECT(W), SELECT(Tw))));
41  }
42 
43  template<typename Tm, typename Tw>
44  polynom<Tm, Tw>::polynom(const polynom& other) : map_(other.map_)
45  {}
46 
47  template<typename Tm, typename Tw>
48  polynom<Tm, Tw>::polynom() : map_()
49  {}
50 
51  template<typename Tm, typename Tw>
52  size_t
53  polynom<Tm, Tw>::size() const
54  {
55  return map_.size();
56  }
57 
58  template<typename Tm, typename Tw>
59  bool polynom<Tm, Tw>::empty() const
60  {
61  return map_.empty();
62  }
63 
64  template<typename Tm, typename Tw>
65  typename polynom<Tm, Tw>::iterator
66  polynom<Tm, Tw>::begin()
67  {
68  return map_.begin();
69  }
70 
71  template<typename Tm, typename Tw>
72  typename polynom<Tm, Tw>::const_iterator
73  polynom<Tm, Tw>::begin() const
74  {
75  return map_.begin();
76  }
77 
78  template<typename Tm, typename Tw>
79  typename polynom<Tm, Tw>::iterator
80  polynom<Tm, Tw>::end()
81  {
82  return map_.end();
83  }
84 
85  template<typename Tm, typename Tw>
86  typename polynom<Tm, Tw>::const_iterator
87  polynom<Tm, Tw>::end() const
88  {
89  return map_.end();
90  }
91 
92  template<typename Tm, typename Tw>
93  typename polynom<Tm, Tw>::iterator
94  polynom<Tm, Tw>::find(const Tm& m)
95  {
96  return map_.find(m);
97  }
98 
99  template<typename Tm, typename Tw>
100  typename polynom<Tm, Tw>::const_iterator
101  polynom<Tm, Tw>::find(const Tm& m) const
102  {
103  return map_.find(m);
104  }
105 
106  template<typename Tm, typename Tw>
107  template<typename W>
108  Tw& polynom<Tm, Tw>::make_get(SELECTOR(W), const Tm& m)
109  {
110  std::pair<iterator, bool> i =
111  map_.insert(std::make_pair(m, zero_value(SELECT(W), SELECT(Tw))));
112  return i.first->second;
113  }
114 
115  template<typename Tm, typename Tw>
116  template<typename W>
117  Tw polynom<Tm, Tw>::get(SELECTOR(W), const Tm& m) const
118  {
119  const_iterator i;
120  if ((i = map_.find(m)) == map_.end())
121  return zero_value(SELECT(W), SELECT(Tw));
122  return i->second;
123  }
124 
125  template<typename Tm, typename Tw>
126  void polynom<Tm, Tw>::insert(const Tm& m, const Tw& w)
127  {
128  map_.insert(std::make_pair(m, w));
129  }
130 
131  template<typename Tm, typename Tw>
132  template<typename W>
133  void polynom<Tm, Tw>::add(const W& semiring, const Tm& m, const Tw& w)
134  {
135  Tw& o = make_get(SELECT(W), m);
136  op_in_add(semiring, o, w);
137  }
138 
139  template<typename Tm, typename Tw>
140  void polynom<Tm, Tw>::erase(iterator i)
141  {
142  map_.erase(i);
143  }
144 
145  template<typename Tm, typename Tw>
146  void polynom<Tm, Tw>::clear()
147  {
148  map_.clear();
149  }
150 
151  template<typename Tm, typename Tw>
152  void polynom<Tm, Tw>::swap(polynom<Tm, Tw>& other)
153  {
154  map_.swap(other.map_);
155  }
156 
157  template<typename Tm, typename Tw>
158  const std::map<Tm, Tw>&
159  polynom<Tm, Tw>::as_map() const
160  {
161  return map_;
162  }
163 
164  template<typename Tm, typename Tw>
165  const Tw&
166  polynom<Tm, Tw>::operator [] (const Tm& m) const
167  {
168  const_iterator i = map_.find(m);
169 
170  postcondition_ (i != map_.end(),
171  "Word is not in the support");
172 
173  return i->second;
174  }
175 
176  template<typename Tm, typename Tw>
177  Tw&
178  polynom<Tm, Tw>::operator [] (const Tm& m)
179  {
180  return map_[m];
181  }
182 
183  template <class Series, class Tm, class Tw>
184  polynom<Tm,Tw>
185  DefaultTransposeFun<Series, polynom<Tm,Tw> >::
186  operator()(const Series& s,const polynom<Tm,Tw>& t) const
187  {
188  typedef typename polynom<Tm, Tw>::const_iterator const_iterator;
189  typedef typename Series::monoid_t monoid_t;
190  typedef Element<monoid_t, Tm> monoid_elt_t;
191 
192  polynom<Tm, Tw> p;
193 
194  for (const_iterator i = t.begin(); i != t.end(); ++i)
195  {
196  monoid_elt_t m (s.monoid(), i->first);
197  m.mirror();
198  p[m.value()] = transpose(s.semiring(), i->second);
199  }
200  return p;
201  }
202 
203  template <class Series, class Tm, class Tw>
204  template <class S>
205  Tw
206  DefaultTransposeFun<Series, polynom<Tm,Tw> >::
207  transpose(const SeriesBase<S>& s, const Tw& t)
208  {
209  Element<S, Tw> e (s.self(), t);
210  e.transpose();
211  return e.value();
212  }
213 
214  template <class Series, class Tm, class Tw>
215  template <class S>
216  Tw
217  DefaultTransposeFun<Series, polynom<Tm,Tw> >::
218  transpose(const SemiringBase<S>&, const Tw& t)
219  {
220  return t;
221  }
222 
223  template <class Tm, class Tw>
224  bool operator==(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs)
225  {
226  return lhs.as_map() == rhs.as_map();
227  }
228 
229  template <class Tm, class Tw>
230  bool operator!=(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs)
231  {
232  return !(lhs == rhs);
233  }
234 
235  template <class Tm, class Tw>
236  bool operator<(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs)
237  {
238  return lhs.as_map() < rhs.as_map();
239  }
240 
241  template <class Tm, class Tw>
242  bool operator>(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs)
243  {
244  return lhs.as_map() > rhs.as_map();
245  }
246 
247  template <class Tm, class Tw>
248  bool operator<=(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs)
249  {
250  return lhs.as_map() <= rhs.as_map();
251  }
252 
253  template <class Tm, class Tw>
254  bool operator>=(const polynom<Tm, Tw>& lhs, const polynom<Tm, Tw>& rhs)
255  {
256  return lhs.as_map() >= rhs.as_map();
257  }
258 
259  /*-------------------.
260  | External functions |
261  `-------------------*/
262 
263  template<typename W, typename M, typename Tm, typename Tw>
264  bool op_contains(const algebra::Series<W, M>& s,
265  const algebra::polynom<Tm, Tw>& m)
266  {
267  for (typename algebra::polynom<Tm, Tw>::const_iterator i = m.begin();
268  i != m.end();
269  ++i)
270  if (!s.monoid().contains(i->first)
271  || !s.semiring().contains(i->second))
272  return false;
273  return true;
274  }
275 
276  template<typename Self, typename Tm, typename Tw>
277  bool op_starable(const algebra::SeriesBase<Self>&,
278  const algebra::polynom<Tm, Tw>& m)
279  {
280  int s = m.size();
281  if (s == 0)
282  return true;
283  if (s > 1)
284  return false;
285 
286  typename std::pair<Tm, Tw> elt = *m.as_map().begin();
287  if (elt.first != identity_value(SELECT(typename Self::monoid_t),
288  SELECT(Tm)))
289  return false;
290 
291  return op_starable(SELECT(typename Self::semiring_t), elt.second);
292  }
293 
294 
295  template<typename Self, typename Tm, typename Tw>
296  void op_in_star(const algebra::SeriesBase<Self>&,
297  algebra::polynom<Tm, Tw>& m)
298  {
299  if (m.size() == 0)
300  {
301  Tw val (zero_value(SELECT(typename Self::semiring_t), SELECT(Tw)));
302  op_in_star(SELECT(typename Self::semiring_t), val);
303  m.insert(identity_value(SELECT(typename Self::monoid_t), SELECT(Tm)),
304  val);
305  }
306  else
307  {
308  typename std::pair<Tm, Tw> elt = *m.as_map().begin();
309  assertion_ (!(m.size() > 1 ||
310  elt.first != identity_value(SELECT(typename
311  Self::monoid_t),
312  SELECT(Tm))),
313  "Support is not empty, star cannot be computed.");
314 
315  op_in_star(SELECT(typename Self::semiring_t), elt.second);
316  m.clear();
317  m.insert(elt.first, elt.second);
318  }
319  }
320 
321  template<typename W, typename M, typename Tm, typename Tw>
322  bool op_is_finite_app(const algebra::Series<W, M>&,
323  const algebra::polynom<Tm, Tw>&)
324  {
325  return true;
326  }
327 
328  template<typename W, typename M, typename Tm, typename Tw>
329  typename algebra::series_traits<algebra::polynom<Tm, Tw> >::support_t
330  op_support(const algebra::Series<W, M>&,
331  const algebra::polynom<Tm, Tw>& m)
332  {
333  return typename algebra::series_traits<algebra::polynom<Tm, Tw> >::
334  support_t(m.as_map());
335  }
336 
337  template<typename W, typename M, typename Tm, typename Tw>
338  const algebra::polynom<Tm, Tw>&
339  identity_value(SELECTOR2(algebra::Series<W, M>),
340  SELECTOR2(algebra::polynom<Tm, Tw>))
341  {
342  static const algebra::polynom<Tm, Tw> instance =
343  algebra::polynom<Tm, Tw>(SELECT(M), SELECT(W));
344  return instance;
345  }
346 
347  template<typename W, typename M, typename Tm, typename Tw>
348  const algebra::polynom<Tm, Tw>&
349  zero_value(SELECTOR2(algebra::Series<W, M>),
350  SELECTOR2(algebra::polynom<Tm, Tw>))
351  {
352  static const algebra::polynom<Tm, Tw> instance;
353  return instance;
354  }
355 
356  template<typename W, typename M, typename Tm, typename Tw>
357  void op_in_add(const algebra::Series<W, M>& s,
358  algebra::polynom<Tm, Tw>& dst,
359  const algebra::polynom<Tm, Tw>& arg)
360  {
361  typename algebra::polynom<Tm, Tw>::iterator p;
362  Tw zero = zero_value(SELECT(W), SELECT(Tw));
363  Tw w;
364 
365  for (typename algebra::polynom<Tm, Tw>::const_iterator i = arg.begin();
366  i != arg.end();
367  ++i)
368  if (i->second != zero)
369  {
370  p = dst.find(i->first);
371  if (p != dst.end())
372  {
373  w = i->second;
374  op_in_add(s.semiring(), w, p->second);
375  if (w == zero_value(SELECT(W), SELECT(Tw)))
376  dst.erase(p);
377  else
378  p->second = w;
379  }
380  else
381  dst.insert(i->first, i->second);
382  }
383  }
384 
385  template<typename W, typename M, typename Tm, typename Tw>
386  algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
387  const algebra::polynom<Tm, Tw>& a,
388  const algebra::polynom<Tm, Tw>& b)
389  {
390  algebra::polynom<Tm, Tw> ret(a);
391  op_in_add(s, ret, b);
392  return ret;
393  }
394 
395  /*-----------------.
396  | cauchy's product |
397  `-----------------*/
398 
399  template<typename W, typename M, typename Tm, typename Tw>
400  algebra::polynom<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
401  const algebra::polynom<Tm, Tw>& a,
402  const algebra::polynom<Tm, Tw>& b)
403  {
404  algebra::polynom<Tm, Tw> ret;
405  for (typename algebra::polynom<Tm, Tw>::const_iterator i = a.begin();
406  i != a.end();
407  ++i)
408  for (typename algebra::polynom<Tm, Tw>::const_iterator j = b.begin();
409  j != b.end();
410  ++j)
411  {
412  Tw w = op_mul(s.semiring(), i->second, j->second);
413  if (w != zero_value(SELECT(W), SELECT(Tw)))
414  ret.add(s.semiring(),
415  op_mul(s.monoid(), i->first, j->first),
416  w);
417  }
418  return ret;
419  }
420 
421  template<typename W, typename M, typename Tm, typename Tw>
422  void op_in_mul(const algebra::Series<W, M>& s,
423  algebra::polynom<Tm, Tw>& dst,
424  const algebra::polynom<Tm, Tw>& arg)
425  {
426  op_assign(s, dst, op_mul(s, dst, arg));
427  }
428 
429  /*---------------------.
430  | foreign constructors |
431  `---------------------*/
432 
433  template <typename Tm, typename Tw, typename W, typename M>
434  algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
435  SELECTOR2(algebra::polynom<Tm, Tw>),
436  const Tm& m_value)
437  {
438  algebra::polynom<Tm, Tw> p(SELECT(M), SELECT(W));
439  p.insert(m_value, identity_value(SELECT(W), SELECT(Tw)));
440  return p;
441  }
442 
443  template<typename Tm, typename Tw, typename W, typename M, typename oTm>
444  algebra::polynom<Tm, Tw> op_convert(const algebra::Series<W, M>& s,
445  SELECTOR2(algebra::polynom<Tm, Tw>),
446  SELECTOR(algebra::MonoidBase<M>),
447  const oTm& m_value)
448  {
449  const M& monoid = s.monoid();
450  const W& semiring = s.semiring();
451 
452  algebra::polynom<Tm, Tw> ret;
453  ret.insert(op_convert(monoid, SELECT(Tm), m_value),
454  identity_value(semiring, SELECT(Tw)));
455  return ret;
456  }
457 
458  template<typename Tm, typename Tw, typename W, typename M, typename oTw>
459  algebra::polynom<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
460  SELECTOR2(algebra::polynom<Tm, Tw>),
461  SELECTOR(algebra::SemiringBase<W>),
462  const oTw& w_value)
463  {
464  algebra::polynom<Tm, Tw> ret;
465  if (w_value != zero_value(SELECT(W), SELECT(oTw)))
466  ret.insert(identity_value(SELECT(M), SELECT(Tm)),
467  op_convert(SELECT(W), SELECT(Tw), w_value));
468  return ret;
469  }
470 
471  template<typename W, typename M, typename Tm, typename Tw, typename oTm>
472  void op_assign(const algebra::Series<W, M>&,
473  const algebra::MonoidBase<M>&,
474  algebra::polynom<Tm, Tw>& dst,
475  const oTm& src)
476  {
477  dst.clear();
478  dst.insert(op_convert(SELECT(M), SELECT(Tm), src),
479  identity_value(SELECT(W), SELECT(Tw)));
480  }
481 
482  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
483  void op_assign(const algebra::Series<W, M>& s,
484  const algebra::SemiringBase<W>&,
485  algebra::polynom<Tm, Tw>& dst,
486  const oTw& src)
487  {
488  dst.clear();
489  if (src != zero_value(SELECT(W), SELECT(oTw)))
490  dst.insert(identity_value(SELECT(M), SELECT(Tm)),
491  op_convert(SELECT(W), SELECT(Tw), src));
492  }
493 
494  /*--------------------------------------.
495  | foreign addition with monoid elements |
496  `--------------------------------------*/
497 
498  template<typename W, typename M, typename Tm, typename Tw, typename oTm>
499  void op_in_add(const algebra::Series<W, M>& s,
500  const algebra::MonoidBase<M>& monoid,
501  algebra::polynom<Tm, Tw>& dst,
502  const oTm& src)
503  {
504  precondition(& s.monoid() == & monoid);
505  dst.add(s.semiring(),
506  op_convert(SELECT(M), SELECT(Tm), src),
507  identity_value(SELECT(W), SELECT(Tw)));
508  }
509 
510  template<typename W, typename M, typename Tm, typename Tw, typename oTm>
511  algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
512  const algebra::MonoidBase<M>& monoid,
513  const algebra::polynom<Tm, Tw>& a,
514  const oTm& b)
515  {
516  algebra::polynom<Tm, Tw> ret(a);
517  op_in_add(s, monoid, ret, b);
518  return ret;
519  }
520 
521  template<typename M, typename W, typename oTm, typename Tm, typename Tw>
522  algebra::polynom<Tm, Tw> op_add(const algebra::MonoidBase<M>& monoid,
523  const algebra::Series<W, M>& s,
524  const oTm& a,
525  const algebra::polynom<Tm, Tw>& b)
526  {
527  algebra::polynom<Tm, Tw> ret(b);
528  op_in_add(s, monoid, ret, a);
529  return ret;
530  }
531 
532  /*----------------------------------------.
533  | foreign addition with semiring elements |
534  `----------------------------------------*/
535 
536  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
537  void op_in_add(const algebra::Series<W, M>& s,
538  const algebra::SemiringBase<W>& semiring,
539  algebra::polynom<Tm, Tw>& dst,
540  const oTw& src)
541  {
542  precondition(& s.semiring() == & semiring);
543  if (src != zero_value(SELECT(W), SELECT(oTw)))
544  dst.add(s.semiring(),
545  identity_value(SELECT(M), SELECT(Tm)),
546  op_convert(SELECT(W), SELECT(Tw), src));
547  }
548 
549  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
550  algebra::polynom<Tm, Tw> op_add(const algebra::Series<W, M>& s,
551  const algebra::SemiringBase<W>& semiring,
552  const algebra::polynom<Tm, Tw>& a,
553  const oTw& b)
554  {
555  algebra::polynom<Tm, Tw> ret(a);
556  op_in_add(s, semiring, ret, b);
557  return ret;
558  }
559 
560  template<typename W, typename M, typename oTw, typename Tm, typename Tw>
561  algebra::polynom<Tm, Tw> op_add(const algebra::SemiringBase<W>& semiring,
562  const algebra::Series<W, M>& s,
563  const oTw& a,
564  const algebra::polynom<Tm, Tw>& b)
565  {
566  algebra::polynom<Tm, Tw> ret(b);
567  op_in_add(s, semiring, ret, a);
568  return ret;
569  }
570 
571  /*--------------------------------------------.
572  | foreign multiplication by semiring elements |
573  `--------------------------------------------*/
574 
575  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
576  void op_in_mul(const algebra::Series<W, M>& s,
577  const algebra::SemiringBase<W>& semiring,
578  algebra::polynom<Tm, Tw>& dst,
579  const oTw& src)
580  {
581  precondition(& s.semiring() == & semiring);
582  (void) s; (void) semiring;
583 
584  typename algebra::polynom<Tm, Tw>::iterator p;
585  for (typename algebra::polynom<Tm, Tw>::iterator i = dst.begin();
586  i != dst.end();
587  )
588  {
589  p = i++;
590  op_in_mul(s.semiring(), p->second, src);
591  if (p->second == zero_value(SELECT(W), SELECT(Tw)))
592  dst.erase(p);
593  }
594  }
595 
596  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
597  algebra::polynom<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
598  const algebra::SemiringBase<W>& semiring,
599  const algebra::polynom<Tm, Tw>& a,
600  const oTw& b)
601  {
602  algebra::polynom<Tm, Tw> ret(a);
603  op_in_mul(s, semiring, ret, b);
604  return ret;
605  }
606 
607  template<typename W, typename M, typename oTw, typename Tm, typename Tw>
608  algebra::polynom<Tm, Tw> op_mul(const algebra::SemiringBase<W>& semiring,
609  const algebra::Series<W, M>& s,
610  const oTw& a,
611  const algebra::polynom<Tm, Tw>& b)
612  {
613  precondition(& s.semiring() == & semiring);
614  (void) s; (void) semiring;
615 
616  algebra::polynom<Tm, Tw> ret(b);
617 
618  typename algebra::polynom<Tm, Tw>::iterator p;
619  for (typename algebra::polynom<Tm, Tw>::iterator i = ret.begin();
620  i != ret.end();)
621  {
622  p = i++;
623  p->second = op_mul(s.semiring(), a, p->second);
624  if (p->second == zero_value(SELECT(W), SELECT(Tw)))
625  ret.erase(p);
626  }
627  return ret;
628  }
629 
630  /*-------------.
631  | input-output |
632  `-------------*/
633 
634  template<typename W, typename M, typename St, typename Tm, typename Tw>
635  St& op_rout(const algebra::Series<W, M>& s,
636  St& st,
637  const algebra::polynom<Tm, Tw>& p)
638  {
639  typename algebra::polynom<Tm, Tw>::const_iterator i = p.begin();
640 
641  while (i != p.end())
642  {
643  if (i != p.begin())
644  st << s.representation()->plus;
645 
646  bool show_weight = (i->second != identity_value(SELECT(W), SELECT(Tw))
647  || show_identity_value(SELECT(W), SELECT(Tw)));
648 
649  if (show_weight)
650  {
651  st << s.representation()->open_par
652  << s.representation()->open_weight;
653  op_rout(s.semiring(), st, i->second);
654  st << s.representation()->close_weight
655  << s.representation()->spaces.front();
656  }
657 
658  op_rout(s.monoid(), st, i->first);
659 
660  if (show_weight)
661  st << s.representation()->close_par;
662 
663  ++i;
664  }
665 
666  if (i == p.begin()) /* case zero */
667  op_rout(s.semiring(), st, zero_value(SELECT(W), SELECT(Tw)));
668 
669  return st;
670  }
671 
672  /*---------------------------------.
673  | design_pattern series operations |
674  `---------------------------------*/
675 
676  template<typename W, typename M, typename Tm, typename Tw, typename oTm>
677  Tw op_series_get(const algebra::Series<W, M>& s,
678  const algebra::polynom<Tm, Tw>& p,
679  const oTm& m)
680  {
681  return p.get(s.semiring(), op_convert(s.semiring(), SELECT(Tm), m));
682  }
683 
684  template <typename W, typename M,
685  typename Tm, typename Tw,
686  typename oTm, typename oTw>
687  void op_series_set(const algebra::Series<W, M>& s,
688  algebra::polynom<Tm, Tw>& p,
689  const oTm& m,
690  const oTw& w)
691  {
692  const M& monoid = s.monoid();
693  const W& semiring = s.semiring();
694 
695  typename misc::static_if
696  <misc::static_eq<Tm, oTm>::value, const Tm&, Tm>::t
697  new_m = op_convert(monoid, SELECT(Tm), m);
698  typename misc::static_if
699  <misc::static_eq<Tw, oTw>::value, const Tw&, Tw>::t
700  new_w = op_convert(semiring, SELECT(Tw), w);
701 
702  typename algebra::polynom<Tm, Tw>::iterator i = p.find(new_m);
703  if (new_w == zero_value(semiring, new_w))
704  {
705  if (i != p.end())
706  p.erase(i);
707  }
708  else if (i == p.end())
709  p.insert(new_m, new_w);
710  else
711  i->second = new_w;
712  }
713 
714  template <class W, class M, class Tm, class Tw>
715  Tm op_choose_from_supp(const algebra::Series<W, M>&,
716  const algebra::polynom<Tm, Tw>& p)
717  {
718  typedef typename algebra::polynom<Tm, Tw>::const_iterator const_iterator;
719 
720  const unsigned size = p.size();
721 
722  if (size == 0)
723  return Tm();
724 
725  const_iterator i = p.begin();
726 
727  // No need to call rand in this case
728  if (size == 1)
729  return i->first;
730 
731  unsigned index = rand() % size;
732  while (index > 0)
733  {
734  --index;
735  ++i;
736  }
737  return i->first;
738  }
739 
740  template <class W, class M, class Tm, class Tw>
741  Element<algebra::Series<W,M>, algebra::polynom<Tm,Tw> >
742  op_choose(const algebra::Series<W,M>& s,
743  SELECTOR2(algebra::polynom<Tm,Tw>))
744  {
745  algebra::polynom<Tm, Tw> p;
746  // FIXME: add global constants to define this !
747  unsigned nb_monome = rand() * 10 / RAND_MAX;
748  for (unsigned i = 0; i < nb_monome; ++i)
749  p[s.monoid().choose()] = s.semiring().choose();
750  return Element<algebra::Series<W,M>, algebra::polynom<Tm,Tw> >(s, p);
751  }
752 
753  /*----------.
754  | transpose |
755  `----------*/
756 
757  template <typename W, typename M, typename Tm, typename Tw>
758  void op_in_transpose(const algebra::Series<W, M>& s,
759  algebra::polynom<Tm, Tw>& t)
760  {
761  algebra::DefaultTransposeFun<algebra::Series<W, M>,
762  algebra::polynom<Tm, Tw> > f;
763  t = f(s, t);
764  }
765 
766  } // ! algebra
767 
768 } // ! vcsn
769 
770 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_POLYNOMS_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1