Vcsn  2.2a
Be Rational
polystate-automaton.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <iostream>
4 #include <queue>
5 #include <set>
6 #include <type_traits>
7 
8 #include <boost/bimap.hpp>
9 #include <boost/bimap/set_of.hpp>
10 #include <boost/bimap/unordered_set_of.hpp>
11 
14 #include <vcsn/misc/bimap.hh> // vcsn::has
15 #include <vcsn/misc/static-if.hh> // vcsn::has
16 #include <vcsn/misc/unordered_map.hh> // vcsn::has
17 
18 namespace vcsn
19 {
20  namespace detail
21  {
27  template <typename StateNameset, typename Stateset,
28  bool Bidirectional>
29  class state_bimap;
30 
37  template <typename StateNameset, typename Stateset>
38  class state_bimap<StateNameset, Stateset, true>
39  {
40  using state_nameset_t = StateNameset;
41  using state_name_t = typename state_nameset_t::value_t;
42 
43  using stateset_t = Stateset;
44  using state_t = typename stateset_t::value_t;
45 
47  using left_t
48  = boost::bimaps::unordered_set_of<state_name_t,
52  using right_t = boost::bimaps::set_of<state_t>;
54  using bimap_t = boost::bimap<left_t, right_t>;
55 
57 
58  public:
59  using const_iterator = typename bimap_t::const_iterator;
60 
61  template <typename... Args>
62  auto emplace(Args&&... args)
63  {
64  return map_.insert({ std::forward<Args>(args)... });
65  }
66 
67  auto find_key(const state_name_t& s) const
68  {
69  return map_.left.find(s);
70  }
71 
72  auto end_key() const
73  {
74  return map_.left.end();
75  }
76 
78  static const state_name_t& state_name(const const_iterator& i)
79  {
80  return i->left;
81  }
82 
84  static state_t state(const const_iterator& i)
85  {
86  return i->right;
87  }
88 
90  using origins_t = typename bimap_t::right_map;
91  const origins_t& origins() const
92  {
93  return map_.right;
94  }
95  };
96 
97 
104  template <typename StateNameset, typename Stateset>
105  class state_bimap<StateNameset, Stateset, false>
106  {
107  using state_nameset_t = StateNameset;
108  using state_name_t = typename state_nameset_t::value_t;
109 
110  using stateset_t = Stateset;
111  using state_t = typename stateset_t::value_t;
112 
113  using map_t = std::unordered_map<state_name_t, state_t,
114  vcsn::hash<state_nameset_t>,
117 
118  public:
119  using const_iterator = typename map_t::const_iterator;
120 
121  template <typename... Args>
122  auto emplace(Args&&... args)
123  {
124  return map_.emplace(std::forward<Args>(args)...);
125  }
126 
127  auto find_key(const state_name_t& sn) const
128  {
129  return map_.find(sn);
130  }
131 
132  auto end_key() const
133  {
134  return map_.end();
135  }
136 
138  static const state_name_t& state_name(const const_iterator& i)
139  {
140  return i->first;
141  }
142 
144  static state_t state(const const_iterator& i)
145  {
146  return i->second;
147  }
148 
150  using origins_t = std::map<state_t, state_name_t>;
152  const origins_t& origins() const
153  {
154  if (origins_.empty())
155  for (const auto& p: map_)
156  origins_.emplace(p.second, p.first);
157  return origins_;
158  }
159  };
160 
161 
167  template <Automaton Aut,
168  wet_kind_t Kind = detail::wet_kind<labelset_t_of<Aut>,
170  bool Lazy = false>
174  weightset_t_of<Aut>>, Kind>,
176  Lazy>
177  {
178  public:
179  using automaton_t = Aut;
181  template <typename Ctx = context_t>
184 
189 
193 
195  using state_nameset_t
197  using state_name_t = typename state_nameset_t::value_t;
198 
199  using state_bimap_t
201  weightset_t_of<Aut>>, Kind>,
203  Lazy>;
204 
208  : super_t{a->context()}
209  , input_{a}
210  {
211  // Pre.
212  {
213  auto pre = zero();
214  ns_.new_weight(pre, input_->pre(), ws_.one());
215  todo_.push(this->emplace(std::move(pre), this->pre()).first);
216  if (Lazy)
217  this->set_lazy(this->pre());
218  }
219 
220  // Post.
221  {
222  auto post = zero();
223  ns_.new_weight(post, input_->post(), ws_.one());
224  this->emplace(std::move(post), this->post());
225  }
226  }
227 
228  bool state_has_name(state_t s) const
229  {
230  return has(this->origins(), s);
231  }
232 
234  state_name_t zero() const
235  {
236  return static_if<Kind == wet_kind_t::bitset>
237  ([] (const auto& self) { return state_name_t(self.state_size_); },
238  [] (const auto& self) { return self.ns_.zero(); })
239  (*this);
240  }
241 
242  std::ostream&
243  print_state_name(state_t s, std::ostream& o,
244  format fmt = {}, bool delimit = false) const
245  {
246  const auto& origs = this->origins();
247  auto i = origs.find(s);
248  if (i == std::end(origs))
249  this->print_state(s, o);
250  else
251  {
252  if (delimit)
253  o << '{';
254  ns_.print(i->second, o, fmt, ", ");
255  if (delimit)
256  o << '}';
257  }
258  return o;
259  }
260 
263  state_t state_(state_name_t n)
264  {
265  state_t res;
266  auto i = this->find_key(n);
267  if (i == this->end_key())
268  {
269  res = this->new_state();
270  if (Lazy)
271  this->set_lazy(res);
272  todo_.push(this->emplace(std::move(n), res).first);
273  }
274  else
275  res = i->second;
276  return res;
277  }
278 
281 
283  weightset_t ws_ = *input_->weightset();
284 
286  state_nameset_t ns_ = {{stateset_t(input_), ws_}};
287 
289  using queue_t = std::queue<typename state_bimap_t::const_iterator>;
291 
295  size_t state_size_ = input_->all_states().back() + 1;
296  };
297 
299  template <Automaton Aut,
300  wet_kind_t Kind = wet_kind<labelset_t_of<Aut>,
301  weightset_t_of<Aut>>(),
302  bool Lazy = false>
303  using polystate_automaton
305 
306  template <Automaton Aut,
307  wet_kind_t Kind = wet_kind<labelset_t_of<Aut>,
308  weightset_t_of<Aut>>(),
309  bool Lazy = false>
310  auto
311  make_polystate_automaton(const Aut& aut)
312  {
314  return make_shared_ptr<res_t>(aut);
315  }
316  }
317 } // namespace vcsn
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
A bidirectional map from state names to state numbers.
Request the unordered_map implementation.
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:53
typename detail::label_t_of_impl< base_t< ValueSet >>::type label_t_of
Definition: traits.hh:54
fresh_automaton_t_of< Aut, Ctx > fresh_automaton_t
labelset_t_of< automaton_t > labelset_t
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
weightset_t_of< automaton_t > weightset_t
polystate_automaton_impl(const automaton_t &a)
Build the determinizer.
wet_kind_t
Different implementations of wets.
Definition: wet.hh:197
auto make_polystate_automaton(const Aut &aut)
State labelset.
Definition: fwd.hh:22
static state_t state(const const_iterator &i)
Get the state from a const_iterator.
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
boost::bimaps::set_of< state_t > right_t
Storage for state index.
boost::bimaps::unordered_set_of< state_name_t, vcsn::hash< state_nameset_t >, vcsn::equal_to< state_nameset_t >> left_t
Storage for state names.
std::queue< typename state_bimap_t::const_iterator > queue_t
The sets of (input) states waiting to be processed.
label_t_of< automaton_t > label_t
Labels and weights.
std::shared_ptr< polystate_automaton_impl< Aut, Kind, Lazy >> polystate_automaton
A polystate automaton as a shared pointer.
#define Automaton
Definition: automaton.hh:24
Aggregate an automaton, and forward calls to it.
This is useful to make hashes with labels or weights as keys without using non-default constructors; ...
Definition: functional.hh:42
static const state_name_t & state_name(const const_iterator &i)
Get the state name from a const_iterator.
static const state_name_t & state_name(const const_iterator &i)
Get the state name from a const_iterator.
boost::bimap< left_t, right_t > bimap_t
Bidirectional map state_name_t -> state_t;.
state_t state_(state_name_t n)
The state for set of states n.
An automaton whose state names are polynomials of states.
auto context(Args &&...args) const -> decltype(aut_-> context(std::forward< Args >(args)...))
std::ostream & print_state_name(state_t s, std::ostream &o, format fmt={}, bool delimit=false) const
This is useful to make hashes with labels or weights as keys without using non-default constructors; ...
Definition: functional.hh:12
static state_t state(const const_iterator &i)
Get the state from a const_iterator.
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
typename bimap_t::right_map origins_t
A map from state indexes to state names.
state_name_t zero() const
The empty polynomial of states.
std::map< state_t, state_name_t > origins_t
A map from state indexes to state names.
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
state_t_of< automaton_t > state_t
State index.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
An input/output format for valuesets.
Definition: format.hh:11
Definition: a-star.hh:8
std::unordered_map< state_name_t, state_t, vcsn::hash< state_nameset_t >, vcsn::equal_to< state_nameset_t >> map_t