Vcsn  2.3a
Be Rational
compose.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <vcsn/algos/focus.hh>
4 #include <vcsn/algos/insplit.hh>
8 #include <vcsn/ctx/context.hh>
9 #include <vcsn/dyn/automaton.hh> // dyn::make_automaton
11 #include <vcsn/misc/raise.hh>
12 #include <vcsn/misc/tuple.hh> // make_index_sequence, cross_tuple
13 #include <vcsn/misc/zip-maps.hh>
15 
16 namespace vcsn
17 {
18  namespace detail
19  {
20 #define DEFINE(Type) \
21  template <Automaton Aut> \
22  struct Type ## _of_impl \
23  { \
24  using type = typename Aut::element_type::Type; \
25  }; \
26  \
27  template <Automaton Aut> \
28  struct Type ## _of_impl<insplit_automaton<Aut>> \
29  : Type ## _of_impl<Aut> \
30  {}; \
31  \
32  template <Automaton Aut> \
33  using Type ## _of \
34  = typename Type ## _of_impl<Aut>::type
35 
36  DEFINE(res_labelset_t);
37  DEFINE(res_label_t);
38  DEFINE(full_context_t);
39 
40 #undef DEFINE
41 
43  template <Automaton Lhs, Automaton Rhs>
45  {
46  using clhs_t = Lhs;
47  using crhs_t = Rhs;
48  // clhs_t and crhs_t are permutation automata, yet we need to
49  // read the res_label_t from their wrapped automaton type.
52  using hidden_l_label_t = typename hidden_l_labelset_t::value_t;
53  using hidden_r_label_t = typename hidden_r_labelset_t::value_t;
54 
55 
61 
62  using res_label_t = typename labelset_t::value_t;
64 
66  };
67 
68 
69  /*------------------------------------------.
70  | compose_automaton<automaton, automaton>. |
71  `------------------------------------------*/
72 
74  template <bool Lazy, Automaton Lhs, Automaton Rhs>
76  : public lazy_tuple_automaton<compose_automaton_impl<Lazy, Lhs, Rhs>,
77  true,
78  Lazy,
79  typename composed_type<Lhs, Rhs>::out_t,
80  Lhs, Rhs>
81  {
82  static_assert(full_context_t_of<Lhs>::is_lat,
83  "compose: lhs labelset must be a tupleset");
84  static_assert(full_context_t_of<Rhs>::is_lat,
85  "compose: rhs labelset must be a tupleset");
86 
87  static_assert(std::is_same<labelset_t_of<Lhs>,
88  labelset_t_of<Rhs>>::value,
89  "compose: common tape must be of same type");
90 
92  template <std::size_t... I>
94 
95  public:
96 
98 
104 
105 
109 
112 
113  using out_t = typename type_helper_t::out_t;
116  using state_t = typename super_t::state_t;
119 
121  using automata_t = std::tuple<Lhs, Rhs>;
122 
124  template <size_t I>
126 
128  enum { Rank = 2 };
129 
130  using super_t::aut_;
131 
132  static symbol sname()
133  {
134  static symbol res(std::string{"compose_automaton<"}
135  + (Lazy ? "true" : "false") + ", "
136  + Lhs::element_type::sname() + ", "
137  + Rhs::element_type::sname() + ">");
138  return res;
139  }
140 
141  std::ostream& print_set(std::ostream& o, format fmt = {}) const
142  {
143  o << "compose_automaton<";
144  std::get<0>(aut_->auts_)->print_set(o, fmt) << ", ";
145  return std::get<1>(aut_->auts_)->print_set(o, fmt) << ">";
146  }
147 
148  compose_automaton_impl(const Lhs& lhs, const Rhs& rhs)
149  : super_t{make_mutable_automaton(make_context_(lhs, rhs)), lhs, rhs}
150  {}
151 
153  void compose()
154  {
156 
157  if (!Lazy)
158  while (!aut_->todo_.empty())
159  {
160  const auto& p = aut_->todo_.front();
161  add_compose_transitions(std::get<1>(p), std::get<0>(p));
162  aut_->todo_.pop_front();
163  }
164  }
165 
167  void add_transitions(const state_t src,
168  const state_name_t& psrc)
169  {
170  add_compose_transitions(src, psrc);
171  }
172 
173  using label_t = typename labelset_t::value_t;
174  using weight_t = typename weightset_t::value_t;
175 
176  private:
179  template <Automaton A>
180  static auto real_aut(const A& aut)
181  {
182  return aut;
183  }
184 
186  template <Automaton A>
187  static auto real_aut(const insplit_automaton<A>& aut)
188  {
189  return aut->aut_out();
190  }
191 
194  template <Automaton A>
195  using transition_map_t
197 
199  const hidden_r_labelset_t& rl)
200  {
201  constexpr auto lsize = hidden_l_labelset_t::size();
202  constexpr auto rsize = hidden_r_labelset_t::size();
205  }
206 
207  template <std::size_t... I1, std::size_t... I2>
209  seq<I1...>,
210  const hidden_r_labelset_t& rl,
211  seq<I2...>)
212  {
213  return labelset_t{std::get<I1>(ll.sets())...,
214  std::get<I2>(rl.sets())...};
215  }
216 
217  static context_t
218  make_context_(const Lhs& lhs, const Rhs& rhs)
219  {
220  return {make_labelset_(lhs->res_labelset(),
221  real_aut(rhs)->res_labelset()),
222  join(*lhs->weightset(), *rhs->weightset())};
223  }
224 
228  {
229  aut_->todo_.emplace_back(aut_->pre_(), aut_->pre());
230  }
231 
233  const hidden_r_label_t& rl) const
234  {
235  return std::tuple_cat(ll, rl);
236  }
237 
238  template <Automaton Aut>
239  std::enable_if_t<labelset_t_of<Aut>::has_one(),
241  get_hidden_one(const Aut& aut) const
242  {
243  return aut->hidden_one();
244  }
245 
246  template <Automaton Aut>
247  std::enable_if_t<labelset_t_of<Aut>::has_one(),
250  {
251  return real_aut(aut)->hidden_one();
252  }
253 
254  template <Automaton Aut>
255  ATTRIBUTE_NORETURN
256  std::enable_if_t<!labelset_t_of<Aut>::has_one(),
258  get_hidden_one(const Aut&) const
259  {
260  raise("should not get here");
261  }
262 
269  const state_name_t& psrc)
270  {
271  const auto& lhs = std::get<0>(aut_->auts_);
272  const auto& rhs = std::get<1>(aut_->auts_);
273 
274  // Outgoing transition cache.
275  const auto& ltm = std::get<0>(transition_maps_)[std::get<0>(psrc)];
276  const auto& rtm = std::get<1>(transition_maps_)[std::get<1>(psrc)];
277 
278  add_one_transitions_<0>(src, psrc);
279  add_one_transitions_<1>(src, psrc);
280 
281  // In order to avoid having to call add_transition each time, we cache
282  // the transitions we add using a polynomial. We conserve a polynomial
283  // for each successor of src.
284  using polynomialset_t
286  using polynomial_t = typename polynomialset_t::value_t;
287  const auto ps = polynomialset_t(aut_->context());
288  auto poly_maps = std::map<state_t, polynomial_t>();
289 
290  for (const auto& t: zip_maps(ltm, rtm))
291  // The type of the common label is that of the visible tape
292  // of either automata.
293  if (!lhs->labelset()->is_one(t.first))
294  // These may not be new transitions: as the automata are focus,
295  // there might be two transitions with the same destination and
296  // label, with only the hidden part that changes.
298  ([&] (const typename transition_map_t<Lhs>::transition& lts,
299  const typename transition_map_t<Rhs>::transition& rts)
300  {
301  // Cache the transitions.
302  ps.add_here(poly_maps[this->state(lts.dst, rts.dst)],
303  join_label(lhs->hidden_label_of(lts.transition),
304  real_aut(rhs)->hidden_label_of(rts.transition)),
305  this->weightset()->mul(lts.weight(), rts.weight()));
306  },
307  t.second);
308 
309  // For each successor, add a transition for each monomial of the
310  // corresponding polynomial.
311  for (const auto& elt: poly_maps)
312  for (const auto& m: elt.second)
313  this->new_transition(src, elt.first, m.first, m.second);
314  }
315 
316 
317  template <std::size_t I>
318  void add_one_transitions_(const state_t src, const state_name_t& psrc)
319  {
320  // The first condition prevents the creation of redundant
321  // paths that would lead to incorrect valuations (in the
322  // weighted case), while the second is purely an optimization,
323  // avoiding the creation of non-coaccessible states.
326  {
327  const auto& ls = *std::get<I>(aut_->auts_)->labelset();
328  const auto& tmap = std::get<I>(transition_maps_)[std::get<I>(psrc)];
329  if (!tmap.empty() && ls.is_one(tmap.begin()->first))
330  for (const auto& t: tmap.begin()->second)
331  {
332  // Tuple of destination states.
333  auto pdst =
334  static_if<I == 0>
335  ([dst=t.dst, &psrc]{
336  return std::make_tuple(dst, std::get<1>(psrc));
337  },
338  [dst=t.dst, &psrc]{
339  return std::make_tuple(std::get<0>(psrc), dst);
340  })();
341  // Label.
342  auto lbl =
343  static_if<I == 0>
344  ([this, t=t.transition](const auto& lhs, const auto& rhs)
345  {
346  return join_label(lhs->hidden_label_of(t),
347  get_hidden_one(real_aut(rhs)));
348  },
349  [this, t=t.transition](const auto& lhs, const auto& rhs)
350  {
351  return join_label(get_hidden_one(lhs),
352  real_aut(rhs)->hidden_label_of(t));
353  })
354  (std::get<0>(aut_->auts_), std::get<1>(aut_->auts_));
355  this->new_transition(src, this->state(pdst), lbl, t.weight());
356  }
357  }
358  }
359 
360  template <Automaton Aut>
361  std::enable_if_t<labelset_t_of<Aut>::has_one(), bool>
362  is_one(const Aut& aut, transition_t_of<Aut> tr) const
363  {
364  return aut->labelset()->is_one(aut->label_of(tr));
365  }
366 
367  template <Automaton Aut>
368  constexpr
369  std::enable_if_t<!labelset_t_of<Aut>::has_one(), bool>
370  is_one(const Aut&, transition_t_of<Aut>) const
371  {
372  return false;
373  }
374 
377  template <std::size_t... I>
378  bool are_proper_in(const state_name_t& psrc, seq<I...>) const
379  {
380  return all(is_proper_in<I>(psrc)...);
381  }
382 
384  template <size_t I>
385  constexpr auto
387  -> std::enable_if_t<!labelset_t_of<input_automaton_t<I>>::has_one(),
388  bool>
389  {
390  return true;
391  }
392 
397  template <size_t I>
398  auto
399  is_proper_in(const state_name_t& sn) const
400  -> std::enable_if_t<labelset_t_of<input_automaton_t<I>>::has_one(),
401  bool>
402  {
403  // Amusingly enough, it is faster to check the incoming
404  // transitions rather than recovering the decoration of the
405  // insplit state, which tells whether the state is proper-in.
406  const auto& aut = std::get<I>(aut_->auts_);
407  auto s = std::get<I>(sn);
408  auto rin = all_in(aut, s);
409  auto rtr = rin.begin();
410  // Insplit state, so checking the first transition suffices.
411  // There can be no incoming transitions in the case of pre.
412  return rtr == rin.end() || !is_one(aut, *rtr);
413  }
414 
417  template <std::size_t... I>
419  {
420  return all(has_proper_out<I>(psrc)...);
421  }
422 
428  template <size_t I>
429  bool
431  {
432  const auto& tmap = std::get<I>(transition_maps_)[std::get<I>(psrc)];
433  auto s = tmap.size();
434  if (s == 0)
435  return false;
436  else if (2 <= s)
437  return true;
438  else
439  return !std::get<I>(aut_->auts_)->labelset()->is_one(tmap.begin()->first);
440  }
441  };
442  }
443 
445  template <bool Lazy, Automaton Lhs, Automaton Rhs>
446  using compose_automaton
447  = std::shared_ptr<detail::compose_automaton_impl<Lazy, Lhs, Rhs>>;
448 
449  template <bool Lazy, std::size_t OutTape, std::size_t InTape,
450  Automaton Lhs, Automaton Rhs>
451  auto
452  make_compose_automaton(const Lhs& lhs, const Rhs& rhs)
453  {
454  auto l = focus<OutTape>(lhs);
455  auto r = insplit(focus<InTape>(rhs), true);
456  using res_t = compose_automaton<Lazy,
458  decltype(r)>;
459  return make_shared_ptr<res_t>(l, r);
460  }
461 
462  /*--------------------------------.
463  | compose(automaton, automaton). |
464  `--------------------------------*/
465 
467  template <Automaton Lhs, Automaton Rhs,
468  std::size_t OutTape = 1, std::size_t InTape = 0>
469  auto
470  compose(const Lhs& lhs, const Rhs& rhs)
471  {
472  auto res = make_compose_automaton<false, OutTape, InTape>(lhs, rhs);
473  res->compose();
474  return res->strip();
475  }
476 
478  template <typename Lhs, typename Rhs,
479  std::size_t OutTape = 1, std::size_t InTape = 0>
480  auto
481  compose_lazy(const Lhs& lhs, const Rhs& rhs)
482  {
483  auto res = make_compose_automaton<true, OutTape, InTape>(lhs, rhs);
484  res->compose();
485  return res;
486  }
487 
488  namespace dyn
489  {
490  namespace detail
491  {
493  template <Automaton Lhs, Automaton Rhs, typename Bool>
494  automaton
495  compose(const automaton& lhs, const automaton& rhs, bool lazy)
496  {
497  auto& l = lhs->as<Lhs>();
498  auto& r = rhs->as<Rhs>();
499  if (lazy)
501  else
503  }
504  }
505  }
506 }
typename tuple_automaton_impl::state_name_t state_name_t
mutable_automaton< context_t > out_t
Definition: compose.hh:65
void initialize_compose()
Fill the worklist with the initial source-state pairs, as needed for the composition algorithm...
Definition: compose.hh:227
zipped_maps< Dereference, Maps... > zip_maps(Maps &&...maps)
Definition: zip-maps.hh:250
static labelset_t make_labelset_(const hidden_l_labelset_t &ll, seq< I1... >, const hidden_r_labelset_t &rl, seq< I2... >)
Definition: compose.hh:208
auto labelset(Args &&...args) const -> decltype(aut_-> labelset(std::forward< Args >(args)...))
typename labelset_t::value_t label_t
Definition: compose.hh:173
std::shared_ptr< detail::focus_automaton_impl< Tape, Aut >> focus_automaton
A focus automaton as a shared pointer.
Definition: fwd.hh:42
std::tuple< Lhs, Rhs > automata_t
The type of input automata.
Definition: compose.hh:121
Decorator implementing the laziness for an algorithm.
void add_transitions(const state_t src, const state_name_t &psrc)
Callback for complete_ when lazy.
Definition: compose.hh:167
typename hidden_l_labelset_t::value_t hidden_l_label_t
Definition: compose.hh:52
typename labelset_t::value_t res_label_t
Definition: compose.hh:62
std::enable_if_t< labelset_t_of< Aut >::has_one(), bool > is_one(const Aut &aut, transition_t_of< Aut > tr) const
Definition: compose.hh:362
Build the (accessible part of the) composition.
Definition: compose.hh:75
ATTRIBUTE_NORETURN std::enable_if_t<!labelset_t_of< Aut >::has_one(), res_label_t_of< Aut > > get_hidden_one(const Aut &) const
Definition: compose.hh:258
typename type_helper_t::labelset_t labelset_t
The type of context of the result.
Definition: compose.hh:107
Definition: a-star.hh:8
typename tuple_automaton_impl::state_t state_t
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.
Definition: insplit.hh:266
std::enable_if_t< labelset_t_of< Aut >::has_one(), res_label_t_of< Aut > > get_hidden_one(const Aut &aut) const
Definition: compose.hh:241
auto all_in(Args &&...args) const -> decltype(aut_-> all_in(std::forward< Args >(args)...))
return res
Definition: multiply.hh:398
base_t< tuple_element_t< I, automata_t >> input_automaton_t
The type of the Ith input automaton, unqualified.
Definition: compose.hh:125
Outgoing signature: weight, destination.
static auto real_aut(const A &aut)
Get the focus automaton, possibly from a non insplit automaton.
Definition: compose.hh:180
res_label_t join_label(const hidden_l_label_t &ll, const hidden_r_label_t &rl) const
Definition: compose.hh:232
typename type_helper_t::weightset_t weightset_t
Definition: compose.hh:108
auto is_proper_in(const state_name_t &sn) const -> std::enable_if_t< labelset_t_of< input_automaton_t< I >>::has_one(), bool >
Whether the state has only proper incoming transitions.
Definition: compose.hh:399
automaton compose(const automaton &lhs, const automaton &rhs, bool lazy)
Bridge.
Definition: compose.hh:495
An input/output format for valuesets.
Definition: format.hh:13
typename res_label_t_of_impl< Aut >::type res_label_t_of
Definition: compose.hh:37
auto make_compose_automaton(const Lhs &lhs, const Rhs &rhs)
Definition: compose.hh:452
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
Build the (accessible part of the) composition.
Definition: compose.hh:44
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
typename full_context_t_of_impl< Aut >::type full_context_t_of
Definition: compose.hh:38
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
bool has_proper_out(const state_name_t &psrc)
Whether the Ith state of psrc in the Ith input automaton has proper outgoing transitions (but possibl...
Definition: compose.hh:430
static labelset_t make_labelset_(const hidden_l_labelset_t &ll, const hidden_r_labelset_t &rl)
Definition: compose.hh:198
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: compose.hh:141
typename type_helper_t::context_t context_t
Definition: compose.hh:111
bool all(Bool &&...values)
Whether all the values evaluate as true.
Definition: tuple.hh:446
typename hidden_r_labelset_t::value_t hidden_r_label_t
Definition: compose.hh:53
A static range.
Definition: tuple.hh:83
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54
bool are_proper_in(const state_name_t &psrc, seq< I... >) const
Whether no tapes in the sequence have spontaneous incoming transitions.
Definition: compose.hh:378
std::string type(const automaton &a)
The implementation type of a.
Definition: others.cc:239
decltype(join(std::declval< ValueSets >()...)) join_t
The type of the join of the ValueSets.
Definition: join.hh:78
transition_map< A, weightset_t, false, true, true > transition_map_t
The type of our transition maps: convert the weight to weightset_t, non deterministic, and including transitions to post().
Definition: compose.hh:196
std::shared_ptr< insplit_automaton_impl< Aut >> insplit_automaton
An insplit automaton as a shared pointer.
Definition: insplit.hh:251
typename type_helper_t::res_label_t res_label_t
Definition: compose.hh:110
auto join(const ValueSet &vs) -> ValueSet
The join of a single valueset.
Definition: join.hh:44
auto compose_lazy(const Lhs &lhs, const Rhs &rhs)
Build the (accessible part of the) lazy composition.
Definition: compose.hh:481
#define DEFINE(Type)
Definition: compose.hh:20
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
Cache the outgoing transitions of an automaton as efficient maps label -> vector<(weight, dst)>.
bool have_proper_out(const state_name_t &psrc, seq< I... >)
Whether all the tapes in the sequence have proper outgoing transitions (but possibly spontaneous too)...
Definition: compose.hh:418
typename type_helper_t::hidden_l_labelset_t hidden_l_labelset_t
Definition: compose.hh:100
std::remove_cv_t< std::remove_reference_t< T >> base_t
T without reference or const/volatile qualifiers.
Definition: traits.hh:13
A dyn automaton.
Definition: automaton.hh:17
typename concat_tupleset< hidden_l_labelset_t, hidden_r_labelset_t >::type labelset_t
The type of context of the result.
Definition: compose.hh:58
static auto real_aut(const insplit_automaton< A > &aut)
Get the focus automaton from an insplit automaton.
Definition: compose.hh:187
typename weightset_t::value_t weight_t
Definition: compose.hh:174
void cross_tuple(Fun f, const std::tuple< Ts... > &ts)
Definition: tuple.hh:301
std::tuple< transition_map_t< Auts >... > transition_maps_
Transition caches.
static context_t make_context_(const Lhs &lhs, const Rhs &rhs)
Definition: compose.hh:218
mutable_automaton< Context > make_mutable_automaton(const Context &ctx)
std::shared_ptr< detail::compose_automaton_impl< Lazy, Lhs, Rhs >> compose_automaton
A compose automaton as a shared pointer.
Definition: compose.hh:447
STL namespace.
constexpr std::enable_if_t<!labelset_t_of< Aut >::has_one(), bool > is_one(const Aut &, transition_t_of< Aut >) const
Definition: compose.hh:370
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
void add_compose_transitions(const state_t src, const state_name_t &psrc)
Add transitions to the given result automaton, starting from the given result input state...
Definition: compose.hh:268
res_labelset_t_of< clhs_t > hidden_l_labelset_t
Definition: compose.hh:50
typename super_t::state_name_t state_name_t
Tuple of states of input automata.
Definition: compose.hh:118
::vcsn::context< labelset_t, weightset_t > context_t
Definition: compose.hh:63
typename super_t::state_t state_t
Result state type.
Definition: compose.hh:116
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
automaton_t aut_
The wrapped automaton, possibly const.
#define Automaton
Definition: automaton.hh:23
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
typename type_helper_t::hidden_r_labelset_t hidden_r_labelset_t
Definition: compose.hh:101
typename res_labelset_t_of_impl< Aut >::type res_labelset_t_of
Definition: compose.hh:36
typename type_helper_t::hidden_l_label_t hidden_l_label_t
Definition: compose.hh:102
compose_automaton_impl(const Lhs &lhs, const Rhs &rhs)
Definition: compose.hh:148
constexpr auto is_proper_in(const state_name_t &) const -> std::enable_if_t<!labelset_t_of< input_automaton_t< I >>::has_one(), bool >
Whether the state has only proper incoming transitions.
Definition: compose.hh:386
join_t< weightset_t_of< context_t_of< Lhs >>, weightset_t_of< context_t_of< Rhs >>> weightset_t
Definition: compose.hh:60
std::enable_if_t< labelset_t_of< Aut >::has_one(), res_label_t_of< Aut > > get_hidden_one(const insplit_automaton< Aut > &aut) const
Definition: compose.hh:249
void add_one_transitions_(const state_t src, const state_name_t &psrc)
Definition: compose.hh:318
typename type_helper_t::out_t out_t
Definition: compose.hh:113
symbol sname()
Definition: name.hh:65
void compose()
The (accessible part of the) composition of lhs_ and rhs_.
Definition: compose.hh:153
res_labelset_t_of< crhs_t > hidden_r_labelset_t
Definition: compose.hh:51
auto new_transition(Args &&...args) -> decltype(aut_-> new_transition(std::forward< Args >(args)...))
typename type_helper_t::hidden_r_label_t hidden_r_label_t
Definition: compose.hh:103
auto weightset(Args &&...args) const -> decltype(aut_-> weightset(std::forward< Args >(args)...))
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46