Vcsn  2.2
Be Rational
de-bruijn.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <iterator> // std::distance
4 #include <stdexcept>
5 
6 #include <vcsn/alphabets/char.hh>
9 #include <vcsn/dyn/automaton.hh>
10 #include <vcsn/dyn/context.hh>
11 #include <vcsn/misc/algorithm.hh> // vcsn::front
12 #include <vcsn/misc/raise.hh>
13 
14 namespace vcsn
15 {
16  // (a+b)*a(a+b)^n.
17  template <typename Context>
18  mutable_automaton<Context>
19  de_bruijn(const Context& ctx, unsigned n)
20  {
21  const auto& ls = *ctx.labelset();
22  const auto& gens = ls.generators();
23  size_t sz = boost::distance(gens);
24  require(2 <= sz, "de_bruijn: the alphabet needs at least 2 letters");
25  using context_t = Context;
26  using automaton_t = mutable_automaton<context_t>;
27  automaton_t res = make_shared_ptr<automaton_t>(ctx);
28 
29  auto init = res->new_state();
30  res->set_initial(init);
31  for (auto l: gens)
32  res->new_transition(init, init, ls.value(l));
33 
34  auto prev = res->new_state();
35  res->new_transition(init, prev, ls.value(detail::front(gens)));
36 
37  while (n--)
38  {
39  auto next = res->new_state();
40  for (auto l: gens)
41  res->new_transition(prev, next, ls.value(l));
42  prev = next;
43  }
44  res->set_final(prev);
45  return res;
46  }
47 
48  /*-----------------.
49  | dyn::de_bruijn. |
50  `-----------------*/
51 
52  namespace dyn
53  {
54  namespace detail
55  {
57  template <typename Ctx, typename Unsigned>
58  automaton
59  de_bruijn(const dyn::context& ctx, unsigned n)
60  {
61  const auto& c = ctx->as<Ctx>();
62  return make_automaton(::vcsn::de_bruijn(c, n));
63  }
64  }
65  }
66 
67 }
automaton make_automaton(const Aut &aut)
Build a dyn::automaton.
Definition: automaton.hh:75
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
Definition: a-star.hh:8
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:78
mutable_automaton< Context > de_bruijn(const Context &ctx, unsigned n)
Definition: de-bruijn.hh:19
std::shared_ptr< const detail::context_base > context
A dyn::context.
Definition: fwd.hh:43
std::shared_ptr< detail::automaton_base > automaton
Definition: automaton.hh:69
automaton de_bruijn(const dyn::context &ctx, unsigned n)
Bridge.
Definition: de-bruijn.hh:59
static dyn::context ctx(const driver &d)
Get the context of the driver.
Definition: parse.cc:82
Container::value_type front(const Container &container)
The first member of this Container.
Definition: algorithm.hh:58