Awali
Another Weighted Automata library
ratexpset.hxx
Go to the documentation of this file.
1 // This file is part of Awali.
2 // Copyright 2016-2022 Sylvain Lombardy, Victor Marsault, Jacques Sakarovitch
3 //
4 // Awali is a free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #include <algorithm>
18 #include <cassert>
19 #include <stdexcept>
20 
31 #include <awali/sttc/misc/cast.hh>
36 
37 namespace awali { namespace sttc
38 {
39 
40  namespace rat
41  {
42 
43  template <typename Context>
46  : ctx_(ctx)
47  , identities_(identities)
48  {
49  require_weightset_commutativity();
50  }
51 
52  template <typename Context>
54  {
55  require(identities_ != identities_t::series
57  "series (currently) depend on weightset commutativity");
58  }
59 
60 #define DEFINE \
61  template <typename Context> \
62  inline \
63  auto \
64  ratexpset_impl<Context>
65 
66  DEFINE::sname()
67  -> std::string
68  {
69  return "ratexpset<" + context_t::sname() + '>';
70  }
71 
72  DEFINE::vname(bool full) const
73  -> std::string
74  {
75  std::string res;
76  if (full)
77  switch (identities_)
78  {
79  case identities_t::trivial:
80  case identities_t::associativity:
81  res += "ratexpset<";
82  break;
83  case identities_t::series:
84  res += "seriesset<";
85  break;
86  default:
87  assert(false);
88  }
89  else
90  res += "ratexpset<";
91  res += context().vname(full) + '>';
92  // if (full)
93  // // FIXME: why do I need rat::? this->to_string is not applicable anyway!
94  // res += "(" + rat::to_string(identities_) +")";
95  return res;
96  }
97 
98  DEFINE::make(std::istream& is)
100  {
101  // name is, for instance, "ratexpset<lal_char(abcd)_z>(trivial)".
102  eat(is, "ratexpset<");
103  auto ctx = Context::make(is);
104  eat(is, '>');
106  if (is.peek() == '(')
107  {
108  eat(is, '(');
109  is >> ids;
110  eat(is, ')');
111  }
112  return {ctx, ids};
113  }
114 
115  DEFINE::open(bool o) const
116  -> bool
117  {
118  return this->labelset()->open(o);
119  }
120 
121  DEFINE::context() const -> const context_t&
122  {
123  return ctx_;
124  }
125 
127  {
128  return identities_;
129  }
130 
131  DEFINE::is_series() const -> bool
132  {
133  return identities_ == identities_t::series;
134  }
135 
136  DEFINE::labelset() const -> const labelset_ptr&
137  {
138  return ctx_.labelset();
139  }
140 
142  {
143  return ctx_.weightset();
144  }
145 
146  DEFINE::atom(const label_t& v)
147  -> value_t
148  {
149  if (labelset_t::is_one(v))
150  return one();
151  return std::make_shared<atom_t>(v);
152  }
153 
154  DEFINE::zero() const
155  -> value_t
156  {
157  return std::make_shared<zero_t>();
158  }
159 
161  -> value_t
162  {
163  return std::make_shared<one_t>();
164  }
165 
166  template <typename Context>
167  template <exp::type_t Type>
168  inline
169  auto
171  -> void
172  {
173  switch(identities_) {
174  case identities_t::trivial :
175  res.push_back(v);
176  return;
177  default :
178  auto variadic = std::dynamic_pointer_cast<const variadic_t<Type>>(v);
179  if (variadic)
180  res.insert(std::end(res), std::begin(*variadic), std::end(*variadic));
181  else
182  res.push_back(v);
183  }
184  }
185 
186  template <typename Context>
187  template <exp::type_t Type>
188  inline
189  auto
191  -> ratexps_t
192  {
193  ratexps_t res;
194  gather<Type>(res, l);
195  gather<Type>(res, r);
196  return res;
197  }
198 
199  DEFINE::add(value_t l, value_t r) const
200  -> value_t
201  {
202  // Trivial Identity
203  // E+0 = 0+E = E
204  value_t res = nullptr;
205  if (l->type() == type_t::zero)
206  res = r;
207  else if (r->type() == type_t::zero)
208  res = l;
209  // END: Trivial Identity
210  else if (is_series())
211  res = add_nonzero_series_(l, r);
212  else
213  res = std::make_shared<sum_t>(gather<type_t::sum>(l, r));
214  return res;
215  }
216 
217  DEFINE::less_than_ignoring_weight_(value_t l, value_t r) const
218  -> bool
219  {
220  return less_than(unwrap_possible_lweight_(l), unwrap_possible_lweight_(r));
221  }
222 
223  DEFINE::remove_from_sum_series_(ratexps_t addends,
224  typename ratexps_t::iterator i) const
225  -> value_t
226  {
227  switch (addends.size())
228  {
229  case 0:
230  assert(false); // Sum node with zero addends.
231  case 1:
232  return zero();
233  case 2:
234  addends.erase(i);
235  return addends[0];
236  default:
237  addends.erase(i);
238  return std::make_shared<sum_t>(std::move(addends));
239  };
240  }
241 
242  DEFINE::insert_in_sum_series_(const sum_t& addends, value_t r) const
243  -> value_t
244  {
245  // We have to clone the addends (actually, their shared_ptr's)
246  // into something we can modify.
247  ratexps_t copy = addends.subs();
248  assert(copy.size() > 0);
249 
250  // Find the right spot where to insert r.
251  const auto& ws = weightset();
252  auto rw = possibly_implicit_lweight_(r);
253  auto rn = unwrap_possible_lweight_(r);
254  auto closure =
255  [this] (value_t left, value_t right)
256  {
257  return less_than_ignoring_weight_(left, right);
258  };
259  const auto i = std::lower_bound(copy.begin(), copy.end(), rn, closure);
260  if (i != copy.end()
261  && equals(unwrap_possible_lweight_(*i), rn))
262  {
263  // An addend alraedy exists whose un-left-weighted value is rn.
264  const weight_t& iw = possibly_implicit_lweight_(*i);
265  const weight_t w = ws->add(rw, iw);
266  if (ws->is_zero(w))
267  return remove_from_sum_series_(std::move(copy), i);
268  else
269  *i = lmul(w, rn);
270  }
271  else
272  copy.insert(i, r);
273 
274  return std::make_shared<sum_t>(std::move(copy));
275  }
276 
277  DEFINE::merge_sum_series_(const sum_t& addends1, value_t aa2) const
278  -> value_t
279  {
280  value_t res = aa2;
281  for (const auto& e: addends1)
282  res = add_nonzero_series_(res, e);
283  return res;
284  }
285 
286  DEFINE::add_nonzero_series_(value_t l, value_t r) const
287  -> value_t
288  {
289  assert(! is_zero(r));
290  if (l->type() == type_t::sum)
291  {
292  const auto ls = down_pointer_cast<const sum_t>(l);
293 
294  if (r->type() == type_t::sum)
295  return merge_sum_series_(*ls, r);
296  else
297  return insert_in_sum_series_(*ls, r);
298  }
299  else
300  {
301  if (r->type() == type_t::sum)
302  return add_nonzero_series_(r, l);
303 
304  // Neither argument is a sum.
305  auto ls = std::make_shared<sum_t>(ratexps_t{l}); // Not in normal form.
306  return insert_in_sum_series_(*ls, r);
307  }
308  }
309 
310  DEFINE::type_ignoring_lweight_(value_t e) const
311  -> exp::type_t
312  {
313  return unwrap_possible_lweight_(e)->type();
314  }
315 
316  DEFINE::possibly_implicit_lweight_(value_t e) const
317  -> weight_t
318  {
319  if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
320  return lw->weight();
321  else
322  return weightset()->one();
323  }
324 
325  DEFINE::unwrap_possible_lweight_(value_t e) const
326  -> value_t
327  {
328  if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
329  return lw->sub();
330  else
331  return e;
332  }
333 
334  DEFINE::mul(value_t l, value_t r) const
335  -> value_t
336  {
337  if (is_series())
338  return mul_series_(l, r);
339  else
340  return mul_expressions_(l, r);
341  }
342 
343  DEFINE::mul_expressions_(value_t l, value_t r) const
344  -> value_t
345  {
346  return mul_(l, r, false);
347  }
348 
349  DEFINE::mul_series_(value_t l, value_t r) const
350  -> value_t
351  {
352  return mul_(l, r, true);
353  }
354 
355  DEFINE::mul_(value_t l, value_t r, bool series) const
356  -> value_t
357  {
358  value_t res = nullptr;
359  // Trivial Identity: T in TAF-Kit doc.
360  // E.0 = 0.E = 0.
361  if (l->type() == type_t::zero)
362  res = l;
363  else if (r->type() == type_t::zero)
364  res = r;
365  // U_K: E.(<k>1) ⇒ E<k>, subsuming T: E.1 = E.
366  else if (type_ignoring_lweight_(r) == type_t::one)
367  res = rmul(l, possibly_implicit_lweight_(r));
368  // U_K: (<k>1).E ⇒ <k>E, subsuming T: 1.E = E.
369  else if (type_ignoring_lweight_(l) == type_t::one)
370  res = lmul(possibly_implicit_lweight_(l), r);
371  // END: Trivial Identity
372  else if (series) // Different from is_series().
373  res = nontrivial_mul_series_(l, r);
374  else
375  res = nontrivial_mul_expressions_(l, r);
376  return res;
377  }
378 
379  DEFINE::is_unweighted_nonsum_(value_t v) const
380  -> bool
381  {
382  assert(v->type() != type_t::lweight);
383  // Of course we can assume v's subterms to be well-formed according
384  // to our invariants: for example zero won't occur within a product.
385  switch (v->type())
386  {
387  case type_t::sum:
388  return false;
389  default:
390  return true;
391  }
392  }
393 
394  DEFINE::is_nonsum_(value_t v) const
395  -> bool
396  {
397  return is_unweighted_nonsum_(unwrap_possible_lweight_(v));
398  }
399 
400  DEFINE::mul_atoms_(const label_t& a, const label_t& b) const
401  -> value_t
402  {
403  return mul_atoms_(a, b, typename std::is_same<kind_t, labels_are_words>::type{});
404  }
405 
406  DEFINE::mul_atoms_(const label_t& a, const label_t& b, std::true_type) const
407  -> value_t
408  {
409  return std::make_shared<atom_t>(labelset()->concat(a, b));
410  }
411 
412  DEFINE::mul_atoms_(const label_t& a, const label_t& b, std::false_type) const
413  -> value_t
414  {
415  return std::make_shared<prod_t>(values_t{std::make_shared<atom_t>(a),
416  std::make_shared<atom_t>(b)});
417  }
418 
419  DEFINE::mul_unweighted_nontrivial_products_(value_t a, value_t b) const
420  -> value_t
421  {
422  assert(! is_zero(a));
423  assert(! is_zero(b));
424  assert(! is_one(a));
425  assert(! is_one(b));
426  assert(! std::dynamic_pointer_cast<const lweight_t>(a));
427  assert(! std::dynamic_pointer_cast<const lweight_t>(b));
428 
429  // The result is a product holding a's factors followed by b's
430  // factors, with one exception: if the last factors of a can be
431  // combined with the first factor of b then the two have to be
432  // merged in the result.
433  return concat(a, b);
434  }
435 
436  DEFINE::mul_products_(value_t a, value_t b) const
437  -> value_t
438  {
439  assert(! is_zero(a));
440  assert(! is_zero(b));
441  value_t na = unwrap_possible_lweight_(a), nb = unwrap_possible_lweight_(b);
442 
443  switch (na->type())
444  {
445  case type_t::one:
446  return lmul(possibly_implicit_lweight_(a), b);
447  default:
448  switch (nb->type())
449  {
450  case type_t::one:
451  return lmul(weightset()->mul(possibly_implicit_lweight_(a),
452  possibly_implicit_lweight_(b)),
453  na);
454  default:
455  return lmul(weightset()->mul(possibly_implicit_lweight_(a),
456  possibly_implicit_lweight_(b)),
457  mul_unweighted_nontrivial_products_(na, nb));
458  } // inner switch
459  } // outer switch
460  }
461 
462  DEFINE::nontrivial_mul_expressions_(value_t l, value_t r) const
463  -> value_t
464  {
465  return std::make_shared<prod_t>(gather<type_t::prod>(l, r));
466  }
467 
468  DEFINE::nontrivial_mul_series_(value_t l, value_t r) const
469  -> value_t
470  {
471  // Compute the result by distributing product over sum. We have
472  // to use add rather than just build a vector in order, since the
473  // addend order in the result will not follow the order in l.
474  const auto& lt = type_ignoring_lweight_(l), rt = type_ignoring_lweight_(r);
475  value_t res = zero();
476  if (lt == type_t::sum)
477  // l is a sum, and r might be as well.
478  for (const auto& la: *down_pointer_cast<const sum_t>(l))
479  res = add(res, mul(la, r));
480  else // l is not a sum.
481  {
482  if (rt == type_t::sum) // r is a sum, l is not.
483  for (const auto& ra: *down_pointer_cast<const sum_t>(r))
484  res = add(res, mul(l, ra));
485  else // neither is a sum.
486  {
487  if (is_nonsum_(l) && is_nonsum_(r))
488  return mul_products_(l, r);
489  else
490  {
491  weight_t lw = possibly_implicit_lweight_(l)
492  , rw = possibly_implicit_lweight_(r);
493  value_t nl = unwrap_possible_lweight_(l)
494  , nr = unwrap_possible_lweight_(r);
495  return lmul(weightset()->mul(lw, rw),
496  std::make_shared<prod_t>(gather<type_t::prod>(nl, nr)));
497  }
498  }
499  }
500  return res;
501  }
502 
504  -> value_t
505  {
506  value_t res = nullptr;
507  // Trivial Identity.
508  // E&0 = 0&E = 0.
509  if (l->type() == type_t::zero)
510  res = l;
511  else if (r->type() == type_t::zero)
512  res = r;
513  // <k>1&<h>1 = <k.h>1.
514  else if (type_ignoring_lweight_(l) == type_t::one
515  && type_ignoring_lweight_(r) == type_t::one)
516  res = lmul(weightset()->mul(possibly_implicit_lweight_(l),
517  possibly_implicit_lweight_(r)),
518  one());
519  // <k>a&<h>a = <k.h>a. <k>a&<h>b = 0.
520  else if (type_ignoring_lweight_(l) == type_t::atom
521  && type_ignoring_lweight_(r) == type_t::atom)
522  {
523  auto lhs = down_pointer_cast<const atom_t>(unwrap_possible_lweight_(l))->value();
524  auto rhs = down_pointer_cast<const atom_t>(unwrap_possible_lweight_(r))->value();
525  if (labelset()->equals(lhs, rhs))
526  res = rmul(l, possibly_implicit_lweight_(r));
527  else
528  res = zero();
529  }
530  // <k>1&<h>a = 0, <k>a&<h>1 = 0.
531  else if ( (type_ignoring_lweight_(l) == type_t::one
532  && type_ignoring_lweight_(r) == type_t::atom)
533  || (type_ignoring_lweight_(l) == type_t::atom
534  && type_ignoring_lweight_(r) == type_t::one))
535  res = zero();
536  // END: Trivial Identity
537  else
538  res = std::make_shared<conjunction_t>(gather<type_t::conjunction>(l, r));
539  return res;
540  }
541 
543  -> value_t
544  {
545  value_t res = nullptr;
546  // 0\E = 0{c}.
547  if (l->type() == type_t::zero)
548  res = complement(zero());
549  // 1\E = E.
550  else if (l->type() == type_t::one)
551  res = r;
552  // E\0 = 0.
553  else if (r->type() == type_t::zero)
554  res = r;
555  else
556  res = std::make_shared<ldiv_t>(ratexps_t{l, r});
557  return res;
558  }
559 
560  DEFINE::rdiv(value_t l, value_t r) const
561  -> value_t
562  {
563  // l/r = (r{T} {\} l{T}){T}.
565  }
566 
568  -> value_t
569  {
570  value_t res = nullptr;
571  // Trivial Identity.
572  // E:0 = 0:E = 0.
573  if (l->type() == type_t::zero)
574  res = l;
575  else if (r->type() == type_t::zero)
576  res = r;
577  // E:1 = 1:E = E.
578  else if (l->type() == type_t::one)
579  res = r;
580  else if (r->type() == type_t::one)
581  res = l;
582  // END: Trivial Identity
583  else
584  res = std::make_shared<shuffle_t>(gather<type_t::shuffle>(l, r));
585  return res;
586  }
587 
588  DEFINE::concat(value_t l, value_t r) const
589  -> value_t
590  {
591  return concat_(l, r, typename std::is_same<kind_t, labels_are_words>::type{});
592  }
593 
594  // Concatenation when not LAW.
595  DEFINE::concat_(value_t l, value_t r, std::false_type) const
596  -> value_t
597  {
598  return mul_expressions_(l, r);
599  }
600 
601  // Concatenation when LAW.
602  DEFINE::concat_(value_t l, value_t r, std::true_type) const
603  -> value_t
604  {
605  // concat((ab).c, d.(ef)) = (ab).(cd).(ef).
606  //
607  // Store (ab) in ratexp, then concat(c, d) if c and d are atoms,
608  // otherwise c then d, then (ef).
609  if ((l->type() == type_t::atom || l->type() == type_t::prod)
610  && (r->type() == type_t::atom || r->type() == type_t::prod))
611  {
612  // Left-hand sides.
613  ratexps_t ls;
614  gather<type_t::prod>(ls, l);
615  // Right-hand sides.
616  ratexps_t rs;
617  gather<type_t::prod>(rs, r);
618 
619  if (ls.back()->type() == type_t::atom
620  && rs.front()->type() == type_t::atom)
621  {
622  auto lhs = std::dynamic_pointer_cast<const atom_t>(ls.back());
623  auto rhs = std::dynamic_pointer_cast<const atom_t>(rs.front());
624  ls.back() = atom(labelset()->concat(lhs->value(), rhs->value()));
625  ls.insert(ls.end(), rs.begin() + 1, rs.end());
626  }
627  else
628  ls.insert(ls.end(), rs.begin(), rs.end());
629  if (ls.size() == 1)
630  return ls.front();
631  else
632  return std::make_shared<prod_t>(ls);
633  }
634  else
635  // Handle all the trivial identities.
636  return mul_expressions_(l, r);
637  }
638 
640  -> value_t
641  {
642  if (e->type() == type_t::zero)
643  // Trivial one
644  // (0)* == 1
645  return one();
646  else
647  {
648  value_t res = std::make_shared<star_t>(e);
649  require(!is_series() || is_valid(*this, res),
650  "star argument ", e, " not starrable");
651  return res;
652  }
653  }
654 
656  -> value_t
657  {
658  // Trivial identity: (k.E){c} => E{c}, (E.k){c} => E{c}.
659  // Without it, derived-term (<2>a)*{c} fails to terminate.
660  if (auto wl = std::dynamic_pointer_cast<const lweight_t>(e))
661  return complement(wl->sub());
662  else if (auto wr = std::dynamic_pointer_cast<const rweight_t>(e))
663  return complement(wr->sub());
664  else
665  return std::make_shared<complement_t>(e);
666  }
667 
669  -> value_t
670  {
671  value_t res = nullptr;
672  // Trivial Identity.
673  // 0{T} = 0.
674  if (e->type() == type_t::zero)
675  res = e;
676  // 1{T} = 1.
677  else if (e->type() == type_t::one)
678  res = e;
679  // a{T} = a, (abc){T} = cba.
680  else if (auto l = std::dynamic_pointer_cast<const atom_t>(e))
681  res = atom(labelset()->transpose(l->value()));
682  // END: Trivial Identity
683  else
684  res = std::make_shared<transposition_t>(e);
685  return res;
686  }
687 
688  /*----------.
689  | weights. |
690  `----------*/
691 
692  DEFINE::lmul(const weight_t& w, value_t e) const
693  -> value_t
694  {
695  // Trivial identities $T_K$: <k>0 => 0, <0>E => 0.
696  if (e->type() == type_t::zero || weightset()->is_zero(w))
697  return zero();
698  // Trivial identity: <1>E => E.
699  else if (weightset()->is_one(w))
700  return e;
701  // Trivial identity: <k>(<h>E) => <kh>E.
702  else if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
703  return lmul(weightset()->mul(w, lw->weight()), lw->sub());
704  // General case: <k>E.
705  else if (is_series())
706  return nontrivial_lmul_series_(w, e);
707  else
708  return nontrivial_lmul_expression_(w, e);
709  }
710 
711  DEFINE::nontrivial_lmul_expression_(const weight_t& w, value_t s) const
712  -> value_t
713  {
714  return std::make_shared<lweight_t>(w, s);
715  }
716 
717  DEFINE::nontrivial_lmul_series_(const weight_t& w, value_t s) const
718  -> value_t
719  {
720  if (s->type() != type_t::sum)
721  return nontrivial_lmul_expression_(w, s);
722  else
723  {
724  const auto& ss = down_pointer_cast<const sum_t>(s);
725  // We can build the result faster by emplace_back'ing addends without
726  // passing thru add; the order will be the same as in *ss.
727  ratexps_t addends;
728  for (auto& a: *ss)
729  addends.emplace_back(lmul(w, a));
730  return std::make_shared<sum_t>(std::move(addends));
731  }
732  }
733 
734  DEFINE::rmul(value_t e, const weight_t& w) const
735  -> value_t
736  {
737  if (e->is_leaf())
738  // Can only have left weights and lmul takes care of normalization.
739  return lmul(w, e);
740  // Trivial identities $T_K$: E<0> => 0.
741  else if (weightset()->is_zero(w))
742  return zero();
743  // Trivial identity: E<1> => E.
744  else if (weightset()->is_one(w))
745  return e;
746  // Trivial identity: (<k>E)<h> => <k>(E<h>).
747  else if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
748  return lmul(lw->weight(), rmul(lw->sub(), w));
749  // Trivial identity: (E<k>)<h> => E<kh>.
750  else if (auto rw = std::dynamic_pointer_cast<const rweight_t>(e))
751  return rmul(rw->sub(), weightset()->mul(rw->weight(), w));
752  // General case: E<k>.
753  else if (is_series())
754  return nontrivial_rmul_series_(e, w);
755  else
756  return nontrivial_rmul_expression_(e, w);
757  }
758 
759  DEFINE::nontrivial_rmul_expression_(value_t e, const weight_t& w) const
760  -> value_t
761  {
762  return std::make_shared<rweight_t>(w, e);
763  }
764 
765  DEFINE::nontrivial_rmul_series_(value_t s, const weight_t& w) const
766  -> value_t
767  {
768  if (s->type() != type_t::sum)
769  return nontrivial_rmul_expression_(s, w);
770  else
771  {
772  const auto& ss = down_pointer_cast<const sum_t>(s);
773  // Differently from the lmul case here the order of addends in
774  // the result may be different from the order in *ss, so we
775  // have to use add.
776  value_t res = zero();
777  for (auto& a: *ss)
778  res = add(res, rmul(a, w));
779  return res;
780  }
781  }
782 
784  -> std::string
785  {
786  std::ostringstream o;
787  print(e, o, "text");
788  return o.str();
789  }
790 
791  /*----------------------------------.
792  | ratexpset as a WeightSet itself. |
793  `----------------------------------*/
794 
795  DEFINE::is_zero(value_t v) const
796  -> bool
797  {
798  return v->type() == type_t::zero;
799  }
800 
801  DEFINE::is_one(value_t v)
802  -> bool
803  {
804  return (v->type() == type_t::one);
805  }
806 
808  -> bool
809  {
810  size<ratexpset_impl> sizer;
811  size_t l = sizer(lhs), r = sizer(rhs);
812  if (l < r)
813  return true;
814  else if (l > r)
815  return false;
816  else
817  {
818  using less_than_t = rat::less_than<ratexpset_impl>;
819  less_than_t lt;
820  return lt(lhs, rhs);
821  }
822  }
823 
825  -> bool
826  {
827  if(lhs.get()==rhs.get())
828  return true;
830  return eq(rhs, lhs);
831  }
832 
833  DEFINE::hash(const value_t& v)
834  -> size_t
835  {
837  return hasher(v);
838  }
839 
841  -> value_t
842  {
843  if (identities() == rs.identities())
844  return v;
845  else
846  return copy(rs, *this, v);
847  }
848 
849  template <typename Context>
850  template <typename GenSet>
851  inline
852  auto
854  typename letterset<GenSet>::value_t v) const
855  -> value_t
856  {
857  return atom(labelset()->conv(ls, v));
858  }
859 
860  DEFINE::conv(b, typename b::value_t v) const
861  -> value_t
862  {
863  return v ? one() : zero();
864  }
865 
866  DEFINE::conv(const z& ws, typename z::value_t v) const
867  -> value_t
868  {
869  return lmul(weightset()->conv(ws, v), one());
870  }
871 
872  DEFINE::conv(const q& ws, typename q::value_t v) const
873  -> value_t
874  {
875  return lmul(weightset()->conv(ws, v), one());
876  }
877 
878  DEFINE::conv(const r& ws, typename r::value_t v) const
879  -> value_t
880  {
881  return lmul(weightset()->conv(ws, v), one());
882  }
883 
884  // Convert from another ratexpset \a rs to ourself. Requires a full
885  // rewrite of the ratexp \a v.
886  template <typename Context>
887  template <typename Ctx2>
888  inline
889  auto
891  typename ratexpset_impl<Ctx2>::value_t v) const
892  -> value_t
893  {
894  return copy(rs, *this, v);
895  }
896 
897  DEFINE::conv(std::istream& is) const
898  -> value_t
899  {
900  std::string s;
901  is >> s;
902  return parse_exp(*this, s);
903  }
904 
905  DEFINE::print(const value_t v, std::ostream& o,
906  const std::string& /*format*/) const
907  -> std::ostream&
908  {
909  return ::awali::sttc::print(*this, v, o);
910  }
911 
912  DEFINE::transpose(const value_t v) const
913  -> value_t
914  {
916  return tr(v);
917  }
918 
919  template <typename Context>
920  template <typename... Args>
921  inline
922  auto
924  -> value_t
925  {
926  return letter_class_<labelset_t>(std::forward<Args>(args)...,
927  std::is_same<labelset_t, oneset>{});
928  }
929 
930  template <typename Context>
931  template <typename LabelSet_>
932  inline
933  auto
935  (std::set<std::pair<typename LabelSet_::letter_t,
936  typename LabelSet_::letter_t>> ccs,
937  bool accept,
938  std::false_type) const
939  -> value_t
940  {
941  value_t res = zero();
942  auto gens = labelset()->genset();
943  // FIXME: This piece of code screams for factoring. Yet, I want
944  // to avoid useless costs such as building a empty/full set of
945  // letters for [^].
946 
947  // [a-c].
948  if (accept)
949  for (const auto& cc: ccs)
950  {
951  auto i = std::find(std::begin(gens), std::end(gens), cc.first);
952  auto end = std::find(i, std::end(gens), cc.second);
953  require(end != std::end(gens),
954  "invalid letter interval: ",
955  format(*labelset(), labelset()->value(std::get<0>(cc))),
956  '-',
957  format(*labelset(), labelset()->value(std::get<1>(cc))));
958  for (end = std::next(end); i != end; ++i)
959  res = add(res, atom(labelset()->value(*i)));
960  }
961  // [^].
962  else if (ccs.empty())
963  for (auto l: gens)
964  res = add(res, atom(labelset()->value(l)));
965  // [^a-z].
966  else
967  {
968  // Match the letters that are in no interval.
969  std::set<typename LabelSet_::letter_t> accepted;
970  for (const auto& cc: ccs)
971  {
972  auto i = std::find(std::begin(gens), std::end(gens), cc.first);
973  auto end = std::find(i, std::end(gens), cc.second);
974  require(end != std::end(gens),
975  "invalid letter interval: ",
976  format(*labelset(), labelset()->value(std::get<0>(cc))),
977  '-',
978  format(*labelset(), labelset()->value(std::get<1>(cc))));
979  for (end = std::next(end); i != end; ++i)
980  accepted.emplace(*i);
981  }
982  for (auto c: gens)
983  if (!has(accepted, c))
984  res = add(res, atom(labelset()->value(c)));
985  }
986  require(!is_zero(res),
987  "invalid empty letter class");
988  return res;
989  }
990 
991  template <typename Context>
992  template <typename LabelSet_, typename... Args>
993  inline
994  auto
996  std::true_type) const
997  -> value_t
998  {
999  return one();
1000  }
1001 
1002 #undef DEFINE
1003 
1004 } // namespace rat
1005 }}//end of ns awali::stc
Definition: qfraction.hh:26
The Boolean semring.
Definition: b.hh:38
bool value_t
Definition: b.hh:56
The semiring of complex numbers.
Definition: c.hh:44
carries the algebraic settings of automata
Definition: context.hh:40
std::string vname(bool full=true) const
Definition: context.hh:137
Definition: transpose.hh:36
Implementation of labels are letters.
Definition: letterset.hh:43
letter_t value_t
Definition: letterset.hh:53
The semiring of rational numbers.
Definition: q.hh:42
The semiring of floating Numbers.
Definition: r.hh:35
double value_t
Definition: r.hh:56
Definition: ratexp.hh:280
Definition: equal_visit.hh:34
rat::type_t type_t
The possible types of ratexps.
Definition: ratexp.hh:43
Definition: hash.hh:28
Definition: less_than.hh:34
A typed ratexp set.
Definition: ratexpset.hh:46
typename node_t::value_t value_t
The value this is a set of: typeful shared pointers.
Definition: ratexpset.hh:93
typename context_t::weightset_ptr weightset_ptr
Definition: ratexpset.hh:54
value_t letter_class(Args &&... chars) const
A ratexp matching one character amongst chars.
label_t_of< context_t > label_t
Definition: ratexpset.hh:55
typename context_t::labelset_ptr labelset_ptr
Definition: ratexpset.hh:53
Context context_t
Definition: ratexpset.hh:49
ratexpset_impl(const context_t &ctx, identities_t identities)
Constructor.
Definition: ratexpset.hxx:44
value_t conv(std::istream &is) const
Definition: ratexpset.hxx:897
typename node_t::ratexps_t ratexps_t
Definition: ratexpset.hh:90
typename weightset_t::value_t weight_t
Definition: ratexpset.hh:56
Definition: size.hh:31
An inner node with multiple children.
Definition: ratexp.hh:115
The semiring of Integers.
Definition: z.hh:35
int value_t
Definition: z.hh:56
weightset_description weightset(const std::string &k)
any_t label_t
Type for (transition) labels; it is an alias to any_t since its precise type depends on the weightset...
Definition: typedefs.hh:48
any_t weight_t
Type for (transition) weights; it is an alias to any_t since the its precise type depends on the weig...
Definition: typedefs.hh:61
automaton_t transpose(automaton_t aut, options_t opts={})
Transposes aut or returns a transposed copy of aut.
std::ostream & print(const std::tuple< Args... > &args, std::ostream &o)
Definition: tuple.hh:254
static constexpr TOP< void > value
Definition: priority.hh:93
ATTRIBUTE_PURE auto find(const std::vector< T, Alloc > &s, const T &e) -> typename std::vector< T, Alloc >::const_iterator
Convenience wrapper around std::find.
Definition: vector.hh:81
bool has(const std::map< Key, Value, Compare, Alloc > &s, const Key &e)
Definition: map.hh:53
unary< type_t::star, Label, Weight > star
Definition: fwd.hh:129
constant< type_t::zero, Label, Weight > zero
Definition: fwd.hh:113
variadic< type_t::ldiv, Label, Weight > ldiv
Definition: fwd.hh:148
variadic< type_t::conjunction, Label, Weight > conjunction
Definition: fwd.hh:145
variadic< type_t::shuffle, Label, Weight > shuffle
Definition: fwd.hh:151
OutRatExpSet::value_t copy(const InRatExpSet &in_rs, const OutRatExpSet &out_rs, const typename InRatExpSet::value_t &v)
Definition: copy.hh:147
unary< type_t::transposition, Label, Weight > transposition
Definition: fwd.hh:132
constant< type_t::one, Label, Weight > one
Definition: fwd.hh:116
unary< type_t::complement, Label, Weight > complement
Definition: fwd.hh:126
identities
A ratexpset can implement several different sets of identities on expressions.
Definition: identities.hh:32
@ trivial
Trivial identities only.
std::string to_string(identities i)
void eat(std::istream &is, char c)
Check lookahead character and advance.
Definition: stream.hh:62
RatExpSet::ratexp_t less_than(const RatExpSet &rs, const typename RatExpSet::ratexp_t &v)
Definition: less_than.hh:166
RatExpSet::ratexp_t equals(const RatExpSet &rs, const typename RatExpSet::ratexp_t &v)
Definition: equal_visit.hh:153
RatExpSet::ratexp_t parse_exp(const RatExpSet &ratexpset, const std::string &s, bool check_complete=true, bool strict_alphabet=true)
parser of rational expressions
Definition: exp_parser.hh:438
AutOut transpose(Aut &aut, bool keep_history=true)
Definition: transpose.hh:79
auto format(const ValueSet &vs, const typename ValueSet::value_t &v, Args &&... args) -> std::string
Format v via vs.print.
Definition: stream.hh:109
bool is_valid(const Aut &aut)
Tests if aut is valid.
Definition: is_valid.hh:162
std::ostream & print(const RatExpSet &rs, const typename RatExpSet::ratexp_t &e, std::ostream &o, bool with_dot=false)
Definition: print_exp.hh:201
void require(bool b, Args &&... args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:55
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
Definition: synchronizing_word.hh:266
auto conv(const ValueSet &vs, const std::string &str, Args &&... args) -> decltype(vs.conv(std::declval< std::istream & >(), std::forward< Args >(args)...))
Parse str via vs.conv.
Definition: stream.hh:45
typename internal::weightset_t_of_impl< internal::base_t< ValueSet > >::type weightset_t_of
Helper to retrieve the type of the weightset of a value set.
Definition: traits.hh:86
static const std::string full
Completely version of Awali as a std::string.
Definition: version.hh:42
Main namespace of Awali.
Definition: ato.hh:22
Provide a variadic mul on top of a binary mul(), and one().
Definition: weightset.hh:38