Vcsn  2.4
Be Rational
synchronize.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <stack>
4 #include <unordered_map>
5 
6 #include <vcsn/algos/fwd.hh>
8 #include <vcsn/ctx/context.hh>
11 #include <vcsn/dyn/automaton.hh> // dyn::make_automaton
13 #include <vcsn/misc/pair.hh> // hash
14 #include <vcsn/misc/unordered_map.hh> // has
15 
16 namespace vcsn
17 {
18 
19  namespace detail
20  {
21 
22  template <Automaton Aut>
24  {
25  template <typename Dummy>
26  struct worded_labelset {};
27 
28  template <typename... LabelSet>
29  struct worded_labelset<tupleset<LabelSet...>>
30  {
31  using in_labelset_t = tupleset<LabelSet...>;
34  template <std::size_t... I>
37 
38  static labelset_t labelset(const in_labelset_t& ls)
39  {
40  return labelset_(ls, index_t{});
41  }
42 
43  template <std::size_t... I>
45  {
46  return labelset_t{(make_wordset(std::get<I>(ls.sets())))...};
47  }
48  };
49  using in_automaton_t = Aut;
52 
55 
62 
64  static labelset_t labelset(const in_labelset_t& ls)
65  {
67  }
68  };
69 
70  template <Automaton Aut>
73 
80  template <Automaton Aut>
82  : public automaton_decorator<fresh_worded_automaton_t<Aut>>
83  {
84  public:
85  using automaton_t = Aut;
94 
96  using state_name_t = std::pair<state_t_of<automaton_t>, label_t>;
97 
98  template <size_t I>
99  using tape_labelset_t = typename labelset_t::template valueset_t<I>;
100 
103  *aut->weightset()})
104  , aut_(aut)
105  {
106  todo_.emplace(aut->pre(), labelset_t::one());
107  }
108 
110  static symbol sname()
111  {
112  static auto res = symbol{"synchronized_automaton<"
114  + '>'};
115  return res;
116  }
117 
118  std::ostream& print_set(std::ostream& o, format fmt = {}) const
119  {
120  o << "synchronized_automaton<";
121  super_t::print_set(o, fmt);
122  return o << '>';
123  }
124 
126  using smap = std::unordered_map<state_name_t, state_t>;
127 
130  state_t state(const state_name_t& r, bool todo = true)
131  {
132  if (r.first == aut_->pre())
133  return this->pre();
134  // Benches show that the map_.emplace technique is slower, and
135  // then that operator[] is faster than emplace.
136  state_t res;
137  auto i = map_.find(r);
138  if (i == std::end(map_))
139  {
140  res = super_t::new_state();
141  map_[r] = res;
142  if (todo)
143  todo_.push(r);
144  }
145  else
146  res = i->second;
147  return res;
148  }
149 
150  using super_t::new_transition;
151 
152  void
153  new_transition(const state_name_t& src, const state_name_t& dst,
154  const label_t& l, const weight_t& w)
155  {
156  super_t::new_transition(state(src), state(dst), l, w);
157  }
158 
159  using super_t::set_final;
160 
161  void set_final(const state_name_t& st, const weight_t& w)
162  {
163  super_t::set_final(map_[st], w);
164  }
165 
166  bool state_has_name(state_t s) const
167  {
168  return has(origins(), s);
169  }
170 
171  std::ostream&
172  print_state_name(state_t s, std::ostream& o,
173  format fmt = {},
174  bool = false) const
175  {
176  auto name = origins().at(s);
177  aut_->print_state_name(name.first, o, fmt, true);
178  o << ':';
179  this->labelset()->print(name.second, o, fmt.for_labels());
180  return o;
181  }
182 
184  using origins_t = std::unordered_map<state_t, state_name_t>;
185  mutable origins_t origins_;
186 
187  const origins_t&
188  origins() const
189  {
190  if (origins_.empty())
191  for (const auto& p: map_)
192  origins_[p.second] = p.first;
193  return origins_;
194  }
195 
197  std::stack<state_name_t, std::vector<state_name_t>> todo_;
199  smap map_;
201  automaton_t aut_;
202  };
203 
204  template <Automaton Aut>
205  using synchronized_automaton
206  = std::shared_ptr<synchronized_automaton_impl<Aut>>;
207 
208  template <Automaton Aut>
209  class synchronizer
210  {
211  static_assert(context_t_of<Aut>::is_lat,
212  "synchronize: automaton labelset must be a tupleset");
213 
214  public:
215  using automaton_t = Aut;
216  using out_automaton_t = synchronized_automaton<automaton_t>;
217  using state_t = state_t_of<automaton_t>;
218  using labelset_t = labelset_t_of<out_automaton_t>;
219  using weightset_t = weightset_t_of<out_automaton_t>;
220  using label_t = typename labelset_t::value_t;
221  using state_name_t = typename out_automaton_t::element_type::state_name_t;
222 
224  template <std::size_t... I>
225  using seq = vcsn::detail::index_sequence<I...>;
226 
227  static constexpr size_t number_of_tapes = labelset_t_of<Aut>::size();
228 
229  using index_t = detail::make_index_sequence<number_of_tapes>;
230 
231  static constexpr index_t indices = {};
232 
233  template <size_t I>
234  using tape_labelset_t = typename labelset_t::template valueset_t<I>;
235 
236  synchronizer(const automaton_t& aut)
237  : in_aut_(aut), out_aut_(make_shared_ptr<out_automaton_t>(aut))
238  {}
239 
240  out_automaton_t synchronize()
241  {
242  while (!out_aut_->todo_.empty())
243  {
244  state_name_t st = std::move(out_aut_->todo_.top());
245  out_aut_->todo_.pop();
246  auto s = st.first;
247  label_t l = st.second;
248  if (in_aut_->is_final(s))
249  {
250  if (labelset_t::is_one(l))
251  out_aut_->set_final(st, in_aut_->get_final_weight(s));
252  else
253  {
254  auto f = state_name_t{s, labelset_t::one()};
255  // Create the state, don't add it to the todo list.
256  out_aut_->state(f, false);
257  out_aut_->new_transition(st, f, l,
258  in_aut_->get_final_weight(s));
259  out_aut_->set_final(f, weightset_t::one());
260  }
261  }
262 
263  for (auto tr : out(in_aut_, s))
264  {
265  label_t combined =
266  out_aut_->labelset()->mul(l,
267  out_aut_->labelset()->conv(*in_aut_->labelset(),
268  in_aut_->label_of(tr)));
269 
270  auto pre_suf = get_prefix(combined);
271  out_aut_->new_transition(st,
272  {in_aut_->dst_of(tr), pre_suf.second},
273  pre_suf.first,
274  in_aut_->weight_of(tr));
275  }
276  }
277  return out_aut_;
278  }
279 
280  private:
281 
282  std::pair<label_t, label_t>
283  get_prefix(const label_t& l)
284  {
285  return get_prefix(get_min_length(l), l);
286  }
287 
290  std::pair<label_t, label_t>
291  get_prefix(size_t length, const label_t& l)
292  {
293  auto ls = out_aut_->labelset();
294  auto prefix = labelset_t::one();
295  auto suffix = labelset_t::one();
296 
297  size_t i = 0;
298  for (auto letter :
299  ls->letters_of_padded(l,
301  {
302  if (i < length)
303  {
304  ++i;
305  prefix = ls->mul(prefix, letter);
306  }
307  else
308  suffix = ls->mul(suffix, letter);
309  }
310 
311  return {prefix, suffix};
312  }
313 
314  size_t
315  get_min_length(const label_t& l)
316  {
317  return get_min_length_(l, indices);
318  }
319 
320  template <size_t... I>
321  size_t
322  get_min_length_(const label_t& l, seq<I...>)
323  {
324  return std::min({tape_labelset_t<I>::size(std::get<I>(l))...});
325  }
328  };
329 
330  template <Automaton Aut>
332  synchronize(const Aut& aut)
333  {
334  synchronizer<Aut> s(aut);
335  return s.synchronize();
336  }
337 
338  }
339 
340  /*--------------.
341  | synchronize. |
342  `--------------*/
343 
348  template <Automaton Aut>
349  auto
350  synchronize(const Aut& aut)
351  -> decltype(detail::synchronize(aut))
352  {
353  return detail::synchronize(aut);
354  }
355 
356  namespace dyn
357  {
358  namespace detail
359  {
361  template <Automaton Aut>
363  {
364  return ::vcsn::synchronize(aut->as<Aut>());
365  }
366  }
367  }
368 }
constant< type_t::one, Context > one
Definition: fwd.hh:113
auto prefix(const Aut &aut) -> decltype(::vcsn::copy(aut))
Definition: prefix.hh:69
static labelset_t labelset_(const in_labelset_t &ls, seq< I... >)
Definition: synchronize.hh:44
out_automaton_t out_aut_
Definition: synchronize.hh:327
return res
Definition: multiply.hh:398
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
An automaton whose states may be qualified by delays and/or prefixes.
Definition: fwd.hh:85
A traits to compute the letterized context.
Definition: labelset.hh:80
fresh_worded_automaton_t< Aut > fresh_t
Definition: synchronize.hh:86
Aggregate an automaton, and forward calls to it.
An input/output format for valuesets.
Definition: format.hh:13
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: synchronize.hh:118
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:62
typename Aut::element_type::template fresh_automaton_t< Context > fresh_automaton_t_of
Given an automaton type, the type of its copies.
Definition: traits.hh:82
context_t_of< in_automaton_t > in_context_t
Definition: synchronize.hh:50
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
return exp min
Definition: multiply.hh:361
std::pair< label_t, label_t > get_prefix(size_t length, const label_t &l)
Split the label in prefix/suffix, with the prefix of size length.
Definition: synchronize.hh:291
labelset_t_of< in_automaton_t > in_labelset_t
Definition: synchronize.hh:51
Definition: a-star.hh:8
auto suffix(const Aut &aut) -> decltype(::vcsn::copy(aut))
Definition: prefix.hh:29
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:85
static symbol sname()
Static name.
Definition: synchronize.hh:110
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
synchronized_automaton_impl(const automaton_t &aut)
Definition: synchronize.hh:101
size_t get_min_length(const label_t &l)
Definition: synchronize.hh:315
out_automaton_t synchronize()
Definition: synchronize.hh:240
automaton synchronize(const automaton &aut)
Bridge.
Definition: synchronize.hh:362
labelset_t_of< super_t > labelset_t
Definition: synchronize.hh:89
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
Definition: traits.hh:66
std::pair< label_t, label_t > get_prefix(const label_t &l)
Definition: synchronize.hh:283
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
weightset_t_of< in_automaton_t > weightset_t
Weightset of the worded automaton (same as input)
Definition: synchronize.hh:54
A dyn automaton.
Definition: automaton.hh:17
static labelset_t labelset(const in_labelset_t &ls)
Create the worded labelset from the original one.
Definition: synchronize.hh:64
mutable_automaton< context_t > automaton_t
Type of the worded automaton.
Definition: synchronize.hh:61
std::pair< state_t_of< automaton_t >, label_t > state_name_t
State + delay.
Definition: synchronize.hh:96
symbol sname()
Definition: name.hh:65
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
An exponent, or range of exponents.
Definition: to.hh:25
typename worded_labelset< in_labelset_t >::labelset_t labelset_t
Labelset of the worded automaton.
Definition: synchronize.hh:57
size_t get_min_length_(const label_t &l, seq< I... >)
Definition: synchronize.hh:322
weightset_t_of< super_t > weightset_t
Definition: synchronize.hh:91
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
std::ostream & list(const PolynomialSet &ps, const typename PolynomialSet::value_t &p, std::ostream &o=std::cout)
Definition: print.hh:249
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:61
synchronized_automaton< automaton_t > out_automaton_t
Definition: synchronize.hh:216
fresh_automaton_t_of< typename worded_automaton< Aut >::automaton_t > fresh_worded_automaton_t
Definition: synchronize.hh:72
law_t< LabelSet > make_wordset(const LabelSet &ls)
The wordset of a labelset.
Definition: labelset.hh:260
typename labelset_t::template valueset_t< I > tape_labelset_t
Definition: synchronize.hh:99