5 #include <boost/range/algorithm/find.hpp>
6 #include <boost/range/algorithm/lower_bound.hpp>
8 #include <vcsn/algos/fwd.hh>
29 template <
typename Context>
36 "series (currently) requires a commutative weightset product");
40 template <typename Context> \
43 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
77 case identities_t::trivial:
80 case identities_t::distributive:
100 o << "expressionset<";
101 context().print_set(o, fmt);
103 if (identities() != vcsn::rat::identities{})
104 o << '(
' << identities() << ')
';
108 raise("invalid format: ", fmt);
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);
203 else if (l->type() == type_t::zero)
207 else if (r->type() == type_t::zero)
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);
366 else if (l->type() == type_t::zero)
370 else if (r->type() == type_t::zero)
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);
428 else if (l->type() == type_t::zero)
432 else if (r->type() == type_t::zero)
435 // <k>1&<h>1 => <kh>1.
436 else if (type_ignoring_lweight_(l) == type_t::one
437 && type_ignoring_lweight_(r) == type_t::one)
438 res = lmul(weightset()->mul(possibly_implicit_lweight_(l),
439 possibly_implicit_lweight_(r)),
442 // <k>a&<h>a => <kh>a. <k>a&<h>b => 0.
443 else if (type_ignoring_lweight_(l) == type_t::atom
444 && type_ignoring_lweight_(r) == type_t::atom)
447 down_pointer_cast<const atom_t>(unwrap_possible_lweight_(l))->value();
449 down_pointer_cast<const atom_t>(unwrap_possible_lweight_(r))->value();
450 if (labelset()->equal(lhs, rhs))
451 res = rmul(l, possibly_implicit_lweight_(r));
456 // <k>1&<h>a => 0, <k>a&<h>1 => 0.
457 else if ((type_ignoring_lweight_(l) == type_t::one
458 && type_ignoring_lweight_(r) == type_t::atom)
459 || (type_ignoring_lweight_(l) == type_t::atom
460 && type_ignoring_lweight_(r) == type_t::one))
464 res = std::make_shared<conjunction_t>(gather_<type_t::conjunction>(l, r));
468 DEFINE::ldiv(const value_t& l, const value_t& r) const
471 value_t res = nullptr;
474 res = std::make_shared<ldiv_t>(l, r);
477 else if (ids_ && l->type() == type_t::zero)
478 res = complement(zero());
481 else if (ids_ && l->type() == type_t::one)
485 else if (ids_ && r->type() == type_t::zero)
489 res = std::make_shared<ldiv_t>(l, r);
493 DEFINE::rdiv(const value_t& l, const value_t& r) const
496 // l/r = (r{T} {\} l{T}){T}.
497 return transposition(ldiv(transposition(r), transposition(l)));
500 template <typename Context>
501 template <typename... Value>
502 auto expressionset_impl<Context>::tuple(Value&&... v) const
505 auto ts = as_tupleset();
506 auto t = ts.tuple(v...);
509 // If this is a tuple of labels, make it a (multitape) label.
510 // That allows algorithms such as standard, thompson, etc. to work
513 // Note that `\e|a` remains a tuple of expression on lal x lal,
514 // but it is turned into a (multitape) label on lan x lan.
515 else if (tuple_of_label<>::is_label(t))
516 return atom(tuple_of_label<>::as_label(t));
518 return std::make_shared<tuple_t>(std::forward<Value>(v)...);
521 DEFINE::infiltration(const value_t& l, const value_t& r) const
524 value_t res = nullptr;
527 res = std::make_shared<infiltration_t>(l, r);
530 else if (ids_ && l->type() == type_t::zero)
534 else if (ids_ && r->type() == type_t::zero)
538 else if (ids_ && l->type() == type_t::one)
542 else if (ids_ && r->type() == type_t::one)
547 std::make_shared<infiltration_t>(gather_<type_t::infiltration>(l, r));
551 DEFINE::shuffle(const value_t& l, const value_t& r) const
554 value_t res = nullptr;
557 res = std::make_shared<shuffle_t>(l, r);
560 else if (ids_ && l->type() == type_t::zero)
564 else if (ids_ && r->type() == type_t::zero)
568 else if (ids_ && l->type() == type_t::one)
572 else if (ids_ && r->type() == type_t::one)
576 res = std::make_shared<shuffle_t>(gather_<type_t::shuffle>(l, r));
584 DEFINE::power(const value_t& e, unsigned n) const
587 value_t res = nullptr;
588 // Given E the expression s.t. E{n} = (<k>a){n}.
599 else if (ids_ && e->type() == type_t::zero)
602 // Case: a == \e or a == <w>\e.
603 else if (ids_ && type_ignoring_lweight_(e) == type_t::one)
605 weight_t w = possibly_implicit_lweight_(e);
606 res = lmul(weightset()->power(w, n), one());
609 // Lweight in linear commutative: (<k>E){n} => <k{n}>(E{n}).
610 else if (ids_.is_linear()
611 && weightset()->is_commutative()
612 && e->type() == type_t::lweight)
614 const auto& lw = down_pointer_cast<const lweight_t>(e);
615 res = lmul(weightset()->power(lw->weight(), n),
616 power(lw->sub(), n));
619 // Sums in series: we have to distribute ([ab]{2} = aa+ab+ba+bb).
620 else if (ids_.is_distributive() && e->type() == type_t::sum)
622 // FIXME: code duplication with weightset_mixin::power_.
624 for (unsigned i = 1; i < n; ++i)
628 // When associative, instead of repeated multiplication,
629 // immediately create n copies of E.
630 else if (ids_.is_associative())
631 res = std::make_shared<prod_t>(n, e);
633 // Default case: E{n} = ((..(EE)...)E.
636 // FIXME: code duplication with weightset_mixin::power_.
638 for (unsigned i = 1; i < n; ++i)
645 DEFINE::concat(const value_t& l, const value_t& r) const
648 // A static dispatch is needed, as the product of labels is not
649 // available if not LAW.
650 return concat_(l, r, typename is_law<Context>::type{});
653 // Concatenation when not LAW.
654 DEFINE::concat_(const value_t& l, const value_t& r, std::false_type) const
660 // Concatenation when LAW.
661 DEFINE::concat_(const value_t& l, const value_t& r, std::true_type) const
664 // concat((ab).<2>c, d.(ef)) = (ab).<2>(cd).(ef).
666 // Store (ab) in expression, then concat(<2>c, d) if c and d are
667 // atoms, otherwise <2>c then d, then (ef).
668 if ((type_ignoring_lweight_(l) == type_t::atom || l->type() == type_t::prod)
669 && (r->type() == type_t::atom || r->type() == type_t::prod))
673 gather_<type_t::prod>(ls, l);
676 gather_<type_t::prod>(rs, r);
678 // FIXME: we should perform that "if" with the one above, and
679 // enter this section only if we really are going to concat.
680 // This would avoid the "else" clause.
681 if (type_ignoring_lweight_(ls.back()) == type_t::atom
682 && rs.front()->type() == type_t::atom)
684 // Fetch weight and atom of the last lhs.
685 auto w = possibly_implicit_lweight_(ls.back());
687 = std::dynamic_pointer_cast<const atom_t>
688 (unwrap_possible_lweight_(ls.back()));
689 // Fetch atom of the first rhs.
690 auto rhs = std::dynamic_pointer_cast<const atom_t>(rs.front());
692 atom(labelset()->mul(lhs->value(), rhs->value())));
693 ls.insert(ls.end(), rs.begin() + 1, rs.end());
696 ls.insert(ls.end(), rs.begin(), rs.end());
700 return std::make_shared<prod_t>(std::move(ls));
703 // Handle all the trivial identities.
707 DEFINE::star(const value_t& e) const
710 value_t res = nullptr;
713 if (ids_ && e->type() == type_t::zero)
718 res = std::make_shared<star_t>(e);
719 require(!ids_.is_distributive() || is_valid(*this, res),
720 "star: not starrable: ", to_string(self(), e));
726 DEFINE::complement(const value_t& e) const
729 value_t res = nullptr;
732 res = std::make_shared<complement_t>(e);
734 // The following identities make derived-term (<2>a)*{c} terminate.
735 // (<k>E){c} => E{c}.
736 else if (auto w = std::dynamic_pointer_cast<const lweight_t>(e))
737 res = complement(w->sub());
739 // (E<k>){c} => E{c}.
740 else if (auto w = std::dynamic_pointer_cast<const rweight_t>(e))
741 res = complement(w->sub());
744 res = std::make_shared<complement_t>(e);
749 DEFINE::transposition(const value_t& e) const
752 value_t res = nullptr;
755 res = std::make_shared<transposition_t>(e);
758 else if (e->type() == type_t::zero)
762 else if (e->type() == type_t::one)
765 // a{T} => a, (abc){T} => cba.
766 else if (auto l = std::dynamic_pointer_cast<const atom_t>(e))
767 res = atom(labelset()->transpose(l->value()));
770 res = std::make_shared<transposition_t>(e);
778 DEFINE::lmul(const weight_t& w, const value_t& e) const
781 value_t res = nullptr;
784 res = std::make_shared<lweight_t>(w, e);
786 // <k>0 => 0, <1>E => E.
787 else if (e->type() == type_t::zero || weightset()->is_one(w))
791 else if (weightset()->is_zero(w))
794 // <k>(<h>E) => <kh>E.
795 else if (auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
796 res = lmul(weightset()->mul(w, lw->weight()), lw->sub());
798 // Distributive: <k>(E+F) => <k>E + <k>F.
799 else if (ids_.is_distributive() && e->type() == type_t::sum)
801 const auto& s = down_pointer_cast<const sum_t>(e);
802 // We can build the result faster by emplace_back'ing addends without
805 for (
const auto& a: *s)
806 addends.emplace_back(lmul(w, a));
807 res = std::make_shared<sum_t>(std::move(addends));
812 res = std::make_shared<lweight_t>(w, e);
823 res = std::make_shared<rweight_t>(w, e);
826 else if (ids_.is_linear() && weightset()->is_commutative())
830 else if (weightset()->is_zero(w))
834 else if (weightset()->is_one(w))
837 else if (e->is_leaf())
842 else if (
auto lw = std::dynamic_pointer_cast<const lweight_t>(e))
843 res = lmul(lw->weight(), rmul(lw->sub(), w));
846 else if (
auto rw = std::dynamic_pointer_cast<const rweight_t>(e))
847 res = rmul(rw->sub(), weightset()->mul(rw->weight(), w));
851 res = std::make_shared<rweight_t>(w, e);
875 return rat::size<self_t>(
v);
888 return less(unwrap_possible_lweight_(lhs),
889 unwrap_possible_lweight_(rhs));
895 return !
less(lhs, rhs) && !
less(rhs, lhs);
914 template <
typename Context>
915 template <
typename GenSet>
934 return lmul(weightset()->
conv(ws,
v),
one());
940 return lmul(weightset()->
conv(ws,
v),
one());
946 return lmul(weightset()->
conv(ws,
v),
one());
952 return lmul(weightset()->
conv(ws,
v),
one());
955 template <
typename Context>
956 template <
typename Ctx2>
975 const auto& res = dynres->template as<self_t>();
976 return res.expression();
995 template <
typename Context>
996 template <
typename... Args>
1002 return letter_class_<labelset_t>(std::forward<Args>(args)...,
1003 std::is_same<labelset_t, vcsn::oneset>{});
1006 template <
typename Context>
1007 template <
typename LabelSet_>
1012 typename LabelSet_::letter_t>> ccs,
1014 std::false_type)
const
1017 using boost::range::find;
1019 auto gens = labelset()->genset();
1026 for (
const auto& cc: ccs)
1028 auto i = find(gens, cc.first);
1029 auto end = std::find(i, std::end(gens), cc.second);
1030 require(end != std::end(gens),
1031 self(),
": invalid letter interval: ",
1032 to_string(*labelset(), labelset()->value(std::get<0>(cc))),
1034 to_string(*labelset(), labelset()->value(std::get<1>(cc))));
1035 for (++end; i != end; ++i)
1036 res = add(res,
atom(labelset()->value(*i)));
1039 else if (ccs.empty())
1041 res = add(res,
atom(labelset()->value(l)));
1046 std::set<typename LabelSet_::letter_t> accepted;
1047 for (
const auto& cc: ccs)
1049 auto i = find(gens, cc.first);
1050 auto end = std::find(i, std::end(gens), cc.second);
1051 require(end != std::end(gens),
1052 "invalid letter interval: ",
1053 to_string(*labelset(), labelset()->value(std::get<0>(cc))),
1055 to_string(*labelset(), labelset()->value(std::get<1>(cc))));
1056 for (++end; i != end; ++i)
1057 accepted.emplace(*i);
1060 if (!
has(accepted, c))
1061 res = add(res,
atom(labelset()->value(c)));
1064 "invalid empty letter class");
1068 template <
typename Context>
1069 template <
typename LabelSet_,
typename... Args>
1073 std::true_type) const
typename node_t::value_t value_t
An expression (a shared pointer to a tree).
Implementation of labels are letters.
std::shared_ptr< const detail::context_base > context
A dyn::context.
expression read_expression(const context &ctx, rat::identities ids, std::istream &is, const std::string &format="default")
Read an expression from a stream.
const identities_t ids_
The set of rewriting rules to apply.
std::istringstream is
The input stream: the specification to translate.
std::string to_string(identities i)
Wrapper around operator<<.
bool is_distributive() const
Whether distributive.
char eat(std::istream &is, char c)
Check lookahead character and advance.
OutExpSet::value_t copy(const InExpSet &in_rs, const OutExpSet &out_rs, const typename InExpSet::value_t &v)
Copy/convert a rational expression.
value_t letter_class(Args &&...chars) const
An expression matching one character amongst chars.
printer< ExpSet > make_printer(const ExpSet &rs, std::ostream &out)
Aut transpose(const transpose_automaton< Aut > &aut)
value_t letter_class_(const Args &&...chars, std::true_type) const
If labelset is oneset.
typename node_t::values_t values_t
A list (vector) of expressions.
Traditional plus distribution. Used for series identities.
A visitor to create a transposed expression,.
static dyn::context ctx(const driver &d)
Get the context of the driver.
std::ostream & print(const Aut &aut, std::ostream &out, const std::string &format)
expressionset_impl(const context_t &ctx, identities_t ids={})
Constructor.
Provide a variadic mul on top of a binary mul(), and one().
A functor to check whether one rational expression is (strictly) less than another one...
value_t conv(const letterset< GenSet > &ls, typename letterset< GenSet >::value_t v) const
static identities ids(const driver &d)
Get the identities of the driver.
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
const weightset_ptr & weightset() const
Accessor to the weightset.
void require(bool b, Args &&...args)
If b is not verified, raise an error with args as message.
context make_context(const std::string &name)
Build a context from its name.
typename weightset_t::value_t weight_t
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
An expressionset can implement several different sets of identities on expressions.
constant< type_t::zero, Context > zero
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
ATTRIBUTE_PURE bool has(const std::deque< T, Allocator > &s, const T &e)
Whether e is member of s.
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.
constant< type_t::one, Context > one
rat::identities identities(const expression &exp)
Bridge.