Vcsn  2.3
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:
54  properer(automaton_t aut,
55  bool prune = true,
56  const std::string& algo = "auto")
57  : aut_(aut)
58  , prune_(prune)
59  , algo_(algo)
60  {}
61 
64  {
65  return proper_star_<weightset_t::star_status()>();
66  }
67 
69  void here()
70  {
71  proper_star_here_<weightset_t::star_status()>();
72  }
73 
74  private:
75 
76  /*-----------------.
77  | Separate proper. |
78  `-----------------*/
79 
81  {
82  static const auto map
84  {
85  "proper algorithm",
86  {
87  {"auto", "inplace"},
88  {"default", "inplace"},
89  {"distance", [](const self_t& s) {
90  auto r =
92  s.prune_};
93  return r();
94  }},
95  {"inplace", [](const self_t& s) {
96  auto a = copy(s.aut_); // in place
98  return r();
99  }},
100  {"separate", [](const self_t& s) {
101  auto r =
103  s.prune_};
104  return r();
105  }},
106  },
107  };
108  return map[algo_](*this);
109  }
110 
111  template <star_status_t Status>
112  std::enable_if_t<Status == star_status_t::ABSVAL, aut_proper_t>
113  proper_star_() const
114  {
115  require(is_valid(aut_), "proper: invalid automaton");
116  return remover_();
117  }
118 
119  template <star_status_t Status>
120  std::enable_if_t<Status == star_status_t::NON_STARRABLE, aut_proper_t>
121  proper_star_() const
122  {
123  require(is_valid(aut_), "proper: invalid automaton");
124  return remover_();
125  }
126 
127  template <star_status_t Status>
128  std::enable_if_t<Status == star_status_t::STARRABLE, aut_proper_t>
129  proper_star_() const
130  {
131  return remover_();
132  }
133 
134  template <star_status_t Status>
135  std::enable_if_t<Status == star_status_t::TOPS, aut_proper_t>
136  proper_star_() const
137  {
138  try
139  {
140  return remover_();
141  }
142  catch (const std::runtime_error&)
143  {
144  raise("proper: invalid automaton");
145  }
146  }
147 
148 
149  /*-----------------.
150  | In place proper. |
151  `-----------------*/
152 
154  {
155  if (algo_ == "auto" || algo_ == "default" || algo_ == "inplace")
156  {
158  r.in_situ_remover();
159  }
160  else if (algo_ == "separate" || algo_ == "distance")
161  raise("proper: algorithm ", algo_, " cannot be used in place");
162  else
163  raise("proper: invalid algorithm: ", algo_);
164  }
165 
166  template <star_status_t Status>
167  std::enable_if_t<Status == star_status_t::ABSVAL>
169  {
170  require(is_valid(aut_), "proper: invalid automaton");
171  remover_here_();
172  }
173 
174  template <star_status_t Status>
175  std::enable_if_t<Status == star_status_t::NON_STARRABLE>
177  {
178  require(is_valid(aut_), "proper: invalid automaton");
179  remover_here_();
180  }
181 
182  template <star_status_t Status>
183  std::enable_if_t<Status == star_status_t::STARRABLE>
185  {
186  remover_here_();
187  }
188 
189  template <star_status_t Status>
190  std::enable_if_t<Status == star_status_t::TOPS>
192  {
193  try
194  {
195  remover_here_();
196  }
197  catch (const std::runtime_error&)
198  {
199  raise("proper: invalid automaton");
200  }
201  }
202 
203  automaton_t aut_;
204  bool prune_;
205  const std::string& algo_;
206  };
207 
208  template <Automaton Aut>
209  auto make_properer(Aut aut,
210  bool prune = true,
211  const std::string& algo = "auto")
212  {
213  try
214  {
215  return properer<Aut>(aut, prune, algo);
216  }
217  catch(const std::runtime_error& e)
218  {
219  raise(e, " while making proper");
220  }
221  }
222  }
223 
224  /*---------.
225  | proper. |
226  `---------*/
227 
241  template <Automaton Aut>
242  auto
243  proper(const Aut& aut, direction dir = direction::backward,
244  bool prune = true, const std::string& algo = "auto")
246  {
247  switch (dir)
248  {
249  case direction::backward:
250  return detail::make_properer(aut, prune, algo)();
251  case direction::forward:
252  return transpose(proper(transpose(aut),
253  direction::backward, prune, algo));
254  }
256  }
257 
258  template <Automaton Aut>
259  auto
261  bool prune = true)
263  {
265  "backward direction for lazy proper is not implemented");
266  return make_shared_ptr<lazy_proper_automaton<Aut>>(aut, prune);
267  }
268 
275  template <Automaton Aut>
277  bool prune = true, const std::string& algo = "auto")
278  {
279  switch (dir)
280  {
281  case direction::backward:
282  detail::make_properer(aut, prune, algo).here();
283  return;
284  case direction::forward:
285  auto tr_aut = transpose(aut);
286  detail::make_properer(tr_aut, prune, algo).here();
287  return;
288  }
289  }
290 
291  namespace dyn
292  {
293  namespace detail
294  {
296  template <Automaton Aut, typename Dir, typename Bool, typename String>
297  automaton proper(const automaton& aut, direction dir, bool prune,
298  const std::string& algo)
299  {
300  const auto& a = aut->as<Aut>();
301  if (algo == "lazy")
302  return proper_lazy(a, dir, prune);
303  else
304  return ::vcsn::proper(a, dir, prune, algo);
305  }
306  }
307  }
308 } // namespace vcsn
std::enable_if_t< Status==star_status_t::STARRABLE, aut_proper_t > proper_star_() const
Definition: proper.hh:129
bool prune_
Whether to prune states that become inaccessible.
std::enable_if_t< Status==star_status_t::NON_STARRABLE > proper_star_here_()
Definition: proper.hh:176
weightset_t_of< automaton_t > weightset_t
Definition: proper.hh:33
Aut transpose(const transpose_automaton< Aut > &aut)
Definition: transpose.hh:238
#define BUILTIN_UNREACHABLE()
Definition: builtins.hh:13
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:243
std::shared_ptr< detail::lazy_proper_automaton_impl< Aut >> lazy_proper_automaton
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
This class contains the core of the proper algorithm.
std::enable_if_t< Status==star_status_t::ABSVAL, aut_proper_t > proper_star_() const
Definition: proper.hh:113
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
Looking downstream.
automaton proper(const automaton &aut, direction dir, bool prune, const std::string &algo)
Bridge.
Definition: proper.hh:297
bool prune_
Whether to prune states that become inaccessible.
auto proper_lazy(const Aut &aut, direction dir=direction::backward, bool prune=true) -> lazy_proper_automaton< Aut >
Definition: proper.hh:260
direction
Orientation.
Definition: direction.hh:11
void here()
In-place spontaneous transition removal.
Definition: proper.hh:69
properer(automaton_t aut, bool prune=true, const std::string &algo="auto")
Remove the epsilon-transitions of the input.
Definition: proper.hh:54
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
Looking upstream.
const std::string & algo_
Definition: proper.hh:205
std::remove_cv_t< Aut > automaton_t
Definition: proper.hh:31
Definition: a-star.hh:8
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:276
std::enable_if_t< Status==star_status_t::ABSVAL > proper_star_here_()
Definition: proper.hh:168
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
std::enable_if_t< Status==star_status_t::STARRABLE > proper_star_here_()
Definition: proper.hh:184
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
Spontaneous transition elimination.
Definition: proper.hh:29
bool prune_
Whether to prune states that become inaccessible.
aut_proper_t remover_() const
Definition: proper.hh:80
auto make_properer(Aut aut, bool prune=true, const std::string &algo="auto")
Definition: proper.hh:209
This class contains the core of the proper algorithm.
labelset_t_of< automaton_t > labelset_t
Definition: proper.hh:34
automaton_t aut_
Definition: proper.hh:203
std::enable_if_t< Status==star_status_t::TOPS, aut_proper_t > proper_star_() const
Definition: proper.hh:136
std::enable_if_t< Status==star_status_t::TOPS > proper_star_here_()
Definition: proper.hh:191
aut_proper_t operator()() const
Proper automata with proper context.
Definition: proper.hh:63
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
A mapping from strings to Values.
Definition: getargs.hh:33
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
std::enable_if_t< Status==star_status_t::NON_STARRABLE, aut_proper_t > proper_star_() const
Definition: proper.hh:121
weightset_mixin< detail::r_impl > r
Definition: fwd.hh:54