39 false, Lazy, Aut, Auts...>
42 "product: requires letterized labels");
53 template <Automaton A>
56 template <
size_t... I>
57 using seq =
typename super_t::template seq<I...>;
60 using super_t::transition_maps_;
65 + super_t::sname_(std::string{Lazy ?
"true" :
"false"}));
71 o <<
"product_automaton";
72 return aut_->print_set_(o, fmt);
80 using label_t =
typename labelset_t::value_t;
81 using weight_t =
typename weightset_t::value_t;
102 initialize_conjunction();
105 while (!
aut_->todo_.empty())
107 const auto& p =
aut_->todo_.front();
108 add_conjunction_transitions(std::get<1>(p), std::get<0>(p));
109 aut_->todo_.pop_front();
114 template <
bool L = Lazy>
115 std::enable_if_t<
sizeof...(Auts) == 2 && !
L> ldivide()
117 static_assert(labelset_t::has_one(),
118 "ldivide: labelset must have a neutral");
119 initialize_conjunction();
121 while (!
aut_->todo_.empty())
123 const auto& p =
aut_->todo_.front();
124 add_ldivide_transitions(std::get<1>(p), std::get<0>(p));
125 aut_->todo_.pop_front();
130 template <
bool L = Lazy>
131 std::enable_if_t<
sizeof...(Auts) == 2 && !
L> add()
133 using lhs_t = input_automaton_t<0>;
134 using rhs_t = input_automaton_t<1>;
135 constexpr
bool bb = (std::is_same<weightset_t_of<lhs_t>,
b>::value
136 && std::is_same<weightset_t_of<rhs_t>,
b>::value);
137 static_assert(bb,
"add: requires Boolean weightset");
138 initialize_conjunction();
140 while (!
aut_->todo_.empty())
142 const auto& p =
aut_->todo_.front();
143 add_add_transitions(std::get<1>(p), std::get<0>(p));
144 aut_->todo_.pop_front();
149 template <
bool L = Lazy>
150 std::enable_if_t<
sizeof...(Auts) == 2 && !
L> ldivide_here()
152 initialize_conjunction();
154 using rhs_t = input_automaton_t<1>;
155 auto new_initials = std::vector<state_t_of<rhs_t>>();
157 const auto& lhs = std::get<0>(
aut_->auts_);
158 auto& rhs = std::get<1>(
aut_->auts_);
160 while (!
aut_->todo_.empty())
162 const auto& p =
aut_->todo_.front();
163 const auto& state_name = std::get<0>(p);
164 add_conjunction_transitions(std::get<1>(p), state_name);
167 if (lhs->is_final(std::get<0>(state_name)))
168 new_initials.push_back(std::get<1>(state_name));
169 aut_->todo_.pop_front();
173 rhs->unset_initial(rhs->dst_of(t));
174 for (
auto s: new_initials)
182 if (!std::is_same<weightset_t, b>{})
185 "shuffle: invalid lhs:"
186 " weighted automata with spontaneous"
187 " transitions are not supported");
189 "shuffle: invalid rhs:"
190 " weighted automata with spontaneous"
191 " transitions are not supported");
194 initialize_shuffle();
196 while (!
aut_->todo_.empty())
198 const auto& p =
aut_->todo_.front();
199 add_shuffle_transitions<false>(std::get<1>(p), std::get<0>(p));
200 aut_->todo_.pop_front();
225 "infiltrate: variadic product does not work");
228 if (!std::is_same<weightset_t, b>{})
231 "infiltrate: invalid lhs:"
232 " weighted automata with spontaneous"
233 " transitions are not supported");
235 "infiltrate: invalid rhs:"
236 " weighted automata with spontaneous"
237 " transitions are not supported");
243 initialize_shuffle();
245 while (!
aut_->todo_.empty())
247 const auto& p =
aut_->todo_.front();
253 add_conjunction_transitions(std::get<1>(p), std::get<0>(p));
254 add_shuffle_transitions<true>(std::get<1>(p), std::get<0>(p));
256 aut_->todo_.pop_front();
261 void add_transitions(
const state_t src,
264 add_conjunction_transitions(src, psrc);
270 void initialize_conjunction()
277 void initialize_shuffle()
281 add_conjunction_transitions(
aut_->pre(),
aut_->pre_());
285 using super_t::state;
290 void add_conjunction_transitions(
const state_t src,
298 if (!
aut_->labelset()->is_one(t.first))
308 add_one_transitions_(src, psrc,
aut_->indices);
317 template <
bool L = Lazy>
318 std::enable_if_t<
sizeof...(Auts) == 2 && !
L>
321 const auto& ls = *
aut_->labelset();
322 const auto& lhs = std::get<0>(
aut_->auts_);
323 const auto& rhs = std::get<1>(
aut_->auts_);
324 const auto& lstate = std::get<0>(psrc);
325 const auto& rstate = std::get<1>(psrc);
327 if (lhs->is_final(lstate) || lstate == lhs->post())
329 for (
auto ts:
all_out(rhs, rstate))
331 const auto&
lweight = lhs->is_final(lstate)
332 ? lhs->get_final_weight(lstate) :
ws_.one();
334 state(lhs->post(), rhs->dst_of(ts)),
340 if (!ls.is_one(t.first)
341 && (!ls.is_special(t.first) || src ==
aut_->pre()))
347 ls.is_special(t.first)
348 ? t.first : ls.one(),
357 template <
bool L = Lazy>
358 std::enable_if_t<
sizeof...(Auts) == 2 && !
L>
361 const auto& lhs = std::get<0>(
aut_->auts_);
362 const auto& rhs = std::get<1>(
aut_->auts_);
363 const auto& lstate = std::get<0>(psrc);
364 const auto& rstate = std::get<1>(psrc);
366 auto common_labels = std::set<label_t_of<Aut>>{};
369 common_labels.insert(t.first);
378 for (
auto t:
all_out(lhs, lstate))
379 if (!
has(common_labels, lhs->label_of(t)))
382 for (
auto t:
all_out(rhs, rstate))
383 if (!
has(common_labels, rhs->label_of(t)))
390 template <std::size_t... I>
395 using swallow =
int[];
398 (add_one_transitions_<I>(*(std::get<I>(
aut_->auts_)->
labelset()),
404 template <std::
size_t I,
typename LS>
405 std::enable_if_t<!LS::has_one(), void>
411 template <std::
size_t I,
typename LS>
412 std::enable_if_t<LS::has_one(), void>
413 add_one_transitions_(
const LS& ls,
const state_t src,
425 if (!tmap.empty() && ls.is_one(tmap.begin()->first))
426 for (
auto t : tmap.begin()->second)
429 std::get<I>(pdst) = t.dst;
430 this->new_transition(src,
state(pdst), ls.one(), t.weight());
437 template <std::size_t... I>
440 return all(is_proper_in<I>(psrc)...);
445 template <std::size_t... I>
448 return all(has_proper_out<I>(psrc)...);
453 template <Automaton Aut_>
454 std::enable_if_t<labelset_t_of<Aut_>::has_one(),
bool>
457 return aut->labelset()->is_one(aut->label_of(tr));
462 template <Automaton Aut_>
463 constexpr std::enable_if_t<!labelset_t_of<Aut_>::has_one(),
bool>
473 -> std::enable_if_t<!labelset_t_of<input_automaton_t<I>>::has_one(),
486 -> std::enable_if_t<labelset_t_of<input_automaton_t<I>>::has_one(),
492 const auto& aut = std::get<I>(
aut_->auts_);
493 auto s = std::get<I>(sn);
494 auto rin =
all_in(aut, s);
495 auto rtr = rin.begin();
498 return rtr == rin.end() || !is_one(aut, *rtr);
511 auto s = tmap.size();
517 return !std::get<I>(
aut_->auts_)->
labelset()->is_one(tmap.begin()->first);
524 template <
bool Infiltrate = false>
525 void add_shuffle_transitions(
const state_t src,
529 = add_shuffle_transitions_<Infiltrate>(src, psrc,
aut_->indices);
530 aut_->set_final(src,
final);
537 template <
bool Infiltrate,
size_t... I>
543 using swallow =
int[];
547 add_shuffle_transitions_<Infiltrate, I>(src, psrc)),
563 template <
bool Infiltrate,
size_t I>
565 add_shuffle_transitions_(
const state_t src,
573 if (std::get<I>(
aut_->auts_)->labelset()->is_special(t.first))
574 res = t.second.front().weight();
586 for (
auto d: t.second)
589 std::get<I>(pdst) = d.dst;
591 || std::get<I>(psrc) == d.dst)
611 return make_shared_ptr<res_t>(aut, auts...);
650 template <
typename Auts,
size_t... I>
662 template <
typename Auts,
typename Bool>
668 return conjunction_<Auts>(as, lazy, indices);
682 template <Automaton Aut1, Automaton Aut2>
684 ldivide(
const Aut1& lhs,
const Aut2& rhs,
auto_tag = {})
686 return detail::static_if<std::is_same<weightset_t_of<Aut1>,
b>::value
687 && std::is_same<weightset_t_of<Aut2>,
b>::value>
688 ([] (
const auto& lhs,
const auto& rhs)
690 return ldivide(lhs, rhs, boolean_tag{});
692 [] (
const auto& lhs,
const auto& rhs)
694 return ldivide(lhs, rhs, weighted_tag{});
699 template <Automaton Aut1, Automaton Aut2>
704 detail::static_if<labelset_t_of<Aut2>::has_one()>
705 ([](
const auto& rhs){
return insplit(rhs); },
706 [](
const auto& rhs){
return copy(rhs); })
710 prod->ldivide_here();
714 template <Automaton Aut1, Automaton Aut2>
719 detail::make_product_automaton<false>(
join_automata(lhs, rhs), lhs, rhs);
721 return prod->strip();
730 template <Automaton Aut1, Automaton Aut2>
734 const auto& a1 = aut1->
as<Aut1>();
735 const auto& a2 = aut2->
as<Aut2>();
736 return vcsn::ldivide<Aut1, Aut2>(a1, a2);
751 template <Automaton Aut1, Automaton Aut2>
765 template <Automaton Aut1, Automaton Aut2>
769 const auto& a1 = aut1->
as<Aut1>();
770 const auto& a2 = aut2->
as<Aut2>();
784 shuffle(
const Auts&... as)
790 detail::make_product_automaton<false>(
join_automata(as...), as...);
800 template <
typename Auts,
size_t... I>
809 template <
typename Auts>
811 shuffle(
const std::vector<automaton>& as)
815 return shuffle_<Auts>(as, indices);
826 template <
typename ValueSet>
827 typename ValueSet::value_t
828 shuffle(
const ValueSet& vs,
829 const typename ValueSet::value_t& lhs,
830 const typename ValueSet::value_t& rhs)
832 return vs.shuffle(lhs, rhs);
840 template <
typename ExpSetLhs,
typename ExpSetRhs>
844 auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
845 return {std::get<0>(join_elts),
847 std::get<1>(join_elts),
848 std::get<2>(join_elts))};
859 template <Automaton A1, Automaton A2>
861 infiltrate(
const A1& a1,
const A2& a2)
866 detail::make_product_automaton<false>(
join_automata(a1, a2), a1, a2);
874 infiltrate(
const A1& a1,
const A2& a2,
const A3& a3,
const Auts&... as)
876 -> decltype(infiltrate(infiltrate(a1, a2), a3, as...))
878 return infiltrate(infiltrate(a1, a2), a3, as...);
886 template <
typename Auts,
size_t... I>
895 template <
typename Auts>
897 infiltrate(
const std::vector<automaton>& as)
901 return infiltrate_<Auts>(as, indices);
911 template <
typename ValueSet>
912 typename ValueSet::value_t
913 infiltrate(
const ValueSet& vs,
914 const typename ValueSet::value_t& lhs,
915 const typename ValueSet::value_t& rhs)
917 return vs.infiltrate(lhs, rhs);
925 template <
typename ExpSetLhs,
typename ExpSetRhs>
929 auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
930 return {std::get<0>(join_elts),
932 std::get<1>(join_elts),
933 std::get<2>(join_elts))};
949 template <Automaton Aut>
960 "conjunction: exponent must be single, ", exp);
962 "conjunction: exponent must be finite, ", exp);
963 unsigned n = exp.min;
967 auto s =
res->new_state();
970 for (
auto l:
res->context().labelset()->generators())
971 res->new_transition(s, s, l);
982 static bool iterative = getenv(
"VCSN_ITERATIVE");
984 for (
size_t i = 0; i < n; ++i)
988 auto power =
strip(aut);
1010 template <Automaton Aut,
typename Un
signed>
1014 const auto& a = aut->
as<Aut>();
1025 template <
typename ValueSet>
1026 typename ValueSet::value_t
1028 const typename ValueSet::value_t& lhs,
1029 const typename ValueSet::value_t& rhs)
1031 return rs.conjunction(lhs, rhs);
1043 template <
typename ExpSetLhs,
typename ExpSetRhs>
1047 auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
1048 return {std::get<0>(join_elts),
1050 std::get<1>(join_elts),
1051 std::get<2>(join_elts))};
1065 template <
typename ExpSetLhs,
typename ExpSetRhs>
1069 auto join_elts = join<ExpSetLhs, ExpSetRhs>(lhs, rhs);
1070 return {std::get<0>(join_elts),
1072 std::get<1>(join_elts),
1073 std::get<2>(join_elts))};
1087 template <
typename PolynomialSetLhs,
typename PolynomialSetRhs>
1091 auto join_elts = join<PolynomialSetLhs, PolynomialSetRhs>(lhs, rhs);
1092 return {std::get<0>(join_elts),
1094 std::get<1>(join_elts),
1095 std::get<2>(join_elts))};
auto tuple(const Auts &...as)
Build the (accessible part of the) tuple.
std::tuple< transition_map_t< Auts >...> transition_maps_
Transition caches.
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
An exponent, or range of exponents.
expression shuffle_expression(const expression &lhs, const expression &rhs)
Bridge (shuffle).
auto conjunction_lazy(const Aut &a, const Auts &...as)
Build the (accessible part of the) conjunction, on-the-fly.
Aut automaton_t
The type of automaton to wrap.
expansion conjunction_expansion(const expansion &lhs, const expansion &rhs)
Bridge (conjunction).
const weightset_t & ws_
The resulting weightset.
automaton_t strip()
The automaton we decorate.
bool is_proper(const Aut &aut)
Test whether an automaton is proper.
automaton shuffle_(const std::vector< automaton > &as, vcsn::detail::index_sequence< I...>)
Variadic bridge helper.
weightset_mixin< detail::b_impl > b
auto make_product_automaton(Aut aut, const Auts &...auts) -> product_automaton< Lazy, Aut, Auts...>
state_t_of< automaton_t > state_t
Request for the weighted version of an algorithm.
Build the (accessible part of the) product.
automaton conjunction_(const std::vector< automaton > &as, bool lazy, vcsn::detail::index_sequence< I...>)
Bridge helper.
value_impl< detail::polynomial_tag > polynomial
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
auto print_set(Args &&...args) const -> decltype(aut_-> print_set(std::forward< Args >(args)...))
Aggregate an automaton, and forward calls to it.
typename labelset_t::value_t label_t
An input/output format for valuesets.
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Decorator implementing the laziness for an algorithm.
auto conjunction(const Aut &a, const Auts &...as)
Build the (accessible part of the) conjunction.
Tag to request the most appropriate version of an algorithm.
automaton conjunction_repeated(const automaton &aut, unsigned n)
Bridge (conjunction).
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
expression infiltrate_expression(const expression &lhs, const expression &rhs)
Bridge (infiltrate).
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
bool all(Bool &&...values)
Whether all the values evaluate as true.
void cross_tuple(Fun f, const std::tuple< Ts...> &ts)
typename context_t::labelset_t labelset_t
typename std::tuple_element< I, T >::type tuple_element_t
C++14.
auto meet_automata(Auts &&...auts) -> decltype(pass(auts->null_state()...), make_mutable_automaton(meet(auts->context()...)))
An automaton whose type is the meet between those of auts.
std::shared_ptr< detail::tuple_automaton_impl< Auts...>> tuple_automaton
A tuple automaton as a shared pointer.
Provide a variadic mul on top of a binary mul(), and one().
auto shuffle(const Auts &...as) -> tuple_automaton< decltype(join_automata(as...)), Auts...>
The (accessible part of the) shuffle product.
variadic< type_t::ldivide, Context > ldivide
auto initial_transitions(const Aut &aut) -> decltype(aut->all_out(aut->pre()))
Indexes of transitions to (visible) initial states.
auto conjunction(const Aut &aut, to exp) -> fresh_automaton_t_of< Aut >
Repeated conjunction of a automaton.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
auto join_automata(Auts &&...auts) -> decltype(pass(auts->null_state()...), make_mutable_automaton(join(auts->context()...)))
An automaton whose type is the join between those of auts.
std::shared_ptr< const node< Context >> expression
std::remove_cv_t< std::remove_reference_t< T >> base_t
T without reference or const/volatile qualifiers.
Request the Boolean specialization for determinization (B and F2).
std::shared_ptr< detail::product_automaton_impl< Lazy, Aut, Auts...>> product_automaton
A product automaton as a shared pointer.
auto insplit(Aut aut, bool lazy=false) -> std::enable_if_t< labelset_t_of< Aut >::has_one(), decltype(make_insplit_automaton(aut))>
Insplit an automaton with possible spontaneous transitions.
typename tuple_automaton_impl::state_name_t state_name_t
auto infiltrate(const A1 &a1, const A2 &a2) -> tuple_automaton< decltype(join_automata(a1, a2)), A1, A2 >
The (accessible part of the) infiltration product.
auto all_in(Args &&...args) const -> decltype(aut_-> all_in(std::forward< Args >(args)...))
Aut transpose(const transpose_automaton< Aut > &aut)
The transpose of a transpose automaton is the original automaton.
lazy_tuple_automaton self_t
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
auto labelset(Args &&...args) const -> decltype(aut_-> labelset(std::forward< Args >(args)...))
auto copy(const AutIn &input, KeepState keep_state, KeepTrans keep_trans) -> decltype(keep_state(input->null_state()), keep_trans(input->null_transition()), make_fresh_automaton< AutIn, AutOut >(input))
A copy of input keeping only its states that are accepted by keep_state, and transitions accepted by ...
zipped_maps< Dereference, Maps...> zip_map_tuple(const std::tuple< Maps...> &maps)
auto all_out(state_t s) const -> decltype(all_out(aut_, s))
All the outgoing transitions.
typename Aut::element_type::template fresh_automaton_t< Context > fresh_automaton_t_of
Given an automaton type, the type of its copies.
automaton infiltrate_(const std::vector< automaton > &as, vcsn::detail::index_sequence< I...>)
Variadic bridge helper.
value_impl< detail::expansion_tag > expansion
Outgoing signature: weight, destination.
typename weightset_t::value_t weight_t
static constexpr auto sname(Args &&...args) -> decltype(element_type::sname(std::forward< Args >(args)...))
expression conjunction_expression(const expression &lhs, const expression &rhs)
Bridge (conjunction).
polynomial conjunction_polynomial(const polynomial &lhs, const polynomial &rhs)
Bridge (conjunction).
Cache the outgoing transitions of an automaton as efficient maps label -> vector<(weight, dst)>.
auto add_transition(Args &&...args) -> decltype(aut_-> add_transition(std::forward< Args >(args)...))
typename tuple_automaton_impl::template seq< I...> seq
automaton_t aut_
The wrapped automaton, possibly const.
auto & as()
Extract wrapped typed automaton.
ValueSet::value_t conjunction(const ValueSet &rs, const typename ValueSet::value_t &lhs, const typename ValueSet::value_t &rhs)
Intersection/Hadamard product of expressions/polynomials.
state_t state(Args &&...args)
Conversion from state name to state number.
weightset_t_of< Aut > weightset_t
auto rdivide(const Aut1 &a1, const Aut2 &a2)
Compute the right quotient.
value_impl< detail::expression_tag > expression
auto lweight(Args &&...args) -> decltype(aut_-> lweight(std::forward< Args >(args)...))
std::tuple< typename transition_map_t< Auts >::map_t &...> out_(const state_name_t &ss)
The outgoing tuple of transitions from state tuple ss.
auto new_transition(Args &&...args) -> decltype(aut_-> new_transition(std::forward< Args >(args)...))