Vcsn  2.3a
Be Rational
proper.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <stdexcept>
4 #include <type_traits>
5 #include <utility>
6 
7 #include <vcsn/algos/copy.hh>
12 #include <vcsn/algos/fwd.hh>
13 #include <vcsn/algos/is-proper.hh>
14 #include <vcsn/algos/is-valid.hh>
15 #include <vcsn/core/kind.hh>
16 #include <vcsn/misc/builtins.hh>
17 #include <vcsn/misc/direction.hh>
18 #include <vcsn/misc/getargs.hh>
19 #include <vcsn/misc/star-status.hh>
20 
21 namespace vcsn
22 {
23  namespace detail
24  {
28  template <Automaton Aut>
29  class properer
30  {
31  using automaton_t = std::remove_cv_t<Aut>;
32  using self_t = properer;
38 
39  public:
55  properer(automaton_t aut,
56  bool prune = true,
57  const std::string& algo = "auto")
58  : aut_(aut)
59  , prune_(prune)
60  , algo_(algo)
61  {}
62 
65  {
66  return proper_star_<weightset_t::star_status()>();
67  }
68 
70  void here()
71  {
72  proper_star_here_<weightset_t::star_status()>();
73  }
74 
75  private:
76 
77  /*-----------------.
78  | Separate proper. |
79  `-----------------*/
80 
82  {
83  static const auto map
85  {
86  "proper algorithm",
87  {
88  {"auto", "inplace"},
89  {"default", "inplace"},
90  {"distance", [](const self_t& s) {
91  auto r =
93  s.prune_};
94  return r();
95  }},
96  {"inplace", [](const self_t& s) {
97  auto a = copy(s.aut_); // in place
99  return r();
100  }},
101  {"separate", [](const self_t& s) {
102  auto r =
104  s.prune_};
105  return r();
106  }},
107  },
108  };
109  return map[algo_](*this);
110  }
111 
112  template <star_status_t Status>
113  std::enable_if_t<Status == star_status_t::ABSVAL, aut_proper_t>
114  proper_star_() const
115  {
116  require(is_valid(aut_), "proper: invalid automaton");
117  return remover_();
118  }
119 
120  template <star_status_t Status>
121  std::enable_if_t<Status == star_status_t::NON_STARRABLE, aut_proper_t>
122  proper_star_() const
123  {
124  require(is_valid(aut_), "proper: invalid automaton");
125  return remover_();
126  }
127 
128  template <star_status_t Status>
129  std::enable_if_t<Status == star_status_t::STARRABLE, aut_proper_t>
130  proper_star_() const
131  {
132  return remover_();
133  }
134 
135  template <star_status_t Status>
136  std::enable_if_t<Status == star_status_t::TOPS, aut_proper_t>
137  proper_star_() const
138  {
139  try
140  {
141  return remover_();
142  }
143  catch (const std::runtime_error&)
144  {
145  raise("proper: invalid automaton");
146  }
147  }
148 
149 
150  /*-----------------.
151  | In place proper. |
152  `-----------------*/
153 
155  {
156  if (algo_ == "auto" || algo_ == "default" || algo_ == "inplace")
157  {
159  r.in_situ_remover();
160  }
161  else if (algo_ == "separate" || algo_ == "distance")
162  raise("proper: algorithm ", algo_, " cannot be used in place");
163  else
164  raise("proper: invalid algorithm: ", algo_);
165  }
166 
167  template <star_status_t Status>
168  std::enable_if_t<Status == star_status_t::ABSVAL>
170  {
171  require(is_valid(aut_), "proper: invalid automaton");
172  remover_here_();
173  }
174 
175  template <star_status_t Status>
176  std::enable_if_t<Status == star_status_t::NON_STARRABLE>
178  {
179  require(is_valid(aut_), "proper: invalid automaton");
180  remover_here_();
181  }
182 
183  template <star_status_t Status>
184  std::enable_if_t<Status == star_status_t::STARRABLE>
186  {
187  remover_here_();
188  }
189 
190  template <star_status_t Status>
191  std::enable_if_t<Status == star_status_t::TOPS>
193  {
194  try
195  {
196  remover_here_();
197  }
198  catch (const std::runtime_error&)
199  {
200  raise("proper: invalid automaton");
201  }
202  }
203 
204  automaton_t aut_;
205  bool prune_;
206  const std::string& algo_;
207  };
208 
209  template <Automaton Aut>
210  auto make_properer(Aut aut,
211  bool prune = true,
212  const std::string& algo = "auto")
213  {
214  try
215  {
216  return properer<Aut>(aut, prune, algo);
217  }
218  catch(const std::runtime_error& e)
219  {
220  raise(e, " while making proper");
221  }
222  }
223  }
224 
225  /*---------.
226  | proper. |
227  `---------*/
228 
242  template <Automaton Aut>
243  auto
244  proper(const Aut& aut, direction dir = direction::backward,
245  bool prune = true, const std::string& algo = "auto")
247  {
248  switch (dir)
249  {
250  case direction::backward:
251  return detail::make_properer(aut, prune, algo)();
252  case direction::forward:
253  return transpose(proper(transpose(aut),
254  direction::backward, prune, algo));
255  }
257  }
258 
259  template <Automaton Aut>
260  auto
262  bool prune = true)
264  {
266  "backward direction for lazy proper is not implemented");
267  return make_shared_ptr<lazy_proper_automaton<Aut>>(aut, prune);
268  }
269 
277  template <Automaton Aut>
279  bool prune = true, const std::string& algo = "auto")
280  {
281  switch (dir)
282  {
283  case direction::backward:
284  detail::make_properer(aut, prune, algo).here();
285  return;
286  case direction::forward:
287  auto tr_aut = transpose(aut);
288  detail::make_properer(tr_aut, prune, algo).here();
289  return;
290  }
291  }
292 
293  namespace dyn
294  {
295  namespace detail
296  {
298  template <Automaton Aut, typename Dir, typename Bool, typename String>
299  automaton proper(const automaton& aut, direction dir, bool prune,
300  const std::string& algo)
301  {
302  const auto& a = aut->as<Aut>();
303  if (algo == "lazy")
304  return proper_lazy(a, dir, prune);
305  else
306  return ::vcsn::proper(a, dir, prune, algo);
307  }
308  }
309  }
310 } // namespace vcsn
auto proper(const Aut &aut, direction dir=direction::backward, bool prune=true, const std::string &algo="auto") -> fresh_automaton_t_of< Aut, detail::proper_context< context_t_of< Aut >>>
Eliminate spontaneous transitions.
Definition: proper.hh:244
fresh_automaton_t_of< automaton_t, detail::proper_context< context_t_of< automaton_t >>> aut_proper_t
The result type.
Definition: proper.hh:37
auto map(const std::tuple< Ts... > &ts, Fun f) -> decltype(map_tuple_(f, ts, make_index_sequence< sizeof...(Ts)>()))
Map a function on a tuple, return tuple of the results.
Definition: tuple.hh:177
bool is_valid(const Aut &aut)
Definition: is-valid.hh:139
aut_proper_t remover_() const
Definition: proper.hh:81
Definition: a-star.hh:8
This class contains the core of the proper algorithm.
std::enable_if_t< Status==star_status_t::STARRABLE > proper_star_here_()
Definition: proper.hh:185
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
std::enable_if_t< Status==star_status_t::TOPS > proper_star_here_()
Definition: proper.hh:192
aut_proper_t operator()() const
Proper automata with proper context.
Definition: proper.hh:64
labelset_t_of< automaton_t > labelset_t
Definition: proper.hh:34
automaton_t aut_
Definition: proper.hh:204
This class contains the core of the proper algorithm.
Looking upstream.
bool prune_
Whether to prune states that become inaccessible.
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
std::enable_if_t< Status==star_status_t::TOPS, aut_proper_t > proper_star_() const
Definition: proper.hh:137
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54
Spontaneous transition elimination.
Definition: proper.hh:29
std::shared_ptr< detail::lazy_proper_automaton_impl< Aut >> lazy_proper_automaton
Looking downstream.
auto make_properer(Aut aut, bool prune=true, const std::string &algo="auto")
Definition: proper.hh:210
weightset_t_of< automaton_t > weightset_t
Definition: proper.hh:33
std::enable_if_t< Status==star_status_t::NON_STARRABLE, aut_proper_t > proper_star_() const
Definition: proper.hh:122
typename detail::weightset_t_of_impl< base_t< ValueSet >>::type weightset_t_of
Definition: traits.hh:67
A dyn automaton.
Definition: automaton.hh:17
std::enable_if_t< Status==star_status_t::STARRABLE, aut_proper_t > proper_star_() const
Definition: proper.hh:130
std::enable_if_t< Status==star_status_t::NON_STARRABLE > proper_star_here_()
Definition: proper.hh:177
Aut transpose(const transpose_automaton< Aut > &aut)
The transpose of a transpose automaton is the original automaton.
Definition: transpose.hh:253
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
std::enable_if_t< Status==star_status_t::ABSVAL, aut_proper_t > proper_star_() const
Definition: proper.hh:114
automaton proper(const automaton &aut, direction dir, bool prune, const std::string &algo)
Bridge.
Definition: proper.hh:299
A mapping from strings to Values.
Definition: getargs.hh:33
#define BUILTIN_UNREACHABLE()
Definition: builtins.hh:13
auto proper_lazy(const Aut &aut, direction dir=direction::backward, bool prune=true) -> lazy_proper_automaton< Aut >
Definition: proper.hh:261
direction
Orientation.
Definition: direction.hh:11
void here()
In-place spontaneous transition removal.
Definition: proper.hh:70
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37
bool prune_
Whether to prune states that become inaccessible.
properer(automaton_t aut, bool prune=true, const std::string &algo="auto")
Remove the epsilon-transitions of the input.
Definition: proper.hh:55
This class contains the core of the proper algorithm.
auto copy(const AutIn &input, KeepState keep_state, KeepTrans keep_trans) -> decltype(keep_state(input->null_state()), keep_trans(input->null_transition()), make_fresh_automaton< AutIn, AutOut >(input))
A copy of input keeping only its states that are accepted by keep_state, and transitions accepted by ...
Definition: copy.hh:322
const std::string & algo_
Definition: proper.hh:206
std::remove_cv_t< Aut > automaton_t
Definition: proper.hh:31
bool prune_
Whether to prune states that become inaccessible.
void proper_here(Aut &aut, direction dir=direction::backward, bool prune=true, const std::string &algo="auto")
Eliminate spontaneous transitions in place.
Definition: proper.hh:278
std::enable_if_t< Status==star_status_t::ABSVAL > proper_star_here_()
Definition: proper.hh:169
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46