Vcsn  2.3
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  {
28  template <Automaton Aut>
30  : public automaton_decorator<fresh_automaton_t_of<Aut>>
31  {
32  static_assert(labelset_t_of<Aut>::has_one(),
33  "insplit: the labelset must have a one label");
34 
35  public:
36  using automaton_t = Aut;
38 
40 
42 
43  using state_t = typename super_t::state_t;
44  using label_t = typename super_t::label_t;
48  using state_name_t = std::pair<state_t, bool>;
49 
50  using super_t::aut_;
51 
52  using bimap_t
53  = boost::bimap<boost::bimaps::unordered_set_of<state_name_t>,
54  boost::bimaps::unordered_set_of<state_t>>;
55  using map_t = typename bimap_t::left_map;
56  using origins_t = typename bimap_t::right_map;
57 
58 
59  static symbol sname()
60  {
61  static symbol res("insplit_automaton<"
63  + ">");
64  return res;
65  }
66 
67  std::ostream& print_set(std::ostream& o, format fmt = {}) const
68  {
69  o << "insplit_automaton<";
70  return aut_->print_set(o, fmt) << ">";
71  }
72 
73  insplit_automaton_impl(const Aut& aut)
75  , in_(aut)
76  {}
77 
78  static constexpr bool
80  {
81  return true;
82  }
83 
85  void insplit(bool lazy = false)
86  {
87  lazy_ = lazy;
89 
90  if (!lazy)
91  while (!todo_.empty())
92  {
93  const auto& p = todo_.front();
94  this->add_insplit_transitions_(std::get<1>(p), std::get<0>(p));
95  todo_.pop_front();
96  }
97  }
98 
99  std::ostream&
100  print_state_name(state_t s, std::ostream& o,
101  format fmt = {}, bool delimit = false)
102  const
103  {
104  const auto& orig = origins();
105  auto i = orig.find(s);
106  if (i == orig.end())
107  this->print_state(s, o);
108  else
109  {
110  if (delimit)
111  o << '(';
112  aut_in()->print_state_name(i->second.first, o, fmt, true);
113  o << ", ";
114  if (fmt == format::latex)
115  o << (i->second.second ? "" : "\\not ") << "\\varepsilon";
116  else if (fmt == format::utf8)
117  o << (i->second.second ? "ε" : "!ε");
118  else
119  o << (i->second.second ? "\\e" : "!\\e");
120  if (delimit)
121  o << ')';
122  }
123  return o;
124  }
125 
127  void complete_(const state_t s) const
128  {
129  auto& self = const_cast<self_t&>(*this);
130  const auto& orig = origins();
131  const state_name_t& sn = orig.at(s);
132  self.aut_->set_lazy(s, false);
133  self.add_insplit_transitions_(s, sn);
134  }
135 
137  using super_t::all_out;
138  auto all_out(const state_t s) const
139  {
140  if (lazy_ && aut_->is_lazy(s))
141  complete_(s);
142  return aut_->all_out(s);
143  }
144 
145  // FIXME: make private
147  {
148  return aut_;
149  }
150 
151  // FIXME: return shared_ptr to const automaton_impl?
152  const out_automaton_t& aut_out() const
153  {
154  return aut_;
155  }
156 
159  const origins_t& origins() const
160  {
161  return bimap_.right;
162  }
163 
164 
165  private:
167  const automaton_t& aut_in() const
168  {
169  return in_;
170  }
171 
173  {
174  pmap_().insert({state_name_t(aut_in()->pre(), false),
175  aut_out()->pre()});
176  pmap_().insert({state_name_t(aut_in()->post(), false),
177  aut_out()->post()});
178  todo_.emplace_back(pre_(), aut_out()->pre());
179  if (lazy_)
180  aut_out()->set_lazy(aut_out()->pre());
181  }
182 
184  {
185  return {aut_->pre(), false};
186  }
187 
191  const state_name_t& sn)
192  {
193  for (auto t : aut_in()->all_out(std::get<0>(sn)))
194  aut_out()->new_transition_copy(s,
195  state({aut_in()->dst_of(t),
196  is_spontaneous_(t)}),
197  aut_in(), t);
198  }
199 
202  {
203  return aut_in()->labelset()->is_one(aut_in()->label_of(t));
204  }
205 
213  {
214  auto lb = pmap_().find(sn);
215  if (lb == pmap_().end())
216  {
217  state_t s = aut_->new_state();
218  if (lazy_)
219  aut_->set_lazy(s, true);
220  lb = pmap_().insert(lb, {sn, s});
221  todo_.emplace_back(sn, s);
222  }
223  return lb->second;
224  }
225 
229  {
230  return bimap_.left;
231  }
232 
235 
237  bool lazy_ = false;
238 
242  mutable bimap_t bimap_;
243 
245  std::deque<std::pair<state_name_t, state_t>> todo_;
246  };
247 
249  template <Automaton Aut>
250  using insplit_automaton
251  = std::shared_ptr<insplit_automaton_impl<Aut>>;
252 
254  template <Automaton Aut>
255  auto
256  make_insplit_automaton(const Aut& aut)
258  {
259  return make_shared_ptr<insplit_automaton<Aut>>(aut);
260  }
261 
262 
264  template <Automaton Aut>
265  auto
266  insplit(Aut aut, bool lazy = false)
267  -> std::enable_if_t<labelset_t_of<Aut>::has_one(),
268  decltype(make_insplit_automaton(aut))>
269  {
270  auto res = make_insplit_automaton(aut);
271  res->insplit(lazy);
272  return res;
273  }
274 
278  template <Automaton Aut>
279  auto
280  insplit(Aut aut, bool = false)
281  -> std::enable_if_t<!labelset_t_of<Aut>::has_one(),
282  Aut>
283  {
284  return aut;
285  }
286  } // namespace detail
287 
288 
290  template <Automaton Aut>
292 
294  using detail::insplit;
295 
296  namespace dyn
297  {
298  namespace detail
299  {
301  template <Automaton Aut, typename Bool>
302  automaton
303  insplit(const automaton& aut, bool lazy)
304  {
305  const auto& a = aut->as<Aut>();
306  return ::vcsn::insplit(a, lazy);
307  }
308  }
309  }
310 
311 } // namespace vcsn
std::pair< state_t, bool > state_name_t
Tuple of states of input automata.
Definition: insplit.hh:48
const automaton_t & aut_in() const
The input automaton.
Definition: insplit.hh:167
boost::bimap< boost::bimaps::unordered_set_of< state_name_t >, boost::bimaps::unordered_set_of< state_t >> bimap_t
Definition: insplit.hh:54
const origins_t & origins() const
A map from result state to original state and status (spontaneous or proper state).
Definition: insplit.hh:159
boost::flyweight< std::string, boost::flyweights::no_tracking, boost::flyweights::intermodule_holder > symbol
An internalized string.
Definition: symbol.hh:23
typename super_t::transition_t transition_t
Definition: insplit.hh:45
static constexpr auto pre(Args &&...args) -> decltype(element_type::pre(std::forward< Args >(args)...))
detail::insplit_automaton< Aut > insplit_automaton
An insplit automaton as a shared pointer.
Definition: insplit.hh:291
bimap_t bimap_
Map (input-state, status) -> result-state.
Definition: insplit.hh:242
state_t_of< automaton_t > state_t
const out_automaton_t & aut_out() const
Definition: insplit.hh:152
symbol sname()
Definition: name.hh:65
state_name_t pre_() const
Definition: insplit.hh:183
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
Aggregate an automaton, and forward calls to it.
typename labelset_t::value_t label_t
void insplit(bool lazy=false)
Insplit the automaton.
Definition: insplit.hh:85
automaton insplit(const automaton &aut, bool lazy)
Bridge.
Definition: insplit.hh:303
return res
Definition: multiply.hh:398
auto label_of(Args &&...args) const -> decltype(aut_-> label_of(std::forward< Args >(args)...))
Insplit automaton decorator.
Definition: insplit.hh:29
std::ostream & print_state_name(state_t s, std::ostream &o, format fmt={}, bool delimit=false) const
Definition: insplit.hh:100
static constexpr bool state_has_name(state_t)
Definition: insplit.hh:79
static constexpr auto post(Args &&...args) -> decltype(element_type::post(std::forward< Args >(args)...))
transition_t_of< automaton_t > transition_t
AutOut make_fresh_automaton(const AutIn &model)
Create an empty, mutable, automaton, based on another one.
Definition: copy.hh:91
Definition: a-star.hh:8
bool is_spontaneous_(transition_t t) const
Whether transition t is labeled by one.
Definition: insplit.hh:201
insplit_automaton_impl(const Aut &aut)
Definition: insplit.hh:73
auto insplit(Aut aut, bool lazy=false) -> std::enable_if_t< labelset_t_of< Aut >::has_one(), decltype(make_insplit_automaton(aut))>
Insplit an automaton with possible spontaneous transitions.
Definition: insplit.hh:266
typename super_t::label_t label_t
Definition: insplit.hh:44
auto all_out(const state_t s) const
Definition: insplit.hh:138
fresh_automaton_t_of< Aut > out_automaton_t
Definition: insplit.hh:37
map_t & pmap_()
A map from original state and status (spontaneous or proper state) to result state.
Definition: insplit.hh:228
A dyn automaton.
Definition: automaton.hh:17
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:82
auto make_insplit_automaton(const Aut &aut) -> insplit_automaton< Aut >
Build an insplit automaton from an automaton.
Definition: insplit.hh:256
An input/output format for valuesets.
Definition: format.hh:13
typename bimap_t::left_map map_t
Definition: insplit.hh:55
typename super_t::state_t state_t
Definition: insplit.hh:43
Print as rich UTF-8 text, escaped.
Definition: format.hh:30
auto print_state(Args &&...args) const -> decltype(aut_-> print_state(std::forward< Args >(args)...))
automaton_t in_
The input automaton.
Definition: insplit.hh:234
void add_insplit_transitions_(const state_t s, const state_name_t &sn)
Split the original outgoing transitions to the insplit states.
Definition: insplit.hh:190
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
automaton_t aut_
The wrapped automaton, possibly const.
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
Print for LaTeX.
Definition: format.hh:22
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: insplit.hh:67
std::shared_ptr< insplit_automaton_impl< Aut >> insplit_automaton
An insplit automaton as a shared pointer.
Definition: insplit.hh:251
typename bimap_t::right_map origins_t
Definition: insplit.hh:56
state_t state(const state_name_t &sn)
The state in the insplit corresponding to a state and a status (spontaneous or proper state)...
Definition: insplit.hh:212
weightset_t_of< Aut > weightset_t
Definition: insplit.hh:46
void complete_(const state_t s) const
Complete a lazy state: find its outgoing transitions.
Definition: insplit.hh:127
bool lazy_
Whether the computation is lazy.
Definition: insplit.hh:237
std::deque< std::pair< state_name_t, state_t > > todo_
Worklist of state tuples.
Definition: insplit.hh:245
auto all_out(Args &&...args) const -> decltype(aut_-> all_out(std::forward< Args >(args)...))