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