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() << ')
';
106 assert(!"print: expression: invalid format: rat");
112 DEFINE::open(bool o) const
115 return this->labelset()->open(o);
118 DEFINE::context() const -> const context_t&
123 DEFINE::identities() const -> identities_t
128 DEFINE::labelset() const -> const labelset_ptr&
130 return ctx_.labelset();
133 DEFINE::weightset() const -> const weightset_ptr&
135 return ctx_.weightset();
138 DEFINE::atom(const label_t& v)
141 if (labelset_t::is_one(v))
144 return std::make_shared<atom_t>(v);
150 return std::make_shared<zero_t>();
156 return std::make_shared<one_t>();
159 template <typename Context>
160 template <typename expressionset_impl<Context>::type_t Type>
163 expressionset_impl<Context>::gather_(values_t& res, const value_t& v) const
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));
173 template <typename Context>
174 template <typename expressionset_impl<Context>::type_t Type>
177 expressionset_impl<Context>::gather_(const value_t& l, const value_t& r) const
181 if (ids_.is_associative())
183 gather_<Type>(res, l);
184 gather_<Type>(res, r);
194 DEFINE::add(const value_t& l, const value_t& r) const
197 value_t res = nullptr;
200 res = std::make_shared<sum_t>(l, r);
211 else if (ids_.is_linear())
212 res = add_linear_(l, r);
215 res = std::make_shared<sum_t>(gather_<type_t::sum>(l, r));
219 DEFINE::add_linear_(const sum_t& s, const value_t& r) const
222 auto res = values_t{};
223 res.reserve(s.size() + 1);
225 // Copy the strictly smaller part.
226 auto i = boost::lower_bound(s, r, less_linear);
227 res.insert(end(res), begin(s), i);
233 if (less_linear(r, *i))
237 auto w = weightset()->add(possibly_implicit_lweight_(*i),
238 possibly_implicit_lweight_(r));
239 if (!weightset()->is_zero(w))
241 auto l = unwrap_possible_lweight_(*i);
242 res.emplace_back(lmul(w, l));
246 res.insert(end(res), i, end(s));
249 return add_(std::move(res));
252 DEFINE::add_(values_t&& vs) const
257 else if (vs.size() == 1)
260 return std::make_shared<sum_t>(std::move(vs));
263 DEFINE::add_linear_(const sum_t& s1, const sum_t& s2) const
266 auto res = values_t{};
267 res.reserve(s1.size() + s2.size());
268 // Merge two increasing lists. Add weights of equal labels.
271 auto i1 = begin(s1), end1 = end(s1);
272 auto i2 = begin(s2), end2 = end(s2);
277 res.insert(res.end(), i2, end2);
282 res.insert(res.end(), i1, end1);
285 else if (less_linear(*i1, *i2))
286 res.emplace_back(*i1++);
287 else if (less_linear(*i2, *i1))
288 res.emplace_back(*i2++);
291 auto w = weightset()->add(possibly_implicit_lweight_(*i1),
292 possibly_implicit_lweight_(*i2));
293 if (!weightset()->is_zero(w))
295 auto l = unwrap_possible_lweight_(*i1);
296 res.emplace_back(lmul(w, l));
302 return add_(std::move(res));
305 DEFINE::add_linear_(const value_t& l, const value_t& r) const
310 value_t res = nullptr;
311 if (auto ls = std::dynamic_pointer_cast<const sum_t>(l))
313 if (auto rs = std::dynamic_pointer_cast<const sum_t>(r))
314 res = add_linear_(*ls, *rs);
316 res = add_linear_(*ls, r);
318 else if (auto rs = std::dynamic_pointer_cast<const sum_t>(r))
319 res = add_linear_(*rs, l);
320 else if (less_linear(l, r))
321 res = std::make_shared<sum_t>(l, r);
322 else if (less_linear(r, l))
323 res = std::make_shared<sum_t>(r, l);
326 auto w = weightset()->add(possibly_implicit_lweight_(l),
327 possibly_implicit_lweight_(r));
328 res = lmul(w, unwrap_possible_lweight_(l));
333 DEFINE::type_ignoring_lweight_(const value_t& e)
336 return unwrap_possible_lweight_(e)->type();
339 DEFINE::possibly_implicit_lweight_(const value_t& e)
342 if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
345 return weightset_t::one();
348 DEFINE::unwrap_possible_lweight_(const value_t& e)
351 if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
357 DEFINE::mul(const value_t& l, const value_t& r) const
360 value_t res = nullptr;
363 res = std::make_shared<prod_t>(l, r);
373 // U_K: E.(<k>1) ⇒ E<k>, subsuming T: E.1 = E.
374 else if (type_ignoring_lweight_(r) == type_t::one)
375 res = rmul(l, possibly_implicit_lweight_(r));
377 // U_K: (<k>1).E ⇒ <k>E, subsuming T: 1.E = E.
378 else if (type_ignoring_lweight_(l) == type_t::one)
379 res = lmul(possibly_implicit_lweight_(l), r);
381 // (<k>E)(<h>F) => <kh>(EF).
382 else if (ids_.is_linear() && weightset()->is_commutative()
383 && (l->type() == type_t::lweight
384 || r->type() == type_t::lweight))
387 lw = possibly_implicit_lweight_(l),
388 rw = possibly_implicit_lweight_(r);
390 nl = unwrap_possible_lweight_(l),
391 nr = unwrap_possible_lweight_(r);
392 res = lmul(weightset()->mul(lw, rw),
396 // (E+F)G => EG + FG.
397 else if (ids_.is_distributive() && l->type() == type_t::sum)
400 // l is a sum, and r might be as well.
401 for (const auto& la: *down_pointer_cast<const sum_t>(l))
402 res = add(res, mul(la, r));
405 // E(F+G) => EF + EG.
406 else if (ids_.is_distributive() && r->type() == type_t::sum)
409 // r is a sum, l is not.
410 for (const auto& ra: *down_pointer_cast<const sum_t>(r))
411 res = add(res, mul(l, ra));
415 res = std::make_shared<prod_t>(gather_<type_t::prod>(l, r));
419 DEFINE::conjunction(const value_t& l, const value_t& r) const
422 value_t res = nullptr;
425 res = std::make_shared<conjunction_t>(l, r);
436 else if (is_universal(r))
440 else if (is_universal(l))
443 // <k>1&<h>1 => <kh>1.
444 else if (type_ignoring_lweight_(l) == type_t::one
445 && type_ignoring_lweight_(r) == type_t::one)
446 res = lmul(weightset()->mul(possibly_implicit_lweight_(l),
447 possibly_implicit_lweight_(r)),
450 // <k>a&<h>a => <kh>a. <k>a&<h>b => 0.
451 else if (type_ignoring_lweight_(l) == type_t::atom
452 && type_ignoring_lweight_(r) == type_t::atom)
455 down_pointer_cast<const atom_t>(unwrap_possible_lweight_(l))->value();
457 down_pointer_cast<const atom_t>(unwrap_possible_lweight_(r))->value();
458 if (labelset()->equal(lhs, rhs))
459 res = rmul(l, possibly_implicit_lweight_(r));
464 // <k>1&<h>a => 0, <k>a&<h>1 => 0.
465 else if ((type_ignoring_lweight_(l) == type_t::one
466 && type_ignoring_lweight_(r) == type_t::atom)
467 || (type_ignoring_lweight_(l) == type_t::atom
468 && type_ignoring_lweight_(r) == type_t::one))
472 res = std::make_shared<conjunction_t>(gather_<type_t::conjunction>(l, r));
476 DEFINE::ldiv(const value_t& l, const value_t& r) const
479 value_t res = nullptr;
482 res = std::make_shared<ldiv_t>(l, r);
485 else if (ids_ && is_zero(l))
486 res = complement(zero());
489 else if (ids_ && is_one(l))
493 else if (ids_ && is_zero(r))
497 res = std::make_shared<ldiv_t>(l, r);
501 DEFINE::rdiv(const value_t& l, const value_t& r) const
504 // l/r = (r{T} {\} l{T}){T}.
505 return transposition(ldiv(transposition(r), transposition(l)));
508 template <typename Context>
509 template <typename... Value>
510 auto expressionset_impl<Context>::tuple(Value&&... v) const
513 auto ts = as_tupleset();
514 auto t = ts.tuple(v...);
517 // If this is a tuple of labels, make it a (multitape) label.
518 // That allows algorithms such as standard, thompson, etc. to work
521 // Note that `\e|a` remains a tuple of expression on lal x lal,
522 // but it is turned into a (multitape) label on lan x lan.
523 else if (tuple_of_label<>::is_label(t))
524 return atom(tuple_of_label<>::as_label(t));
526 return std::make_shared<tuple_t>(std::forward<Value>(v)...);
529 DEFINE::infiltration(const value_t& l, const value_t& r) const
532 value_t res = nullptr;
535 res = std::make_shared<infiltration_t>(l, r);
538 else if (ids_ && is_zero(l))
542 else if (ids_ && is_zero(r))
546 else if (ids_ && is_one(l))
550 else if (ids_ && is_one(r))
555 std::make_shared<infiltration_t>(gather_<type_t::infiltration>(l, r));
559 DEFINE::shuffle(const value_t& l, const value_t& r) const
562 value_t res = nullptr;
565 res = std::make_shared<shuffle_t>(l, r);
568 else if (ids_ && is_zero(l))
572 else if (ids_ && is_zero(r))
576 else if (ids_ && is_one(l))
580 else if (ids_ && is_one(r))
584 res = std::make_shared<shuffle_t>(gather_<type_t::shuffle>(l, r));
592 DEFINE::power(const value_t& e, unsigned n) const
595 value_t res = nullptr;
596 // Given E the expression s.t. E{n} = (<k>a){n}.
607 else if (ids_ && is_zero(e))
610 // Case: a == \e or a == <w>\e.
611 else if (ids_ && type_ignoring_lweight_(e) == type_t::one)
613 weight_t w = possibly_implicit_lweight_(e);
614 res = lmul(weightset()->power(w, n), one());
617 // Lweight in linear commutative: (<k>E){n} => <k{n}>(E{n}).
618 else if (ids_.is_linear()
619 && weightset()->is_commutative()
620 && e->type() == type_t::lweight)
622 const auto& lw = down_pointer_cast<const lweight_t>(e);
623 res = lmul(weightset()->power(lw->weight(), n),
624 power(lw->sub(), n));
627 // Sums in series: we have to distribute ([ab]{2} = aa+ab+ba+bb).
628 else if (ids_.is_distributive() && e->type() == type_t::sum)
630 // FIXME: code duplication with weightset_mixin::power_.
632 for (unsigned i = 1; i < n; ++i)
636 // When associative, instead of repeated multiplication,
637 // immediately create n copies of E.
638 else if (ids_.is_associative())
639 res = std::make_shared<prod_t>(n, e);
641 // Default case: E{n} = ((..(EE)...)E.
644 // FIXME: code duplication with weightset_mixin::power_.
646 for (unsigned i = 1; i < n; ++i)
653 DEFINE::concat(const value_t& l, const value_t& r) const
656 // A static dispatch is needed, as the product of labels is not
657 // available if not LAW.
658 return concat_(l, r, typename is_law<Context>::type{});
661 // Concatenation when not LAW.
662 DEFINE::concat_(const value_t& l, const value_t& r, std::false_type) const
668 // Concatenation when LAW.
669 DEFINE::concat_(const value_t& l, const value_t& r, std::true_type) const
672 // concat((ab).<2>c, d.(ef)) = (ab).<2>(cd).(ef).
674 // Store (ab) in expression, then concat(<2>c, d) if c and d are
675 // atoms, otherwise <2>c then d, then (ef).
676 if ((type_ignoring_lweight_(l) == type_t::atom || l->type() == type_t::prod)
677 && (r->type() == type_t::atom || r->type() == type_t::prod))
681 gather_<type_t::prod>(ls, l);
684 gather_<type_t::prod>(rs, r);
686 // FIXME: we should perform that "if" with the one above, and
687 // enter this section only if we really are going to concat.
688 // This would avoid the "else" clause.
689 if (type_ignoring_lweight_(ls.back()) == type_t::atom
690 && rs.front()->type() == type_t::atom)
692 // Fetch weight and atom of the last lhs.
693 auto w = possibly_implicit_lweight_(ls.back());
695 = std::dynamic_pointer_cast<const atom_t>
696 (unwrap_possible_lweight_(ls.back()));
697 // Fetch atom of the first rhs.
698 auto rhs = std::dynamic_pointer_cast<const atom_t>(rs.front());
700 atom(labelset()->mul(lhs->value(), rhs->value())));
701 ls.insert(ls.end(), rs.begin() + 1, rs.end());
704 ls.insert(ls.end(), rs.begin(), rs.end());
708 return std::make_shared<prod_t>(std::move(ls));
711 // Handle all the trivial identities.
715 DEFINE::star(const value_t& e) const
718 value_t res = nullptr;
721 if (ids_ && is_zero(e))
726 res = std::make_shared<star_t>(e);
727 VCSN_REQUIRE(!ids_.is_distributive() || is_valid(*this, res),
728 "star: not starrable: ", to_string(self(), e));
734 DEFINE::complement(const value_t& e) const
737 value_t res = nullptr;
740 res = std::make_shared<complement_t>(e);
742 // The following identities make derived-term (<2>a)*{c} terminate.
743 // (<k>E){c} => E{c}.
744 else if (auto w = std::dynamic_pointer_cast<const lweight_t>(e))
745 res = complement(w->sub());
747 // (E<k>){c} => E{c}.
748 else if (auto w = std::dynamic_pointer_cast<const rweight_t>(e))
749 res = complement(w->sub());
751 // E{c}{c} => E if on B or F2.
753 // Indeed, (<2>a)*{c}{c} is actually denoting a*, not (<2>a)*.
754 else if (e->type() == type_t::complement
755 && std::is_same<weight_t, bool>{})
756 res = down_pointer_cast<const complement_t>(e)->sub();
759 res = std::make_shared<complement_t>(e);
764 DEFINE::transposition(const value_t& e) const
767 value_t res = nullptr;
770 res = std::make_shared<transposition_t>(e);
780 // a{T} => a, (abc){T} => cba.
781 else if (auto l = std::dynamic_pointer_cast<const atom_t>(e))
782 res = atom(labelset()->transpose(l->value()));
785 res = std::make_shared<transposition_t>(e);
793 DEFINE::lmul(const weight_t& w, const value_t& e) const
796 value_t res = nullptr;
799 res = std::make_shared<lweight_t>(w, e);
801 // <k>0 => 0, <1>E => E.
802 else if (is_zero(e) || weightset()->is_one(w))
806 else if (weightset()->is_zero(w))
809 // <k>(<h>E) => <kh>E.
810 else if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
811 res = lmul(weightset()->mul(w, lw->weight()), lw->sub());
813 // Distributive: <k>(E+F) => <k>E + <k>F.
814 else if (ids_.is_distributive() && e->type() == type_t::sum)
816 const auto& s = down_pointer_cast<const sum_t>(e);
817 // We can build the result faster by emplace_back'ing addends without
820 for (
const auto& a: *s)
821 addends.emplace_back(lmul(w, a));
822 res = std::make_shared<sum_t>(std::move(addends));
827 res = std::make_shared<lweight_t>(w, e);
838 res = std::make_shared<rweight_t>(w, e);
841 else if (ids_.is_linear() && weightset()->is_commutative())
845 else if (weightset()->is_zero(w))
849 else if (weightset()->is_one(w))
852 else if (e->is_leaf())
857 else if (
auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
858 res = lmul(lw->weight(), rmul(lw->sub(), w));
861 else if (
auto rw = std::dynamic_pointer_cast<const rweight_t>(e))
862 res = rmul(rw->sub(), weightset()->mul(rw->weight(), w));
866 res = std::make_shared<rweight_t>(w, e);
891 && is_zero(down_pointer_cast<const complement_t>(
v)->sub()));
897 return rat::size<self_t>(
v);
910 return less(unwrap_possible_lweight_(lhs),
911 unwrap_possible_lweight_(rhs));
917 return !
less(lhs, rhs) && !
less(rhs, lhs);
936 template <
typename Context>
937 template <
typename GenSet>
956 return lmul(weightset()->
conv(ws,
v),
one());
962 return lmul(weightset()->
conv(ws,
v),
one());
968 return lmul(weightset()->
conv(ws,
v),
one());
974 return lmul(weightset()->
conv(ws,
v),
one());
977 template <
typename Context>
978 template <
typename Ctx2>
997 const auto& res = dynres->template as<self_t>();
998 return res.expression();
1017 template <
typename Context>
1018 template <
typename... Args>
1024 return letter_class_<labelset_t>(std::forward<Args>(args)...,
1025 std::is_same<labelset_t, vcsn::oneset>{});
1028 template <
typename Context>
1029 template <
typename LabelSet_>
1034 typename LabelSet_::letter_t>> ccs,
1036 std::false_type)
const
1039 using boost::range::find;
1041 const auto& ls = *labelset();
1042 auto gens = ls.generators();
1049 for (
const auto& cc: ccs)
1051 auto i = find(gens, cc.first);
1052 auto end = std::find(i, std::end(gens), cc.second);
1054 self(),
": invalid letter interval: ",
1055 to_string(*labelset(), ls.value(std::get<0>(cc))),
1057 to_string(*labelset(), ls.value(std::get<1>(cc))));
1058 for (++end; i != end; ++i)
1059 res = add(res,
atom(ls.value(*i)));
1062 else if (ccs.empty())
1064 res = add(res,
atom(ls.value(l)));
1069 std::set<typename LabelSet_::letter_t> accepted;
1070 for (
const auto& cc: ccs)
1072 auto i = find(gens, cc.first);
1073 auto end = std::find(i, std::end(gens), cc.second);
1075 "invalid letter interval: ",
1076 to_string(*labelset(), ls.value(std::get<0>(cc))),
1078 to_string(*labelset(), ls.value(std::get<1>(cc))));
1079 for (++end; i != end; ++i)
1080 accepted.emplace(*i);
1083 if (!
has(accepted, c))
1084 res = add(res,
atom(ls.value(c)));
1087 "invalid empty letter class");
1091 template <
typename Context>
1092 template <
typename LabelSet_,
typename... Args>
1096 std::true_type) const
std::istringstream is
The input stream: the specification to translate.
printer< ExpSet > make_printer(const ExpSet &rs, std::ostream &out)
constant< type_t::one, Context > one
Provide a variadic mul on top of a binary mul(), and one().
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
typename node_t::value_t value_t
An expression (a shared pointer to a tree).
rat::identities identities(const expression &exp)
Bridge.
auto conv(const letterset< GenSet > &ls, typename letterset< GenSet >::value_t v) const -> value_t
std::ostream & print(const Aut &aut, std::ostream &out, const std::string &fmt)
expression read_expression(const context &ctx, rat::identities ids, std::istream &is, const std::string &format="default")
Read an expression from a stream.
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
typename weightset_t::value_t weight_t
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.
Print as a parsable type string.
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
std::shared_ptr< const detail::context_base > context
A dyn::context.
Implementation of labels are letters.
#define VCSN_REQUIRE(Cond,...)
A macro similar to require.
auto letter_class_(const Args &&...chars, std::true_type) const -> value_t
If labelset is oneset.
typename node_t::values_t values_t
A list (vector) of expressions.
A functor to check whether one rational expression is (strictly) less than another one...
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
expressionset_impl(const context_t &ctx, identities_t ids={})
Constructor.
Request the set implementation (bool weights).
std::string to_string(identities i)
Wrapper around operator<<.
context make_context(const std::string &name)
Build a context from its name.
OutExpSet::value_t copy(const InExpSet &in_rs, const OutExpSet &out_rs, const typename InExpSet::value_t &v)
Copy/convert a rational expression.
char eat(std::istream &is, char c)
Check lookahead character and advance.
const weightset_ptr & weightset() const
Accessor to the weightset.
static identities ids(const driver &d)
Get the identities of the driver.
const identities_t ids_
The set of rewriting rules to apply.
static dyn::context ctx(const driver &d)
Get the context of the driver.
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
auto letter_class(Args &&...chars) const -> value_t
An expression matching one character amongst chars.
A visitor to create a transposed expression,.
bool is_distributive() const
Whether distributive.
Aut transpose(const transpose_automaton< Aut > &aut)
An expressionset can implement several different sets of identities on expressions.
An input/output format for valuesets.
constant< type_t::zero, Context > zero