Vcsn  2.4
Be Rational
expressionset.hxx
Go to the documentation of this file.
1 #include <algorithm>
2 #include <cassert>
3 #include <stdexcept>
4 
5 #include <boost/range/algorithm/find.hpp>
6 #include <boost/range/algorithm/lower_bound.hpp>
7 
8 #include <vcsn/algos/fwd.hh> // is-valid
9 #include <vcsn/core/rat/copy.hh>
11 #include <vcsn/core/rat/hash.hh>
12 #include <vcsn/core/rat/less.hh>
13 #include <vcsn/core/rat/size.hh>
15 #include <vcsn/dyn/algos.hh> // dyn::read_expression
16 #include <vcsn/dyn/context.hh> // dyn::make_context
17 #include <vcsn/dyn/fwd.hh>
18 #include <vcsn/labelset/oneset.hh>
19 #include <vcsn/misc/algorithm.hh>
20 #include <vcsn/misc/attributes.hh>
21 #include <vcsn/misc/cast.hh>
22 #include <vcsn/misc/stream.hh>
23 #include <vcsn/misc/tuple.hh>
24 
25 namespace vcsn
26 {
27  namespace rat
28  {
29 
30  template <typename Context>
33  : ctx_(ctx)
34  , ids_(ids)
35  {
36  require(!ids_.is_distributive() || weightset()->is_commutative(),
37  "series (currently) requires a commutative weightset product");
38  }
39 
40 #define DEFINE \
41  template <typename Context> \
42  auto \
43  expressionset_impl<Context>
44 
46  -> symbol
47  {
48  static auto res = symbol{"expressionset<" + context_t::sname() + '>'};
49  return res;
50  }
51 
52 
53  DEFINE::make(std::istream& is)
55  {
56  // name is, for instance, "expressionset<lal_char(abcd), z>(trivial)".
57  eat(is, "expressionset<");
58  auto ctx = Context::make(is);
59  eat(is, '>');
60  auto ids = identities_t{};
61  if (is.peek() == '(')
62  {
63  eat(is, '(');
64  is >> ids;
65  eat(is, ')');
66  }
67  return {ctx, ids};
68  }
69 
70  DEFINE::print_set(std::ostream& o, format fmt) const
71  -> std::ostream&
72  {
73  switch (fmt.kind())
74  {
75  case format::latex:
76  o << "\\mathsf{"
77  << (identities().is_distributive() ? "Series" : "RatE")
78  << "}[";
79  context().print_set(o, fmt);
80  o << ']';
81  break;
82  case format::sname:
83  if (identities().is_distributive())
84  {
85  o << "seriesset<";
86  context().print_set(o, fmt);
87  o << '>';
88  }
89  else
90  {
91  o << "expressionset<";
92  context().print_set(o, fmt);
93  o << '>';
94  if (identities() != vcsn::rat::identities{})
95  o << '(' << identities() << ')';
96  }
97  break;
98  case format::text:
99  case format::utf8:
100  o << "RatE[";
101  context().print_set(o, fmt);
102  o << ']';
103  if (identities() != vcsn::rat::identities{})
104  o << '(' << identities() << ')';
105  break;
106  case format::raw:
107  assert(!"expressionset::print_set: invalid format: rat");
108  break;
109  }
110  return o;
111  }
112 
113  DEFINE::open(bool o) const
114  -> bool
115  {
116  return this->labelset()->open(o);
117  }
118 
119  DEFINE::context() const -> const context_t&
120  {
121  return ctx_;
122  }
123 
124  DEFINE::identities() const -> identities_t
125  {
126  return ids_;
127  }
128 
129  DEFINE::labelset() const -> const labelset_ptr&
130  {
131  return ctx_.labelset();
132  }
133 
134  DEFINE::weightset() const -> const weightset_ptr&
135  {
136  return ctx_.weightset();
137  }
138 
139  DEFINE::atom(const label_t& v)
140  -> value_t
141  {
142  if (labelset_t::is_one(v))
143  return one();
144  else
145  return std::make_shared<atom_t>(v);
146  }
147 
148  DEFINE::zero() const
149  -> value_t
150  {
151  return std::make_shared<zero_t>();
152  }
153 
154  DEFINE::one()
155  -> value_t
156  {
157  return std::make_shared<one_t>();
158  }
159 
160  template <typename Context>
161  template <typename expressionset_impl<Context>::type_t Type>
162  auto
163  expressionset_impl<Context>::gather_(values_t& res, const value_t& v) const
164  -> void
165  {
166  auto variadic = std::dynamic_pointer_cast<const variadic_t<Type>>(v);
167  if (variadic && ids_.is_associative())
168  res.insert(std::end(res), std::begin(*variadic), std::end(*variadic));
169  else
170  res.push_back(v);
171  }
172 
173  template <typename Context>
174  template <typename expressionset_impl<Context>::type_t Type>
175  auto
176  expressionset_impl<Context>::gather_(const value_t& l, const value_t& r) const
177  -> values_t
178  {
179  values_t res;
180  if (ids_.is_associative())
181  {
182  gather_<Type>(res, l);
183  gather_<Type>(res, r);
184  }
185  else
186  {
187  res.emplace_back(l);
188  res.emplace_back(r);
189  }
190  return res;
191  }
192 
193  DEFINE::add(const value_t& l, const value_t& r) const
194  -> value_t
195  {
196  value_t res = nullptr;
197 
198  if (!ids_)
199  res = std::make_shared<add_t>(l, r);
200 
201  // 0+E => E.
202  else if (is_zero(l))
203  res = r;
204 
205  // E+0 => E.
206  else if (is_zero(r))
207  res = l;
208 
209  // E+E => <2>E.
210  else if (ids_.is_linear())
211  res = add_linear_(l, r);
212 
213  else
214  res = std::make_shared<add_t>(gather_<type_t::add>(l, r));
215  return res;
216  }
217 
218  DEFINE::add_linear_(const add_t& s, const value_t& r) const
219  -> value_t
220  {
221  auto res = values_t{};
222  res.reserve(s.size() + 1);
223 
224  // Copy the strictly smaller part.
225  auto i = boost::lower_bound(s, r, less_linear);
226  res.insert(end(res), begin(s), i);
227 
228  if (i == end(s))
229  res.emplace_back(r);
230  else
231  {
232  if (less_linear(r, *i))
233  res.emplace_back(r);
234  else
235  {
236  auto w = weightset()->add(possibly_implicit_lweight_(*i),
237  possibly_implicit_lweight_(r));
238  if (!weightset()->is_zero(w))
239  {
240  auto l = unwrap_possible_lweight_(*i);
241  res.emplace_back(lweight(w, l));
242  }
243  ++i;
244  }
245  res.insert(end(res), i, end(s));
246  }
247 
248  return add_(std::move(res));
249  }
250 
251  DEFINE::add_(values_t&& vs) const
252  -> value_t
253  {
254  if (vs.size() == 0)
255  return zero();
256  else if (vs.size() == 1)
257  return vs[0];
258  else
259  return std::make_shared<add_t>(std::move(vs));
260  }
261 
262  DEFINE::add_linear_(const add_t& s1, const add_t& s2) const
263  -> value_t
264  {
265  auto res = values_t{};
266  res.reserve(s1.size() + s2.size());
267  // Merge two increasing lists. Add weights of equal labels.
268  using std::begin;
269  using std::end;
270  auto i1 = begin(s1), end1 = end(s1);
271  auto i2 = begin(s2), end2 = end(s2);
272  while (true)
273  {
274  if (i1 == end1)
275  {
276  res.insert(res.end(), i2, end2);
277  break;
278  }
279  else if (i2 == end2)
280  {
281  res.insert(res.end(), i1, end1);
282  break;
283  }
284  else if (less_linear(*i1, *i2))
285  res.emplace_back(*i1++);
286  else if (less_linear(*i2, *i1))
287  res.emplace_back(*i2++);
288  else
289  {
290  auto w = weightset()->add(possibly_implicit_lweight_(*i1),
291  possibly_implicit_lweight_(*i2));
292  if (!weightset()->is_zero(w))
293  {
294  auto l = unwrap_possible_lweight_(*i1);
295  res.emplace_back(lweight(w, l));
296  }
297  ++i1;
298  ++i2;
299  }
300  }
301  return add_(std::move(res));
302  }
303 
304  DEFINE::add_linear_(const value_t& l, const value_t& r) const
305  -> value_t
306  {
307  assert(!is_zero(l));
308  assert(!is_zero(r));
309  value_t res = nullptr;
310  if (auto ls = std::dynamic_pointer_cast<const add_t>(l))
311  {
312  if (auto rs = std::dynamic_pointer_cast<const add_t>(r))
313  res = add_linear_(*ls, *rs);
314  else
315  res = add_linear_(*ls, r);
316  }
317  else if (auto rs = std::dynamic_pointer_cast<const add_t>(r))
318  res = add_linear_(*rs, l);
319  else if (less_linear(l, r))
320  res = std::make_shared<add_t>(l, r);
321  else if (less_linear(r, l))
322  res = std::make_shared<add_t>(r, l);
323  else
324  {
325  auto w = weightset()->add(possibly_implicit_lweight_(l),
326  possibly_implicit_lweight_(r));
327  res = lweight(w, unwrap_possible_lweight_(l));
328  }
329  return res;
330  }
331 
332  DEFINE::type_ignoring_lweight_(const value_t& e)
333  -> type_t
334  {
335  return unwrap_possible_lweight_(e)->type();
336  }
337 
338  DEFINE::possibly_implicit_lweight_(const value_t& e)
339  -> weight_t
340  {
341  if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
342  return lw->weight();
343  else
344  return weightset_t::one();
345  }
346 
347  DEFINE::unwrap_possible_lweight_(const value_t& e)
348  -> value_t
349  {
350  if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
351  return lw->sub();
352  else
353  return e;
354  }
355 
356  DEFINE::mul(const value_t& l, const value_t& r) const
357  -> value_t
358  {
359  value_t res = nullptr;
360 
361  if (!ids_)
362  res = std::make_shared<mul_t>(l, r);
363 
364  // 0.E => 0.
365  else if (is_zero(l))
366  res = l;
367 
368  // E.0 => 0.
369  else if (is_zero(r))
370  res = r;
371 
372  // U_K: E.(<k>1) ⇒ E<k>, subsuming T: E.1 = E.
373  else if (type_ignoring_lweight_(r) == type_t::one)
374  res = rweight(l, possibly_implicit_lweight_(r));
375 
376  // U_K: (<k>1).E ⇒ <k>E, subsuming T: 1.E = E.
377  else if (type_ignoring_lweight_(l) == type_t::one)
378  res = lweight(possibly_implicit_lweight_(l), r);
379 
380  // (<k>E)(<h>F) => <kh>(EF).
381  else if (ids_.is_linear() && weightset()->is_commutative()
382  && (l->type() == type_t::lweight
383  || r->type() == type_t::lweight))
384  {
385  weight_t
386  lw = possibly_implicit_lweight_(l),
387  rw = possibly_implicit_lweight_(r);
388  value_t
389  nl = unwrap_possible_lweight_(l),
390  nr = unwrap_possible_lweight_(r);
391  res = lweight(weightset()->mul(lw, rw),
392  mul(nl, nr));
393  }
394 
395  // (E+F)G => EG + FG.
396  else if (ids_.is_distributive() && l->type() == type_t::add)
397  {
398  res = zero();
399  // l is a sum, and r might be as well.
400  for (const auto& la: *down_pointer_cast<const add_t>(l))
401  res = add(res, mul(la, r));
402  }
403 
404  // E(F+G) => EF + EG.
405  else if (ids_.is_distributive() && r->type() == type_t::add)
406  {
407  res = zero();
408  // r is a sum, l is not.
409  for (const auto& ra: *down_pointer_cast<const add_t>(r))
410  res = add(res, mul(l, ra));
411  }
412 
413  else
414  res = std::make_shared<mul_t>(gather_<type_t::mul>(l, r));
415  return res;
416  }
417 
418  DEFINE::compose(const value_t& l, const value_t& r) const
419  -> value_t
420  {
421  value_t res = nullptr;
422 
423  if (!ids_)
424  res = std::make_shared<compose_t>(l, r);
425 
426  // 0 @ E => 0.
427  else if (is_zero(l))
428  res = l;
429 
430  // E @ 0 => 0.
431  else if (is_zero(r))
432  res = r;
433 
434  // <k>1 @ <h>1 => <kh>1
435  else if (type_ignoring_lweight_(l) == type_t::one
436  && type_ignoring_lweight_(r) == type_t::one)
437  res = lweight(weightset()->mul(possibly_implicit_lweight_(l),
438  possibly_implicit_lweight_(r)),
439  one());
440 
441  // General case.
442  else
443  res = std::make_shared<compose_t>(gather_<type_t::compose>(l, r));
444  return res;
445  }
446 
447  DEFINE::conjunction(const value_t& l, const value_t& r) const
448  -> value_t
449  {
450  value_t res = nullptr;
451 
452  if (!ids_)
453  res = std::make_shared<conjunction_t>(l, r);
454 
455  // 0&E => 0.
456  else if (is_zero(l))
457  res = l;
458 
459  // E&0 => 0.
460  else if (is_zero(r))
461  res = r;
462 
463  // E&0{c} => E.
464  else if (is_universal(r))
465  res = l;
466 
467  // 0{c}&E => E.
468  else if (is_universal(l))
469  res = r;
470 
471  // <k>1&<h>1 => <kh>1.
472  else if (type_ignoring_lweight_(l) == type_t::one
473  && type_ignoring_lweight_(r) == type_t::one)
474  res = lweight(weightset()->mul(possibly_implicit_lweight_(l),
475  possibly_implicit_lweight_(r)),
476  one());
477 
478  // <k>a&<h>a => <kh>a. <k>a&<h>b => 0.
479  else if (type_ignoring_lweight_(l) == type_t::atom
480  && type_ignoring_lweight_(r) == type_t::atom)
481  {
482  auto lhs =
483  down_pointer_cast<const atom_t>(unwrap_possible_lweight_(l))->value();
484  auto rhs =
485  down_pointer_cast<const atom_t>(unwrap_possible_lweight_(r))->value();
486  if (labelset()->equal(lhs, rhs))
487  res = rweight(l, possibly_implicit_lweight_(r));
488  else
489  res = zero();
490  }
491 
492  // <k>1&<h>a => 0, <k>a&<h>1 => 0.
493  else if ((type_ignoring_lweight_(l) == type_t::one
494  && type_ignoring_lweight_(r) == type_t::atom)
495  || (type_ignoring_lweight_(l) == type_t::atom
496  && type_ignoring_lweight_(r) == type_t::one))
497  res = zero();
498 
499  // General case: E & F.
500  else
501  res = std::make_shared<conjunction_t>(gather_<type_t::conjunction>(l, r));
502  return res;
503  }
504 
505  DEFINE::ldivide(const value_t& l, const value_t& r) const
506  -> value_t
507  {
508  value_t res = nullptr;
509 
510  if (!ids_)
511  res = std::make_shared<ldivide_t>(l, r);
512 
513  // 0\E => 0.
514  else if (is_zero(l))
515  res = l;
516 
517  // 1\E => E.
518  else if (is_one(l))
519  res = r;
520 
521  // E\0 => 0.
522  else if (is_zero(r))
523  res = r;
524 
525  else
526  res = std::make_shared<ldivide_t>(l, r);
527  return res;
528  }
529 
530  DEFINE::rdivide(const value_t& l, const value_t& r) const
531  -> value_t
532  {
533  // l/r = (r{T} {\} l{T}){T}.
534  return transposition(ldivide(transposition(r), transposition(l)));
535  }
536 
537  template <typename Context>
538  template <typename... Value>
539  auto expressionset_impl<Context>::tuple(Value&&... v) const
540  -> value_t
541  {
542  auto ts = as_tupleset();
543  auto t = ts.tuple(v...);
544  // \z | E => \z.
545  //
546  // FIXME: maybe we should introduce a short-circuiting version
547  // that would not make useless invocation when a \z was found.
548  if (detail::apply(any{},
549  detail::apply(([](const auto& rs, const auto& r)
550  { return rs.is_zero(r); }),
551  ts.sets(), t)))
552  return zero();
553  // \e | \e => \e.
554  if (ts.is_one(t))
555  return one();
556  // If this is a tuple of labels, make it a (multitape) label.
557  // That allows algorithms such as standard, thompson, etc. to work
558  // on lal x lal.
559  //
560  // Note that `\e|a` remains a tuple of expressions on lal x lal,
561  // but it is turned into a (multitape) label on lan x lal.
562  else if (tuple_of_label<>{self()}.is_label(t))
563  return atom(tuple_of_label<>{self()}.as_label(t));
564  else
565  return std::make_shared<tuple_t>(std::forward<Value>(v)...);
566  }
567 
568  DEFINE::infiltrate(const value_t& l, const value_t& r) const
569  -> value_t
570  {
571  value_t res = nullptr;
572 
573  if (!ids_)
574  res = std::make_shared<infiltrate_t>(l, r);
575 
576  // 0 &: E => 0.
577  else if (is_zero(l))
578  res = l;
579 
580  // E &: 0 => 0.
581  else if (is_zero(r))
582  res = r;
583 
584  // 1 &: E => E.
585  else if (is_one(l))
586  res = r;
587 
588  // E &: 1 => E.
589  else if (is_one(r))
590  res = l;
591 
592  else
593  res =
594  std::make_shared<infiltrate_t>(gather_<type_t::infiltrate>(l, r));
595  return res;
596  }
597 
598  DEFINE::shuffle(const value_t& l, const value_t& r) const
599  -> value_t
600  {
601  value_t res = nullptr;
602 
603  if (!ids_)
604  res = std::make_shared<shuffle_t>(l, r);
605 
606  // 0:E => 0.
607  else if (is_zero(l))
608  res = l;
609 
610  // E:0 => 0.
611  else if (is_zero(r))
612  res = r;
613 
614  // 1:E => E.
615  else if (is_one(l))
616  res = r;
617 
618  // E:1 => E.
619  else if (is_one(r))
620  res = l;
621 
622  else
623  res = std::make_shared<shuffle_t>(gather_<type_t::shuffle>(l, r));
624  return res;
625  }
626 
627  /*-------.
628  | power. |
629  `-------*/
630 
631  DEFINE::power(const value_t& e, unsigned n) const
632  -> value_t
633  {
634  value_t res = nullptr;
635  // Given E the expression s.t. E{n} = (<k>a){n}.
636 
637  // E{0} => 1.
638  if (n == 0)
639  res = one();
640 
641  // E{1} => E.
642  else if (n == 1)
643  res = e;
644 
645  // \z{n} => \z.
646  else if (ids_ && is_zero(e))
647  res = e;
648 
649  // Case: a == \e or a == <w>\e.
650  else if (ids_ && type_ignoring_lweight_(e) == type_t::one)
651  {
652  weight_t w = possibly_implicit_lweight_(e);
653  res = lweight(weightset()->power(w, n), one());
654  }
655 
656  // Lweight in linear commutative: (<k>E){n} => <k{n}>(E{n}).
657  else if (ids_.is_linear()
658  && weightset()->is_commutative()
659  && e->type() == type_t::lweight)
660  {
661  const auto& lw = down_pointer_cast<const lweight_t>(e);
662  res = lweight(weightset()->power(lw->weight(), n),
663  power(lw->sub(), n));
664  }
665 
666  // Sums in series: we have to distribute ([ab]{2} = aa+ab+ba+bb).
667  else if (ids_.is_distributive() && e->type() == type_t::add)
668  {
669  // FIXME: code duplication with weightset_mixin::power_.
670  res = e;
671  for (unsigned i = 1; i < n; ++i)
672  res = mul(res, e);
673  }
674 
675  // When associative, instead of repeated multiplication,
676  // immediately create n copies of E.
677  else if (ids_.is_associative())
678  res = std::make_shared<mul_t>(n, e);
679 
680  // Default case: E{n} = ((..(EE)...)E.
681  else
682  {
683  // FIXME: code duplication with weightset_mixin::power_.
684  res = e;
685  for (unsigned i = 1; i < n; ++i)
686  res = mul(res, e);
687  }
688 
689  return res;
690  }
691 
692  DEFINE::concat(const value_t& l, const value_t& r) const
693  -> value_t
694  {
695  // A static dispatch is needed, as the product of labels is not
696  // available if not LAW.
697  return concat_(l, r, typename is_law<Context>::type{});
698  }
699 
700  // Concatenation when not LAW.
701  DEFINE::concat_(const value_t& l, const value_t& r, std::false_type) const
702  -> value_t
703  {
704  return mul(l, r);
705  }
706 
707  // Concatenation when LAW.
708  DEFINE::concat_(const value_t& l, const value_t& r, std::true_type) const
709  -> value_t
710  {
711  // For instance:
712  // concat((ab).<2>c, d.(ef)) = (ab).<2>(cd).(ef).
713  //
714  // Store (ab) in expression, then concat(<2>c, d) if c and d are
715  // atoms, otherwise <2>c then d, then (ef).
716  if ((type_ignoring_lweight_(l) == type_t::atom || l->type() == type_t::mul)
717  && (r->type() == type_t::atom || r->type() == type_t::mul))
718  {
719  // Left-hand sides.
720  values_t ls;
721  gather_<type_t::mul>(ls, l);
722  // Right-hand sides.
723  values_t rs;
724  gather_<type_t::mul>(rs, r);
725 
726  // FIXME: we should perform that "if" with the one above, and
727  // enter this section only if we really are going to concat.
728  // This would avoid the "else" clause.
729  if (type_ignoring_lweight_(ls.back()) == type_t::atom
730  && rs.front()->type() == type_t::atom)
731  {
732  // Fetch atom of the last lhs.
733  auto lhs
734  = std::dynamic_pointer_cast<const atom_t>
735  (unwrap_possible_lweight_(ls.back()));
736  // Fetch atom of the first rhs.
737  auto rhs = std::dynamic_pointer_cast<const atom_t>(rs.front());
738 
739  auto product = atom(labelset()->mul(lhs->value(), rhs->value()));
740 
741  if (ls.back()->type() == type_t::lweight)
742  {
743  const auto& lw = down_pointer_cast<const lweight_t>(ls.back());
744  product = lweight(lw->weight(), product);
745  }
746  ls.back() = product;
747 
748  ls.insert(ls.end(), rs.begin() + 1, rs.end());
749  }
750  else
751  ls.insert(ls.end(), rs.begin(), rs.end());
752  if (ls.size() == 1)
753  return ls.front();
754  else
755  return std::make_shared<mul_t>(std::move(ls));
756  }
757  else
758  // Handle all the trivial identities.
759  return mul(l, r);
760  }
761 
762  DEFINE::star(const value_t& e) const
763  -> value_t
764  {
765  value_t res = nullptr;
766 
767  // \z* => 1.
768  if (ids_ && is_zero(e))
769  res = one();
770 
771  // E** => E* if on B.
772  else if (ids_.is_agressive()
773  && e->type() == type_t::star
774  && std::is_same<weightset_t, b>{})
775  res = e;
776 
777  else
778  {
779  res = std::make_shared<star_t>(e);
780  if (ids_.is_distributive() && !is_valid(*this, res))
781  raise_not_starrable(self(), e);
782  }
783 
784  return res;
785  }
786 
787  DEFINE::complement(const value_t& e) const
788  -> value_t
789  {
790  value_t res = nullptr;
791 
792  if (!ids_)
793  res = std::make_shared<complement_t>(e);
794 
795  // The following identities make derived-term (<2>a)*{c} terminate.
796  // (<k>E){c} => E{c}.
797  else if (auto w = std::dynamic_pointer_cast<const lweight_t>(e))
798  res = complement(w->sub());
799 
800  // (E<k>){c} => E{c}.
801  else if (auto w = std::dynamic_pointer_cast<const rweight_t>(e))
802  res = complement(w->sub());
803 
804  // E{c}{c} => E if on B or F2.
805  //
806  // Indeed, (<2>a)*{c}{c} is actually denoting a*, not (<2>a)*.
807  else if (e->type() == type_t::complement
808  && std::is_same<weight_t, bool>{})
809  res = down_pointer_cast<const complement_t>(e)->sub();
810 
811  else
812  res = std::make_shared<complement_t>(e);
813 
814  return res;
815  }
816 
817  DEFINE::transposition(const value_t& e) const
818  -> value_t
819  {
820  value_t res = nullptr;
821 
822  if (!ids_)
823  res = std::make_shared<transposition_t>(e);
824 
825  // E{T} => E{t} when agressive.
826  else if (ids_.is_agressive())
827  res = transpose(e);
828 
829  // 0{T} => 0.
830  else if (is_zero(e))
831  res = e;
832 
833  // 1{T} => 1.
834  else if (is_one(e))
835  res = e;
836 
837  // a{T} => a, (abc){T} => cba.
838  else if (auto l = std::dynamic_pointer_cast<const atom_t>(e))
839  res = atom(labelset()->transpose(l->value()));
840 
841  // E{T}{T} => E, if agressive.
842  else if (ids_.is_agressive()
843  && e->type() == type_t::transposition)
844  res = down_pointer_cast<const transposition_t>(e)->sub();
845 
846  else
847  res = std::make_shared<transposition_t>(e);
848  return res;
849  }
850 
851  /*----------.
852  | weights. |
853  `----------*/
854 
855  DEFINE::lweight(const weight_t& w, const value_t& e) const
856  -> value_t
857  {
858  value_t res = nullptr;
859 
860  if (!ids_)
861  res = std::make_shared<lweight_t>(w, e);
862 
863  // <k>0 => 0, <1>E => E.
864  else if (is_zero(e) || weightset()->is_one(w))
865  res = e;
866 
867  // <0>E => 0.
868  else if (weightset()->is_zero(w))
869  res = zero();
870 
871  // <k>(<h>E) => <kh>E.
872  else if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
873  res = lweight(weightset()->mul(w, lw->weight()), lw->sub());
874 
875  // Distributive: <k>(E+F) => <k>E + <k>F.
876  else if (ids_.is_distributive() && e->type() == type_t::add)
877  {
878  const auto& s = down_pointer_cast<const add_t>(e);
879  // We can build the result faster by emplace_back'ing addends without
880  // passing thru add; the order will be the same as in *ss.
881  values_t addends;
882  for (const auto& a: *s)
883  addends.emplace_back(lweight(w, a));
884  res = std::make_shared<add_t>(std::move(addends));
885  }
886 
887  // General case: <k>E.
888  else
889  res = std::make_shared<lweight_t>(w, e);
890 
891  return res;
892  }
893 
894  DEFINE::rweight(const value_t& e, const weight_t& w) const
895  -> value_t
896  {
897  value_t res = nullptr;
898 
899  if (!ids_)
900  res = std::make_shared<rweight_t>(w, e);
901 
902  // Linear identity: E<k> => <k>E.
903  else if (ids_.is_linear() && weightset()->is_commutative())
904  res = lweight(w, e);
905 
906  // Trivial identity: E<0> => 0.
907  else if (weightset()->is_zero(w))
908  res = zero();
909 
910  // Trivial identity: E<1> => E.
911  else if (weightset()->is_one(w))
912  res = e;
913 
914  else if (e->is_leaf())
915  // Can only have left weights and lweight takes care of normalization.
916  res = lweight(w, e);
917 
918  // Trivial identity: (<k>E)<h> => <k>(E<h>).
919  else if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
920  res = lweight(lw->weight(), rweight(lw->sub(), w));
921 
922  // Trivial identity: (E<k>)<h> => E<kh>.
923  else if (auto rw = std::dynamic_pointer_cast<const rweight_t>(e))
924  res = rweight(rw->sub(), weightset()->mul(rw->weight(), w));
925 
926  // General case: E<k>.
927  else
928  res = std::make_shared<rweight_t>(w, e);
929 
930  return res;
931  }
932 
933  /*--------------------------------------.
934  | expressionset as a WeightSet itself. |
935  `--------------------------------------*/
936 
937  DEFINE::is_zero(const value_t& v) const
938  -> bool
939  {
940  return v->type() == type_t::zero;
941  }
942 
943  DEFINE::is_one(const value_t& v)
944  -> bool
945  {
946  return v->type() == type_t::one;
947  }
948 
949  DEFINE::is_universal(const value_t& v) const
950  -> bool
951  {
952  return (v->type() == type_t::complement
953  && is_zero(down_pointer_cast<const complement_t>(v)->sub()));
954  }
955 
957  -> size_t
958  {
959  return rat::size<self_t>(v);
960  }
961 
962  DEFINE::less(const value_t& lhs, const value_t& rhs)
963  -> bool
964  {
965  auto lt = rat::less<self_t>{};
966  return lt(lhs, rhs);
967  }
968 
969  DEFINE::less_linear(const value_t& lhs, const value_t& rhs)
970  -> bool
971  {
972  return less(unwrap_possible_lweight_(lhs),
973  unwrap_possible_lweight_(rhs));
974  }
975 
976  DEFINE::equal(const value_t& lhs, const value_t& rhs)
977  -> bool
978  {
979  return ! less(lhs, rhs) && ! less(rhs, lhs);
980  }
981 
982  DEFINE::hash(const value_t& v)
983  -> size_t
984  {
985  auto hasher = rat::hash<self_t>{};
986  return hasher(v);
987  }
988 
989  DEFINE::conv(const self_t& rs, const value_t& v) const
990  -> value_t
991  {
992  if (ids_ == rs.ids_)
993  return v;
994  else
995  return vcsn::rat::copy(rs, self(), v);
996  }
997 
998  template <typename Context>
999  template <typename GenSet>
1000  auto
1002  typename letterset<GenSet>::value_t v) const
1003  -> value_t
1004  {
1005  return atom(labelset()->conv(ls, v));
1006  }
1007 
1008  DEFINE::conv(b, typename b::value_t v) const
1009  -> value_t
1010  {
1011  return v ? one() : zero();
1012  }
1013 
1014  DEFINE::conv(const z& ws, typename z::value_t v) const
1015  -> value_t
1016  {
1017  return lweight(weightset()->conv(ws, v), one());
1018  }
1019 
1020  DEFINE::conv(const q& ws, typename q::value_t v) const
1021  -> value_t
1022  {
1023  return lweight(weightset()->conv(ws, v), one());
1024  }
1025 
1026  DEFINE::conv(const r& ws, typename r::value_t v) const
1027  -> value_t
1028  {
1029  return lweight(weightset()->conv(ws, v), one());
1030  }
1031 
1032  DEFINE::conv(const zmin& ws, typename zmin::value_t v) const
1033  -> value_t
1034  {
1035  return lweight(weightset()->conv(ws, v), one());
1036  }
1037 
1038  template <typename Context>
1039  template <typename Ctx2>
1040  auto
1043  const
1044  -> value_t
1045  {
1046  return vcsn::rat::copy(rs, self(), r);
1047  }
1048 
1049  DEFINE::conv(std::istream& is, bool) const
1050  -> value_t
1051  {
1052  // Our expression parser is written in dyn::, so we get a
1053  // dyn::expression that we down_cast.
1054  auto dynres = dyn::read_expression(context(), identities(), is);
1055  const auto& res = dynres->template as<self_t>();
1056  return res.value();
1057  }
1058 
1059  DEFINE::print(const value_t& v, std::ostream& o,
1060  format fmt) const
1061  -> std::ostream&
1062  {
1063  auto print = make_printer(self(), o);
1064  print.format(fmt);
1065  return print(v);
1066  }
1067 
1069  -> value_t
1070  {
1071  return vcsn::transpose(self(), v);
1072  }
1073 
1074  template <typename Context>
1075  template <typename... Args>
1076  auto
1078  -> value_t
1079  {
1080  return letter_class_<labelset_t>(std::forward<Args>(args)...,
1081  std::is_same<labelset_t, vcsn::oneset>{});
1082  }
1083 
1084  template <typename Context>
1085  template <typename LabelSet_>
1086  auto
1088  (std::set<std::pair<typename LabelSet_::letter_t,
1089  typename LabelSet_::letter_t>> ccs,
1090  bool accept,
1091  std::false_type) const
1092  -> value_t
1093  {
1094  value_t res = zero();
1095  const auto& ls = *labelset();
1096  auto gens = ls.generators();
1097  // FIXME: This piece of code screams for factoring. Yet, I want
1098  // to avoid useless costs such as building a empty/full set of
1099  // letters for [^].
1100 
1101  // [a-c].
1102  if (accept)
1103  for (const auto& cc: ccs)
1104  {
1105  auto i = std::find(std::begin(gens), std::end(gens), cc.first);
1106  auto end = std::find(i, std::end(gens), cc.second);
1107  VCSN_REQUIRE(end != std::end(gens),
1108  self(), ": invalid letter interval: ",
1109  to_string(*labelset(), ls.value(std::get<0>(cc))),
1110  '-',
1111  to_string(*labelset(), ls.value(std::get<1>(cc))));
1112  for (++end; i != end; ++i)
1113  // We want to avoid having (\z + a) + b in case of [ab].
1114  res = (is_zero(res)
1115  ? atom(ls.value(*i))
1116  : add(res, atom(ls.value(*i))));
1117  }
1118  // [^].
1119  else if (ccs.empty())
1120  for (auto l: gens)
1121  res = add(res, atom(ls.value(l)));
1122  // [^a-z].
1123  else
1124  {
1125  // Match the letters that are in no interval.
1126  std::set<typename LabelSet_::letter_t> accepted;
1127  for (const auto& cc: ccs)
1128  {
1129  auto i = std::find(std::begin(gens), std::end(gens), cc.first);
1130  auto end = std::find(i, std::end(gens), cc.second);
1131  VCSN_REQUIRE(end != std::end(gens),
1132  "invalid letter interval: ",
1133  to_string(*labelset(), ls.value(std::get<0>(cc))),
1134  '-',
1135  to_string(*labelset(), ls.value(std::get<1>(cc))));
1136  for (++end; i != end; ++i)
1137  accepted.emplace(*i);
1138  }
1139  for (auto c: gens)
1140  if (!has(accepted, c))
1141  // We want to avoid having (\z + c) in case of [^ab]
1142  // (considering lal_char(abc)).
1143  res = (is_zero(res)
1144  ? atom(ls.value(c))
1145  : add(res, atom(ls.value(c))));
1146  }
1147  require(!is_zero(res),
1148  "invalid empty letter class");
1149  return res;
1150  }
1151 
1152  template <typename Context>
1153  template <typename LabelSet_, typename... Args>
1154  auto
1156  std::true_type) const
1157  -> value_t
1158  {
1159  return one();
1160  }
1161 
1162 #undef DEFINE
1163 
1164 } // namespace rat
1165 } // namespace vcsn
constant< type_t::one, Context > one
Definition: fwd.hh:113
weight_node< type_t::rweight, Context > rweight
Definition: fwd.hh:182
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82
constant< type_t::zero, Context > zero
Definition: fwd.hh:110
char eat(std::istream &is, char c)
Check lookahead character and advance.
Definition: stream.cc:90
Print as a parsable type string.
Definition: format.hh:26
typename weightset_t::value_t weight_t
auto rs
Definition: lift.hh:152
return res
Definition: multiply.hh:398
static identities ids(const driver &d)
Get the identities of the driver.
Definition: parse.cc:89
Print for LaTeX.
Definition: format.hh:22
expression read_expression(const context &ctx, identities ids, std::istream &is, const std::string &format="default")
Read an expression from a stream.
expressionset_impl(const context_t &ctx, identities_t ids={})
Constructor.
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: context.hh:106
const weightset_ptr & weightset() const
Accessor to the weightset.
An input/output format for valuesets.
Definition: format.hh:13
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
letter_t value_t
Definition: letterset.hh:33
auto letter_class(Args &&...chars) const -> value_t
An expression matching one character amongst chars.
auto conv(const letterset< GenSet > &ls, typename letterset< GenSet >::value_t v) const -> value_t
typename node_t::values_t values_t
A list (vector) of expressions.
std::ostream & print(const Aut &aut, std::ostream &out=std::cout, const std::string &fmt="default")
Definition: print.hh:83
Definition: a-star.hh:8
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
#define VCSN_REQUIRE(Cond,...)
A macro similar to require.
Definition: raise.hh:111
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
Definition: pair.hh:252
typename node_t::value_t value_t
An expression (a shared pointer to a tree).
return hasher(v)
weight_node< type_t::lweight, Context > lweight
Definition: fwd.hh:179
variadic< type_t::add, Context > add
Definition: fwd.hh:157
const identities_t ids_
The set of rewriting rules to apply.
An expressionset can implement several different sets of identities on expressions.
Definition: identities.hh:21
return v
Definition: multiply.hh:361
Implementation of labels are letters.
Definition: fwd.hh:10
symbol sname()
Definition: name.hh:65
printer< ExpSet > make_printer(const ExpSet &rs, std::ostream &out)
Definition: printer.hh:373
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:29
A functor to check whether one rational expression is (strictly) less than another one...
Definition: less.hh:21
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
OutExpSet::value_t copy(const InExpSet &in_rs, const OutExpSet &out_rs, const typename InExpSet::value_t &v)
Copy/convert a rational expression.
Definition: copy.hh:175
auto letter_class_(const Args &&...chars, std::true_type) const -> value_t
If labelset is oneset.
bool is_distributive() const
Whether distributive.
Definition: identities.hh:79
std::string to_string(identities i)
Wrapper around operator<<.
Definition: identities.cc:42
Request the set implementation (bool weights).
Aut transpose(const transpose_automaton< Aut > &aut)
The transpose of a transpose automaton is the original automaton.
Definition: transpose.hh:253