3 #include <unordered_map>
5 #include <boost/bimap.hpp>
6 #include <boost/bimap/unordered_set_of.hpp>
10 #include <vcsn/algos/fwd.hh>
21 template <Automaton Aut,
bool HasOne>
34 using state_t =
typename super_t::state_t;
35 using label_t =
typename super_t::label_t;
39 using state_name_t = std::pair<state_t, bool>;
43 using bimap_t = boost::bimap<boost::bimaps::unordered_set_of<state_name_t>,
44 boost::bimaps::unordered_set_of<state_t>>;
45 using map_t =
typename bimap_t::left_map;
46 using origins_t =
typename bimap_t::right_map;
58 o <<
"insplit_automaton<";
59 return aut_->print_set(o, fmt) <<
">";
79 while (!todo_.empty())
81 const auto& p = todo_.front();
82 this->complete_(std::get<1>(p));
87 void add_transitions(
const state_t src,
88 const state_name_t& psrc)
90 add_insplit_transitions(src, psrc);
95 format fmt = {},
bool delimit =
false)
98 const auto& orig = origins();
99 auto i = orig.find(s);
106 aut_in()->print_state_name(i->second.first, o, fmt,
true);
109 o << (i->second.second ?
"" :
"\\not ") <<
"\\varepsilon";
111 o << (i->second.second ?
"ε" :
"!ε");
113 o << (i->second.second ?
"\\e" :
"!\\e");
126 return !
has(done_, s);
130 void complete_(
state_t s)
const
132 const auto& orig = origins();
133 state_name_t sn = orig.at(s);
134 const_cast<self_t&
>(*this).add_transitions(s, sn);
141 -> decltype(
aut_->all_out(s))
145 return aut_->all_out(s);
149 out_automaton_t& aut_out()
155 const out_automaton_t& aut_out()
const
176 void initialize_insplit()
178 pmap_().insert({state_name_t(aut_in()->
pre(),
false), aut_out()->pre()});
179 pmap_().insert({state_name_t(aut_in()->
post(),
false), aut_out()->post()});
180 todo_.emplace_back(pre_(),
aut_->pre());
183 state_name_t pre_()
const
185 return {
aut_->pre(),
false};
188 void add_insplit_transitions(
const state_t st,
189 const state_name_t& psrc)
191 for (
auto t : aut_in()->
all_out(std::get<0>(psrc)))
192 aut_out()->new_transition_copy(st,
193 state({aut_in()->dst_of(t),
200 return pmap_().find(state_name_t(st, epsilon)) != pmap_().end();
206 return aut_in()->labelset()->is_one(aut_in()->
label_of(tr));
215 state_t state(
const state_name_t& state)
217 auto lb = pmap_().find(state);
218 if (lb == pmap_().end())
221 lb = pmap_().insert(lb, {state, s});
222 todo_.emplace_back(state, s);
244 mutable bimap_t bimap_;
249 mutable std::set<state_t> done_ = {
aut_->post()};
252 std::deque<std::pair<state_name_t, state_t>> todo_;
255 template <Automaton Aut>
289 template<Automaton Aut>
292 -> std::enable_if_t<labelset_t_of<Aut>::has_one(),
300 template <Automaton Aut>
301 std::enable_if_t<!labelset_t_of<Aut>::has_one(), Aut>
310 template <Automaton Aut>
312 = std::shared_ptr<detail::insplit_automaton_impl<Aut, labelset_t_of<Aut>::has_one()>>;
314 template <Automaton Aut>
319 return make_shared_ptr<insplit_automaton<Aut>>(aut);
322 template <Automaton Aut>
333 template <Automaton Aut>
347 template <Automaton Aut,
typename Bool>
351 const auto& a = aut->as<Aut>();
insplit_automaton_impl(const Aut &aut)
automaton insplit(const automaton &aut, bool lazy)
Bridge.
auto insplit(const Aut &aut) -> decltype(detail::insplit(aut))
Print as rich UTF-8 text, escaped.
std::shared_ptr< detail::insplit_automaton_impl< Aut, labelset_t_of< Aut >::has_one()>> insplit_automaton
A compose automaton as a shared pointer.
transition_t_of< automaton_t > transition_t
state_t_of< automaton_t > state_t
static constexpr auto pre(Args &&...args) -> decltype(element_type::pre(std::forward< Args >(args)...))
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
static constexpr auto post(Args &&...args) -> decltype(element_type::post(std::forward< Args >(args)...))
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
const automaton_t & aut_out() const
Aut automaton_t
The type of automaton to wrap.
automaton_t aut_
The wrapped automaton, possibly const.
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
An input/output format for valuesets.
bool exists(const path &p)
auto insplit(Aut &aut) -> std::enable_if_t< labelset_t_of< Aut >::has_one(), decltype(make_insplit_automaton(aut))>
auto make_insplit_automaton(const Aut &aut) -> insplit_automaton< Aut >
auto insplit_lazy(const Aut &aut) -> decltype(make_insplit_automaton(aut))
typename labelset_t::value_t label_t
auto is_lazy(Args &&...args) const -> decltype(aut_-> is_lazy(std::forward< Args >(args)...))
typename Aut::element_type::template fresh_automaton_t< Context > fresh_automaton_t_of
Given an automaton type, the type of its copies.
auto all_out(Args &&...args) const -> decltype(aut_-> all_out(std::forward< Args >(args)...))
Aggregate an automaton, and forward calls to it.
static constexpr auto sname(Args &&...args) -> decltype(element_type::sname(std::forward< Args >(args)...))
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
auto print_set(Args &&...args) const -> decltype(aut_-> print_set(std::forward< Args >(args)...))
auto print_state(Args &&...args) const -> decltype(aut_-> print_state(std::forward< Args >(args)...))
auto label_of(Args &&...args) const -> decltype(aut_-> label_of(std::forward< Args >(args)...))
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
auto print_state_name(Args &&...args) const -> decltype(aut_-> print_state_name(std::forward< Args >(args)...))
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
auto state_has_name(Args &&...args) const -> decltype(aut_-> state_has_name(std::forward< Args >(args)...))
typename context_t::weightset_t weightset_t
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
std::shared_ptr< detail::automaton_base > automaton