Vcsn  2.2
Be Rational
insplit.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <unordered_map>
4 
5 #include <boost/bimap.hpp>
6 #include <boost/bimap/unordered_set_of.hpp>
7 
8 #include <vcsn/dyn/automaton.hh> // dyn::make_automaton
9 #include <vcsn/algos/copy.hh> // real_context
10 #include <vcsn/algos/fwd.hh>
11 #include <vcsn/misc/bimap.hh>
12 #include <vcsn/misc/pair.hh>
13 #include <vcsn/misc/memory.hh>
14 
15 namespace vcsn
16 {
17 
18  namespace detail
19  {
20 
21  template <Automaton Aut, bool HasOne>
23  : public automaton_decorator<fresh_automaton_t_of<Aut>>
24  {
25  static_assert(labelset_t_of<Aut>::has_one(), "insplit: the labelset must have a one label");
26  public:
27  using automaton_t = Aut;
29 
31 
33 
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>;
40 
41  using super_t::aut_;
42 
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;
47 
48 
49 
50  static symbol sname()
51  {
52  static symbol res("insplit_automaton<" + Aut::element_type::sname() + ">");
53  return res;
54  }
55 
56  std::ostream& print_set(std::ostream& o, format fmt = {}) const
57  {
58  o << "insplit_automaton<";
59  return aut_->print_set(o, fmt) << ">";
60  }
61 
62  insplit_automaton_impl(const Aut& aut)
64  , in_(aut)
65  {}
66 
67  static constexpr bool
69  {
70  return true;
71  }
72 
73 
74  void insplit(bool lazy = false)
75  {
77 
78  if (!lazy)
79  while (!todo_.empty())
80  {
81  const auto& p = todo_.front();
82  this->complete_(std::get<1>(p));
83  todo_.pop_front();
84  }
85  }
86 
87  void add_transitions(const state_t src,
88  const state_name_t& psrc)
89  {
90  add_insplit_transitions(src, psrc);
91  }
92 
93  std::ostream&
94  print_state_name(state_t s, std::ostream& o,
95  format fmt = {}, bool delimit = false)
96  const
97  {
98  const auto& orig = origins();
99  auto i = orig.find(s);
100  if (i == orig.end())
101  this->print_state(s, o);
102  else
103  {
104  if (delimit)
105  o << '(';
106  aut_in()->print_state_name(i->second.first, o, fmt, true);
107  o << ", ";
108  if (fmt == format::latex)
109  o << (i->second.second ? "" : "\\not ") << "\\varepsilon";
110  else if (fmt == format::utf8)
111  o << (i->second.second ? "ε" : "!ε");
112  else
113  o << (i->second.second ? "\\e" : "!\\e");
114  if (delimit)
115  o << ')';
116  }
117  return o;
118  }
119 
120  // Lazy
121 
124  bool is_lazy(state_t s) const
125  {
126  return !has(done_, s);
127  }
128 
130  void complete_(state_t s) const
131  {
132  const auto& orig = origins();
133  state_name_t sn = orig.at(s);
134  const_cast<self_t&>(*this).add_transitions(s, sn);
135  done_.insert(s);
136  }
137 
139  using super_t::all_out;
140  auto all_out(state_t s) const
141  -> decltype(aut_->all_out(s))
142  {
143  if (is_lazy(s))
144  complete_(s);
145  return aut_->all_out(s);
146  }
147 
148  // FIXME: make private
150  {
151  return aut_;
152  }
153 
154  // FIXME: return shared_ptr to const automaton_impl?
155  const out_automaton_t& aut_out() const
156  {
157  return aut_;
158  }
159 
162  const origins_t&
163  origins() const
164  {
165  return bimap_.right;
166  }
167 
168 
169  private:
170 
171  const automaton_t& aut_in() const
172  {
173  return in_;
174  }
175 
177  {
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());
181  }
182 
184  {
185  return {aut_->pre(), false};
186  }
187 
189  const state_name_t& psrc)
190  {
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),
194  is_spontaneous(t)}),
195  aut_in(), t);
196  }
197 
198  inline bool exists(state_t st, bool epsilon)
199  {
200  return pmap_().find(state_name_t(st, epsilon)) != pmap_().end();
201  }
202 
203  bool
205  {
206  return aut_in()->labelset()->is_one(aut_in()->label_of(tr));
207  }
208 
216  {
217  auto lb = pmap_().find(state);
218  if (lb == pmap_().end())
219  {
220  state_t s = aut_->new_state();
221  lb = pmap_().insert(lb, {state, s});
222  todo_.emplace_back(state, s);
223  }
224  return lb->second;
225  }
226 
229  map_t&
231  {
232  return bimap_.left;
233  }
234 
237 
239  const weightset_t& ws_ = *aut_->weightset();
240 
244  mutable bimap_t bimap_;
245 
249  mutable std::set<state_t> done_ = {aut_->post()};
250 
252  std::deque<std::pair<state_name_t, state_t>> todo_;
253  };
254 
255  template <Automaton Aut>
256  class insplit_automaton_impl<Aut, false>
257  : public automaton_decorator<Aut>
258  {
260  public:
261  insplit_automaton_impl(const Aut& aut)
262  : super_t(aut)
263  {}
264 
265  static symbol sname()
266  {
267  static symbol res("insplit_automaton<" + Aut::element_type::sname() + ">");
268  return res;
269  }
270 
271  using automaton_t = Aut;
272 
273  using super_t::aut_;
274 
275  void insplit(bool = false)
276  {}
277 
279  {
280  return aut_;
281  }
282 
283  const automaton_t& aut_out() const
284  {
285  return aut_;
286  }
287  };
288 
289  template<Automaton Aut>
290  auto
291  insplit(Aut& aut)
292  -> std::enable_if_t<labelset_t_of<Aut>::has_one(),
293  decltype(make_insplit_automaton(aut))>
294  {
295  auto res = make_insplit_automaton(aut);
296  res->insplit(false);
297  return res;
298  }
299 
300  template <Automaton Aut>
301  std::enable_if_t<!labelset_t_of<Aut>::has_one(), Aut>
302  insplit(Aut& aut)
303  {
304  return aut;
305  }
306 
307  } // namespace detail
308 
310  template <Automaton Aut>
311  using insplit_automaton
312  = std::shared_ptr<detail::insplit_automaton_impl<Aut, labelset_t_of<Aut>::has_one()>>;
313 
314  template <Automaton Aut>
315  auto
316  make_insplit_automaton(const Aut& aut)
318  {
319  return make_shared_ptr<insplit_automaton<Aut>>(aut);
320  }
321 
322  template <Automaton Aut>
323  inline
324  auto
325  insplit_lazy(const Aut& aut)
326  -> decltype(make_insplit_automaton(aut))
327  {
328  auto res = make_insplit_automaton(aut);
329  res->insplit(true);
330  return res;
331  }
332 
333  template <Automaton Aut>
334  inline
335  auto
336  insplit(const Aut& aut)
337  -> decltype(detail::insplit(aut))
338  {
339  return detail::insplit(aut);
340  }
341 
342  namespace dyn
343  {
344  namespace detail
345  {
347  template <Automaton Aut, typename Bool>
348  automaton
349  insplit(const automaton& aut, bool lazy)
350  {
351  const auto& a = aut->as<Aut>();
352  if (lazy)
353  return make_automaton(::vcsn::insplit_lazy(a));
354  else
355  return make_automaton(::vcsn::insplit(a));
356  }
357  }
358  }
359 
360 } // namespace vcsn
std::shared_ptr< detail::insplit_automaton_impl< Aut, labelset_t_of< Aut >::has_one()>> insplit_automaton
A compose automaton as a shared pointer.
Definition: insplit.hh:312
void complete_(state_t s) const
Complete a state: find its outgoing transitions.
Definition: insplit.hh:130
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: insplit.hh:56
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:75
Print as rich UTF-8 text, escaped.
Definition: format.hh:28
state_name_t pre_() const
Definition: insplit.hh:183
automaton_t in_
The input automaton.
Definition: insplit.hh:236
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
insplit_automaton_impl(const Aut &aut)
Definition: insplit.hh:62
transition_t_of< automaton_t > transition_t
state_t_of< automaton_t > state_t
typename super_t::label_t label_t
Definition: insplit.hh:35
bool is_lazy(state_t s) const
Whether a given state's outgoing transitions have been computed.
Definition: insplit.hh:124
Definition: a-star.hh:8
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 insplit(const Aut &aut) -> decltype(detail::insplit(aut))
Definition: insplit.hh:336
std::deque< std::pair< state_name_t, state_t > > todo_
Worklist of state tuples.
Definition: insplit.hh:252
map_t & pmap_()
A map from original state and status (spontaneous or proper state) to result state.
Definition: insplit.hh:230
Print for LaTeX.
Definition: format.hh:20
boost::bimap< boost::bimaps::unordered_set_of< state_name_t >, boost::bimaps::unordered_set_of< state_t >> bimap_t
Definition: insplit.hh:44
automaton_t aut_
The wrapped automaton, possibly const.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
auto insplit(Aut &aut) -> std::enable_if_t< labelset_t_of< Aut >::has_one(), decltype(make_insplit_automaton(aut))>
Definition: insplit.hh:291
An input/output format for valuesets.
Definition: format.hh:11
void add_insplit_transitions(const state_t st, const state_name_t &psrc)
Definition: insplit.hh:188
auto insplit_lazy(const Aut &aut) -> decltype(make_insplit_automaton(aut))
Definition: insplit.hh:325
bool exists(state_t st, bool epsilon)
Definition: insplit.hh:198
static constexpr bool state_has_name(state_t)
Definition: insplit.hh:68
typename super_t::transition_t transition_t
Definition: insplit.hh:36
bimap_t bimap_
Map input-state, status -> result-state.
Definition: insplit.hh:244
typename super_t::state_t state_t
Definition: insplit.hh:34
auto print_state(Args &&...args) const -> decltype(aut_-> print_state(std::forward< Args >(args)...))
typename labelset_t::value_t label_t
weightset_t_of< Aut > weightset_t
Definition: insplit.hh:37
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
Aggregate an automaton, and forward calls to it.
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:74
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
bool is_spontaneous(transition_t tr)
Definition: insplit.hh:204
symbol sname()
Definition: name.hh:67
std::ostream & print_state_name(state_t s, std::ostream &o, format fmt={}, bool delimit=false) const
Definition: insplit.hh:94
state_t state(const state_name_t &state)
The state in the insplit corresponding to a state and a status (spontaneous or proper state)...
Definition: insplit.hh:215
const automaton_t & aut_in() const
Definition: insplit.hh:171
auto all_out(Args &&...args) const -> decltype(aut_-> all_out(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.
Definition: setalpha.hh:25
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
Definition: copy.hh:90
void add_transitions(const state_t src, const state_name_t &psrc)
Definition: insplit.hh:87
typename bimap_t::right_map origins_t
Definition: insplit.hh:46
void insplit(bool lazy=false)
Definition: insplit.hh:74
const out_automaton_t & aut_out() const
Definition: insplit.hh:155
typename bimap_t::left_map map_t
Definition: insplit.hh:45
automaton insplit(const automaton &aut, bool lazy)
Bridge.
Definition: insplit.hh:349
auto make_insplit_automaton(const Aut &aut) -> insplit_automaton< Aut >
Definition: insplit.hh:316
std::set< state_t > done_
When performing the lazy construction, list of states that have been completed (i.e., their outgoing transitions have been computed).
Definition: insplit.hh:249
auto all_out(state_t s) const -> decltype(aut_->all_out(s))
Definition: insplit.hh:140
std::pair< state_t, bool > state_name_t
Tuple of states of input automata.
Definition: insplit.hh:39
fresh_automaton_t_of< Aut > out_automaton_t
Definition: insplit.hh:28
const weightset_t & ws_
The resulting weightset.
Definition: insplit.hh:239
auto label_of(Args &&...args) const -> decltype(aut_-> label_of(std::forward< Args >(args)...))
const origins_t & origins() const
A map from result state to original state and status (spontaneous or proper state).
Definition: insplit.hh:163