Vcsn  2.4
Be Rational
divkbaseb.hh
Go to the documentation of this file.
1 #pragma once
2 
4 #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 
14  template <typename Context>
15  mutable_automaton<Context>
16  divkbaseb(const Context& ctx, unsigned divisor, unsigned base)
17  {
18  using context_t = Context;
19  using automaton_t = mutable_automaton<context_t>;
20  using state_t = state_t_of<automaton_t>;
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 
27  require(divisor,
28  "divkbaseb: divisor cannot be 0");
29  require(2 <= base,
30  "divkbaseb: base (", base, ") must be at least 2");
31  VCSN_REQUIRE(base <= letters.size(),
32  "divkbaseb: base (", base,
33  ") must be less than or equal to the alphabet size (",
34  letters.size(), ')');
35 
36  automaton_t res = make_shared_ptr<automaton_t>(ctx);
37 
38  // Add one state for each possible remainder. The last state encountered
39  // during the evaluation will be n % k. If the last state is the state 0,
40  // it means that the residue is 0, ie the word will be accepted, ie the
41  // number is a multiple of k.
42  std::vector<state_t> states;
43  for (unsigned i = 0; i < divisor; ++i)
44  states.emplace_back(res->new_state());
45 
46  res->set_initial(states[0]);
47  res->set_final(states[0]);
48 
49  for (unsigned i = 0; i < divisor; ++i)
50  {
51  int e = i * base;
52  for (unsigned l = 0; l < base; ++l)
53  {
54  int d = (e + l) % divisor;
55  res->new_transition(states[i], states[d], letters[l]);
56  }
57  }
58  return res;
59  }
60 
61 
62  namespace dyn
63  {
64  namespace detail
65  {
67  template <typename Ctx, typename Unsigned1, typename Unsigned2>
68  automaton
69  divkbaseb(const context& ctx, unsigned divisor, unsigned base)
70  {
71  const auto& c = ctx->as<Ctx>();
72  return ::vcsn::divkbaseb(c, divisor, base);
73  }
74  }
75  }
76 }
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
auto & as()
Downcast to the exact type.
Definition: context.hh:36
Definition: a-star.hh:8
#define VCSN_REQUIRE(Cond,...)
A macro similar to require.
Definition: raise.hh:111
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
automaton divkbaseb(const context &ctx, unsigned divisor, unsigned base)
Bridge.
Definition: divkbaseb.hh:69
mutable_automaton< Context > divkbaseb(const Context &ctx, unsigned divisor, unsigned base)
Build the Boolean automaton which accepts a word n representing a number in base "base" if and only i...
Definition: divkbaseb.hh:16