Vcsn  2.2
Be Rational
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
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;
28  using out_automaton_t = fresh_automaton_t_of<Aut>;
29 
30  using self_t = insplit_automaton_impl;
31 
33 
34  using state_t = typename super_t::state_t;
35  using label_t = typename super_t::label_t;
36  using transition_t = typename super_t::transition_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)
63  : super_t(make_fresh_automaton(aut))
64  , in_(aut)
65  {}
66 
67  static constexpr bool
69  {
70  return true;
71  }
72 
73 
74  void insplit(bool lazy = false)
75  {
76  initialize_insplit();
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
149  out_automaton_t& aut_out()
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 
176  void initialize_insplit()
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 
183  state_name_t pre_() const
184  {
185  return {aut_->pre(), false};
186  }
187 
188  void add_insplit_transitions(const state_t st,
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
204  is_spontaneous(transition_t tr)
205  {
206  return aut_in()->labelset()->is_one(aut_in()->label_of(tr));
207  }
208 
215  state_t state(const state_name_t& state)
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&
230  pmap_()
231  {
232  return bimap_.left;
233  }
234 
236  automaton_t in_;
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
automaton insplit(const automaton &aut, bool lazy)
Bridge.
Definition: insplit.hh:349
Definition: a-star.hh:8
auto insplit(const Aut &aut) -> decltype(detail::insplit(aut))
Definition: insplit.hh:336
Print as rich UTF-8 text, escaped.
Definition: format.hh:28
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
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.
Definition: copy.hh:90
static constexpr auto post(Args &&...args) -> decltype(element_type::post(std::forward< Args >(args)...))
Print for LaTeX.
Definition: format.hh:20
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
automaton_t aut_
The wrapped automaton, possibly const.
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:75
An input/output format for valuesets.
Definition: format.hh:11
bool exists(const path &p)
Definition: path.cc:98
auto insplit(Aut &aut) -> std::enable_if_t< labelset_t_of< Aut >::has_one(), decltype(make_insplit_automaton(aut))>
Definition: insplit.hh:291
auto make_insplit_automaton(const Aut &aut) -> insplit_automaton< Aut >
Definition: insplit.hh:316
auto insplit_lazy(const Aut &aut) -> decltype(make_insplit_automaton(aut))
Definition: insplit.hh:325
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.
Definition: traits.hh:74
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
Definition: traits.hh:59
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)...))
symbol sname()
Definition: name.hh:67
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
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.
Definition: symbol.hh:23
auto state_has_name(Args &&...args) const -> decltype(aut_-> state_has_name(std::forward< Args >(args)...))
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:37
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69