Vcsn  2.4
Be Rational
u.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <vcsn/ctx/traits.hh>
5 #include <vcsn/dyn/automaton.hh>
6 #include <vcsn/dyn/context.hh>
7 #include <vcsn/misc/raise.hh>
8 
9 namespace vcsn
10 {
11 
13  template <typename Context>
14  mutable_automaton<Context>
15  u(const Context& ctx, unsigned n)
16  {
17  using context_t = Context;
18  using automaton_t = mutable_automaton<context_t>;
19  using state_t = state_t_of<automaton_t>;
20  require(2 <= n, "u: n must be at least 3");
21  const auto& ls = *ctx.labelset();
22  const auto& gens = ls.generators();
23  std::vector<label_t_of<context_t>> letters;
24  for (auto l: gens)
25  letters.emplace_back(ls.value(l));
26  require(3 <= letters.size(), "u: the alphabet needs at least 3 letters");
27  automaton_t res = make_shared_ptr<automaton_t>(ctx);
28 
29  // The states.
30  std::vector<state_t> states;
31  for (unsigned i = 0; i < n; ++i)
32  states.push_back(res->new_state());
33  res->set_initial(states[0]);
34  res->set_final(states[n-1]);
35 
36  // The 'a' transitions.
37  auto a = letters[0];
38  for (unsigned i = 0; i < n; ++i)
39  res->new_transition(states[i], states[(i+1) % n], a);
40 
41  // The 'b' transitions.
42  auto b = letters[1];
43  res->new_transition(states[0], states[1], b);
44  res->new_transition(states[1], states[0], b);
45  for (unsigned i = 2; i < n; ++i)
46  res->new_transition(states[i], states[i], b);
47 
48  // The 'c' transitions.
49  auto c = letters[2];
50  for (unsigned i = 0; i < n - 1; ++i)
51  res->new_transition(states[i], states[i], c);
52  res->new_transition(states[n - 1], states[0], c);
53 
54  return res;
55  }
56 
57  /*---------.
58  | dyn::u. |
59  `---------*/
60 
61  namespace dyn
62  {
63  namespace detail
64  {
66  template <typename Ctx, typename Unsigned>
67  automaton
68  u(const context& ctx, unsigned n)
69  {
70  const auto& c = ctx->as<Ctx>();
71  return ::vcsn::u(c, n);
72  }
73  }
74  }
75 
76 }
mutable_automaton< Context > u(const Context &ctx, unsigned n)
The Brzozowski universal witness.
Definition: u.hh:15
return res
Definition: multiply.hh:398
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
Provide a variadic mul on top of a binary mul(), and one().
Definition: fwd.hh:46
automaton u(const context &ctx, unsigned n)
Bridge.
Definition: u.hh:68
auto & as()
Downcast to the exact type.
Definition: context.hh:36
Definition: a-star.hh:8
Template-less root for contexts.
Definition: context.hh:16
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64