Vcsn  2.4
Be Rational
polynomialset.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <algorithm>
4 #include <iostream>
5 #include <sstream>
6 #include <type_traits>
7 #include <vector>
8 
9 #include <boost/optional.hpp>
10 #include <boost/range/algorithm/equal.hpp>
11 #include <boost/range/algorithm/find_if.hpp>
12 #include <boost/range/algorithm/lexicographical_compare.hpp>
13 
14 #include <vcsn/ctx/context.hh> // We need context to define join.
16 #include <vcsn/ctx/traits.hh>
17 #include <vcsn/misc/algorithm.hh> // front
18 #include <vcsn/misc/attributes.hh>
19 #include <vcsn/misc/functional.hh>
20 #include <vcsn/misc/math.hh>
21 #include <vcsn/misc/raise.hh>
22 #include <vcsn/misc/star-status.hh>
23 #include <vcsn/misc/static-if.hh>
24 #include <vcsn/misc/stream.hh>
25 #include <vcsn/misc/wet.hh>
26 #include <vcsn/misc/zip-maps.hh>
27 #include <vcsn/weightset/f2.hh>
28 #include <vcsn/weightset/fwd.hh>
29 #include <vcsn/weightset/z.hh>
30 
31 namespace vcsn
32 {
33  // http://llvm.org/bugs/show_bug.cgi?id=18571
34 #if defined __clang__
35 # pragma clang diagnostic push
36 # pragma clang diagnostic ignored "-Wunused-value"
37 #endif
38  template <typename LabelSet>
39  auto label_is_zero(const LabelSet& ls, const typename LabelSet::value_t* l)
40  -> decltype(ls.is_zero(l), bool())
41  {
42  return ls.is_zero(*l);
43  }
44 
45 #if defined __clang__
46 # pragma clang diagnostic pop
47 #endif
48 
49  template <typename LabelSet>
50  bool label_is_zero(const LabelSet&, ...)
51  ATTRIBUTE_CONST;
52 
53  template <typename LabelSet>
54  bool label_is_zero(const LabelSet&, ...)
55  {
56  return false;
57  }
58 
59  namespace detail
60  {
61  template <typename WeightSet>
63  : std::true_type
64  {};
65 
66  template <>
68  : std::false_type
69  {};
70 
71  template <typename Context, wet_kind_t Kind>
72  struct is_division_ring<polynomialset<Context, Kind>>
73  : std::false_type
74  {};
75 
78  template <typename Context, wet_kind_t Kind>
79  class polynomialset_impl
80  {
81  public:
83  using context_t = Context;
86 
87  using labelset_ptr = typename context_t::labelset_ptr;
88  using weightset_ptr = typename context_t::weightset_ptr;
90  using label_t = typename labelset_t::value_t;
92 
95  using monomial_t = typename value_t::value_type;
96 
97  polynomialset_impl() = delete;
98  polynomialset_impl(const polynomialset_impl&) = default;
101  : ctx_{ctx}
102  {}
103 
114  const self_t& self() const { return static_cast<const self_t&>(*this); }
115 
117  static symbol sname()
118  {
119  static auto res = symbol{"polynomialset<" + context_t::sname() + '>'};
120  return res;
121  }
122 
123  const context_t& context() const { return ctx_; }
124  const labelset_ptr& labelset() const { return ctx_.labelset(); }
125  const weightset_ptr& weightset() const { return ctx_.weightset(); }
126 
127  static constexpr bool is_commutative() { return false; }
128  static constexpr bool has_lightening_weights()
129  {
130  return weightset_t::has_lightening_weights();
131  }
132 
134  value_t value(const label_t& l, const weight_t w) const
135  {
136  return value_t{{l, w}};
137  }
138 
140  value_t&
141  del_weight(value_t& v, const label_t& l) const
142  {
143  v.erase(l);
144  return v;
145  }
146 
149  value_t&
150  new_weight(value_t& v, const label_t& l, const weight_t w) const
151  {
152  assert(!weightset()->is_zero(w));
153  v.set(l, w);
154  return v;
155  }
156 
158  value_t&
159  set_weight(value_t& v, const label_t& l, const weight_t w) const
160  {
161  if (weightset()->is_zero(w))
162  return del_weight(v, l);
163  else
164  return new_weight(v, l, w);
165  }
166 
167  const weight_t
168  get_weight(const value_t& v, const label_t& l) const ATTRIBUTE_PURE
169  {
170  auto i = v.find(l);
171  if (i == v.end())
172  return weightset()->zero();
173  else
174  return weight_of(*i);
175  }
176 
177 
178  /*---------.
179  | clear. |
180  `---------*/
181 
183  void clear(value_t& v)
184  {
185  v.clear();
186  }
187 
188 
189  /*-------.
190  | add. |
191  `-------*/
192 
194  value_t&
195  add_here(value_t& v, const label_t& l, const weight_t k) const
196  {
197  if (!label_is_zero(*labelset(), &l))
198  {
199  auto i = v.find(l);
200  if (i == v.end())
201  {
202  set_weight(v, l, k);
203  }
204  else
205  {
206  // Do not use set_weight() because it would lookup l
207  // again and we already have the right iterator.
208  auto w2 = weightset()->add(weight_of(*i), k);
209  if (weightset()->is_zero(w2))
210  v.erase(i);
211  else
212  v.set(i, w2);
213  }
214  }
215  return v;
216  }
217 
219  value_t&
220  add_here(value_t& v, const monomial_t& m) const
221  {
222  return add_here(v, label_of(m), weight_of(m));
223  }
224 
226  template <wet_kind_t WetType, typename WS>
227  auto
228  add_here_impl_(value_t& l, const value_t& r) const
229  -> std::enable_if_t<WetType != wet_kind_t::bitset,
230  value_t&>
231  {
232  for (const auto& m: r)
233  add_here(l, m);
234  return l;
235  }
236 
238  template <wet_kind_t WetType, typename WS>
239  auto
240  add_here_impl_(value_t& l, const value_t& r) const
241  -> std::enable_if_t<(WetType == wet_kind_t::bitset
242  && std::is_same<WS, b>::value),
243  value_t&>
244  {
245  l.set() |= r.set();
246  return l;
247  }
248 
250  template <wet_kind_t WetType, typename WS>
251  auto
252  add_here_impl_(value_t& l, const value_t& r) const
253  -> std::enable_if_t<(WetType == wet_kind_t::bitset
254  && std::is_same<WS, f2>::value),
255  value_t&>
256  {
257  l.set() ^= r.set();
258  return l;
259  }
260 
261  value_t&
262  add_here(value_t& l, const value_t& r) const
263  {
264  return add_here_impl_<value_t::kind, weightset_t>(l, r);
265  }
266 
268  value_t add(const value_t& l, const value_t& r) const
269  {
270  value_t res = l;
271  add_here(res, r);
272  return res;
273  }
274 
275 
276  /*-------.
277  | sub. |
278  `-------*/
279 
281  value_t&
282  sub_here(value_t& v, const monomial_t& m) const
283  {
284  if (!label_is_zero(*labelset(), &label_of(m)))
285  {
286  auto i = v.find(label_of(m));
287  if (i == v.end())
288  {
289  raise(*this, ": sub_here: invalid arguments: ",
290  to_string(*this, v), ", ", to_string(*this, m));
291  }
292  else
293  {
294  // Do not use set_weight() because it would lookup w
295  // again and we already have the right iterator.
296  auto w2 = weightset()->sub(weight_of(*i), weight_of(m));
297  if (weightset()->is_zero(w2))
298  v.erase(i);
299  else
300  weight_set(*i, w2);
301  }
302  }
303  return v;
304  }
305 
307  value_t
308  sub(const value_t& l, const value_t& r) const
309  {
310  value_t res = l;
311  for (const auto& rm: r)
312  sub_here(res, rm);
313  return res;
314  }
315 
316 
317  /*-------.
318  | mul. |
319  `-------*/
320 
322  monomial_t
323  mul(const monomial_t& l, const monomial_t& r) const
324  {
325  return {labelset()->mul(label_of(l), label_of(r)),
326  weightset()->mul(weight_of(l), weight_of(r))};
327  }
328 
331  template <wet_kind_t WetType>
332  auto
333  mul_impl_(const value_t& l, const value_t& r) const
334  -> std::enable_if_t<WetType != wet_kind_t::bitset,
335  value_t>
336  {
337  value_t res;
338  for (const auto& lm: l)
339  for (const auto& rm: r)
340  add_here(res,
341  labelset()->mul(label_of(lm), label_of(rm)),
342  weightset()->mul(weight_of(lm), weight_of(rm)));
343  return res;
344  }
345 
348  template <wet_kind_t WetType>
349  auto
350  mul_impl_(const value_t& l, const value_t& r) const
351  -> std::enable_if_t<WetType == wet_kind_t::bitset,
352  value_t>
353  {
354  return l.set() & r.set();
355  }
356 
358  auto
359  mul(const value_t& l, const value_t& r) const
360  -> value_t
361  {
362  return mul_impl_<value_t::kind>(l, r);
363  }
364 
366  auto
367  mul(const value_t& p, const label_t& l, const weight_t w) const
368  -> value_t
369  {
370  value_t res;
371  for (const auto& m: p)
372  add_here(res,
373  labelset()->mul(label_of(m), l),
374  weightset()->mul(weight_of(m), w));
375  return res;
376  }
377 
378 
379  /*---------------.
380  | conjunction. |
381  `---------------*/
382 
385  template <typename Ctx>
386  std::enable_if_t<Ctx::is_lar, value_t>
387  conjunction_impl_(const value_t& l, const value_t& r) const
388  {
389  value_t res;
390  for (const auto& lm: l)
391  for (const auto& rm: r)
392  add_here(res,
393  labelset()->conjunction(label_of(lm), label_of(rm)),
394  weightset()->mul(weight_of(lm), weight_of(rm)));
395  return res;
396  }
397 
400  template <typename Ctx>
401  std::enable_if_t<!Ctx::is_lar, value_t>
402  conjunction_impl_(const value_t& l, const value_t& r) const
403  {
404  value_t res;
405  for (const auto& p: zip_maps<vcsn::as_tuple>(l, r))
406  add_here(res,
407  label_of(std::get<0>(p)),
408  weightset()->mul(weight_of(std::get<0>(p)),
409  weight_of(std::get<1>(p))));
410  return res;
411  }
412 
413  value_t
414  conjunction(const value_t& l, const value_t& r) const
415  {
416  return conjunction_impl_<context_t>(l, r);
417  }
418 
421  value_t
422  infiltrate(const value_t& l, const value_t& r) const
423  {
424  value_t res;
425  for (const auto& lm: l)
426  for (const auto& rm: r)
427  add_here(res,
428  labelset()->infiltrate(label_of(lm), label_of(rm)),
429  weightset()->mul(weight_of(lm), weight_of(rm)));
430  return res;
431  }
432 
435  template <wet_kind_t WetType = value_t::kind>
436  auto
437  scalar_product(const value_t& l, const value_t& r) const
438  -> std::enable_if_t<WetType != wet_kind_t::bitset,
439  weight_t>
440  {
441  auto res = weightset()->zero();
442  for (const auto& p: zip_maps<vcsn::as_tuple>(l, r))
443  res = weightset()->add(res,
444  weightset()->mul(weight_of(std::get<0>(p)),
445  weight_of(std::get<1>(p))));
446  return res;
447  }
448 
451  template <wet_kind_t WetType = value_t::kind, typename WS = weightset_t>
452  auto
453  scalar_product(const value_t& l, const value_t& r) const
454  -> std::enable_if_t<(WetType == wet_kind_t::bitset
455  && std::is_same<WS, b>::value),
456  weight_t>
457  {
458  return l.set().intersects(r.set());
459  }
460 
463  template <wet_kind_t WetType = value_t::kind, typename WS = weightset_t>
464  auto
465  scalar_product(const value_t& l, const value_t& r) const
466  -> std::enable_if_t<(WetType == wet_kind_t::bitset
467  && std::is_same<WS, f2>::value),
468  weight_t>
469  {
470  return (l.set() & r.set()).count() % 2;
471  }
472 
474  value_t abs(const value_t& v) const
475  {
476  value_t res;
477  for (const auto& m: v)
478  add_here(res, label_of(m), weightset()->abs(weight_of(m)));
479  return res;
480  }
481 
483  value_t
484  star(const value_t& v) const
485  {
486  // The only starrable polynomials are scalars (if they are
487  // starrable too).
488  auto s = v.size();
489  if (s == 0)
490  return one();
491  else if (s == 1)
492  {
493  auto i = v.find(labelset()->one());
494  if (i != v.end())
495  return {{i->first, weightset()->star(i->second)}};
496  }
497  raise_not_starrable(*this, v);
498  }
499 
501  value_t
502  lweight(const weight_t w, const value_t& v) const
503  {
504  value_t res;
505  if (weightset()->is_one(w))
506  res = v;
507  else if (!weightset()->is_zero(w))
508  for (const auto& m: v)
509  add_here(res, label_of(m), weightset()->mul(w, weight_of(m)));
510  return res;
511  }
512 
514  value_t
515  lmul_label(const label_t& lhs, const value_t& v) const
516  {
517  value_t res;
518  for (const auto& m: v)
519  add_here(res,
520  labelset()->mul(lhs, label_of(m)),
521  weight_of(m));
522  return res;
523  }
524 
526  value_t
527  mul(const monomial_t& lhs, const value_t& v) const
528  {
529  value_t res;
530  for (const auto& m: v)
531  add_here(res,
532  labelset()->mul(label_of(lhs), label_of(m)),
533  weightset()->mul(weight_of(lhs), weight_of(m)));
534  return res;
535  }
536 
538  template <typename Ctx>
539  using rweight_t
540  = decltype(std::declval<labelset_t_of<Ctx>>()
541  .rweight(std::declval<label_t_of<Ctx>>(),
542  std::declval<weight_t_of<Ctx>>()));
543 
545  template <typename Ctx>
547 
549  auto
550  rweight(const value_t& v, const weight_t w) const
551  -> value_t
552  {
553  value_t res;
554  if (weightset()->is_one(w))
555  res = v;
556  else if (!weightset()->is_zero(w))
557  for (const auto& m: v)
558  // Beware that if the labelset supports weights (e.g.,
559  // polynomial of expressions), we do not multiply the weight
560  // here, but the label.
561  static_if<has_rweight_fn<context_t>{}>
562  ([this, &res] (const auto& ls, const auto& m, const auto& w)
563  {
564  add_here(res,
565  ls.rweight(label_of(m), w),
566  weight_of(m));
567  },
568  [this, &res] (const auto&, const auto& m, const auto& w)
569  {
570  add_here(res,
571  label_of(m),
572  weightset()->mul(w, weight_of(m)));
573  })
574  (*labelset(), m, w);
575  return res;
576  }
577 
579  value_t
580  rmul_label(const value_t& v, const label_t& rhs) const
581  {
582  value_t res;
583  for (const auto& lhs: v)
584  add_here(res,
585  labelset()->mul(label_of(lhs), rhs),
586  weight_of(lhs));
587  return res;
588  }
589 
591  value_t
592  mul(const value_t& l, const monomial_t& rhs) const
593  {
594  value_t res;
595  for (const auto& lhs: l)
596  add_here(res,
597  labelset()->mul(label_of(lhs), label_of(rhs)),
598  weightset()->mul(weight_of(lhs), weight_of(rhs)));
599  return res;
600  }
601 
602  value_t
603  rdivide(const value_t& l, const value_t& r) const
604  {
605  raise(*this, ": rdivide: not implemented (",
606  to_string(*this, l), ", ", to_string(*this, r), ")");
607  }
608 
610  monomial_t
611  ldivide(const monomial_t& l, const monomial_t& r) const
612  {
613  return {labelset()->ldivide(label_of(l), label_of(r)),
614  weightset()->ldivide(weight_of(l), weight_of(r))};
615  }
616 
618  value_t
619  ldivide(const monomial_t& l, const value_t& r) const
620  {
621  value_t res;
622  for (const auto& m: r)
623  add_here(res, ldivide(l, m));
624  return res;
625  }
626 
629  template <typename Ctx = context_t>
630  std::enable_if_t<Ctx::is_lar, value_t&>
631  add_ldivide_here(value_t& res, const value_t& l, const value_t& r) const
632  {
633  for (const auto& lm: l)
634  for (const auto& rm: r)
635  add_here(res, ldivide(lm, rm));
636  return res;
637  }
638 
641  template <typename Ctx = context_t>
642  std::enable_if_t<!Ctx::is_lar, value_t&>
643  add_ldivide_here(value_t& res, const value_t& l, const value_t& r) const
644  {
645  if (is_zero(l))
646  raise(*this, ": ldivide: division by zero");
647  else
648  {
649  value_t remainder = r;
650  while (!is_zero(remainder))
651  {
652  auto factor = ldivide(detail::front(l), detail::front(remainder));
653  add_here(res, factor);
654  remainder = sub(remainder, mul(l, factor));
655  }
656 
657  if (!is_zero(remainder))
658  raise(*this, ": ldivide: not implemented (",
659  to_string(*this, l), ", ", to_string(*this, r), ")");
660  }
661  return res;
662  }
663 
665  value_t
666  ldivide(const value_t& l, const value_t& r) const
667  {
668  value_t res;
669  add_ldivide_here(res, l, r);
670  return res;
671  }
672 
674  value_t&
675  ldivide_here(const weight_t w, value_t& v) const
676  {
677  if (!weightset()->is_one(w))
678  for (auto&& m: v)
679  weight_set(m, weightset()->ldivide(w, weight_of(m)));
680  return v;
681  }
682 
684  value_t&
685  rdivide_here(value_t& v, const weight_t w) const
686  {
687  if (!weightset()->is_one(w))
688  for (auto& m: v)
689  weight_set(m, weightset()->rdivide(weight_of(m), w));
690  return v;
691  }
692 
699  value_t lgcd(const value_t& lhs, const value_t& rhs) const
700  {
701  using std::begin;
702  using std::end;
703  value_t res;
704  // For each monomial, look for the matching GCD of the weight.
705  auto i = begin(lhs), i_end = end(lhs);
706  auto j = begin(rhs), j_end = end(rhs);
707  for (;
708  i != i_end && j != j_end
709  && labelset()->equal(i->first, j->first);
710  ++i, ++j)
711  res.set(i->first, weightset()->lgcd(i->second, j->second));
712  // If the sets of labels are different, the polynomials
713  // cannot be "colinear", and the GCD is just 1.
714  if (i != i_end || j != j_end)
715  res = one();
716  return res;
717  }
718 
719  /*--------.
720  | norm. |
721  `--------*/
722 
724  template <typename WeightSet, typename Dummy = void>
725  struct norm_
726  {
727  typename WeightSet::value_t operator()(const value_t& v) const
728  {
729  return weight_of(front(v));
730  }
731  const WeightSet& ws_;
732  };
733 
735  template <typename Dummy>
736  struct norm_<z, Dummy>
737  {
738  typename z::value_t operator()(const value_t& v) const
739  {
740  int sign = 0 < weight_of(detail::front(v)) ? 1 : -1;
741  auto res = std::abs(weight_of(detail::front(v)));
742  for (const auto& m: v)
743  res = z_.lgcd(res, std::abs(weight_of(m)));
744  res *= sign;
745  return res;
746  }
747  const z& z_;
748  };
749 
751  template <typename Ctx, wet_kind_t Knd, typename Dummy>
752  struct norm_<polynomialset<Ctx, Knd>, Dummy>
753  {
755 
756  typename ps_t::value_t operator()(const value_t& v) const
757  {
758  typename ps_t::value_t res = weight_of(detail::front(v));
759  for (const auto& p: v)
760  res = ps_.lgcd(res, weight_of(p));
761  return res;
762  }
763  const ps_t& ps_;
764  };
765 
768  auto norm(const value_t& v) const
769  -> weight_t
770  {
771  if (is_zero(v))
772  return weightset()->zero();
773  else
774  return norm_<weightset_t>{*weightset()}(v);
775  }
776 
777 
778  /*-------------.
779  | normalize. |
780  `-------------*/
781 
785  {
786  // Zero is in normal form, don't try to divide by zero.
787  auto res = norm(v);
788  if (!weightset()->is_zero(res))
789  ldivide_here(res, v);
790  return res;
791  }
792 
795  {
796  normalize_here(res);
797  return res;
798  }
799 
800 
801 
802  /*---------------.
803  | tuple(v...). |
804  `---------------*/
805 
808  template <typename... Polys>
809  auto
810  tuple(Polys&&... vs) const
811  -> value_t
812  {
813  auto res = value_t{};
814  detail::cross([&res, this](auto... ms)
815  {
816  this->add_here(res,
817  this->labelset()->tuple(ms.first...),
818  this->weightset()->mul(ms.second...));
819  },
820  std::forward<Polys>(vs)...);
821  return res;
822  }
823 
825  template <size_t Tape>
826  auto project() const
827  {
828  return make_polynomialset(vcsn::detail::project<Tape>(context()));
829  }
830 
832  template <size_t Tape>
833  auto project(const value_t& v) const
834  {
835  auto ps = project<Tape>();
836  auto res = ps.zero();
837  for (const auto& m: v)
838  ps.add_here(res,
839  labelset()->template project<Tape>(label_of(m)),
840  weight_of(m));
841  return res;
842  }
843 
844  /*-----------.
845  | compose. |
846  `-----------*/
847 
849  template <typename Ctx>
850  using compose_t
851  = decltype(std::declval<labelset_t_of<Ctx>>()
852  .compose(std::declval<label_t_of<Ctx>>(),
853  std::declval<label_t_of<Ctx>>()));
854 
856  template <typename Ctx>
858 
859 
862  template <typename Ctx = context_t>
863  auto
864  compose(const value_t& l, const value_t& r) const
865  -> std::enable_if_t<are_composable<Ctx, Ctx>{}, value_t>
866  {
867  value_t res;
868  for (const auto& lm: l)
869  for (const auto& rm: r)
870  if (labelset()->template set<0>().equal(std::get<1>(label_of(lm)),
871  std::get<0>(label_of(rm))))
872  add_here(res, labelset()->tuple(std::get<0>(label_of(lm)),
873  std::get<1>(label_of(rm))),
874  weightset()->mul(weight_of(lm), weight_of(rm)));
875  return res;
876  }
877 
880  template <typename Ctx = context_t>
881  auto
882  compose(const value_t& l, const value_t& r) const
883  -> std::enable_if_t<has_compose_fn<Ctx>{}, value_t>
884  {
885  value_t res;
886  for (const auto& lm: l)
887  for (const auto& rm: r)
888  add_here(res, labelset()->compose(label_of(lm), label_of(rm)),
889  weightset()->mul(weight_of(lm),
890  weight_of(rm)));
891  return res;
892  }
893 
894 
895 
902  label_t to_label(const value_t& v) const
903  {
904  label_t res = labelset()->zero();
905  for (const auto& m: v)
906  res = labelset()->add(res,
907  labelset()->lweight(weight_of(m), label_of(m)));
908  return res;
909  }
910 
915  {
916  weight_t w = normalize_here(v);
917  return {to_label(v), w};
918  }
919 
923  value_t complement(const value_t& v) const
924  {
925  return {{labelset()->complement(to_label(normalize(v))),
926  weightset()->one()}};
927  }
928 
929  /*---------------.
930  | equal(l, r). |
931  `---------------*/
932 
933  ATTRIBUTE_PURE
934  static bool monomial_equal(const monomial_t& lhs,
935  const monomial_t& rhs)
936  {
937  return (labelset_t::equal(label_of(lhs), label_of(rhs))
938  && weightset_t::equal(weight_of(lhs), weight_of(rhs)));
939  }
940 
941  template <wet_kind_t WetType>
942  ATTRIBUTE_PURE
943  static auto
944  equal_impl_(const value_t& l, const value_t& r)
945  -> std::enable_if_t<WetType != wet_kind_t::bitset,
946  bool>
947  {
948  return boost::equal(l, r, monomial_equal);
949  }
950 
951  template <wet_kind_t WetType>
952  ATTRIBUTE_PURE
953  static auto
954  equal_impl_(const value_t& l, const value_t& r)
955  -> std::enable_if_t<WetType == wet_kind_t::bitset,
956  bool>
957  {
958  return l.set() == r.set();
959  }
960 
961  ATTRIBUTE_PURE
962  static bool
963  equal(const value_t& l, const value_t& r)
964  {
965  return equal_impl_<value_t::kind>(l, r);
966  }
967 
969  static const value_t& one()
970  {
971  static value_t res{monomial_one()};
972  return res;
973  }
974 
976  static const monomial_t& monomial_one()
977  {
979  return res;
980  }
981 
983  static bool is_one(const value_t& v) ATTRIBUTE_PURE
984  {
985  if (v.size() != 1)
986  return false;
987  auto i = v.find(labelset_t::one());
988  if (i == v.end())
989  return false;
990  return weightset_t::is_one(i->second);
991  }
992 
993  const value_t&
994  zero() const
995  {
996  static value_t res;
997  return res;
998  }
999 
1000  bool
1001  is_zero(const value_t& v) const
1002  {
1003  return v.empty();
1004  }
1005 
1006  static constexpr bool show_one() { return false; }
1007  static constexpr star_status_t star_status()
1008  {
1009  return weightset_t::star_status();
1010  }
1011 
1013  static value_t
1015  {
1016  return v;
1017  }
1018 
1022  template <typename WS>
1023  value_t
1024  conv(const WS& ws, const typename WS::value_t& v) const
1025  {
1026  return {{labelset()->one(), weightset()->conv(ws, v)}};
1027  }
1028 
1030  template <typename C, wet_kind_t K>
1031  value_t
1033  const typename polynomialset<C, K>::value_t& v) const
1034  {
1035  const typename C::labelset_t& sls = *sps.labelset();
1036  const typename C::weightset_t& sws = *sps.weightset();
1037  const labelset_t& tls = *labelset();
1038  const weightset_t& tws = *weightset();
1039  value_t res;
1040  for (const auto& m: v)
1041  add_here(res, tls.conv(sls, label_of(m)), tws.conv(sws, weight_of(m)));
1042  return res;
1043  }
1044 
1045 
1046  /*--------------.
1047  | less(l, r). |
1048  `--------------*/
1049 
1050  ATTRIBUTE_PURE
1051  static bool monomial_less(const monomial_t& lhs, const monomial_t& rhs)
1052  {
1053  if (labelset_t::less(label_of(lhs), label_of(rhs)))
1054  return true;
1055  else if (labelset_t::less(label_of(rhs), label_of(lhs)))
1056  return false;
1057  else
1058  return weightset_t::less(weight_of(lhs), weight_of(rhs));
1059  }
1060 
1061  template <wet_kind_t WetType>
1062  ATTRIBUTE_PURE
1063  static auto
1064  less_impl_(const value_t& l, const value_t& r)
1065  -> std::enable_if_t<WetType != wet_kind_t::bitset,
1066  bool>
1067  {
1068  return boost::range::lexicographical_compare(l, r, monomial_less);
1069  }
1070 
1071  template <wet_kind_t WetType>
1072  ATTRIBUTE_PURE
1073  static auto
1074  less_impl_(const value_t& l, const value_t& r)
1075  -> std::enable_if_t<WetType == wet_kind_t::bitset,
1076  bool>
1077  {
1078  return l.set() < r.set();
1079  }
1080 
1081  ATTRIBUTE_PURE
1082  static bool
1083  less(const value_t& l, const value_t& r)
1084  {
1085  return less_impl_<value_t::kind>(l, r);
1086  }
1087 
1088 
1094  value_t
1095  transpose(const value_t& v) const
1096  {
1097  value_t res;
1098  auto label_transpose
1099  = static_if<context_t::is_lar>
1100  ([](const auto& ls, const auto& l) { return ls.transposition(l); },
1101  [](const auto& ls, const auto& l) { return ls.transpose(l); });
1102  for (const auto& i: v)
1103  res.set(label_transpose(*labelset(), label_of(i)),
1104  weightset()->transpose(weight_of(i)));
1105  return res;
1106  }
1107 
1108 
1109  /*--------.
1110  | hash. |
1111  `--------*/
1112  ATTRIBUTE_PURE
1113  static size_t hash(const monomial_t& m, size_t res = 0)
1114  {
1115  hash_combine(res, labelset_t::hash(label_of(m)));
1116  hash_combine(res, weightset_t::hash(weight_of(m)));
1117  return res;
1118  }
1119 
1120  template <wet_kind_t WetType>
1121  ATTRIBUTE_PURE
1122  static auto
1124  -> std::enable_if_t<WetType != wet_kind_t::bitset,
1125  size_t>
1126  {
1127  size_t res = 0;
1128  for (const auto& m: p)
1129  res = hash(m, res);
1130  return res;
1131  }
1132 
1133  template <wet_kind_t WetType>
1134  ATTRIBUTE_PURE
1135  static auto
1137  -> std::enable_if_t<WetType == wet_kind_t::bitset,
1138  size_t>
1139  {
1140  return hash_value(p.set());
1141  }
1142 
1143  ATTRIBUTE_PURE
1144  static size_t hash(const value_t& v)
1145  {
1146  return hash_impl_<value_t::kind>(v);
1147  }
1148 
1149 
1151  static self_t make(std::istream& is)
1152  {
1153  // name is, for instance, "polynomialset<lal_char(abcd), z>".
1154  eat(is, "polynomialset<");
1155  auto ctx = Context::make(is);
1156  eat(is, '>');
1157  return {ctx};
1158  }
1159 
1160  std::ostream&
1161  print_set(std::ostream& o, format fmt = {}) const
1162  {
1163  switch (fmt.kind())
1164  {
1165  case format::latex:
1166  o << "\\mathsf{Poly}[";
1167  context().print_set(o, fmt);
1168  o << ']';
1169  break;
1170  case format::sname:
1171  o << "polynomialset<";
1172  context().print_set(o, fmt);
1173  o << '>';
1174  break;
1175  case format::text:
1176  case format::utf8:
1177  o << "Poly[";
1178  context().print_set(o, fmt);
1179  o << ']';
1180  break;
1181  case format::raw:
1182  assert(0);
1183  break;
1184  }
1185  return o;
1186  }
1187 
1193  boost::optional<label_t>
1194  conv_label(std::istream& i, bool weighted, const char sep = '+') const
1195  {
1196  int peek = i.peek();
1197  assert(peek != '[');
1198  if (peek == '\\')
1199  {
1200  i.ignore();
1201  if (i.peek() == 'z')
1202  {
1203  i.ignore();
1204  return boost::none;
1205  }
1206  else
1207  i.unget();
1208  }
1209 
1210  // The label is not \z.
1211  // Check if there is a label that comes. Or rather, check if
1212  // there is something else than EOF or the separator, in which
1213  // case it must be a label.
1214  label_t res;
1215  if (peek == EOF || peek == sep || isspace(peek))
1216  {
1217  // There is no label. This counts as '$', the special
1218  // label.
1219  //
1220  // Indeed, that's how we represent the initial and final
1221  // transitions: '$ -> 0 "<2>"'. Using the one label is
1222  // tempting, but it does not exist for lal_char for
1223  // instance. And it would be wrong to have '\e' when we
1224  // can, and '$' otherwise...
1225  //
1226  // However, we must have at least a weight: a completely
1227  // empty mononial ($ -> 0 "<2>,") is invalid.
1228  VCSN_REQUIRE(weighted,
1229  *this, ": conv: invalid monomial: ",
1230  str_escape(peek),
1231  " (did you mean \\e or \\z?)");
1232  res = labelset()->special();
1233  }
1234  else
1235  {
1236  auto pos = i.tellg();
1237  res = labelset()->conv(i);
1238  // In law_char, when reading the monomial `a|b` (yes, `|` is
1239  // not escaped), we looped for ever: the `a` was read by
1240  // setalpha::get_word, which then returned, and then
1241  // conv_label repeatedly called get_word on `|b`, which
1242  // endlessly returned the empty word, refusing to pass the
1243  // `|`.
1244  //
1245  // Make sure we catch this. Beware that tellg returns -1
1246  // (yes, signed!) on EOF.
1247  require(i.peek() == EOF || pos < i.tellg(),
1248  *this, ": invalid implicit empty word before: ", i);
1249  }
1250  return res;
1251  }
1252 
1254  weight_t
1255  conv_weight(std::istream& i) const
1256  {
1257  if (i.peek() == langle)
1258  // FIXME: convert to use conv(std::istream).
1259  //
1260  // The problem is when we have a rational expression as a
1261  // weight: in that case, conv expect to parse up to EOF, not
1262  // up to '>'. We first need to fix the parsing of expression
1263  // to work on a flow, to be able to use weightset()->conv
1264  // here. Which means to get back the stream from a Flex
1265  // scanner. It might not be easy.
1267  else
1268  return weightset()->one();
1269  }
1270 
1277  boost::optional<monomial_t>
1278  conv_monomial(std::istream& i, const char sep = '+') const
1279  {
1280 #define SKIP_SPACES() \
1281  while (isspace(i.peek())) \
1282  i.ignore()
1283 
1284  // Nothing to read: signal EOF as an empty result.
1285  SKIP_SPACES();
1286  if (i.peek() == EOF)
1287  return boost::none;
1288 
1289  // Possibly a weight in braces.
1290  bool weighted = i.peek() == langle;
1291  weight_t w = conv_weight(i);
1292 
1293  // Possibly, a label.
1294  SKIP_SPACES();
1295  auto l = conv_label(i, weighted, sep);
1296  require(l, *this, ": \\z is invalid for monomials");
1297  return monomial_t{*l, w};
1298 #undef SKIP_SPACES
1299  }
1300 
1309  value_t
1310  conv(std::istream& i, const char sep = '+') const
1311  {
1312  value_t res;
1313 #define SKIP_SPACES() \
1314  while (isspace(i.peek())) \
1315  i.ignore()
1316 
1317  do
1318  {
1319  // Possibly a weight in braces.
1320  SKIP_SPACES();
1321  bool weighted = i.peek() == langle;
1322  weight_t w = conv_weight(i);
1323 
1324  SKIP_SPACES();
1325  // Possibly, a label.
1326  // Handle label classes.
1327  if (i.peek() == '[')
1328  labelset()->convs(i, [this, &res, &w](const label_t& l)
1329  {
1330  add_here(res, l, w);
1331  });
1332  else if (auto l = conv_label(i, weighted, sep))
1333  {
1334  require(l, *this, ": \\z is invalid for monomials");
1335  add_here(res, *l, w);
1336  }
1337 
1338  // sep (e.g., '+'), or stop parsing.
1339  SKIP_SPACES();
1340  if (i.peek() == sep)
1341  i.ignore();
1342  else
1343  break;
1344  }
1345  while (true);
1346 #undef SKIP_SPACES
1347 
1348  return res;
1349  }
1350 
1352  std::ostream&
1353  print(const monomial_t& m, std::ostream& out,
1354  format fmt = {}) const
1355  {
1356  static bool parens = getenv("VCSN_PARENS");
1357  print_weight_(weight_of(m), out, fmt);
1358  if (parens)
1359  out << (fmt == format::latex ? "\\left(" : "(");
1360  labelset()->print(label_of(m), out, fmt.for_labels());
1361  if (parens)
1362  out << (fmt == format::latex ? "\\right)" : ")");
1363  return out;
1364  }
1365 
1372  std::ostream&
1373  print(const value_t& v, std::ostream& out,
1374  format fmt = {},
1375  const std::string& sep = " + ") const
1376  {
1377  if (is_zero(v))
1378  out << (fmt == format::latex ? "\\emptyset"
1379  : fmt == format::utf8 ? "∅"
1380  : "\\z");
1381  else
1382  {
1383  const auto s =
1384  (sep == " + "
1385  ? (fmt == format::latex ? std::string{" \\oplus "}
1386  : fmt == format::utf8 ? std::string{"⊕"}
1387  : sep)
1388  : sep);
1389  print_(v, out, fmt, s);
1390  }
1391  return out;
1392  }
1393 
1394  private:
1396  std::ostream&
1397  print_weight_(const weight_t w, std::ostream& out,
1398  format fmt) const
1399  {
1400  static bool parens = getenv("VCSN_PARENS");
1401  if (parens || weightset()->show_one() || !weightset()->is_one(w))
1402  {
1403  out << (fmt == format::latex ? "\\left\\langle "
1404  : fmt == format::utf8 ? "⟨"
1405  : "<");
1406  weightset()->print(w, out, fmt.for_weights());
1407  out << (fmt == format::latex ? "\\right\\rangle "
1408  : fmt == format::utf8 ? "⟩"
1409  : ">");
1410  }
1411  return out;
1412  }
1413 
1415  std::ostream&
1416  print_without_classes_(const value_t& v, std::ostream& out,
1417  format fmt,
1418  const std::string& sep) const
1419  {
1420  bool first = true;
1421  for (const auto& m: v)
1422  {
1423  if (!first)
1424  out << sep;
1425  first = false;
1426  print(m, out, fmt);
1427  }
1428  return out;
1429  }
1430 
1432  std::ostream&
1433  print_with_classes_(const value_t& v, std::ostream& out,
1434  format fmt,
1435  const std::string& sep) const
1436  {
1437  using std::begin;
1438  using std::end;
1439 
1440  // We can use a vector, as we know that the labels are already
1441  // sorted, and random access iteration will be handy below.
1442  using labels_t = std::vector<label_t>;
1443 
1444  // Cluster the letters per weight.
1445  auto per_weight = std::map<weight_t, labels_t,
1447  // No classes if the weights of the letters aren't all the same.
1448  for (const auto& m: v)
1449  if (!labelset()->is_one(label_of(m)))
1450  per_weight[weight_of(m)].emplace_back(label_of(m));
1451 
1452  // Sort the clusters per label.
1453  auto per_label = std::map<label_t,
1454  std::pair<weight_t, labels_t>,
1456  for (const auto& p: per_weight)
1457  // Split classes which are too small.
1458  if (p.second.size() < 3)
1459  for (auto l: p.second)
1460  per_label[l] = std::make_pair(p.first, labels_t{l});
1461  else
1462  per_label[detail::front(p.second)] = p;
1463 
1464  // Whether we must not issue a separator.
1465  bool first = true;
1466 
1467  // Print with classes. First, the constant-term.
1468  if (labelset()->is_one(label_of(detail::front(v))))
1469  {
1470  print(detail::front(v), out, fmt);
1471  first = false;
1472  }
1473 
1474  for (const auto& p: per_label)
1475  {
1476  if (!first)
1477  out << sep;
1478  first = false;
1479 
1480  // The weight.
1481  print_weight_(p.second.first, out, fmt);
1482 
1483  if (1 < p.second.second.size())
1484  // Print the character class. 'letters' are sorted, since
1485  // polynomials are shortlex-sorted on the labels.
1486  print_label_class(*labelset(), p.second.second,
1487  out, fmt.for_labels());
1488  else
1489  labelset()->print(detail::front(p.second.second),
1490  out, fmt.for_labels());
1491  }
1492  return out;
1493  }
1494 
1496  template <typename Ctx = context_t>
1498  std::ostream&>
1499  print_(const value_t& v, std::ostream& out,
1500  format fmt = {},
1501  const std::string& sep = " + ") const
1502  {
1503  return print_without_classes_(v, out, fmt, sep);
1504  }
1505 
1508  template <typename Ctx = context_t>
1510  std::ostream&>
1511  print_(const value_t& v, std::ostream& out,
1512  format fmt = {},
1513  const std::string& sep = " + ") const
1514  {
1515  // No classes if not at least 3 elements.
1516  if (sep == " + " || v.size() <= 2)
1517  return print_without_classes_(v, out, fmt, sep);
1518  else
1519  return print_with_classes_(v, out, fmt, sep);
1520  }
1521 
1522 
1523  private:
1525 
1527  constexpr static char langle = '<';
1529  constexpr static char rangle = '>';
1530  };
1531 
1532  template <typename Context,
1533  wet_kind_t Kind = detail::wet_kind<labelset_t_of<Context>,
1536  make_polynomialset(const Context& context)
1537  {
1538  return {context};
1539  }
1540 
1541  template <typename Ctx1, wet_kind_t Kind1,
1542  typename Ctx2, wet_kind_t Kind2>
1543  struct join_impl<polynomialset<Ctx1, Kind1>,
1544  polynomialset<Ctx2, Kind2>>
1545  {
1546  // Use the default kind.
1549  const polynomialset<Ctx2, Kind2>& ps2)
1550  {
1551  return {vcsn::join(ps1.context(), ps2.context())};
1552  }
1553  };
1554 
1555  template <typename Ctx1, wet_kind_t Kind1,
1556  typename WS2>
1557  struct join_impl<polynomialset<Ctx1, Kind1>, WS2>
1558  {
1559  using type
1560  = polynomialset<context<typename Ctx1::labelset_t,
1562  static type join(const polynomialset<Ctx1, Kind1>& ps1, const WS2& ws2)
1563  {
1564  return {*ps1.labelset(), vcsn::join(*ps1.weightset(), ws2)};
1565  }
1566  };
1567  }
1568 }
auto tuple(Polys &&...vs) const -> value_t
Build a tuple of polynomials: (e.E+f.F)|(g.G+h.H) => eg.
auto mul_impl_(const value_t &l, const value_t &r) const -> std::enable_if_t< WetType==wet_kind_t::bitset, value_t >
The product of polynomials l and r.
constant< type_t::one, Context > one
Definition: fwd.hh:113
weight_t normalize_here(value_t &v) const
Normalize v in place: compute the LGCD of the weights, ldivide the monomials with that factor...
value_t ldivide(const monomial_t &l, const value_t &r) const
Left division by a monomial: l \ r.
value_t transpose(const value_t &v) const
Transpose the labels and the weights.
labelset_t_of< context_t > labelset_t
value_t mul(const monomial_t &lhs, const value_t &v) const
Left product by a monomial.
std::ostream & print_without_classes_(const value_t &v, std::ostream &out, format fmt, const std::string &sep) const
Print a polynomial value without classes.
value_t & ldivide_here(const weight_t w, value_t &v) const
Left exterior division.
static ATTRIBUTE_PURE auto less_impl_(const value_t &l, const value_t &r) -> std::enable_if_t< WetType!=wet_kind_t::bitset, bool >
static ATTRIBUTE_PURE size_t hash(const monomial_t &m, size_t res=0)
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
Container::value_type front(const Container &container)
The first member of this Container.
Definition: algorithm.hh:68
WeightSet::value_t operator()(const value_t &v) const
auto scalar_product(const value_t &l, const value_t &r) const -> std::enable_if_t< WetType!=wet_kind_t::bitset, weight_t >
The sum of the weights of the common labels.
std::ostream & print(const monomial_t &m, std::ostream &out, format fmt={}) const
Print a monomial.
monomial_t mul(const monomial_t &l, const monomial_t &r) const
The product of monomials l and r.
label_t to_label(const value_t &v) const
Convert into a label.
auto compose(const value_t &l, const value_t &r) const -> std::enable_if_t< has_compose_fn< Ctx >
The composition of polynomials l and r when the context features compose.
static constexpr char langle
Left marker for weight in concrete syntax.
value_t & new_weight(value_t &v, const label_t &l, const weight_t w) const
Set the monomial of l in v to weight w.
format for_labels() const
A copy of this format, but to print labels.
Definition: format.hh:42
std::string bracketed(std::istream &i, char lbracket, char rbracket)
Extract the string which is here between lbracket and rbracket.
Definition: stream.cc:17
Print for LaTeX.
Definition: format.hh:22
static ATTRIBUTE_PURE bool equal(const value_t &l, const value_t &r)
Functor to compare Values of ValueSets.
Definition: functional.hh:76
static type join(const polynomialset< Ctx1, Kind1 > &ps1, const WS2 &ws2)
auto mul(const value_t &p, const label_t &l, const weight_t w) const -> value_t
The product of polynomials l and r.
value_t ldivide(const value_t &l, const value_t &r) const
Left division of two polynomials: l \ r.
value_t & rdivide_here(value_t &v, const weight_t w) const
Right exterior division.
value_t normalize(value_t res) const
Normalized v.
static ATTRIBUTE_PURE bool less(const value_t &l, const value_t &r)
const weight_t get_weight(const value_t &v, const label_t &l) const ATTRIBUTE_PURE
auto weight_of(const welement< Label, Weight > &m) -> decltype(m.weight())
The weight of a welement.
Definition: wet.hh:154
for(const auto &lm:l) for(const auto &rm return res
typename value_t::value_type monomial_t
A pair .
An input/output format for valuesets.
Definition: format.hh:13
typename context_t::weightset_ptr weightset_ptr
wet_of< context_t, Kind > value_t
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54
decltype(join(std::declval< ValueSets >()...)) join_t
The type of the join of the ValueSets.
Definition: join.hh:78
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
auto factor(const Aut &aut) -> decltype(::vcsn::copy(aut))
Definition: prefix.hh:106
value_t rmul_label(const value_t &v, const label_t &rhs) const
Right product.
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
typename labelset_t::value_t label_t
Polynomials over labels.
value_t conv(const polynomialset< C, K > &sps, const typename polynomialset< C, K >::value_t &v) const
Convert from another polynomialset to type_t.
static constexpr bool has_lightening_weights()
Linear combination of labels: map labels to weights.
Definition: fwd.hh:41
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
static ATTRIBUTE_PURE auto equal_impl_(const value_t &l, const value_t &r) -> std::enable_if_t< WetType!=wet_kind_t::bitset, bool >
auto hash_value(const T &v) -> decltype(std::hash< T >
Following the naming convention of Boost.
Definition: functional.hh:30
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
std::enable_if_t< Ctx::is_lar, value_t & > add_ldivide_here(value_t &res, const value_t &l, const value_t &r) const
The left-division of polynomials l and r: res += l \ r.
auto compose(const value_t &l, const value_t &r) const -> std::enable_if_t< are_composable< Ctx, Ctx >
The composition of polynomials l and r when the context is a composable tupleset. ...
auto project(const value_t &v) const
Extract a single tape.
static bool is_one(const value_t &v) ATTRIBUTE_PURE
Whether is the unit polynomial.
weight_t_of< context_t > weight_t
static symbol sname()
The static name.
value_t conv(const WS &ws, const typename WS::value_t &v) const
FIXME: use enable_if to prevent this from being instantiated when WS is a polynomialset.
Request the map implementation.
static ATTRIBUTE_PURE bool monomial_less(const monomial_t &lhs, const monomial_t &rhs)
polynomialset< Context, Kind > make_polynomialset(const Context &context)
static ATTRIBUTE_PURE auto hash_impl_(const value_t &p) -> std::enable_if_t< WetType!=wet_kind_t::bitset, size_t >
wet< label_t_of< Context >, weight_t_of< Context >, Kind, vcsn::less< labelset_t_of< Context >>, vcsn::hash< labelset_t_of< Context >>, vcsn::equal_to< labelset_t_of< Context >>> wet_of
The corresponding wet for a LabelSet -> WeightSet context.
Definition: wet.hh:863
static ATTRIBUTE_PURE auto equal_impl_(const value_t &l, const value_t &r) -> std::enable_if_t< WetType==wet_kind_t::bitset, bool >
static value_t conv(self_t, const value_t &v)
Conversion from (this and) other weightsets.
auto mul(const value_t &l, const value_t &r) const -> value_t
The product of polynomials l and r.
const context_t & context() const
Definition: a-star.hh:8
weightset_t_of< context_t > weightset_t
boost::optional< monomial_t > conv_monomial(std::istream &i, const char sep= '+') const
Read a monomial from a stream.
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:85
value_t star(const value_t &v) const
The star of polynomial v.
auto scalar_product(const value_t &l, const value_t &r) const -> std::enable_if_t<(WetType==wet_kind_t::bitset &&std::is_same< WS, f2 >::value), weight_t >
The sum of the weights of the common labels.
#define VCSN_REQUIRE(Cond,...)
A macro similar to require.
Definition: raise.hh:111
Print as rich UTF-8 text, escaped.
Definition: format.hh:30
value_t lgcd(const value_t &lhs, const value_t &rhs) const
LGCD between two polynomials.
static constexpr char rangle
Right marker for weight in concrete syntax.
static ATTRIBUTE_PURE auto hash_impl_(const value_t &p) -> std::enable_if_t< WetType==wet_kind_t::bitset, size_t >
A structure that implements the computation of join(V1, V2).
Definition: join.hh:18
static type join(const polynomialset< Ctx1, Kind1 > &ps1, const polynomialset< Ctx2, Kind2 > &ps2)
std::enable_if_t<!labelset_t_of< Ctx >::is_letterized(), std::ostream & > print_(const value_t &v, std::ostream &out, format fmt={}, const std::string &sep=" + ") const
Print a non-null value for a non letterized labelset.
std::enable_if_t< Ctx::is_lar, value_t > conjunction_impl_(const value_t &l, const value_t &r) const
The conjunction of polynomials l and r.
static constexpr star_status_t star_status()
static ATTRIBUTE_PURE auto less_impl_(const value_t &l, const value_t &r) -> std::enable_if_t< WetType==wet_kind_t::bitset, bool >
auto add_here_impl_(value_t &l, const value_t &r) const -> std::enable_if_t< WetType!=wet_kind_t::bitset, value_t & >
v += p, default case.
std::enable_if_t< labelset_t_of< Ctx >::is_letterized(), std::ostream & > print_(const value_t &v, std::ostream &out, format fmt={}, const std::string &sep=" + ") const
Print a non-null value for a letterized labelset (e.g., letterset or nullableset. ...
value_t & set_weight(value_t &v, const label_t &l, const weight_t w) const
Set the monomial of l in v to weight w.
std::enable_if_t<!is_letterized_t< labelset_t_of< Aut > >{}, bool > is_letterized(const Aut &aut)
Definition: letterize.hh:161
value_t sub(const value_t &l, const value_t &r) const
The subtraction of polynomials l and r.
std::ostream & print_set(std::ostream &o, format fmt={}) const
value_t add(const value_t &l, const value_t &r) const
The sum of polynomials l and r.
value_t lmul_label(const label_t &lhs, const value_t &v) const
Left product by a label.
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
boost::optional< label_t > conv_label(std::istream &i, bool weighted, const char sep= '+') const
Read a label, if there is one.
value_t & add_here(value_t &v, const label_t &l, const weight_t k) const
v += l.
value_t & del_weight(value_t &v, const label_t &l) const
Remove the monomial of l in v.
std::ostream & print(const value_t &v, std::ostream &out, format fmt={}, const std::string &sep=" + ") const
Print a value (a polynomial).
auto add_here_impl_(value_t &l, const value_t &r) const -> std::enable_if_t<(WetType==wet_kind_t::bitset &&std::is_same< WS, f2 >::value), value_t & >
v += p, F2 and bitsets.
std::ostream & str_escape(std::ostream &os, const std::string &str, const char *special=nullptr)
Output a string, escaping special characters.
Definition: escape.cc:51
auto mul_impl_(const value_t &l, const value_t &r) const -> std::enable_if_t< WetType!=wet_kind_t::bitset, value_t >
The product of polynomials l and r.
weight_t conv_weight(std::istream &i) const
Read a weight, if there is one, bracketed.
value_t complement(const value_t &v) const
Complement this polynomial.
value_t conjunction(const value_t &l, const value_t &r) const
void clear(value_t &v)
Set to zero.
value_t abs(const value_t &v) const
Map all weights to their absolute value.
const weightset_ptr & weightset() const
std::enable_if_t<!Ctx::is_lar, value_t > conjunction_impl_(const value_t &l, const value_t &r) const
The conjunction of polynomials l and r.
value_t & add_here(value_t &l, const value_t &r) const
static ATTRIBUTE_PURE bool monomial_equal(const monomial_t &lhs, const monomial_t &rhs)
bool is_zero(const value_t &v) const
value_t rdivide(const value_t &l, const value_t &r) const
In the general case, normalize by the first (non null) weight.
polynomialset_impl(const context_t &ctx)
star_status_t
Definition: star-status.hh:5
symbol sname()
Definition: name.hh:65
std::ostream & print_weight_(const weight_t w, std::ostream &out, format fmt) const
Print a weight.
std::string to_string(direction d)
Conversion to string.
Definition: direction.cc:7
#define SKIP_SPACES()
std::ostream & print_with_classes_(const value_t &v, std::ostream &out, format fmt, const std::string &sep) const
Print a polynomial value with classes.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
static self_t make(std::istream &is)
Build from the description in is.
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
decltype(std::declval< labelset_t_of< Ctx >>().compose(std::declval< label_t_of< Ctx >>(), std::declval< label_t_of< Ctx >>())) compose_t
Detect whether the labelset features compose.
value_t conv(std::istream &i, const char sep= '+') const
Read a polynomial from a stream.
ATTRIBUTE_NORETURN void raise_not_starrable(const WeightSet &ws, const typename WeightSet::value_t &w)
This value is not starrable.
Definition: raise.hh:100
monomial_t ldivide(const monomial_t &l, const monomial_t &r) const
Left division between two mononials: l \ r.
typename context_t::labelset_ptr labelset_ptr
static const monomial_t & monomial_one()
The unit monomial.
auto join(const ValueSet &vs) -> ValueSet
The join of a single valueset.
Definition: join.hh:44
std::enable_if_t<!Ctx::is_lar, value_t & > add_ldivide_here(value_t &res, const value_t &l, const value_t &r) const
The left-division of polynomials l and r: res += l \ r.
const labelset_ptr & labelset() const
void hash_combine(std::size_t &seed, const T &v)
Definition: functional.hh:48
void cross(Fun f)
Variadic Cartesian product of containers.
Definition: tuple.hh:273
auto add_here_impl_(value_t &l, const value_t &r) const -> std::enable_if_t<(WetType==wet_kind_t::bitset &&std::is_same< WS, b >::value), value_t & >
v += p, B and bitsets.
value_t & sub_here(value_t &v, const monomial_t &m) const
v -= m.
auto label_is_zero(const LabelSet &ls, const typename LabelSet::value_t *l) -> decltype(ls.is_zero(l), bool())
static constexpr bool show_one()
z::value_t operator()(const value_t &v) const
auto rweight(const value_t &v, const weight_t w) const -> value_t
Right exterior product.
auto norm(const value_t &v) const -> weight_t
The norm: the weight with which we should divide a polynomial to normalize it.
const value_t & zero() const
decltype(std::declval< labelset_t_of< Ctx >>().rweight(std::declval< label_t_of< Ctx >>(), std::declval< weight_t_of< Ctx >>())) rweight_t
Detect whether the labelset features rweight.
auto label_of(const welement< Label, Weight > &m) -> decltype(m.label())
The label of a welement.
Definition: wet.hh:146
static const value_t & one()
The unit polynomial.
static ATTRIBUTE_PURE size_t hash(const value_t &v)
value_t infiltrate(const value_t &l, const value_t &r) const
The infiltration of polynomials l and r.
Request the bitset implementation (bool weights).
value_t mul(const value_t &l, const monomial_t &rhs) const
Right product by a monomial.
std::ostream & print_label_class(const LabelSet &ls, const std::vector< typename LabelSet::value_t > &letters, std::ostream &out, format fmt)
Print a set of labels (letterized) with classes.
Definition: labelset.hh:326
monomial_t determinize(value_t v) const
"Determinize" this polynomial: turn into a monomial.
wet_kind_t
Different implementations of wets.
Definition: wet.hh:197
value_t value(const label_t &l, const weight_t w) const
Create a polynomial with a single value.
auto project() const
The polynomialset for tape Tape.
value_t lweight(const weight_t w, const value_t &v) const
Left exterior product.
value_t & add_here(value_t &v, const monomial_t &m) const
v += m.
void weight_set(welement< Label, Weight > &m, const Weight &w)
Set the weight of a welement.
Definition: wet.hh:162
auto scalar_product(const value_t &l, const value_t &r) const -> std::enable_if_t<(WetType==wet_kind_t::bitset &&std::is_same< WS, b >::value), weight_t >
The sum of the weights of the common labels.
static constexpr bool is_commutative()