5 #include <boost/range/algorithm/find.hpp>
6 #include <boost/range/algorithm/lower_bound.hpp>
8 #include <vcsn/algos/fwd.hh>
28 template <
typename Context>
35 "series (currently) requires a commutative weightset product");
39 template <typename Context> \
42 expressionset_impl<Context>
52 DEFINE::make(std::istream&
is)
56 eat(
is,
"expressionset<");
57 auto ctx = Context::make(
is);
69 DEFINE::print_set(std::ostream& o,
format fmt)
const
90 o << "expressionset<";
91 context().print_set(o, fmt);
93 if (identities() != vcsn::rat::identities{})
94 o << '(
' << identities() << ')
';
100 context().print_set(o, fmt);
102 if (identities() != vcsn::rat::identities{})
103 o << '(
' << identities() << ')
';
113 DEFINE::open(bool o) const
116 return this->labelset()->open(o);
119 DEFINE::context() const -> const context_t&
124 DEFINE::identities() const -> identities_t
129 DEFINE::labelset() const -> const labelset_ptr&
131 return ctx_.labelset();
134 DEFINE::weightset() const -> const weightset_ptr&
136 return ctx_.weightset();
139 DEFINE::atom(const label_t& v)
142 if (labelset_t::is_one(v))
145 return std::make_shared<atom_t>(v);
151 return std::make_shared<zero_t>();
157 return std::make_shared<one_t>();
160 template <typename Context>
161 template <typename expressionset_impl<Context>::type_t Type>
164 expressionset_impl<Context>::gather_(values_t& res, const value_t& v) const
167 auto variadic = std::dynamic_pointer_cast<const variadic_t<Type>>(v);
168 if (variadic && ids_.is_associative())
169 res.insert(std::end(res), std::begin(*variadic), std::end(*variadic));
174 template <typename Context>
175 template <typename expressionset_impl<Context>::type_t Type>
178 expressionset_impl<Context>::gather_(const value_t& l, const value_t& r) const
182 if (ids_.is_associative())
184 gather_<Type>(res, l);
185 gather_<Type>(res, r);
195 DEFINE::add(const value_t& l, const value_t& r) const
198 value_t res = nullptr;
201 res = std::make_shared<sum_t>(l, r);
212 else if (ids_.is_linear())
213 res = add_linear_(l, r);
216 res = std::make_shared<sum_t>(gather_<type_t::sum>(l, r));
220 DEFINE::add_linear_(const sum_t& s, const value_t& r) const
223 auto res = values_t{};
224 res.reserve(s.size() + 1);
226 // Copy the strictly smaller part.
227 auto i = boost::lower_bound(s, r, less_linear);
228 res.insert(end(res), begin(s), i);
234 if (less_linear(r, *i))
238 auto w = weightset()->add(possibly_implicit_lweight_(*i),
239 possibly_implicit_lweight_(r));
240 if (!weightset()->is_zero(w))
242 auto l = unwrap_possible_lweight_(*i);
243 res.emplace_back(lmul(w, l));
247 res.insert(end(res), i, end(s));
250 return add_(std::move(res));
253 DEFINE::add_(values_t&& vs) const
258 else if (vs.size() == 1)
261 return std::make_shared<sum_t>(std::move(vs));
264 DEFINE::add_linear_(const sum_t& s1, const sum_t& s2) const
267 auto res = values_t{};
268 res.reserve(s1.size() + s2.size());
269 // Merge two increasing lists. Add weights of equal labels.
272 auto i1 = begin(s1), end1 = end(s1);
273 auto i2 = begin(s2), end2 = end(s2);
278 res.insert(res.end(), i2, end2);
283 res.insert(res.end(), i1, end1);
286 else if (less_linear(*i1, *i2))
287 res.emplace_back(*i1++);
288 else if (less_linear(*i2, *i1))
289 res.emplace_back(*i2++);
292 auto w = weightset()->add(possibly_implicit_lweight_(*i1),
293 possibly_implicit_lweight_(*i2));
294 if (!weightset()->is_zero(w))
296 auto l = unwrap_possible_lweight_(*i1);
297 res.emplace_back(lmul(w, l));
303 return add_(std::move(res));
306 DEFINE::add_linear_(const value_t& l, const value_t& r) const
311 value_t res = nullptr;
312 if (auto ls = std::dynamic_pointer_cast<const sum_t>(l))
314 if (auto rs = std::dynamic_pointer_cast<const sum_t>(r))
315 res = add_linear_(*ls, *rs);
317 res = add_linear_(*ls, r);
319 else if (auto rs = std::dynamic_pointer_cast<const sum_t>(r))
320 res = add_linear_(*rs, l);
321 else if (less_linear(l, r))
322 res = std::make_shared<sum_t>(l, r);
323 else if (less_linear(r, l))
324 res = std::make_shared<sum_t>(r, l);
327 auto w = weightset()->add(possibly_implicit_lweight_(l),
328 possibly_implicit_lweight_(r));
329 res = lmul(w, unwrap_possible_lweight_(l));
334 DEFINE::type_ignoring_lweight_(const value_t& e)
337 return unwrap_possible_lweight_(e)->type();
340 DEFINE::possibly_implicit_lweight_(const value_t& e)
343 if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
346 return weightset_t::one();
349 DEFINE::unwrap_possible_lweight_(const value_t& e)
352 if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
358 DEFINE::mul(const value_t& l, const value_t& r) const
361 value_t res = nullptr;
364 res = std::make_shared<prod_t>(l, r);
374 // U_K: E.(<k>1) ⇒ E<k>, subsuming T: E.1 = E.
375 else if (type_ignoring_lweight_(r) == type_t::one)
376 res = rmul(l, possibly_implicit_lweight_(r));
378 // U_K: (<k>1).E ⇒ <k>E, subsuming T: 1.E = E.
379 else if (type_ignoring_lweight_(l) == type_t::one)
380 res = lmul(possibly_implicit_lweight_(l), r);
382 // (<k>E)(<h>F) => <kh>(EF).
383 else if (ids_.is_linear() && weightset()->is_commutative()
384 && (l->type() == type_t::lweight
385 || r->type() == type_t::lweight))
388 lw = possibly_implicit_lweight_(l),
389 rw = possibly_implicit_lweight_(r);
391 nl = unwrap_possible_lweight_(l),
392 nr = unwrap_possible_lweight_(r);
393 res = lmul(weightset()->mul(lw, rw),
397 // (E+F)G => EG + FG.
398 else if (ids_.is_distributive() && l->type() == type_t::sum)
401 // l is a sum, and r might be as well.
402 for (const auto& la: *down_pointer_cast<const sum_t>(l))
403 res = add(res, mul(la, r));
406 // E(F+G) => EF + EG.
407 else if (ids_.is_distributive() && r->type() == type_t::sum)
410 // r is a sum, l is not.
411 for (const auto& ra: *down_pointer_cast<const sum_t>(r))
412 res = add(res, mul(l, ra));
416 res = std::make_shared<prod_t>(gather_<type_t::prod>(l, r));
420 DEFINE::conjunction(const value_t& l, const value_t& r) const
423 value_t res = nullptr;
426 res = std::make_shared<conjunction_t>(l, r);
437 else if (is_universal(r))
441 else if (is_universal(l))
444 // <k>1&<h>1 => <kh>1.
445 else if (type_ignoring_lweight_(l) == type_t::one
446 && type_ignoring_lweight_(r) == type_t::one)
447 res = lmul(weightset()->mul(possibly_implicit_lweight_(l),
448 possibly_implicit_lweight_(r)),
451 // <k>a&<h>a => <kh>a. <k>a&<h>b => 0.
452 else if (type_ignoring_lweight_(l) == type_t::atom
453 && type_ignoring_lweight_(r) == type_t::atom)
456 down_pointer_cast<const atom_t>(unwrap_possible_lweight_(l))->value();
458 down_pointer_cast<const atom_t>(unwrap_possible_lweight_(r))->value();
459 if (labelset()->equal(lhs, rhs))
460 res = rmul(l, possibly_implicit_lweight_(r));
465 // <k>1&<h>a => 0, <k>a&<h>1 => 0.
466 else if ((type_ignoring_lweight_(l) == type_t::one
467 && type_ignoring_lweight_(r) == type_t::atom)
468 || (type_ignoring_lweight_(l) == type_t::atom
469 && type_ignoring_lweight_(r) == type_t::one))
473 res = std::make_shared<conjunction_t>(gather_<type_t::conjunction>(l, r));
477 DEFINE::ldiv(const value_t& l, const value_t& r) const
480 value_t res = nullptr;
483 res = std::make_shared<ldiv_t>(l, r);
486 else if (ids_ && is_zero(l))
487 res = complement(zero());
490 else if (ids_ && is_one(l))
494 else if (ids_ && is_zero(r))
498 res = std::make_shared<ldiv_t>(l, r);
502 DEFINE::rdiv(const value_t& l, const value_t& r) const
505 // l/r = (r{T} {\} l{T}){T}.
506 return transposition(ldiv(transposition(r), transposition(l)));
509 template <typename Context>
510 template <typename... Value>
511 auto expressionset_impl<Context>::tuple(Value&&... v) const
514 auto ts = as_tupleset();
515 auto t = ts.tuple(v...);
518 // If this is a tuple of labels, make it a (multitape) label.
519 // That allows algorithms such as standard, thompson, etc. to work
522 // Note that `\e|a` remains a tuple of expression on lal x lal,
523 // but it is turned into a (multitape) label on lan x lan.
524 else if (tuple_of_label<>::is_label(t))
525 return atom(tuple_of_label<>::as_label(t));
527 return std::make_shared<tuple_t>(std::forward<Value>(v)...);
530 DEFINE::infiltration(const value_t& l, const value_t& r) const
533 value_t res = nullptr;
536 res = std::make_shared<infiltration_t>(l, r);
539 else if (ids_ && is_zero(l))
543 else if (ids_ && is_zero(r))
547 else if (ids_ && is_one(l))
551 else if (ids_ && is_one(r))
556 std::make_shared<infiltration_t>(gather_<type_t::infiltration>(l, r));
560 DEFINE::shuffle(const value_t& l, const value_t& r) const
563 value_t res = nullptr;
566 res = std::make_shared<shuffle_t>(l, r);
569 else if (ids_ && is_zero(l))
573 else if (ids_ && is_zero(r))
577 else if (ids_ && is_one(l))
581 else if (ids_ && is_one(r))
585 res = std::make_shared<shuffle_t>(gather_<type_t::shuffle>(l, r));
593 DEFINE::power(const value_t& e, unsigned n) const
596 value_t res = nullptr;
597 // Given E the expression s.t. E{n} = (<k>a){n}.
608 else if (ids_ && is_zero(e))
611 // Case: a == \e or a == <w>\e.
612 else if (ids_ && type_ignoring_lweight_(e) == type_t::one)
614 weight_t w = possibly_implicit_lweight_(e);
615 res = lmul(weightset()->power(w, n), one());
618 // Lweight in linear commutative: (<k>E){n} => <k{n}>(E{n}).
619 else if (ids_.is_linear()
620 && weightset()->is_commutative()
621 && e->type() == type_t::lweight)
623 const auto& lw = down_pointer_cast<const lweight_t>(e);
624 res = lmul(weightset()->power(lw->weight(), n),
625 power(lw->sub(), n));
628 // Sums in series: we have to distribute ([ab]{2} = aa+ab+ba+bb).
629 else if (ids_.is_distributive() && e->type() == type_t::sum)
631 // FIXME: code duplication with weightset_mixin::power_.
633 for (unsigned i = 1; i < n; ++i)
637 // When associative, instead of repeated multiplication,
638 // immediately create n copies of E.
639 else if (ids_.is_associative())
640 res = std::make_shared<prod_t>(n, e);
642 // Default case: E{n} = ((..(EE)...)E.
645 // FIXME: code duplication with weightset_mixin::power_.
647 for (unsigned i = 1; i < n; ++i)
654 DEFINE::concat(const value_t& l, const value_t& r) const
657 // A static dispatch is needed, as the product of labels is not
658 // available if not LAW.
659 return concat_(l, r, typename is_law<Context>::type{});
662 // Concatenation when not LAW.
663 DEFINE::concat_(const value_t& l, const value_t& r, std::false_type) const
669 // Concatenation when LAW.
670 DEFINE::concat_(const value_t& l, const value_t& r, std::true_type) const
673 // concat((ab).<2>c, d.(ef)) = (ab).<2>(cd).(ef).
675 // Store (ab) in expression, then concat(<2>c, d) if c and d are
676 // atoms, otherwise <2>c then d, then (ef).
677 if ((type_ignoring_lweight_(l) == type_t::atom || l->type() == type_t::prod)
678 && (r->type() == type_t::atom || r->type() == type_t::prod))
682 gather_<type_t::prod>(ls, l);
685 gather_<type_t::prod>(rs, r);
687 // FIXME: we should perform that "if" with the one above, and
688 // enter this section only if we really are going to concat.
689 // This would avoid the "else" clause.
690 if (type_ignoring_lweight_(ls.back()) == type_t::atom
691 && rs.front()->type() == type_t::atom)
693 // Fetch weight and atom of the last lhs.
694 auto w = possibly_implicit_lweight_(ls.back());
696 = std::dynamic_pointer_cast<const atom_t>
697 (unwrap_possible_lweight_(ls.back()));
698 // Fetch atom of the first rhs.
699 auto rhs = std::dynamic_pointer_cast<const atom_t>(rs.front());
701 atom(labelset()->mul(lhs->value(), rhs->value())));
702 ls.insert(ls.end(), rs.begin() + 1, rs.end());
705 ls.insert(ls.end(), rs.begin(), rs.end());
709 return std::make_shared<prod_t>(std::move(ls));
712 // Handle all the trivial identities.
716 DEFINE::star(const value_t& e) const
719 value_t res = nullptr;
722 if (ids_ && is_zero(e))
727 res = std::make_shared<star_t>(e);
728 VCSN_REQUIRE(!ids_.is_distributive() || is_valid(*this, res),
729 "star: not starrable: ", to_string(self(), e));
735 DEFINE::complement(const value_t& e) const
738 value_t res = nullptr;
741 res = std::make_shared<complement_t>(e);
743 // The following identities make derived-term (<2>a)*{c} terminate.
744 // (<k>E){c} => E{c}.
745 else if (auto w = std::dynamic_pointer_cast<const lweight_t>(e))
746 res = complement(w->sub());
748 // (E<k>){c} => E{c}.
749 else if (auto w = std::dynamic_pointer_cast<const rweight_t>(e))
750 res = complement(w->sub());
752 // E{c}{c} => E if on B or F2.
754 // Indeed, (<2>a)*{c}{c} is actually denoting a*, not (<2>a)*.
755 else if (e->type() == type_t::complement
756 && std::is_same<weight_t, bool>{})
757 res = down_pointer_cast<const complement_t>(e)->sub();
760 res = std::make_shared<complement_t>(e);
765 DEFINE::transposition(const value_t& e) const
768 value_t res = nullptr;
771 res = std::make_shared<transposition_t>(e);
781 // a{T} => a, (abc){T} => cba.
782 else if (auto l = std::dynamic_pointer_cast<const atom_t>(e))
783 res = atom(labelset()->transpose(l->value()));
786 res = std::make_shared<transposition_t>(e);
794 DEFINE::lmul(const weight_t& w, const value_t& e) const
797 value_t res = nullptr;
800 res = std::make_shared<lweight_t>(w, e);
802 // <k>0 => 0, <1>E => E.
803 else if (is_zero(e) || weightset()->is_one(w))
807 else if (weightset()->is_zero(w))
810 // <k>(<h>E) => <kh>E.
811 else if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
812 res = lmul(weightset()->mul(w, lw->weight()), lw->sub());
814 // Distributive: <k>(E+F) => <k>E + <k>F.
815 else if (ids_.is_distributive() && e->type() == type_t::sum)
817 const auto& s = down_pointer_cast<const sum_t>(e);
818 // We can build the result faster by emplace_back'ing addends without
821 for (
const auto& a: *s)
822 addends.emplace_back(lmul(w, a));
823 res = std::make_shared<sum_t>(std::move(addends));
828 res = std::make_shared<lweight_t>(w, e);
839 res = std::make_shared<rweight_t>(w, e);
842 else if (ids_.is_linear() && weightset()->is_commutative())
846 else if (weightset()->is_zero(w))
850 else if (weightset()->is_one(w))
853 else if (e->is_leaf())
858 else if (
auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
859 res = lmul(lw->weight(), rmul(lw->sub(), w));
862 else if (
auto rw = std::dynamic_pointer_cast<const rweight_t>(e))
863 res = rmul(rw->sub(), weightset()->mul(rw->weight(), w));
867 res = std::make_shared<rweight_t>(w, e);
892 && is_zero(down_pointer_cast<const complement_t>(
v)->sub()));
898 return rat::size<self_t>(
v);
911 return less(unwrap_possible_lweight_(lhs),
912 unwrap_possible_lweight_(rhs));
918 return !
less(lhs, rhs) && !
less(rhs, lhs);
937 template <
typename Context>
938 template <
typename GenSet>
957 return lmul(weightset()->
conv(ws,
v),
one());
963 return lmul(weightset()->
conv(ws,
v),
one());
969 return lmul(weightset()->
conv(ws,
v),
one());
975 return lmul(weightset()->
conv(ws,
v),
one());
978 template <
typename Context>
979 template <
typename Ctx2>
998 const auto& res = dynres->template as<self_t>();
999 return res.expression();
1018 template <
typename Context>
1019 template <
typename... Args>
1025 return letter_class_<labelset_t>(std::forward<Args>(args)...,
1026 std::is_same<labelset_t, vcsn::oneset>{});
1029 template <
typename Context>
1030 template <
typename LabelSet_>
1035 typename LabelSet_::letter_t>> ccs,
1037 std::false_type)
const
1040 using boost::range::find;
1042 const auto& ls = *labelset();
1043 auto gens = ls.generators();
1050 for (
const auto& cc: ccs)
1052 auto i = find(gens, cc.first);
1053 auto end = std::find(i, std::end(gens), cc.second);
1055 self(),
": invalid letter interval: ",
1056 to_string(*labelset(), ls.value(std::get<0>(cc))),
1058 to_string(*labelset(), ls.value(std::get<1>(cc))));
1059 for (++end; i != end; ++i)
1060 res = add(res,
atom(ls.value(*i)));
1063 else if (ccs.empty())
1065 res = add(res,
atom(ls.value(l)));
1070 std::set<typename LabelSet_::letter_t> accepted;
1071 for (
const auto& cc: ccs)
1073 auto i = find(gens, cc.first);
1074 auto end = std::find(i, std::end(gens), cc.second);
1076 "invalid letter interval: ",
1077 to_string(*labelset(), ls.value(std::get<0>(cc))),
1079 to_string(*labelset(), ls.value(std::get<1>(cc))));
1080 for (++end; i != end; ++i)
1081 accepted.emplace(*i);
1084 if (!
has(accepted, c))
1085 res = add(res,
atom(ls.value(c)));
1088 "invalid empty letter class");
1092 template <
typename Context>
1093 template <
typename LabelSet_,
typename... Args>
1097 std::true_type) const
std::ostream & print(const Aut &aut, std::ostream &out, const std::string &fmt)
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
typename weightset_t::value_t weight_t
const weightset_ptr & weightset() const
Accessor to the weightset.
A functor to check whether one rational expression is (strictly) less than another one...
An expressionset can implement several different sets of identities on expressions.
auto letter_class_(const Args &&...chars, std::true_type) const -> value_t
If labelset is oneset.
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
auto letter_class(Args &&...chars) const -> value_t
An expression matching one character amongst chars.
expressionset_impl(const context_t &ctx, identities_t ids={})
Constructor.
Aut transpose(const transpose_automaton< Aut > &aut)
constant< type_t::one, Context > one
context make_context(const std::string &name)
Build a context from its name.
static dyn::context ctx(const driver &d)
Get the context of the driver.
expression read_expression(const context &ctx, rat::identities ids, std::istream &is, const std::string &format="default")
Read an expression from a stream.
An input/output format for valuesets.
typename node_t::value_t value_t
An expression (a shared pointer to a tree).
typename node_t::values_t values_t
A list (vector) of expressions.
static identities ids(const driver &d)
Get the identities of the driver.
const identities_t ids_
The set of rewriting rules to apply.
OutExpSet::value_t copy(const InExpSet &in_rs, const OutExpSet &out_rs, const typename InExpSet::value_t &v)
Copy/convert a rational expression.
printer< ExpSet > make_printer(const ExpSet &rs, std::ostream &out)
A visitor to create a transposed expression,.
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.
auto conv(const letterset< GenSet > &ls, typename letterset< GenSet >::value_t v) const -> value_t
std::istringstream is
The input stream: the specification to translate.
constant< type_t::zero, Context > zero
Provide a variadic mul on top of a binary mul(), and one().
Print as a parsable type string.
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
char eat(std::istream &is, char c)
Check lookahead character and advance.
Implementation of labels are letters.
#define VCSN_REQUIRE(Cond,...)
A macro similar to require.
std::string to_string(identities i)
Wrapper around operator<<.
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
bool is_distributive() const
Whether distributive.
rat::identities identities(const expression &exp)
Bridge.
Request the set implementation (bool weights).
std::shared_ptr< const detail::context_base > context
A dyn::context.
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)