Vcsn  2.2
Be Rational
pair.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <vector>
4 
7 #include <vcsn/dyn/automaton.hh>
8 #include <vcsn/misc/map.hh>
10 #include <vcsn/misc/pair.hh> // hash<pair>.
11 #include <vcsn/misc/zip-maps.hh>
12 
13 namespace vcsn
14 {
15 
16  /*-----------------.
17  | pair_automaton. |
18  `-----------------*/
19 
20  namespace detail
21  {
22 
25  template <Automaton Aut>
27 #if 0
28  // See comments below.
29  : public automaton_decorator<fresh_automaton_t_of<Aut>>
30 #else
31  : public automaton_decorator<mutable_automaton<context_t_of<Aut>>>
32 #endif
33  {
34  public:
35  using automaton_t = Aut;
38  // FIXME: cannot use fresh_automaton_t_of<Aut>. To see why, run
39  // the tests/python/focus.py test. We should probably stop
40  // having make_free_context behave a special way with
41  // focus_automaton, rather we should call a special function to
42  // duplicate a focus_automaton.
43 #if 0
44  template <typename Ctx = context_t>
47 #else
48  template <typename Ctx = context_t>
51 #endif
56  using weight_t = typename weightset_t::value_t;
57  using state_t = typename super_t::state_t;
58 
59  private:
62  using state_name_t = std::pair<in_state_t, in_state_t>;
64  using origins_t = std::map<state_t, state_name_t>;
65 
66  public:
67  pair_automaton_impl(const automaton_t& aut, bool keep_initials = false)
68  : super_t(aut->context())
69  , input_(aut)
70  , transition_map_(aut)
71  , keep_initials_(keep_initials)
72  {
73  auto ctx = input_->context();
74  auto ws = ctx.weightset();
75 
76  if (keep_initials_)
77  for (auto s : input_->states())
78  pair_states_.emplace(std::make_pair(s, s), this->new_state());
79  else
80  {
81  q0_ = this->new_state(); // q0 special state
82  for (auto l : input_->labelset()->generators())
83  this->add_transition(q0_, q0_, l, ws->one());
84  }
85 
86  // States are unordered: (s1, s2) is defined only for s1 < s2.
87  {
88  auto states = input_->states();
89  auto end = std::end(states);
90  for (auto i1 = std::begin(states); i1 != end; ++i1)
91  {
92  // FIXME: cannot use i2 = std::next(i1) with clang 3.5
93  // and Boost 1.55.
94  // https://svn.boost.org/trac/boost/ticket/9984
95  auto i2 = i1;
96  for (++i2; i2 != end; ++i2)
97  // s1 < s2, no need for make_unordered_pair.
98  pair_states_.emplace(std::make_pair(*i1, *i2),
99  this->new_state());
100  }
101  }
102 
103  for (const auto& ps : pair_states_)
104  {
105  auto pstates = ps.first; // pair of states
106  auto cstate = ps.second; // current state
107 
108  for (const auto& p : zip_maps(transition_map_[pstates.first],
109  transition_map_[pstates.second]))
110  this->add_transition(cstate,
111  state_(std::get<0>(p.second).dst,
112  std::get<1>(p.second).dst),
113  p.first, ws->one());
114  }
115 
116  for (const auto& p: pair_states_)
117  origins_.emplace(p.second, p.first);
118 
119  if (keep_initials_)
120  for (auto s : input_->states())
121  singletons_.push_back(state_(s, s));
122  else
123  singletons_.push_back(q0_);
124  }
125 
126  static symbol sname()
127  {
128  static auto res = symbol{"pair_automaton<"
130  return res;
131  }
132 
133  std::ostream& print_set(std::ostream& o, format fmt = {}) const
134  {
135  o << "pair_automaton<";
136  input_->print_set(o, fmt);
137  return o << '>';
138  }
139 
140  state_t get_q0() const
141  {
142  require(!keep_initials_,
143  "can't get_q0() on a pairer that keeps origins");
144  return q0_;
145  }
146 
147  bool is_singleton(state_t s) const
148  {
149  if (keep_initials_)
150  {
151  state_name_t p = get_origin(s);
152  return p.first == p.second;
153  }
154  else
155  return s == q0_;
156  }
157 
158  using singletons_t = std::vector<state_t>;
159  const singletons_t& singletons() const
160  {
161  return singletons_;
162  }
163 
164  using pair_states_t
165  = std::unordered_map<state_name_t, state_t>;
167  {
168  return pair_states_;
169  }
170 
172  const origins_t& origins() const
173  {
174  return origins_;
175  }
176 
178  {
179  auto i = origins().find(s);
180  require(i != std::end(origins()), "state not found in origins");
181  return i->second;
182  }
183 
184  bool state_has_name(state_t s) const
185  {
186  return has(origins(), s);
187  }
188 
189  std::ostream&
190  print_state_name(state_t ss, std::ostream& o,
191  format fmt = {},
192  bool delimit = false) const
193  {
194  auto i = origins().find(ss);
195  if (i == std::end(origins()))
196  this->print_state(ss, o);
197  else
198  {
199  if (delimit)
200  o << '{';
201  input_->print_state_name(i->second.first, o, fmt);
202  if (!is_singleton(ss))
203  {
204  o << ", ";
205  input_->print_state_name(i->second.second, o, fmt);
206  }
207  if (delimit)
208  o << '}';
209  }
210  return o;
211  }
212 
213  private:
217  {
218  // Benches show it is slightly faster to handle this case
219  // especially rather that mapping these "diagonal states" to
220  // q0_ in pair_states_.
221  if (s1 == s2 && !keep_initials_)
222  return q0_;
223  else
224  return pair_states_[make_unordered_pair(s1, s2)];
225  }
226 
237  state_t q0_ = this->null_state();
238  bool keep_initials_ = false;
239  };
240  }
241 
242  template <Automaton Aut>
243  using pair_automaton
244  = std::shared_ptr<detail::pair_automaton_impl<Aut>>;
245 
246  /*------------------.
247  | pair(automaton). |
248  `------------------*/
249 
250  template <Automaton Aut>
251  pair_automaton<Aut> pair(const Aut& aut, bool keep_initials = false)
252  {
253  return make_shared_ptr<pair_automaton<Aut>>(aut, keep_initials);
254  }
255 
256  namespace dyn
257  {
258  namespace detail
259  {
261  template <Automaton Aut, typename>
262  automaton
263  pair(const automaton& aut, bool keep_initials)
264  {
265  const auto& a = aut->as<Aut>();
266  return make_automaton(::vcsn::pair(a, keep_initials));
267  }
268  }
269  }
270 }
pair_automaton< Aut > pair(const Aut &aut, bool keep_initials=false)
Definition: pair.hh:251
auto new_state(Args &&...args) -> decltype(aut_-> new_state(std::forward< Args >(args)...))
bool is_singleton(state_t s) const
Definition: pair.hh:147
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:75
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:59
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
state_t get_q0() const
Definition: pair.hh:140
const state_name_t & get_origin(state_t s) const
Definition: pair.hh:177
std::ostream & print_state_name(state_t ss, std::ostream &o, format fmt={}, bool delimit=false) const
Definition: pair.hh:190
state_t_of< automaton_t > state_t
std::map< state_t, state_name_t > origins_t
State index -> pair of input automaton states.
Definition: pair.hh:64
Definition: a-star.hh:8
typename weightset_t::value_t weight_t
Definition: pair.hh:56
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:78
std::shared_ptr< detail::pair_automaton_impl< Aut >> pair_automaton
Definition: pair.hh:244
transition_map_t transition_map_
Definition: pair.hh:231
std::ostream & print_set(std::ostream &o, format fmt={}) const
Definition: pair.hh:133
automaton_t input_
Input automaton.
Definition: pair.hh:228
bool state_has_name(state_t s) const
Definition: pair.hh:184
std::unordered_map< state_name_t, state_t > pair_states_t
Definition: pair.hh:165
state_t state_(in_state_t s1, in_state_t s2)
The state in the result automaton that corresponds to (s1, s2).
Definition: pair.hh:216
An input/output format for valuesets.
Definition: format.hh:11
mutable_automaton< Ctx > fresh_automaton_t
When creating a copy of this automaton type.
Definition: pair.hh:50
origins_t origins_
From state index to state name.
Definition: pair.hh:235
typename super_t::state_t state_t
Definition: pair.hh:57
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
pair_states_t pair_states_
From state name to state index.
Definition: pair.hh:233
auto print_state(Args &&...args) const -> decltype(aut_-> print_state(std::forward< Args >(args)...))
const origins_t & origins() const
A map from result state to tuple of original states.
Definition: pair.hh:172
pair_automaton_impl(const automaton_t &aut, bool keep_initials=false)
Definition: pair.hh:67
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.
static constexpr auto null_state(Args &&...args) -> decltype(element_type::null_state(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
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:57
symbol sname()
Definition: name.hh:67
typename detail::context_t_of_impl< base_t< ValueSet >>::type context_t_of
Definition: traits.hh:53
weightset_t_of< automaton_t > weightset_t
Definition: pair.hh:55
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82
auto add_transition(Args &&...args) -> decltype(aut_-> add_transition(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
state_t_of< automaton_t > in_state_t
Definition: pair.hh:53
const singletons_t & singletons() const
Definition: pair.hh:159
std::pair< in_state_t, in_state_t > state_name_t
The semantics of the result states: unordered pair of input states.
Definition: pair.hh:62
std::vector< state_t > singletons_t
Definition: pair.hh:158
auto make_unordered_pair(T &&e1, T &&e2)
Definition: pair.hh:34
context_t_of< automaton_t > context_t
Definition: pair.hh:37
transition_t_of< automaton_t > in_transition_t
Definition: pair.hh:54
zipped_maps< Dereference, Maps... > zip_maps(Maps &&...maps)
Definition: zip-maps.hh:250
auto states(Args &&...args) const -> decltype(aut_-> states(std::forward< Args >(args)...))
const pair_states_t & get_map_pair() const
Definition: pair.hh:166
The pair automaton is used by several algorithms for synchronizing words.
Definition: pair.hh:26