Vcsn  2.3
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 
7 #include <vcsn/dyn/automaton.hh>
8 #include <vcsn/dyn/context.hh>
9 #include <vcsn/misc/algorithm.hh> // vcsn::front
10 #include <vcsn/misc/raise.hh>
11 
12 namespace vcsn
13 {
14  // (a+b)*a(a+b)^n.
15  template <typename Context>
16  mutable_automaton<Context>
17  de_bruijn(const Context& ctx, unsigned n)
18  {
19  const auto& ls = *ctx.labelset();
20  const auto& gens = ls.generators();
21  size_t sz = boost::distance(gens);
22  require(2 <= sz, "de_bruijn: the alphabet needs at least 2 letters");
23  using context_t = Context;
24  using automaton_t = mutable_automaton<context_t>;
25  automaton_t res = make_shared_ptr<automaton_t>(ctx);
26 
27  auto init = res->new_state();
28  res->set_initial(init);
29  for (auto l: gens)
30  res->new_transition(init, init, ls.value(l));
31 
32  auto prev = res->new_state();
33  res->new_transition(init, prev, ls.value(detail::front(gens)));
34 
35  while (n--)
36  {
37  auto next = res->new_state();
38  for (auto l: gens)
39  res->new_transition(prev, next, ls.value(l));
40  prev = next;
41  }
42  res->set_final(prev);
43  return res;
44  }
45 
46  /*-----------------.
47  | dyn::de_bruijn. |
48  `-----------------*/
49 
50  namespace dyn
51  {
52  namespace detail
53  {
55  template <typename Ctx, typename Unsigned>
56  automaton
57  de_bruijn(const dyn::context& ctx, unsigned n)
58  {
59  const auto& c = ctx->as<Ctx>();
61  }
62  }
63  }
64 
65 }
std::shared_ptr< detail::mutable_automaton_impl< Context >> mutable_automaton
Definition: fwd.hh:25
automaton de_bruijn(const dyn::context &ctx, unsigned n)
Bridge.
Definition: de-bruijn.hh:57
void require(Bool b, Args &&...args)
If b is not verified, raise an error with args as message.
Definition: raise.hh:91
auto & as()
Downcast to the exact type.
Definition: context.hh:36
return res
Definition: multiply.hh:398
Template-less root for contexts.
Definition: context.hh:16
Definition: a-star.hh:8
Container::value_type front(const Container &container)
The first member of this Container.
Definition: algorithm.hh:68
mutable_automaton< Context > de_bruijn(const Context &ctx, unsigned n)
Definition: de-bruijn.hh:17