Vcsn  2.4
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  auto num_gens = ls.generators().size();
33 
34  // The outgoing labels of a state.
35  auto labels_met = std::unordered_set<letter_t>{};
36  for (auto st : aut->states())
37  if (st != sink)
38  {
39  labels_met.clear();
40  for (auto tr : out(aut, st))
41  labels_met.insert(aut->label_of(tr));
42 
43  if (labels_met.size() < num_gens)
44  for (auto letter : ls.generators())
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 
53  // Sink is created in two different cases, be careful if you want
54  // to factor.
55  if (sink != aut->null_state())
56  for (auto letter : ls.generators())
57  aut->new_transition(sink, sink, letter);
58 
59  return aut;
60  }
61 
63  template <Automaton Aut>
64  auto
65  complete(const Aut& aut)
66  -> decltype(::vcsn::copy(aut))
67  {
68  auto res = ::vcsn::copy(aut);
70  return res;
71  }
72 
73  namespace dyn
74  {
75  namespace detail
76  {
78  template <Automaton Aut>
79  automaton
80  complete(const automaton& aut)
81  {
82  const auto& a = aut->as<Aut>();
84  }
85  }
86  }
87 
88 } // namespace vcsn
return res
Definition: multiply.hh:398
typename detail::labelset_t_of_impl< base_t< ValueSet >>::type labelset_t_of
Definition: traits.hh:63
automaton complete(const automaton &aut)
Bridge.
Definition: complete.hh:80
Definition: a-star.hh:8
auto out(const Aut &aut, state_t_of< Aut > s)
Indexes of visible transitions leaving state s.
Definition: automaton.hh:85
auto complete(const Aut &aut) -> decltype(::vcsn::copy(aut))
A complete copy of aut.
Definition: complete.hh:65
Aut & complete_here(Aut &aut)
Complete aut and return it.
Definition: complete.hh:13
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
A dyn automaton.
Definition: automaton.hh:17
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
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
auto & as()
Extract wrapped typed automaton.
Definition: automaton.hh:37