Vcsn  2.2
Be Rational
sort.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <vector>
4 
5 #include <boost/range/algorithm/sort.hpp>
6 
8 #include <vcsn/ctx/traits.hh> // base_t
9 #include <vcsn/dyn/automaton.hh>
10 #include <vcsn/dyn/fwd.hh>
11 #include <vcsn/misc/algorithm.hh>
12 
13 namespace vcsn
14 {
15 
16  namespace detail
17  {
22  template <Automaton Aut>
24  {
25  using automaton_t = Aut;
27 
29  : aut_(a)
30  {}
31 
32  ATTRIBUTE_PURE
33  bool operator()(const transition_t l,
34  const transition_t r) const
35  {
36  const auto& llab = aut_->label_of(l);
37  const auto& rlab = aut_->label_of(r);
38  if (aut_->labelset()->less(llab, rlab))
39  return true;
40  else if (aut_->labelset()->less(rlab, llab))
41  return false;
42  else
43  return aut_->dst_of(l) < aut_->dst_of(r);
44  }
45 
46  private:
48  };
49  }
50 
51  /*------------------.
52  | is_label_sorted. |
53  `------------------*/
54 
57  template <Automaton Aut>
58  inline
59  bool
60  is_out_sorted(const Aut& a)
61  {
63  for (auto s: a->states())
64  if (!detail::is_sorted_forward(out(a, s), less))
65  return false;
66  return true;
67  }
68 
69  namespace dyn
70  {
71  namespace detail
72  {
74  template <Automaton Aut>
75  bool
77  {
78  const auto& a = aut->as<Aut>();
79  return is_out_sorted(a);
80  }
81  }
82  }
83 
84 
85  /*-------.
86  | sort. |
87  `-------*/
88  namespace detail
89  {
91  template <Automaton Aut>
92  class sorter
93  {
95  using input_automaton_t = Aut;
96 
99 
103 
104  public:
107  {}
108 
110  {
114  return std::move(res_);
115  }
116 
117  private:
119  {
120  while (! res_->todo_.empty())
121  {
122  auto p = res_->todo_.front();
123  res_->todo_.pop();
124  visit_successors_of_(p.first, p.second);
125  }
126  }
127 
129  {
130  std::vector<input_transition_t> ts;
131  // Here out(a_, s) would just as well as all_out(a_, s) but it
132  // would be slower; later we have to test one condition per
133  // transition anyway, which is just the additional work
134  // performed by out.
135  for (auto t: all_out(res_->input_, s))
136  ts.emplace_back(t);
137 
139 
140  for (auto t: ts)
141  res_->new_transition_copy(res_s, res_->state(res_->input_->dst_of(t)),
142  res_->input_, t);
143  }
144 
146  {
147  // States are processed in order. Like above, a_->states()
148  // would work.
149  for (auto s: res_->input_->all_states())
150  res_->state(s);
151  }
152 
155  const labelset_t_of<input_automaton_t>& ls_ = *res_->input_->labelset();
156  const weightset_t_of<input_automaton_t>& ws_ = *res_->input_->weightset();
157  }; // class
158  } // namespace
159 
160  template <Automaton Aut>
161  inline
162  auto
163  sort(const Aut& a)
165  {
166  detail::sorter<Aut> sorter(a);
167  return sorter();
168  }
169 
170  namespace dyn
171  {
172  namespace detail
173  {
174 
176  template <Automaton Aut>
177  automaton
178  sort(const automaton& aut)
179  {
180  const auto& a = aut->as<Aut>();
181  return make_automaton(::vcsn::sort(a));
182  }
183  }
184  }
185 }
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:37
ATTRIBUTE_PURE bool operator()(const transition_t l, const transition_t r) const
Definition: sort.hh:33
transition_t_of< automaton_t > transition_t
Definition: sort.hh:26
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
automaton sort(const automaton &aut)
Bridge.
Definition: sort.hh:178
bool is_sorted_forward(const Container &container, Compare comp)
Same as std::is_sorted, but works with an input iterator, not just a forward iterator.
Definition: algorithm.hh:92
Definition: a-star.hh:8
transition_less(const automaton_t &a)
Definition: sort.hh:28
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
SharedPtr make_shared_ptr(Args &&...args)
Same as std::make_shared, but parameterized by the shared_ptr type, not the (pointed to) element_type...
Definition: memory.hh:14
const weightset_t_of< input_automaton_t > & ws_
Definition: sort.hh:156
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
void visit_successors_of_(input_state_t s, state_t res_s)
Definition: sort.hh:128
permutation_automaton< input_automaton_t > automaton_t
Result automaton type.
Definition: sort.hh:101
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:56
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:56
state_t_of< input_automaton_t > input_state_t
Definition: sort.hh:97
bool is_out_sorted(const Aut &a)
Whether for each state, the outgoing transitions are sorted by increasing label.
Definition: sort.hh:60
std::shared_ptr< detail::permutation_automaton_impl< Aut >> permutation_automaton
A permutation automaton as a shared pointer.
Definition: fwd.hh:48
state_t_of< automaton_t > state_t
Definition: sort.hh:102
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
void visit_and_update_res_()
Definition: sort.hh:118
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:57
transition_t_of< input_automaton_t > input_transition_t
Definition: sort.hh:98
Compare transitions of an automaton.
Definition: sort.hh:23
bool is_out_sorted(const automaton &aut)
Bridge.
Definition: sort.hh:76
automaton_t operator()()
Definition: sort.hh:109
auto sort(const Aut &a) -> permutation_automaton< Aut >
Definition: sort.hh:163
sorter(const input_automaton_t &a)
Definition: sort.hh:105
automaton_t res_
Sorted automaton.
Definition: sort.hh:154
const labelset_t_of< input_automaton_t > & ls_
Definition: sort.hh:155
A function to sort an automaton.
Definition: sort.hh:92
void push_inaccessible_states_()
Definition: sort.hh:145
Aut input_automaton_t
Input automaton type.
Definition: sort.hh:95
Functor to compare Values of ValueSets.
Definition: functional.hh:78