Vcsn  2.0
Be Rational
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
complete.hh
Go to the documentation of this file.
1 #ifndef VCSN_ALGOS_COMPLETE_HH
2 # define VCSN_ALGOS_COMPLETE_HH
3 
4 # include <queue>
5 # include <unordered_map>
6 
7 # include <vcsn/algos/copy.hh>
8 # include <vcsn/dyn/automaton.hh> // dyn::make_automaton
9 # include <vcsn/dyn/fwd.hh>
11 
12 namespace vcsn
13 {
15  template <typename Aut>
16  Aut&
17  complete_here(Aut& aut)
18  {
19  static_assert(labelset_t_of<Aut>::is_free(),
20  "complete: requires free labelset");
21 
22  using automaton_t = Aut;
23  using state_t = state_t_of<automaton_t>;
24  using letter_t = typename labelset_t_of<automaton_t>::letter_t;
25 
26  // A sink state, to allocate if needed.
27  state_t sink = aut->null_state();
28  const auto& ls = *aut->labelset();
29 
30  if (aut->num_initials() == 0)
31  {
32  sink = aut->new_state();
33  aut->set_initial(sink);
34  }
35 
36  // The outgoing labels of a state.
37  std::unordered_set<letter_t> labels_met;
38  for (auto st : aut->states())
39  if (st != sink)
40  {
41  for (auto tr : aut->out(st))
42  labels_met.insert(aut->label_of(tr));
43 
44  for (auto letter : ls.genset())
45  if (!has(labels_met, letter))
46  {
47  if (sink == aut->null_state())
48  sink = aut->new_state();
49  aut->new_transition(st, sink, letter);
50  }
51 
52  labels_met.clear();
53  }
54 
55  if (sink != aut->null_state())
56  for (auto letter : ls.genset())
57  aut->new_transition(sink, sink, letter);
58 
59  return aut;
60  }
61 
62  template <typename Aut>
63  auto
64  complete(const Aut& aut)
65  -> decltype(::vcsn::copy(aut))
66  {
67  auto res = ::vcsn::copy(aut);
68  complete_here(res);
69  return res;
70  }
71 
72  namespace dyn
73  {
74  namespace detail
75  {
77  template <typename Aut>
78  automaton
79  complete(const automaton& aut)
80  {
81  const auto& a = aut->as<Aut>();
82  return make_automaton(::vcsn::complete(a));
83  }
84 
86  (const automaton& aut) -> automaton);
87  }
88  }
89 
90 } // namespace vcsn
91 
92 #endif // !VCSN_ALGOS_COMPLETE_HH
REGISTER_DECLARE(accessible,(const automaton &) -> automaton)
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:71
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:34
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:77
Aut & complete_here(Aut &aut)
Complete aut and return it.
Definition: complete.hh:17
AutOut copy(const AutIn &input, Pred keep_state)
A copy of input keeping only its states that are accepted by keep_state.
Definition: copy.hh:171
auto complete(const Aut &aut) -> decltype(::vcsn::copy(aut))
Definition: complete.hh:64
automaton complete(const automaton &aut)
Bridge.
Definition: complete.hh:79
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:35
bool has(const std::map< Key, Value, Compare, Alloc > &s, const Key &e)
Definition: map.hh:35