Vaucanson  1.4.1
krat.hxx
1 // krat.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, 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_KRAT_HXX
19 # define VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_HXX
20 
21 # include <utility>
22 # include <list>
23 
24 # include <vaucanson/algebra/implementation/series/series.hh>
25 # include <vaucanson/algebra/implementation/series/rat/exp.hh>
26 # include <vaucanson/algebra/implementation/series/rat/random_visitor.hh>
27 # include <vaucanson/misc/usual_macros.hh>
28 
29 # include <vaucanson/algebra/implementation/series/krat_exp_is_finite_app.hxx>
30 # include <vaucanson/algebra/implementation/series/krat_exp_support.hxx>
31 # include <vaucanson/algebra/implementation/series/krat_exp_transpose.hxx>
32 
33 # include <vaucanson/algorithms/eval.hh>
34 # include <vaucanson/algorithms/standard_of.hh>
35 
36 # include <vaucanson/algebra/implementation/series/polynoms.hh>
37 # include <vaucanson/automata/concept/automata.hh>
38 
39 # include <vaucanson/misc/contract.hh>
40 
41 namespace vcsn
42 {
43  namespace algebra
44  {
59  template<typename W, typename M, typename Tm, typename Tw>
60  bool op_contains(const algebra::Series<W, M>&, const rat::exp<Tm, Tw>&)
61  {
62  pure_service_call ("default version of op_contains(Series<W,M>, exp<Tm,Tw>)");
63  return true;
64  }
65 
66  template<typename W, typename M, typename Tm, typename Tw>
67  bool op_is_finite_app(const algebra::Series<W, M>&,
68  const rat::exp<Tm, Tw>& m)
69  {
70  vcsn::IsFiniteAppMatcher<
71  algebra::Series<W, M>,
72  vcsn::rat::exp<Tm, Tw>,
73  algebra::DispatchFunction<vcsn::rat::exp<Tm, Tw> >
74  > matcher;
75  return matcher.match(m);
76  }
77 
78  template<typename W, typename M, typename Tm, typename Tw>
79  typename algebra::series_traits<rat::exp<Tm, Tw> >::support_t
80  op_support(const algebra::Series<W, M>& s, const rat::exp<Tm, Tw>& m)
81  {
82  vcsn::SupportMatcher<
83  algebra::Series<W, M>, rat::exp<Tm, Tw>,
84  algebra::DispatchFunction<rat::exp<Tm, Tw> >
85  > matcher(s);
86  matcher.match(m);
87  return matcher.get();
88  }
89 
90  template <typename W, typename M, typename Tm, typename Tw>
91  Tm op_choose_from_supp(const algebra::Series<W, M>&,
92  const rat::exp<Tm, Tw>& m)
93  {
94  rat::RandomVisitor<Tm, Tw> v;
95  m.accept(v);
96  return v.get();
97  }
98 
99  template<typename W, typename M, typename Tm, typename Tw>
100  const rat::exp<Tm, Tw>& identity_value(SELECTOR2(algebra::Series<W, M>),
101  SELECTOR2(rat::exp<Tm, Tw>))
102  {
103  static const rat::exp<Tm, Tw> instance = rat::exp<Tm, Tw>::one();
104  return instance;
105  }
106 
107  template<typename W, typename M, typename Tm, typename Tw>
108  bool show_identity_value(SELECTOR2(algebra::Series<W, M>),
109  SELECTOR2(rat::exp<Tm, Tw>))
110  {
111  return true;
112  }
113 
114  template<typename W, typename M, typename Tm, typename Tw>
115  const rat::exp<Tm, Tw>& zero_value(SELECTOR2(algebra::Series<W, M>),
116  SELECTOR2(rat::exp<Tm, Tw>))
117  {
118  static const rat::exp<Tm, Tw> instance = rat::exp<Tm, Tw>::zero();
119  return instance;
120  }
121 
122  template <typename W, typename M, typename Tm, typename Tw>
123  void op_in_transpose(const algebra::Series<W, M>& s,
124  rat::exp<Tm, Tw>& exp)
125  {
126  Element<algebra::Series<W, M>,
127  rat::exp<Tm, Tw> > elt(s, exp);
128 
129  vcsn::algebra::KRatExpTranspose<
130  algebra::Series<W, M>,
131  rat::exp<Tm, Tw>,
132  algebra::DispatchFunction<vcsn::rat::exp<Tm, Tw> >
133  > matcher(elt);
134 
135  elt = matcher.match(exp);
136  exp = elt.value();
137  }
138 
139  template<typename W, typename M, typename Tm, typename Tw>
140  void op_in_add(const algebra::Series<W, M>&,
141  rat::exp<Tm, Tw>& dst,
142  const rat::exp<Tm, Tw>& arg)
143  {
144  // case E + 0
145  if (arg.base()->what() == rat::Node<Tm, Tw>::zero)
146  return ;
147 
148  // case 0 + E
149  if (dst.base()->what() == rat::Node<Tm, Tw>::zero)
150  {
151  delete dst.base();
152  dst.base() = arg.base()->clone();
153  return;
154  }
155 
156  dst.base() = new rat::Sum<Tm, Tw>(dst.base(), arg.base()->clone());
157  }
158 
159  template<typename W, typename M, typename Tm, typename Tw>
160  rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
161  const rat::exp<Tm, Tw>& a,
162  const rat::exp<Tm, Tw>& b)
163  {
164  rat::exp<Tm, Tw> ret(a);
165  op_in_add(s, ret, b);
166  return ret;
167  }
168 
169  template<typename W, typename M, typename Tm, typename Tw>
170  void op_in_mul(const algebra::Series<W, M>& s,
171  rat::exp<Tm, Tw>& dst,
172  const rat::exp<Tm, Tw>& arg)
173  {
174  typedef rat::Node<Tm, Tw> node_t;
175  typedef typename rat::Node<Tm, Tw>::type type;
176  typedef rat::One<Tm, Tw> n_one_t;
177  typedef rat::Constant<Tm, Tw> n_const_t;
178  typedef rat::Zero<Tm, Tw> n_zero_t;
179  typedef rat::Star<Tm, Tw> n_star_t;
180  typedef rat::LeftWeighted<Tm, Tw> n_lweight_t;
181  typedef rat::RightWeighted<Tm, Tw> n_rweight_t;
182  typedef rat::Sum<Tm, Tw> n_sum_t;
183  typedef rat::Product<Tm, Tw> n_prod_t;
184 
185  type this_type = dst.base()->what();
186  type arg_type = arg.base()->what();
187 
188  // case 0 . E -> 0
189  if (this_type == node_t::zero)
190  return;
191 
192  // case E . 0 -> 0
193  if (arg_type == node_t::zero)
194  {
195  delete dst.base();
196  dst.base() = new n_zero_t;
197  return;
198  }
199 
200  // case 1 . E -> E
201  if (this_type == node_t::one)
202  {
203  delete dst.base();
204  dst.base() = arg.base()->clone();
205  return;
206  }
207 
208  // case E . 1 -> E
209  if (arg_type == node_t::one)
210  {
211  return;
212  }
213 
214  // case E . {k'} 1 -> E {k'}
215  if (arg_type == node_t::lweight)
216  {
217  n_lweight_t *p = dynamic_cast<n_lweight_t*>(arg.base());
218  if (p->child_->what() == node_t::one)
219  {
220  op_in_mul(s, s.semiring(), dst, p->weight_);
221  return;
222  }
223  }
224 
225  // case {k} 1 . E -> {k} E
226  if (this_type == node_t::lweight)
227  {
228  n_lweight_t *p = dynamic_cast<n_lweight_t*>(dst.base());
229  if (p->child_->what() == node_t::one)
230  {
231  dst = op_mul(s.semiring(), s, p->weight_, arg);
232  return;
233  }
234  }
235 
236  // general case : {k} E . E'
237  dst.base() = new n_prod_t(dst.base(), arg.base()->clone());
238  return;
239  }
240 
241  template<typename W, typename M, typename Tm, typename Tw>
242  rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
243  const rat::exp<Tm, Tw>& a,
244  const rat::exp<Tm, Tw>& b)
245  {
246  rat::exp<Tm, Tw> ret(a);
247  op_in_mul(s, ret, b);
248  return ret;
249  }
250 
251  template <typename W, typename M, typename Tm, typename Tw, typename St>
252  St&
253  op_rout(const algebra::Series<W, M>& s,
254  St& st,
255  const rat::exp<Tm, Tw>& e)
256  {
257  rat::DumpVisitor<Tm, Tw, W, M> v (st, s.monoid(), s.representation());
258  e.accept(v);
259  return st;
260  }
261 
262  /*---------------------.
263  | foreign constructors |
264  `---------------------*/
265 
266  template<typename Tm, typename Tw, typename M, typename W>
267  rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<M, W>),
268  SELECTOR2(rat::exp<Tm, Tw>),
269  const Tm& m_value)
270  {
271  return new rat::Constant<Tm, Tw>(m_value);
272  }
273 
274  template<typename Tm, typename Tw, typename M, typename W>
275  rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<M, W>),
276  SELECTOR2(rat::exp<Tm, Tw>),
277  char m_value)
278  {
279  const char str[] = {m_value, '\0'};
280  return new rat::Constant<Tm, Tw>(str);
281  }
282 
283  template<typename Tm, typename Tw, typename W, typename M, typename oTm>
284  rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>) s,
285  SELECTOR2(rat::exp<Tm, Tw>),
286  SELECTOR(M),
287  const oTm& m_value)
288  {
289  if (m_value == identity_value(SELECT(M), SELECT(oTm)))
290  return rat::exp<Tm, Tw>::one();
291 
292  return rat::exp<Tm, Tw>::constant(op_convert(s.monoid(), SELECT(Tm),
293  m_value));
294  }
295 
296  template<typename Tm, typename Tw, typename W, typename M, typename oTw>
297  rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>),
298  SELECTOR2(rat::exp<Tm, Tw>),
299  SELECTOR(W),
300  const oTw& w_value)
301  {
302  if (w_value == identity_value(SELECT(W), SELECT(oTw)))
303  return rat::exp<Tm, Tw>::one();
304  if (w_value == zero_value(SELECT(W), SELECT(oTw)))
305  return rat::exp<Tm, Tw>::zero();
306  rat::exp<Tm, Tw> ret = rat::exp<Tm, Tw>::one();
307  ret.base() = new rat::LeftWeighted<Tm, Tw>
308  (op_convert(SELECT(W), SELECT(Tw),
309  w_value), ret.base());
310  return ret;
311  }
312 
313  template <typename W, typename M, typename Tm, typename Tw, typename oTm>
314  void op_assign(SELECTOR2(algebra::Series<W, M>) s,
315  SELECTOR(M),
316  rat::exp<Tm, Tw>& dst,
317  const oTm& src)
318  {
319  dst = op_convert(s,
320  SELECT2(rat::exp<Tm, Tw>),
321  SELECT(M), src);
322  }
323 
324  template <typename W, typename M, typename Tm, typename Tw, typename oTw>
325  void op_assign(SELECTOR2(algebra::Series<W, M>) s,
326  SELECTOR(W),
327  rat::exp<Tm, Tw>& dst,
328  const oTw& src)
329  {
330  dst = op_convert(s,
331  SELECT2(rat::exp<Tm, Tw>),
332  SELECT(W), src);
333  }
334 
335  /*-----.
336  | star |
337  `-----*/
338 
339  template<typename W, typename M, typename Tm, typename Tw>
340  bool op_starable(const algebra::Series<W, M>&,
341  const rat::exp<Tm, Tw>&)
342  {
343  return true;
344  }
345 
346  template<typename W, typename M, typename Tm, typename Tw>
347  void op_in_star(const algebra::Series<W, M>&,
348  rat::exp<Tm, Tw>& dst)
349  {
350  // rewrite 0* as 1
351  if (dst.base()->what() == rat::Node<Tm, Tw>::zero)
352  dst = rat::exp<Tm, Tw>::one();
353  else
354  dst.base() = new rat::Star<Tm, Tw>(dst.base());
355  }
356 
357  template<typename W, typename M, typename Tm, typename Tw>
358  rat::exp<Tm, Tw>
359  op_star(const algebra::Series<W, M>& s,
360  const rat::exp<Tm, Tw>& src)
361  {
362  rat::exp<Tm, Tw> ret(src);
363  op_in_star(s, ret);
364  return ret;
365  }
366 
367  /*--------------------------------------.
368  | foreign addition with monoid elements |
369  `--------------------------------------*/
370 
371  template<typename W, typename M, typename Tm, typename Tw, typename oTm>
372  void op_in_add(const algebra::Series<W, M>& s,
373  const M& monoid,
374  rat::exp<Tm, Tw>& dst,
375  const oTm& src)
376  {
377  op_in_add(s, dst, op_convert(s,
378  SELECT2(rat::exp<Tm, Tw>),
379  SELECT(M),
380  src));
381  }
382 
383  template<typename W, typename M, typename Tm, typename Tw, typename oTm>
384  rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
385  const M& monoid,
386  const rat::exp<Tm, Tw>& a,
387  const oTm& b)
388  {
389  rat::exp<Tm, Tw> ret(a);
390  op_in_add(s, monoid, ret, b);
391  return ret;
392  }
393 
394  template<typename M, typename W, typename oTm, typename Tm, typename Tw>
395  rat::exp<Tm, Tw> op_add(const M& monoid,
396  const algebra::Series<W, M>& s,
397  const oTm& a,
398  const rat::exp<Tm, Tw>& b)
399  {
400  rat::exp<Tm, Tw> ret(b);
401  op_in_add(s, monoid, ret, a);
402  return ret;
403  }
404 
405  /*----------------------------------------.
406  | foreign addition with semiring elements |
407  `----------------------------------------*/
408 
409  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
410  void op_in_add(const algebra::Series<W, M>& s,
411  const W& semiring,
412  rat::exp<Tm, Tw>& dst,
413  const oTw& src)
414  {
415  precondition(& s.semiring() == & semiring);
416  op_in_add(s, dst, op_convert(s,
417  SELECT2(rat::exp<Tm, Tw>),
418  SELECT(W),
419  src));
420  }
421 
422  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
423  rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s,
424  const W& semiring,
425  const rat::exp<Tm, Tw>& a,
426  const oTw& b)
427  {
428  rat::exp<Tm, Tw> ret(a);
429  op_in_add(s, semiring, ret, b);
430  return ret;
431  }
432 
433  template<typename W, typename M, typename oTw, typename Tm, typename Tw>
434  rat::exp<Tm, Tw> op_add(const W& semiring,
435  const algebra::Series<W, M>& s,
436  const oTw& a,
437  const rat::exp<Tm, Tw>& b)
438  {
439  rat::exp<Tm, Tw> ret(b);
440  op_in_add(s, semiring, ret, a);
441  return ret;
442  }
443 
444  /*--------------------------------------------.
445  | foreign multiplication by semiring elements |
446  `--------------------------------------------*/
447 
448  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
449  void op_in_mul(const algebra::Series<W, M>& s,
450  const W& semiring,
451  rat::exp<Tm, Tw>& ret,
452  const oTw& w)
453  {
454  precondition(& s.semiring() == & semiring);
455  (void) s; (void) semiring;
456 
457  typedef rat::Node<Tm, Tw> node_t;
458  typedef typename rat::Node<Tm, Tw>::type type;
459  typedef rat::One<Tm, Tw> n_one_t;
460  typedef rat::Constant<Tm, Tw> n_const_t;
461  typedef rat::Zero<Tm, Tw> n_zero_t;
462  typedef rat::Star<Tm, Tw> n_star_t;
463  typedef rat::LeftWeighted<Tm, Tw> n_lweight_t;
464  typedef rat::RightWeighted<Tm, Tw> n_rweight_t;
465  typedef rat::Sum<Tm, Tw> n_sum_t;
466  typedef rat::Product<Tm, Tw> n_prod_t;
467 
468  type this_type = ret.base()->what();
469 
470  // case 0 {k} -> 0
471  if (this_type == node_t::zero)
472  return;
473 
474  // case E {1} -> E
475  if (w == identity_value(SELECT(W), SELECT(oTw)))
476  return;
477 
478  // case E {0} -> 0
479  if (w == zero_value(SELECT(W), SELECT(oTw)))
480  {
481  delete ret.base();
482  ret.base() = new n_zero_t;
483  return;
484  }
485 
486  // case 1 {k} -> {k} 1
487  if (this_type == node_t::one)
488  {
489  ret.base() = new n_lweight_t
490  (op_convert(SELECT(W), SELECT(Tw), w), ret.base());
491  return;
492  }
493 
494  // case c {k} -> {k} c (where c is an atom)
495  if ((this_type == node_t::constant)
496  && op_is_atom(s.monoid(),
497  dynamic_cast<n_const_t*>(ret.base())->value_))
498  {
499  ret.base() = new n_lweight_t
500  (op_convert(SELECT(W), SELECT(Tw), w), ret.base());
501  return;
502  }
503 
504  // case (E {k'}) {k} -> E {k'k}
505  if (this_type == node_t::rweight)
506  {
507  op_in_mul(s.semiring(),
508  dynamic_cast<n_rweight_t* >(ret.base())->weight_,
509  op_convert(SELECT(W), SELECT(Tw), w));
510  return;
511  }
512 
513  // [1] case ({k'} c) {k} -> {k'k} c if c is an atom or a constant
514  // (Note: case [2] is like if you had applied case [1]
515  // followed by the c {k} -> {k} c, and then the
516  // {k'} (E {k}) -> {k'k} E rewritings.)
517  // [2] case ({k'} E) {k} -> {k'} (E {k})
518  // subcase: ({k'} (E {k''}) {k} -> {k'} (E {k''k})
519  if (this_type == node_t::lweight)
520  {
521  // [1]
522  n_lweight_t* p = dynamic_cast<n_lweight_t*>(ret.base());
523  if ((p->child_->what() == node_t::constant
524  && op_is_atom(s.monoid(),
525  dynamic_cast<n_const_t*>(p->child_)->value_))
526  || p->child_->what() == node_t::one)
527  {
528  p->weight_ = op_mul (s.semiring(), p->weight_,
529  op_convert(SELECT(W), SELECT(Tw), w));
530  }
531  else // [2]
532  {
533  // subcase
534  if (p->child_->what() == node_t::rweight)
535  {
536  n_rweight_t* q = dynamic_cast<n_rweight_t*>(p->child_);
537  assert(q);
538  q->weight_ = op_mul (s.semiring(),
539  q->weight_,
540  op_convert(SELECT(W), SELECT(Tw), w));
541  }
542  else // general case
543  {
544  p->child_ =
545  new n_rweight_t(op_convert(SELECT(W), SELECT(Tw), w),
546  p->child_);
547  }
548  }
549  return;
550  }
551 
552  // case ({k'} E) {k} -> general case
553  ret.base() =
554  new n_rweight_t(op_convert(SELECT(W), SELECT(Tw), w), ret.base());
555  return;
556  }
557 
558  template<typename W, typename M, typename Tm, typename Tw, typename oTw>
559  rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s,
560  const W& semiring,
561  const rat::exp<Tm, Tw>& a,
562  const oTw& w)
563  {
564  rat::exp<Tm, Tw> ret(a);
565  op_in_mul(s, semiring, ret, w);
566  return ret;
567  }
568 
569  template<typename W, typename M, typename oTw, typename Tm, typename Tw>
570  rat::exp<Tm, Tw> op_mul(const W& semiring,
571  const algebra::Series<W, M>& s,
572  const oTw& w,
573  const rat::exp<Tm, Tw>& b)
574  {
575  precondition(& s.semiring() == & semiring);
576  (void) s; (void) semiring;
577 
578  typedef rat::Node<Tm, Tw> node_t;
579  typedef typename rat::Node<Tm, Tw>::type type;
580  typedef rat::One<Tm, Tw> n_one_t;
581  typedef rat::Constant<Tm, Tw> n_const_t;
582  typedef rat::Zero<Tm, Tw> n_zero_t;
583  typedef rat::Star<Tm, Tw> n_star_t;
584  typedef rat::LeftWeighted<Tm, Tw> n_lweight_t;
585  typedef rat::RightWeighted<Tm, Tw> n_rweight_t;
586  typedef rat::Sum<Tm, Tw> n_sum_t;
587  typedef rat::Product<Tm, Tw> n_prod_t;
588 
589  rat::exp<Tm, Tw> ret(b);
590 
591  type this_type = ret.base()->what();
592 
593  // case {k} 0 -> 0
594  if (this_type == node_t::zero)
595  return ret;
596 
597  // case {k} 1 -> general case
598 
599  // case {0} E -> 0
600  if (w == zero_value(SELECT(W), SELECT(oTw)))
601  { return rat::exp<Tm, Tw>::zero(); }
602 
603  // case {1} E -> E
604  if (w == identity_value(SELECT(W), SELECT(oTw)))
605  return ret;
606 
607  // case {k} ({k'} E) -> {k k'} E
608  if (this_type == node_t::lweight)
609  {
610  n_lweight_t* p = dynamic_cast<n_lweight_t*>(ret.base());
611  p->weight_ = op_mul
612  (s.semiring(), op_convert(SELECT(W), SELECT(Tw), w), p->weight_);
613  return ret;
614  }
615 
616  // general case {k} E
617  ret.base() = new n_lweight_t(w, ret.base());
618  return ret;
619  }
620 
621  template<typename W, typename M, typename Tm, typename Tw, typename oTm>
622  Tw op_series_get(const algebra::Series<W, M>& s,
623  const rat::exp<Tm, Tw>& p,
624  const oTm& m)
625  {
626  typedef typename standard_of_traits<algebra::Series<W, M>,
627  rat::exp<Tm, Tw> >::
628  automaton_t automaton_t;
629 
630  typename automaton_t::set_t automata (s);
631  automaton_t a (automata);
632  standard_of(a, p);
633  return eval(a, m).value();
634  }
635 
636  template<typename W, typename M, typename Tm, typename Tw,
637  typename oTm, typename oTw>
638  void op_series_set(const algebra::Series<W, M>& s,
639  rat::exp<Tm, Tw>& p,
640  const oTm& m,
641  const oTw& w)
642  {
643  if ((m == algebra::identity_as<oTm>::of(s.monoid())) &&
644  (w == algebra::identity_as<oTw>::of(s.semiring())) &&
645  (p == algebra::zero_as<rat::exp<Tm, Tw> >::of(s)))
646  {
647  p = algebra::identity_as<rat::exp<Tm, Tw> >::of(s).value();
648  return ;
649  }
650 
651  typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> > series_set_elt_t;
652  typedef typename series_set_elt_t::monoid_elt_t monoid_elt_t;
653  typedef typename monoid_elt_t::value_t monoid_elt_value_t;
654  typedef std::list<monoid_elt_value_t> support_t;
655 
656  rat::exp<Tm, Tw> pp = p;
657  p = algebra::zero_as<rat::exp<Tm, Tw> >::of(s).value();
658 
659  // FIXME Should not rebuild the serie from stratch
660  // Should use some kind of visitor and update the tree
661  support_t supp = op_support(s, pp);
662  oTw sw;
663  bool exist = false;
664  for_all_const_(support_t, e, supp)
665  {
666  rat::exp<Tm, Tw> ret = op_convert(s,
667  SELECT2(rat::exp<Tm, Tw>),
668  SELECT(M), *e);
669  if (*e == m)
670  {
671  exist = true;
672  sw = w;
673  }
674  else
675  sw = op_series_get(s, pp, *e);
676 
677  op_in_add(s, p, op_mul(s.semiring(), s, sw, ret));
678  }
679  if (!exist)
680  op_in_add(s, p, op_mul(s.semiring(), s, w,
681  op_convert(s,
682  SELECT2(rat::exp<Tm, Tw>),
683  SELECT(M), m)));
684  }
685 
686  } // ! algebra
687 
688  /*----------------------------------------------------------------------------.
689  | MetaElement<algebra::SeriesBase<algebra::Series<W, M> >, rat::exp<Tm, Tw> > |
690  `----------------------------------------------------------------------------*/
691 
692  template <typename W, typename M, typename Tm, typename Tw>
693  void
694  MetaElement<algebra::Series<W, M>, rat::exp<Tm, Tw> >::accept
695  (const rat::ConstNodeVisitor<Tm, Tw>& v) const
696  {
697  this->value().accept(v);
698  }
699 
700  template <typename W, typename M, typename Tm, typename Tw>
701  size_t
702  MetaElement<algebra::Series<W, M>, rat::exp<Tm, Tw> >::depth() const
703  {
704  return this->value().depth();
705  }
706 
707  namespace algebra
708  {
709  template <class W, class M, class Tm, class Tw>
710  Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >
711  op_choose(const algebra::Series<W,M>& s,
712  SELECTOR2(rat::exp<Tm,Tw>))
713  {
714  Element<algebra::Series<W,M>, rat::exp<Tm, Tw> > e(s);
715  // FIXME : add global constants to do this !
716  unsigned nb = RAND___(10);
717  while (nb != 0)
718  {
719  --nb;
720  unsigned t = RAND___(3);
721  switch (t)
722  {
723  // star
724  case 0 :
725  {
726  e = e.star();
727  continue;
728  }
729  // plus
730  case 1 :
731  {
732  Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >
733  ep(s, s.monoid().choose(SELECT(Tm)));
734  ep = ep * s.semiring().choose(SELECT(Tw));
735  unsigned t = RAND___(2);
736  if (t < 1)
737  e = e + ep;
738  else
739  e = ep + e;
740  continue;
741  }
742  // mult
743  case 2 :
744  {
745  Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >
746  ep(s, s.monoid().choose(SELECT(Tm)));
747  ep = ep * s.semiring().choose(SELECT(Tw));
748  unsigned t = RAND___(2);
749  if (t < 1)
750  e = e * ep;
751  else
752  e = ep * e;
753  continue;
754  }
755  }
756  }
757  return Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >(s, e);
758  }
759 
760  } // ! algebra
761 
762 } // ! vcsn
763 
764 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_HXX
Generated on Sat Jul 14 2012 18:46:40 for Vaucanson by   doxygen 1.8.1.1