5 #include <unordered_map>
7 #include <boost/bimap.hpp>
8 #include <boost/bimap/unordered_set_of.hpp>
10 #include <vcsn/algos/fwd.hh>
31 template <Automaton Aut>
32 class delay_automaton_impl
33 :
public automaton_decorator<fresh_automaton_t_of<Aut>>
45 template <std::size_t... I>
55 using delay_t = std::array<size_t, number_of_tapes>;
61 using bimap_t = boost::bimap<boost::bimaps::unordered_set_of<state_name_t>, boost::bimaps::unordered_set_of<state_t>>;
62 using map_t =
typename bimap_t::left_map;
79 static auto res =
symbol{
"delay_automaton<"
86 o <<
"delay_automaton<";
93 state_t state(const state_name_t& r)
95 if (r.first == aut_->post())
98 auto i = map_().find(r);
99 if (i == std::end(map_()))
101 res = super_t::new_state();
102 // Emplace is not available because of the internals of bimap
103 map_().insert({r, res});
111 using super_t::new_transition;
114 new_transition(const state_name_t& src, const state_name_t& dst,
115 const label_t& l, const weight_t& w)
117 super_t::new_transition(state(src), state(dst), l, w);
120 bool state_has_name(state_t s) const
122 return has(origins(), s);
126 print_state_name(state_t s, std::ostream& o,
130 auto ns = origins().at(s);
131 aut_->print_state_name(ns.first, o, fmt, true);
134 for (int i = 0; i < a.size() - 1; i++)
137 o << a[a.size() - 1];
142 delay_t delay_of(state_t s)
144 auto i = origins().find(s);
145 if (i == std::end(origins()))
148 return i->second.second;
164 std::stack<state_name_t, std::vector<state_name_t>> todo_;
171 template <Automaton Aut>
172 class synchronize_checker
174 static_assert(context_t_of<Aut>::is_lat,
175 "synchronize: automaton labelset must be a tupleset");
178 using automaton_t = Aut;
179 using out_automaton_t = delay_automaton<automaton_t>;
180 using state_t = state_t_of<automaton_t>;
181 using labelset_t = labelset_t_of<out_automaton_t>;
182 using label_t = typename labelset_t::value_t;
183 using delay_t = typename out_automaton_t::element_type::delay_t;
184 using state_name_t = typename out_automaton_t::element_type::state_name_t;
187 using tape_labelset_t = typename labelset_t::template valueset_t<I>;
190 template <std::size_t... I>
191 using seq = vcsn::detail::index_sequence<I...>;
194 synchronize_checker(const automaton_t& aut)
195 : in_aut_(aut), out_aut_(make_shared_ptr<out_automaton_t>(aut))
205 bool is_synchronized()
207 // tag the states with the delays
209 for (auto s : out_aut_->states())
211 delay_t d = out_aut_->delay_of(s);
213 for (auto tr : out(out_aut_, s))
215 if (out_aut_->labelset()->is_one(out_aut_->label_of(tr)))
217 auto dst = out_aut_->dst_of(tr);
218 if (out_aut_->post() == dst)
220 delay_t dst_d = out_aut_->delay_of(dst);
221 for (size_t i = 0; i < out_aut_->number_of_tapes; i++) {
222 if (d[i] && dst_d[i] <= d[i])
231 make_delay_automaton()
240 * Compute the automaton with states tagged with their delays.
242 * If split, create the artificial states required for synchronizing.
244 void value_automaton()
246 out_aut_->todo_.emplace(in_aut_->pre(), delay_t{});
248 while (!out_aut_->todo_.empty())
250 auto val_state = std::move(out_aut_->todo_.top());
251 auto st = val_state.first;
252 delay_t delay = val_state.second;
253 out_aut_->todo_.pop();
254 for (auto t : all_out(in_aut_, st))
256 auto l = in_aut_->label_of(t);
257 auto dst = in_aut_->dst_of(t);
258 delay_t d = add_delay_(delay, l, out_aut_->indices);
259 state_name_t new_state(dst, d);
260 out_aut_->new_transition(val_state,
263 in_aut_->weight_of(t));
269 template <size_t... I>
271 add_delay_(delay_t d, const label_t& l, seq<I...>) const
274 = {(std::get<I>(d) + tape_labelset_t<I>::size(std::get<I>(l)))...};
275 size_t min = *std::min_element(begin(del), end(del));
276 return {(std::get<I>(del) - min)...};
280 out_automaton_t out_aut_;
283 template <Automaton Aut>
284 bool is_synchronized(const Aut& aut)
286 synchronize_checker<Aut> s(aut);
287 return s.is_synchronized();
290 template <Automaton Aut>
292 make_delay_automaton(const Aut& aut)
294 synchronize_checker<Aut> s(aut);
295 return s.make_delay_automaton();
300 /*------------------.
302 `------------------*/
308 template <Automaton Aut>
310 is_synchronized(const Aut& aut)
312 return detail::is_synchronized(aut);
320 template <Automaton Aut>
321 bool is_synchronized(const automaton& aut)
323 return vcsn::is_synchronized(aut->as<Aut>());
328 /*------------------.
330 `------------------*/
336 template <Automaton Aut>
338 make_delay_automaton(const Aut& aut)
339 -> decltype(detail::make_delay_automaton(aut))
341 return detail::make_delay_automaton(aut);
349 template <Automaton Aut>
350 automaton delay_automaton(const automaton& aut)
352 return make_automaton(vcsn::make_delay_automaton(aut->as<Aut>()));
typename labelset_t::template valueset_t< I > tape_labelset_t
static symbol sname()
Static name.
static constexpr auto pre(Args &&...args) -> decltype(element_type::pre(std::forward< Args >(args)...))
static constexpr auto post(Args &&...args) -> decltype(element_type::post(std::forward< Args >(args)...))
auto print_set(Args &&...args) const -> decltype(aut_-> print_set(std::forward< Args >(args)...))
typename bimap_t::right_map origins_t
label_t_of< super_t > label_t
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
An input/output format for valuesets.
std::pair< state_t, delay_t > state_name_t
State + delay.
typename detail::weight_t_of_impl< base_t< ValueSet >>::type weight_t_of
typename bimap_t::left_map map_t
labelset_t_of< super_t > labelset_t
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
context_t_of< super_t > context_t
boost::bimap< boost::bimaps::unordered_set_of< state_name_t >, boost::bimaps::unordered_set_of< state_t >> bimap_t
Symbolic states to state handlers.
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
static constexpr index_t indices
Aggregate an automaton, and forward calls to it.
state_t_of< super_t > state_t
static constexpr size_t number_of_tapes
std::array< size_t, number_of_tapes > delay_t
The delay associated with each state.
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
delay_automaton_impl(const automaton_t &aut)
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
std::ostream & print_set(std::ostream &o, format fmt={}) const
automaton_t aut_
The original automaton.
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
weight_t_of< super_t > weight_t