Vcsn  2.3
Be Rational
quotkbaseb.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 #include <vcsn/misc/vector.hh> // make_vector
9 
10 namespace vcsn
11 {
12 
15  template <typename Context>
16  mutable_automaton<Context>
17  quotkbaseb(const Context& ctx, unsigned divisor, unsigned base)
18  {
19  // Highly redundant with divkbaseb.
20  using context_t = Context;
21  using automaton_t = mutable_automaton<context_t>;
22  using state_t = state_t_of<automaton_t>;
23  const auto& ls = *ctx.labelset();
24  const auto& gens = ls.generators();
25  auto lgens = detail::make_vector(ls.template set<0>().generators());
26  auto rgens = detail::make_vector(ls.template set<1>().generators());
27 
28  require(divisor,
29  "quotkbaseb: divisor cannot be 0");
30  require(2 <= base,
31  "quotkbaseb: base (", base, ") must be at least 2");
32  VCSN_REQUIRE(base <= lgens.size(),
33  "quotkbaseb: base (", base,
34  ") must be less than or equal to the left alphabet size (",
35  lgens.size(), ')');
36  VCSN_REQUIRE(base <= rgens.size(),
37  "quotkbaseb: base (", base,
38  ") must be less than or equal to the right alphabet size (",
39  rgens.size(), ')');
40 
41  automaton_t res = make_shared_ptr<automaton_t>(ctx);
42 
43  // Add one state for each possible remainder. The last state encountered
44  // during the evaluation will be n % k. If the last state is the state 0,
45  // it means that the residue is 0, ie the word will be accepted, ie the
46  // number is a multiple of k.
47  std::vector<state_t> states;
48  for (unsigned i = 0; i < divisor; ++i)
49  states.emplace_back(res->new_state());
50 
51  res->set_initial(states[0]);
52  res->set_final(states[0]);
53 
54  for (unsigned i = 0; i < divisor; ++i)
55  {
56  int e = i * base;
57  for (unsigned l = 0; l < base; ++l)
58  {
59  int d = (e + l) % divisor;
60  int f = (e + l) / divisor;
61  res->new_transition(states[i], states[d],
62  ls.tuple(lgens[l], rgens[f]));
63  }
64  }
65  return res;
66  }
67 
68 
69  namespace dyn
70  {
71  namespace detail
72  {
74  template <typename Ctx, typename Unsigned1, typename Unsigned2>
75  automaton
76  quotkbaseb(const context& ctx, unsigned divisor, unsigned base)
77  {
78  const auto& c = ctx->as<Ctx>();
79  return ::vcsn::quotkbaseb(c, divisor, base);
80  }
81  }
82  }
83 }
mutable_automaton< Context > quotkbaseb(const Context &ctx, unsigned divisor, unsigned base)
Build the transducer which accepts a word n representing a number in base "base" and outputs the quot...
Definition: quotkbaseb.hh:17
std::vector< typename Cont::value_type > make_vector(const Cont &cont)
The content of cont as a vector.
Definition: vector.hh:20
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
return res
Definition: multiply.hh:398
typename detail::state_t_of_impl< base_t< ValueSet >>::type state_t_of
Definition: traits.hh:64
Template-less root for contexts.
Definition: context.hh:16
Definition: a-star.hh:8
#define VCSN_REQUIRE(Cond,...)
A macro similar to require.
Definition: raise.hh:111
automaton quotkbaseb(const context &ctx, unsigned divisor, unsigned base)
Bridge.
Definition: quotkbaseb.hh:76