|
Vaucanson 1.4
|
00001 // krat.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, 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_KRAT_HXX 00019 # define VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_HXX 00020 00021 # include <utility> 00022 # include <list> 00023 00024 # include <vaucanson/algebra/implementation/series/series.hh> 00025 # include <vaucanson/algebra/implementation/series/rat/exp.hh> 00026 # include <vaucanson/algebra/implementation/series/rat/random_visitor.hh> 00027 # include <vaucanson/misc/usual_macros.hh> 00028 00029 # include <vaucanson/algebra/implementation/series/krat_exp_is_finite_app.hxx> 00030 # include <vaucanson/algebra/implementation/series/krat_exp_support.hxx> 00031 # include <vaucanson/algebra/implementation/series/krat_exp_transpose.hxx> 00032 00033 # include <vaucanson/algorithms/eval.hh> 00034 # include <vaucanson/algorithms/standard_of.hh> 00035 00036 # include <vaucanson/algebra/implementation/series/polynoms.hh> 00037 # include <vaucanson/automata/concept/automata.hh> 00038 00039 # include <vaucanson/misc/contract.hh> 00040 00041 namespace vcsn 00042 { 00043 namespace algebra 00044 { 00059 template<typename W, typename M, typename Tm, typename Tw> 00060 bool op_contains(const algebra::Series<W, M>&, const rat::exp<Tm, Tw>&) 00061 { 00062 pure_service_call ("default version of op_contains(Series<W,M>, exp<Tm,Tw>)"); 00063 return true; 00064 } 00065 00066 template<typename W, typename M, typename Tm, typename Tw> 00067 bool op_is_finite_app(const algebra::Series<W, M>&, 00068 const rat::exp<Tm, Tw>& m) 00069 { 00070 vcsn::IsFiniteAppMatcher< 00071 algebra::Series<W, M>, 00072 vcsn::rat::exp<Tm, Tw>, 00073 algebra::DispatchFunction<vcsn::rat::exp<Tm, Tw> > 00074 > matcher; 00075 return matcher.match(m); 00076 } 00077 00078 template<typename W, typename M, typename Tm, typename Tw> 00079 typename algebra::series_traits<rat::exp<Tm, Tw> >::support_t 00080 op_support(const algebra::Series<W, M>& s, const rat::exp<Tm, Tw>& m) 00081 { 00082 vcsn::SupportMatcher< 00083 algebra::Series<W, M>, rat::exp<Tm, Tw>, 00084 algebra::DispatchFunction<rat::exp<Tm, Tw> > 00085 > matcher(s); 00086 matcher.match(m); 00087 return matcher.get(); 00088 } 00089 00090 template <typename W, typename M, typename Tm, typename Tw> 00091 Tm op_choose_from_supp(const algebra::Series<W, M>&, 00092 const rat::exp<Tm, Tw>& m) 00093 { 00094 rat::RandomVisitor<Tm, Tw> v; 00095 m.accept(v); 00096 return v.get(); 00097 } 00098 00099 template<typename W, typename M, typename Tm, typename Tw> 00100 const rat::exp<Tm, Tw>& identity_value(SELECTOR2(algebra::Series<W, M>), 00101 SELECTOR2(rat::exp<Tm, Tw>)) 00102 { 00103 static const rat::exp<Tm, Tw> instance = rat::exp<Tm, Tw>::one(); 00104 return instance; 00105 } 00106 00107 template<typename W, typename M, typename Tm, typename Tw> 00108 bool show_identity_value(SELECTOR2(algebra::Series<W, M>), 00109 SELECTOR2(rat::exp<Tm, Tw>)) 00110 { 00111 return true; 00112 } 00113 00114 template<typename W, typename M, typename Tm, typename Tw> 00115 const rat::exp<Tm, Tw>& zero_value(SELECTOR2(algebra::Series<W, M>), 00116 SELECTOR2(rat::exp<Tm, Tw>)) 00117 { 00118 static const rat::exp<Tm, Tw> instance = rat::exp<Tm, Tw>::zero(); 00119 return instance; 00120 } 00121 00122 template <typename W, typename M, typename Tm, typename Tw> 00123 void op_in_transpose(const algebra::Series<W, M>& s, 00124 rat::exp<Tm, Tw>& exp) 00125 { 00126 Element<algebra::Series<W, M>, 00127 rat::exp<Tm, Tw> > elt(s, exp); 00128 00129 vcsn::algebra::KRatExpTranspose< 00130 algebra::Series<W, M>, 00131 rat::exp<Tm, Tw>, 00132 algebra::DispatchFunction<vcsn::rat::exp<Tm, Tw> > 00133 > matcher(elt); 00134 00135 elt = matcher.match(exp); 00136 exp = elt.value(); 00137 } 00138 00139 template<typename W, typename M, typename Tm, typename Tw> 00140 void op_in_add(const algebra::Series<W, M>&, 00141 rat::exp<Tm, Tw>& dst, 00142 const rat::exp<Tm, Tw>& arg) 00143 { 00144 // case E + 0 00145 if (arg.base()->what() == rat::Node<Tm, Tw>::zero) 00146 return ; 00147 00148 // case 0 + E 00149 if (dst.base()->what() == rat::Node<Tm, Tw>::zero) 00150 { 00151 delete dst.base(); 00152 dst.base() = arg.base()->clone(); 00153 return; 00154 } 00155 00156 dst.base() = new rat::Sum<Tm, Tw>(dst.base(), arg.base()->clone()); 00157 } 00158 00159 template<typename W, typename M, typename Tm, typename Tw> 00160 rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s, 00161 const rat::exp<Tm, Tw>& a, 00162 const rat::exp<Tm, Tw>& b) 00163 { 00164 rat::exp<Tm, Tw> ret(a); 00165 op_in_add(s, ret, b); 00166 return ret; 00167 } 00168 00169 template<typename W, typename M, typename Tm, typename Tw> 00170 void op_in_mul(const algebra::Series<W, M>& s, 00171 rat::exp<Tm, Tw>& dst, 00172 const rat::exp<Tm, Tw>& arg) 00173 { 00174 typedef rat::Node<Tm, Tw> node_t; 00175 typedef typename rat::Node<Tm, Tw>::type type; 00176 typedef rat::One<Tm, Tw> n_one_t; 00177 typedef rat::Constant<Tm, Tw> n_const_t; 00178 typedef rat::Zero<Tm, Tw> n_zero_t; 00179 typedef rat::Star<Tm, Tw> n_star_t; 00180 typedef rat::LeftWeighted<Tm, Tw> n_lweight_t; 00181 typedef rat::RightWeighted<Tm, Tw> n_rweight_t; 00182 typedef rat::Sum<Tm, Tw> n_sum_t; 00183 typedef rat::Product<Tm, Tw> n_prod_t; 00184 00185 type this_type = dst.base()->what(); 00186 type arg_type = arg.base()->what(); 00187 00188 // case 0 . E -> 0 00189 if (this_type == node_t::zero) 00190 return; 00191 00192 // case E . 0 -> 0 00193 if (arg_type == node_t::zero) 00194 { 00195 delete dst.base(); 00196 dst.base() = new n_zero_t; 00197 return; 00198 } 00199 00200 // case 1 . E -> E 00201 if (this_type == node_t::one) 00202 { 00203 delete dst.base(); 00204 dst.base() = arg.base()->clone(); 00205 return; 00206 } 00207 00208 // case E . 1 -> E 00209 if (arg_type == node_t::one) 00210 { 00211 return; 00212 } 00213 00214 // case E . {k'} 1 -> E {k'} 00215 if (arg_type == node_t::lweight) 00216 { 00217 n_lweight_t *p = dynamic_cast<n_lweight_t*>(arg.base()); 00218 if (p->child_->what() == node_t::one) 00219 { 00220 op_in_mul(s, s.semiring(), dst, p->weight_); 00221 return; 00222 } 00223 } 00224 00225 // case {k} 1 . E -> {k} E 00226 if (this_type == node_t::lweight) 00227 { 00228 n_lweight_t *p = dynamic_cast<n_lweight_t*>(dst.base()); 00229 if (p->child_->what() == node_t::one) 00230 { 00231 dst = op_mul(s.semiring(), s, p->weight_, arg); 00232 return; 00233 } 00234 } 00235 00236 // general case : {k} E . E' 00237 dst.base() = new n_prod_t(dst.base(), arg.base()->clone()); 00238 return; 00239 } 00240 00241 template<typename W, typename M, typename Tm, typename Tw> 00242 rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s, 00243 const rat::exp<Tm, Tw>& a, 00244 const rat::exp<Tm, Tw>& b) 00245 { 00246 rat::exp<Tm, Tw> ret(a); 00247 op_in_mul(s, ret, b); 00248 return ret; 00249 } 00250 00251 template <typename W, typename M, typename Tm, typename Tw, typename St> 00252 St& 00253 op_rout(const algebra::Series<W, M>& s, 00254 St& st, 00255 const rat::exp<Tm, Tw>& e) 00256 { 00257 rat::DumpVisitor<Tm, Tw, W, M> v (st, s.monoid(), s.representation()); 00258 e.accept(v); 00259 return st; 00260 } 00261 00262 /*---------------------. 00263 | foreign constructors | 00264 `---------------------*/ 00265 00266 template<typename Tm, typename Tw, typename M, typename W> 00267 rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<M, W>), 00268 SELECTOR2(rat::exp<Tm, Tw>), 00269 const Tm& m_value) 00270 { 00271 return new rat::Constant<Tm, Tw>(m_value); 00272 } 00273 00274 template<typename Tm, typename Tw, typename M, typename W> 00275 rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<M, W>), 00276 SELECTOR2(rat::exp<Tm, Tw>), 00277 char m_value) 00278 { 00279 const char str[] = {m_value, '\0'}; 00280 return new rat::Constant<Tm, Tw>(str); 00281 } 00282 00283 template<typename Tm, typename Tw, typename W, typename M, typename oTm> 00284 rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>) s, 00285 SELECTOR2(rat::exp<Tm, Tw>), 00286 SELECTOR(M), 00287 const oTm& m_value) 00288 { 00289 if (m_value == identity_value(SELECT(M), SELECT(oTm))) 00290 return rat::exp<Tm, Tw>::one(); 00291 00292 return rat::exp<Tm, Tw>::constant(op_convert(s.monoid(), SELECT(Tm), 00293 m_value)); 00294 } 00295 00296 template<typename Tm, typename Tw, typename W, typename M, typename oTw> 00297 rat::exp<Tm, Tw> op_convert(SELECTOR2(algebra::Series<W, M>), 00298 SELECTOR2(rat::exp<Tm, Tw>), 00299 SELECTOR(W), 00300 const oTw& w_value) 00301 { 00302 if (w_value == identity_value(SELECT(W), SELECT(oTw))) 00303 return rat::exp<Tm, Tw>::one(); 00304 if (w_value == zero_value(SELECT(W), SELECT(oTw))) 00305 return rat::exp<Tm, Tw>::zero(); 00306 rat::exp<Tm, Tw> ret = rat::exp<Tm, Tw>::one(); 00307 ret.base() = new rat::LeftWeighted<Tm, Tw> 00308 (op_convert(SELECT(W), SELECT(Tw), 00309 w_value), ret.base()); 00310 return ret; 00311 } 00312 00313 template <typename W, typename M, typename Tm, typename Tw, typename oTm> 00314 void op_assign(SELECTOR2(algebra::Series<W, M>) s, 00315 SELECTOR(M), 00316 rat::exp<Tm, Tw>& dst, 00317 const oTm& src) 00318 { 00319 dst = op_convert(s, 00320 SELECT2(rat::exp<Tm, Tw>), 00321 SELECT(M), src); 00322 } 00323 00324 template <typename W, typename M, typename Tm, typename Tw, typename oTw> 00325 void op_assign(SELECTOR2(algebra::Series<W, M>) s, 00326 SELECTOR(W), 00327 rat::exp<Tm, Tw>& dst, 00328 const oTw& src) 00329 { 00330 dst = op_convert(s, 00331 SELECT2(rat::exp<Tm, Tw>), 00332 SELECT(W), src); 00333 } 00334 00335 /*-----. 00336 | star | 00337 `-----*/ 00338 00339 template<typename W, typename M, typename Tm, typename Tw> 00340 bool op_starable(const algebra::Series<W, M>&, 00341 const rat::exp<Tm, Tw>&) 00342 { 00343 return true; 00344 } 00345 00346 template<typename W, typename M, typename Tm, typename Tw> 00347 void op_in_star(const algebra::Series<W, M>&, 00348 rat::exp<Tm, Tw>& dst) 00349 { 00350 // rewrite 0* as 1 00351 if (dst.base()->what() == rat::Node<Tm, Tw>::zero) 00352 dst = rat::exp<Tm, Tw>::one(); 00353 else 00354 dst.base() = new rat::Star<Tm, Tw>(dst.base()); 00355 } 00356 00357 template<typename W, typename M, typename Tm, typename Tw> 00358 rat::exp<Tm, Tw> 00359 op_star(const algebra::Series<W, M>& s, 00360 const rat::exp<Tm, Tw>& src) 00361 { 00362 rat::exp<Tm, Tw> ret(src); 00363 op_in_star(s, ret); 00364 return ret; 00365 } 00366 00367 /*--------------------------------------. 00368 | foreign addition with monoid elements | 00369 `--------------------------------------*/ 00370 00371 template<typename W, typename M, typename Tm, typename Tw, typename oTm> 00372 void op_in_add(const algebra::Series<W, M>& s, 00373 const M& monoid, 00374 rat::exp<Tm, Tw>& dst, 00375 const oTm& src) 00376 { 00377 op_in_add(s, dst, op_convert(s, 00378 SELECT2(rat::exp<Tm, Tw>), 00379 SELECT(M), 00380 src)); 00381 } 00382 00383 template<typename W, typename M, typename Tm, typename Tw, typename oTm> 00384 rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s, 00385 const M& monoid, 00386 const rat::exp<Tm, Tw>& a, 00387 const oTm& b) 00388 { 00389 rat::exp<Tm, Tw> ret(a); 00390 op_in_add(s, monoid, ret, b); 00391 return ret; 00392 } 00393 00394 template<typename M, typename W, typename oTm, typename Tm, typename Tw> 00395 rat::exp<Tm, Tw> op_add(const M& monoid, 00396 const algebra::Series<W, M>& s, 00397 const oTm& a, 00398 const rat::exp<Tm, Tw>& b) 00399 { 00400 rat::exp<Tm, Tw> ret(b); 00401 op_in_add(s, monoid, ret, a); 00402 return ret; 00403 } 00404 00405 /*----------------------------------------. 00406 | foreign addition with semiring elements | 00407 `----------------------------------------*/ 00408 00409 template<typename W, typename M, typename Tm, typename Tw, typename oTw> 00410 void op_in_add(const algebra::Series<W, M>& s, 00411 const W& semiring, 00412 rat::exp<Tm, Tw>& dst, 00413 const oTw& src) 00414 { 00415 precondition(& s.semiring() == & semiring); 00416 op_in_add(s, dst, op_convert(s, 00417 SELECT2(rat::exp<Tm, Tw>), 00418 SELECT(W), 00419 src)); 00420 } 00421 00422 template<typename W, typename M, typename Tm, typename Tw, typename oTw> 00423 rat::exp<Tm, Tw> op_add(const algebra::Series<W, M>& s, 00424 const W& semiring, 00425 const rat::exp<Tm, Tw>& a, 00426 const oTw& b) 00427 { 00428 rat::exp<Tm, Tw> ret(a); 00429 op_in_add(s, semiring, ret, b); 00430 return ret; 00431 } 00432 00433 template<typename W, typename M, typename oTw, typename Tm, typename Tw> 00434 rat::exp<Tm, Tw> op_add(const W& semiring, 00435 const algebra::Series<W, M>& s, 00436 const oTw& a, 00437 const rat::exp<Tm, Tw>& b) 00438 { 00439 rat::exp<Tm, Tw> ret(b); 00440 op_in_add(s, semiring, ret, a); 00441 return ret; 00442 } 00443 00444 /*--------------------------------------------. 00445 | foreign multiplication by semiring elements | 00446 `--------------------------------------------*/ 00447 00448 template<typename W, typename M, typename Tm, typename Tw, typename oTw> 00449 void op_in_mul(const algebra::Series<W, M>& s, 00450 const W& semiring, 00451 rat::exp<Tm, Tw>& ret, 00452 const oTw& w) 00453 { 00454 precondition(& s.semiring() == & semiring); 00455 (void) s; (void) semiring; 00456 00457 typedef rat::Node<Tm, Tw> node_t; 00458 typedef typename rat::Node<Tm, Tw>::type type; 00459 typedef rat::One<Tm, Tw> n_one_t; 00460 typedef rat::Constant<Tm, Tw> n_const_t; 00461 typedef rat::Zero<Tm, Tw> n_zero_t; 00462 typedef rat::Star<Tm, Tw> n_star_t; 00463 typedef rat::LeftWeighted<Tm, Tw> n_lweight_t; 00464 typedef rat::RightWeighted<Tm, Tw> n_rweight_t; 00465 typedef rat::Sum<Tm, Tw> n_sum_t; 00466 typedef rat::Product<Tm, Tw> n_prod_t; 00467 00468 type this_type = ret.base()->what(); 00469 00470 // case 0 {k} -> 0 00471 if (this_type == node_t::zero) 00472 return; 00473 00474 // case E {1} -> E 00475 if (w == identity_value(SELECT(W), SELECT(oTw))) 00476 return; 00477 00478 // case E {0} -> 0 00479 if (w == zero_value(SELECT(W), SELECT(oTw))) 00480 { 00481 delete ret.base(); 00482 ret.base() = new n_zero_t; 00483 return; 00484 } 00485 00486 // case 1 {k} -> {k} 1 00487 if (this_type == node_t::one) 00488 { 00489 ret.base() = new n_lweight_t 00490 (op_convert(SELECT(W), SELECT(Tw), w), ret.base()); 00491 return; 00492 } 00493 00494 // case c {k} -> {k} c (where c is an atom) 00495 if ((this_type == node_t::constant) 00496 && op_is_atom(s.monoid(), 00497 dynamic_cast<n_const_t*>(ret.base())->value_)) 00498 { 00499 ret.base() = new n_lweight_t 00500 (op_convert(SELECT(W), SELECT(Tw), w), ret.base()); 00501 return; 00502 } 00503 00504 // case (E {k'}) {k} -> E {k'k} 00505 if (this_type == node_t::rweight) 00506 { 00507 op_in_mul(s.semiring(), 00508 dynamic_cast<n_rweight_t* >(ret.base())->weight_, 00509 op_convert(SELECT(W), SELECT(Tw), w)); 00510 return; 00511 } 00512 00513 // [1] case ({k'} c) {k} -> {k'k} c if c is an atom or a constant 00514 // (Note: case [2] is like if you had applied case [1] 00515 // followed by the c {k} -> {k} c, and then the 00516 // {k'} (E {k}) -> {k'k} E rewritings.) 00517 // [2] case ({k'} E) {k} -> {k'} (E {k}) 00518 // subcase: ({k'} (E {k''}) {k} -> {k'} (E {k''k}) 00519 if (this_type == node_t::lweight) 00520 { 00521 // [1] 00522 n_lweight_t* p = dynamic_cast<n_lweight_t*>(ret.base()); 00523 if ((p->child_->what() == node_t::constant 00524 && op_is_atom(s.monoid(), 00525 dynamic_cast<n_const_t*>(p->child_)->value_)) 00526 || p->child_->what() == node_t::one) 00527 { 00528 p->weight_ = op_mul (s.semiring(), p->weight_, 00529 op_convert(SELECT(W), SELECT(Tw), w)); 00530 } 00531 else // [2] 00532 { 00533 // subcase 00534 if (p->child_->what() == node_t::rweight) 00535 { 00536 n_rweight_t* q = dynamic_cast<n_rweight_t*>(p->child_); 00537 assert(q); 00538 q->weight_ = op_mul (s.semiring(), 00539 q->weight_, 00540 op_convert(SELECT(W), SELECT(Tw), w)); 00541 } 00542 else // general case 00543 { 00544 p->child_ = 00545 new n_rweight_t(op_convert(SELECT(W), SELECT(Tw), w), 00546 p->child_); 00547 } 00548 } 00549 return; 00550 } 00551 00552 // case ({k'} E) {k} -> general case 00553 ret.base() = 00554 new n_rweight_t(op_convert(SELECT(W), SELECT(Tw), w), ret.base()); 00555 return; 00556 } 00557 00558 template<typename W, typename M, typename Tm, typename Tw, typename oTw> 00559 rat::exp<Tm, Tw> op_mul(const algebra::Series<W, M>& s, 00560 const W& semiring, 00561 const rat::exp<Tm, Tw>& a, 00562 const oTw& w) 00563 { 00564 rat::exp<Tm, Tw> ret(a); 00565 op_in_mul(s, semiring, ret, w); 00566 return ret; 00567 } 00568 00569 template<typename W, typename M, typename oTw, typename Tm, typename Tw> 00570 rat::exp<Tm, Tw> op_mul(const W& semiring, 00571 const algebra::Series<W, M>& s, 00572 const oTw& w, 00573 const rat::exp<Tm, Tw>& b) 00574 { 00575 precondition(& s.semiring() == & semiring); 00576 (void) s; (void) semiring; 00577 00578 typedef rat::Node<Tm, Tw> node_t; 00579 typedef typename rat::Node<Tm, Tw>::type type; 00580 typedef rat::One<Tm, Tw> n_one_t; 00581 typedef rat::Constant<Tm, Tw> n_const_t; 00582 typedef rat::Zero<Tm, Tw> n_zero_t; 00583 typedef rat::Star<Tm, Tw> n_star_t; 00584 typedef rat::LeftWeighted<Tm, Tw> n_lweight_t; 00585 typedef rat::RightWeighted<Tm, Tw> n_rweight_t; 00586 typedef rat::Sum<Tm, Tw> n_sum_t; 00587 typedef rat::Product<Tm, Tw> n_prod_t; 00588 00589 rat::exp<Tm, Tw> ret(b); 00590 00591 type this_type = ret.base()->what(); 00592 00593 // case {k} 0 -> 0 00594 if (this_type == node_t::zero) 00595 return ret; 00596 00597 // case {k} 1 -> general case 00598 00599 // case {0} E -> 0 00600 if (w == zero_value(SELECT(W), SELECT(oTw))) 00601 { return rat::exp<Tm, Tw>::zero(); } 00602 00603 // case {1} E -> E 00604 if (w == identity_value(SELECT(W), SELECT(oTw))) 00605 return ret; 00606 00607 // case {k} ({k'} E) -> {k k'} E 00608 if (this_type == node_t::lweight) 00609 { 00610 n_lweight_t* p = dynamic_cast<n_lweight_t*>(ret.base()); 00611 p->weight_ = op_mul 00612 (s.semiring(), op_convert(SELECT(W), SELECT(Tw), w), p->weight_); 00613 return ret; 00614 } 00615 00616 // general case {k} E 00617 ret.base() = new n_lweight_t(w, ret.base()); 00618 return ret; 00619 } 00620 00621 template<typename W, typename M, typename Tm, typename Tw, typename oTm> 00622 Tw op_series_get(const algebra::Series<W, M>& s, 00623 const rat::exp<Tm, Tw>& p, 00624 const oTm& m) 00625 { 00626 typedef typename standard_of_traits<algebra::Series<W, M>, 00627 rat::exp<Tm, Tw> >:: 00628 automaton_t automaton_t; 00629 00630 typename automaton_t::set_t automata (s); 00631 automaton_t a (automata); 00632 standard_of(a, p); 00633 return eval(a, m).value(); 00634 } 00635 00636 template<typename W, typename M, typename Tm, typename Tw, 00637 typename oTm, typename oTw> 00638 void op_series_set(const algebra::Series<W, M>& s, 00639 rat::exp<Tm, Tw>& p, 00640 const oTm& m, 00641 const oTw& w) 00642 { 00643 if ((m == algebra::identity_as<oTm>::of(s.monoid())) && 00644 (w == algebra::identity_as<oTw>::of(s.semiring())) && 00645 (p == algebra::zero_as<rat::exp<Tm, Tw> >::of(s))) 00646 { 00647 p = algebra::identity_as<rat::exp<Tm, Tw> >::of(s).value(); 00648 return ; 00649 } 00650 00651 typedef Element<algebra::Series<W, M>, rat::exp<Tm, Tw> > series_set_elt_t; 00652 typedef typename series_set_elt_t::monoid_elt_t monoid_elt_t; 00653 typedef typename monoid_elt_t::value_t monoid_elt_value_t; 00654 typedef std::list<monoid_elt_value_t> support_t; 00655 00656 rat::exp<Tm, Tw> pp = p; 00657 p = algebra::zero_as<rat::exp<Tm, Tw> >::of(s).value(); 00658 00659 // FIXME Should not rebuild the serie from stratch 00660 // Should use some kind of visitor and update the tree 00661 support_t supp = op_support(s, pp); 00662 oTw sw; 00663 bool exist = false; 00664 for_all_const_(support_t, e, supp) 00665 { 00666 rat::exp<Tm, Tw> ret = op_convert(s, 00667 SELECT2(rat::exp<Tm, Tw>), 00668 SELECT(M), *e); 00669 if (*e == m) 00670 { 00671 exist = true; 00672 sw = w; 00673 } 00674 else 00675 sw = op_series_get(s, pp, *e); 00676 00677 op_in_add(s, p, op_mul(s.semiring(), s, sw, ret)); 00678 } 00679 if (!exist) 00680 op_in_add(s, p, op_mul(s.semiring(), s, w, 00681 op_convert(s, 00682 SELECT2(rat::exp<Tm, Tw>), 00683 SELECT(M), m))); 00684 } 00685 00686 } // ! algebra 00687 00688 /*----------------------------------------------------------------------------. 00689 | MetaElement<algebra::SeriesBase<algebra::Series<W, M> >, rat::exp<Tm, Tw> > | 00690 `----------------------------------------------------------------------------*/ 00691 00692 template <typename W, typename M, typename Tm, typename Tw> 00693 void 00694 MetaElement<algebra::Series<W, M>, rat::exp<Tm, Tw> >::accept 00695 (const rat::ConstNodeVisitor<Tm, Tw>& v) const 00696 { 00697 this->value().accept(v); 00698 } 00699 00700 template <typename W, typename M, typename Tm, typename Tw> 00701 size_t 00702 MetaElement<algebra::Series<W, M>, rat::exp<Tm, Tw> >::depth() const 00703 { 00704 return this->value().depth(); 00705 } 00706 00707 namespace algebra 00708 { 00709 template <class W, class M, class Tm, class Tw> 00710 Element<algebra::Series<W,M>, rat::exp<Tm,Tw> > 00711 op_choose(const algebra::Series<W,M>& s, 00712 SELECTOR2(rat::exp<Tm,Tw>)) 00713 { 00714 Element<algebra::Series<W,M>, rat::exp<Tm, Tw> > e(s); 00715 // FIXME : add global constants to do this ! 00716 unsigned nb = RAND___(10); 00717 while (nb != 0) 00718 { 00719 --nb; 00720 unsigned t = RAND___(3); 00721 switch (t) 00722 { 00723 // star 00724 case 0 : 00725 { 00726 e = e.star(); 00727 continue; 00728 } 00729 // plus 00730 case 1 : 00731 { 00732 Element<algebra::Series<W,M>, rat::exp<Tm,Tw> > 00733 ep(s, s.monoid().choose(SELECT(Tm))); 00734 ep = ep * s.semiring().choose(SELECT(Tw)); 00735 unsigned t = RAND___(2); 00736 if (t < 1) 00737 e = e + ep; 00738 else 00739 e = ep + e; 00740 continue; 00741 } 00742 // mult 00743 case 2 : 00744 { 00745 Element<algebra::Series<W,M>, rat::exp<Tm,Tw> > 00746 ep(s, s.monoid().choose(SELECT(Tm))); 00747 ep = ep * s.semiring().choose(SELECT(Tw)); 00748 unsigned t = RAND___(2); 00749 if (t < 1) 00750 e = e * ep; 00751 else 00752 e = ep * e; 00753 continue; 00754 } 00755 } 00756 } 00757 return Element<algebra::Series<W,M>, rat::exp<Tm,Tw> >(s, e); 00758 } 00759 00760 } // ! algebra 00761 00762 } // ! vcsn 00763 00764 #endif // ! VCSN_ALGEBRA_IMPLEMENTATION_SERIES_KRAT_HXX
1.7.4