Vcsn  2.2
Be Rational
complete.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <vcsn/algos/copy.hh>
4 #include <vcsn/dyn/automaton.hh> // dyn::make_automaton
5 #include <vcsn/dyn/fwd.hh>
7 
8 namespace vcsn
9 {
11  template <Automaton Aut>
12  Aut&
13  complete_here(Aut& aut)
14  {
15  static_assert(labelset_t_of<Aut>::is_free(),
16  "complete: requires free labelset");
17 
18  using automaton_t = Aut;
19  using state_t = state_t_of<automaton_t>;
20  using letter_t = typename labelset_t_of<automaton_t>::letter_t;
21 
22  // A sink state, to allocate if needed.
23  state_t sink = aut->null_state();
24  const auto& ls = *aut->labelset();
25 
26  if (aut->num_initials() == 0)
27  {
28  sink = aut->new_state();
29  aut->set_initial(sink);
30  }
31 
32  // The outgoing labels of a state.
33  std::unordered_set<letter_t> labels_met;
34  for (auto st : aut->states())
35  if (st != sink)
36  {
37  labels_met.clear();
38  for (auto tr : out(aut, st))
39  labels_met.insert(aut->label_of(tr));
40 
41  for (auto letter : ls.generators())
42  if (!has(labels_met, letter))
43  {
44  if (sink == aut->null_state())
45  sink = aut->new_state();
46  aut->new_transition(st, sink, letter);
47  }
48  }
49 
50  // Sink is created in two different cases, be careful if you want
51  // to factor.
52  if (sink != aut->null_state())
53  for (auto letter : ls.generators())
54  aut->new_transition(sink, sink, letter);
55 
56  return aut;
57  }
58 
59  template <Automaton Aut>
60  auto
61  complete(const Aut& aut)
62  -> decltype(::vcsn::copy(aut))
63  {
64  auto res = ::vcsn::copy(aut);
65  complete_here(res);
66  return res;
67  }
68 
69  namespace dyn
70  {
71  namespace detail
72  {
74  template <Automaton Aut>
75  automaton
76  complete(const automaton& aut)
77  {
78  const auto& a = aut->as<Aut>();
79  return make_automaton(::vcsn::complete(a));
80  }
81  }
82  }
83 
84 } // namespace vcsn
auto complete(const Aut &aut) -> decltype(::vcsn::copy(aut))
Definition: complete.hh:61
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:75
Definition: a-star.hh:8
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:55
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
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
Aut & complete_here(Aut &aut)
Complete aut and return it.
Definition: complete.hh:13
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
automaton complete(const automaton &aut)
Bridge.
Definition: complete.hh:76
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:308