5 #include <unordered_map>
7 #include <boost/bimap.hpp>
8 #include <boost/bimap/unordered_set_of.hpp>
10 #include <vcsn/algos/fwd.hh>
30 template <Automaton Aut>
31 class delay_automaton_impl
32 :
public automaton_decorator<fresh_automaton_t_of<Aut>>
44 template <std::size_t... I>
54 using delay_t = std::array<size_t, number_of_tapes>;
60 using bimap_t = boost::bimap<boost::bimaps::unordered_set_of<state_name_t>, boost::bimaps::unordered_set_of<state_t>>;
61 using map_t =
typename bimap_t::left_map;
78 static auto res =
symbol{
"delay_automaton<"
85 o <<
"delay_automaton<";
92 state_t state(const state_name_t& r)
94 if (r.first == aut_->post())
97 auto i = map_().find(r);
98 if (i == std::end(map_()))
100 res = super_t::new_state();
101 // Emplace is not available because of the internals of bimap
102 map_().insert({r, res});
110 using super_t::new_transition;
113 new_transition(const state_name_t& src, const state_name_t& dst,
114 const label_t& l, const weight_t& w)
116 super_t::new_transition(state(src), state(dst), l, w);
119 bool state_has_name(state_t s) const
121 return has(origins(), s);
125 print_state_name(state_t s, std::ostream& o,
129 auto ns = origins().at(s);
130 aut_->print_state_name(ns.first, o, fmt, true);
133 for (int i = 0; i < a.size() - 1; i++)
136 o << a[a.size() - 1];
141 delay_t delay_of(state_t s)
143 auto i = origins().find(s);
144 if (i == std::end(origins()))
147 return i->second.second;
163 std::stack<state_name_t, std::vector<state_name_t>> todo_;
170 template <Automaton Aut>
171 class synchronize_checker
173 static_assert(context_t_of<Aut>::is_lat,
174 "synchronize: automaton labelset must be a tupleset");
177 using automaton_t = Aut;
178 using out_automaton_t = delay_automaton<automaton_t>;
179 using state_t = state_t_of<automaton_t>;
180 using labelset_t = labelset_t_of<out_automaton_t>;
181 using label_t = typename labelset_t::value_t;
182 using delay_t = typename out_automaton_t::element_type::delay_t;
183 using state_name_t = typename out_automaton_t::element_type::state_name_t;
186 using tape_labelset_t = typename labelset_t::template valueset_t<I>;
189 template <std::size_t... I>
190 using seq = vcsn::detail::index_sequence<I...>;
193 synchronize_checker(const automaton_t& aut)
194 : in_aut_(aut), out_aut_(make_shared_ptr<out_automaton_t>(aut))
204 bool is_synchronized()
206 // tag the states with the delays
208 for (auto s : out_aut_->states())
210 delay_t d = out_aut_->delay_of(s);
212 for (auto tr : out(out_aut_, s))
214 if (out_aut_->labelset()->is_one(out_aut_->label_of(tr)))
216 auto dst = out_aut_->dst_of(tr);
217 if (out_aut_->post() == dst)
219 delay_t dst_d = out_aut_->delay_of(dst);
220 for (size_t i = 0; i < out_aut_->number_of_tapes; i++) {
221 if (d[i] && dst_d[i] <= d[i])
230 make_delay_automaton()
239 * Compute the automaton with states tagged with their delays.
241 * If split, create the artificial states required for synchronizing.
243 void value_automaton()
245 out_aut_->todo_.emplace(in_aut_->pre(), delay_t{});
247 while (!out_aut_->todo_.empty())
249 auto val_state = std::move(out_aut_->todo_.top());
250 auto st = val_state.first;
251 delay_t delay = val_state.second;
252 out_aut_->todo_.pop();
253 for (auto t : all_out(in_aut_, st))
255 auto l = in_aut_->label_of(t);
256 auto dst = in_aut_->dst_of(t);
257 delay_t d = add_delay_(delay, l, out_aut_->indices);
258 state_name_t new_state(dst, d);
259 out_aut_->new_transition(val_state,
262 in_aut_->weight_of(t));
268 template <size_t... I>
270 add_delay_(delay_t d, const label_t& l, seq<I...>) const
273 = {(std::get<I>(d) + tape_labelset_t<I>::size(std::get<I>(l)))...};
274 size_t min = *std::min_element(begin(del), end(del));
275 return {(std::get<I>(del) - min)...};
279 out_automaton_t out_aut_;
282 template <Automaton Aut>
283 bool is_synchronized(const Aut& aut)
285 synchronize_checker<Aut> s(aut);
286 return s.is_synchronized();
289 template <Automaton Aut>
291 make_delay_automaton(const Aut& aut)
293 synchronize_checker<Aut> s(aut);
294 return s.make_delay_automaton();
299 /*------------------.
301 `------------------*/
307 template <Automaton Aut>
309 is_synchronized(const Aut& aut)
311 return detail::is_synchronized(aut);
319 template <Automaton Aut>
320 bool is_synchronized(const automaton& aut)
322 return vcsn::is_synchronized(aut->as<Aut>());
327 /*------------------.
329 `------------------*/
335 template <Automaton Aut>
337 make_delay_automaton(const Aut& aut)
338 -> decltype(detail::make_delay_automaton(aut))
340 return detail::make_delay_automaton(aut);
348 template <Automaton Aut>
349 automaton delay_automaton(const automaton& aut)
351 return vcsn::make_delay_automaton(aut->as<Aut>());
std::ostream & print_set(std::ostream &o, format fmt={}) const
state_t_of< super_t > state_t
static constexpr auto pre(Args &&...args) -> decltype(element_type::pre(std::forward< Args >(args)...))
context_t_of< super_t > context_t
typename labelset_t::template valueset_t< I > tape_labelset_t
automaton_t aut_
The original automaton.
std::array< size_t, number_of_tapes > delay_t
The delay associated with each state.
label_t_of< super_t > label_t
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Aggregate an automaton, and forward calls to it.
An input/output format for valuesets.
auto print_set(Args &&...args) const -> decltype(aut_-> print_set(std::forward< Args >(args)...))
delay_automaton_impl(const automaton_t &aut)
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
typename bimap_t::left_map map_t
static constexpr size_t number_of_tapes
static constexpr auto post(Args &&...args) -> decltype(element_type::post(std::forward< Args >(args)...))
static symbol sname()
Static name.
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
labelset_t_of< super_t > labelset_t
static constexpr index_t indices
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
weight_t_of< super_t > weight_t
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
boost::bimap< boost::bimaps::unordered_set_of< state_name_t >, boost::bimaps::unordered_set_of< state_t >> bimap_t
Symbolic states to state handlers.
typename bimap_t::right_map origins_t
std::pair< state_t, delay_t > state_name_t
State + delay.
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of