Vcsn  2.3
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  bool
59  is_out_sorted(const Aut& a)
60  {
62  for (auto s: a->states())
63  if (!detail::is_sorted_forward(out(a, s), less))
64  return false;
65  return true;
66  }
67 
68  namespace dyn
69  {
70  namespace detail
71  {
73  template <Automaton Aut>
74  bool
76  {
77  const auto& a = aut->as<Aut>();
78  return is_out_sorted(a);
79  }
80  }
81  }
82 
83 
84  /*-------.
85  | sort. |
86  `-------*/
87  namespace detail
88  {
90  template <Automaton Aut>
91  class sorter
92  {
94  using input_automaton_t = Aut;
95 
98 
102 
103  public:
106  {}
107 
109  {
113  return std::move(res_);
114  }
115 
116  private:
118  {
119  while (! res_->todo_.empty())
120  {
121  auto p = res_->todo_.front();
122  res_->todo_.pop();
123  visit_successors_of_(p.first, p.second);
124  }
125  }
126 
128  {
129  std::vector<input_transition_t> ts;
130  // Here out(a_, s) would just as well as all_out(a_, s) but it
131  // would be slower; later we have to test one condition per
132  // transition anyway, which is just the additional work
133  // performed by out.
134  for (auto t: all_out(res_->input_, s))
135  ts.emplace_back(t);
136 
138 
139  for (auto t: ts)
140  res_->new_transition_copy(res_s, res_->state(res_->input_->dst_of(t)),
141  res_->input_, t);
142  }
143 
145  {
146  // States are processed in order. Like above, a_->states()
147  // would work.
148  for (auto s: res_->input_->all_states())
149  res_->state(s);
150  }
151 
154  const labelset_t_of<input_automaton_t>& ls_ = *res_->input_->labelset();
155  const weightset_t_of<input_automaton_t>& ws_ = *res_->input_->weightset();
156  }; // class
157  } // namespace
158 
159  template <Automaton Aut>
160  auto
161  sort(const Aut& a)
163  {
164  auto sorter = detail::sorter<Aut>(a);
165  return sorter();
166  }
167 
168  namespace dyn
169  {
170  namespace detail
171  {
172 
174  template <Automaton Aut>
175  automaton
176  sort(const automaton& aut)
177  {
178  const auto& a = aut->as<Aut>();
180  }
181  }
182  }
183 }
std::shared_ptr< detail::permutation_automaton_impl< Aut >> permutation_automaton
A permutation automaton as a shared pointer.
Definition: fwd.hh:48
const weightset_t_of< input_automaton_t > & ws_
Definition: sort.hh:155
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:13
state_t_of< automaton_t > state_t
Definition: sort.hh:101
transition_t_of< automaton_t > transition_t
Definition: sort.hh:26
Compare transitions of an automaton.
Definition: sort.hh:23
typename detail::transition_t_of_impl< base_t< ValueSet >>::type transition_t_of
Definition: traits.hh:65
const labelset_t_of< input_automaton_t > & ls_
Definition: sort.hh:154
void visit_successors_of_(input_state_t s, state_t res_s)
Definition: sort.hh:127
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
transition_less(const automaton_t &a)
Definition: sort.hh:28
bool is_out_sorted(const automaton &aut)
Bridge.
Definition: sort.hh:75
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:64
permutation_automaton< input_automaton_t > automaton_t
Result automaton type.
Definition: sort.hh:100
void push_inaccessible_states_()
Definition: sort.hh:144
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
A function to sort an automaton.
Definition: sort.hh:91
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:101
Definition: a-star.hh:8
A dyn automaton.
Definition: automaton.hh:17
void visit_and_update_res_()
Definition: sort.hh:117
automaton sort(const automaton &aut)
Bridge.
Definition: sort.hh:176
Functor to compare Values of ValueSets.
Definition: functional.hh:76
Aut input_automaton_t
Input automaton type.
Definition: sort.hh:94
ATTRIBUTE_PURE bool operator()(const transition_t l, const transition_t r) const
Definition: sort.hh:33
bool is_out_sorted(const Aut &a)
Whether for each state, the outgoing transitions are sorted by increasing label.
Definition: sort.hh:59
sorter(const input_automaton_t &a)
Definition: sort.hh:104
transition_t_of< input_automaton_t > input_transition_t
Definition: sort.hh:97
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
auto sort(const Aut &a) -> permutation_automaton< Aut >
Definition: sort.hh:161
automaton_t operator()()
Definition: sort.hh:108
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
auto all_out(const Aut &aut, state_t_of< Aut > s)
Indexes of transitions leaving state s.
Definition: automaton.hh:45
automaton_t res_
Sorted automaton.
Definition: sort.hh:153
state_t_of< input_automaton_t > input_state_t
Definition: sort.hh:96