1///////////////////////////////////////////////////////////////
2// Copyright Jens Maurer 2000-2021
3// Copyright Steven Watanabe 2011-2021
4// Copyright John Maddock 2015-2021
5// Copyright Matt Borland 2021
6// Distributed under the Boost Software License, Version 1.0.
7// (See accompanying file LICENSE_1_0.txt or copy at
8// https://www.boost.org/LICENSE_1_0.txt
9//
10// This is a C++11 compliant port of Boost.Random's implementation
11// of uniform_int_distribution. See their comments for detailed
12// descriptions
13
14#ifndef BOOST_MP_UNIFORM_INT_DISTRIBUTION_HPP
15#define BOOST_MP_UNIFORM_INT_DISTRIBUTION_HPP
16
17#include <limits>
18#include <type_traits>
19#include <boost/multiprecision/detail/standalone_config.hpp>
20#include <boost/multiprecision/detail/assert.hpp>
21#include <boost/multiprecision/traits/std_integer_traits.hpp>
22
23namespace boost { namespace multiprecision {
24
25namespace detail {
26
27template <typename T, bool intrinsic>
28struct make_unsigned_impl
29{
30 using type = typename boost::multiprecision::detail::make_unsigned<T>::type;
31};
32
33template <typename T>
34struct make_unsigned_impl<T, false>
35{
36 using type = T;
37};
38
39template <typename T>
40struct make_unsigned_mp
41{
42 using type = typename make_unsigned_impl<T, boost::multiprecision::detail::is_integral<T>::value>::type;
43};
44
45template <typename Engine, typename T>
46T generate_uniform_int (Engine& eng, T min_value, T max_value)
47{
48 using range_type = typename boost::multiprecision::detail::make_unsigned_mp<T>::type;
49 using base_result = typename Engine::result_type;
50 using base_unsigned = typename boost::multiprecision::detail::make_unsigned_mp<base_result>::type;
51
52 const range_type range = max_value - min_value;
53 const base_result bmin = (eng.min)();
54 const base_unsigned brange = (eng.max)() - (eng.min)();
55
56 if(range == 0)
57 {
58 return min_value;
59 }
60 else if (brange < range)
61 {
62 for(;;)
63 {
64 range_type limit;
65 if(range == (std::numeric_limits<range_type>::max)())
66 {
67 limit = range / (range_type(brange) + 1);
68 if(range % (range_type(brange) + 1) == range_type(brange))
69 {
70 ++limit;
71 }
72 }
73 else
74 {
75 limit = (range + 1) / (range_type(brange) + 1);
76 }
77
78 range_type result = 0;
79 range_type mult = 1;
80
81 while (mult <= limit)
82 {
83 result += static_cast<range_type>(static_cast<range_type>(eng() - bmin) * mult);
84
85 if(mult * range_type(brange) == range - mult + 1)
86 {
87 return(result);
88 }
89
90 mult *= range_type(brange)+range_type(1);
91 }
92
93 range_type result_increment = generate_uniform_int(eng, range_type(0), range_type(range/mult));
94
95 if(std::numeric_limits<range_type>::is_bounded && ((std::numeric_limits<range_type>::max)() / mult < result_increment))
96 {
97 continue;
98 }
99
100 result_increment *= mult;
101 result += result_increment;
102
103 if(result < result_increment)
104 {
105 continue;
106 }
107 if(result > range)
108 {
109 continue;
110 }
111
112 return result + min_value;
113 }
114 }
115 else
116 {
117 using mixed_range_type =
118 typename std::conditional<std::numeric_limits<range_type>::is_specialized && std::numeric_limits<base_unsigned>::is_specialized &&
119 (std::numeric_limits<range_type>::digits >= std::numeric_limits<base_unsigned>::digits),
120 range_type, base_unsigned>::type;
121
122 mixed_range_type bucket_size;
123
124 if(brange == (std::numeric_limits<base_unsigned>::max)())
125 {
126 bucket_size = static_cast<mixed_range_type>(brange) / (static_cast<mixed_range_type>(range)+1);
127 if(static_cast<mixed_range_type>(brange) % (static_cast<mixed_range_type>(range)+1) == static_cast<mixed_range_type>(range))
128 {
129 ++bucket_size;
130 }
131 }
132 else
133 {
134 bucket_size = static_cast<mixed_range_type>(brange + 1) / (static_cast<mixed_range_type>(range)+1);
135 }
136
137 for(;;)
138 {
139 mixed_range_type result = eng() - bmin;
140 result /= bucket_size;
141
142 if(result <= static_cast<mixed_range_type>(range))
143 {
144 return result + min_value;
145 }
146 }
147 }
148}
149
150} // Namespace detail
151
152template <typename Integer = int>
153class uniform_int_distribution
154{
155private:
156 Integer min_;
157 Integer max_;
158
159public:
160 class param_type
161 {
162 private:
163 Integer min_;
164 Integer max_;
165
166 public:
167 explicit param_type(Integer min_val, Integer max_val) : min_ {min_val}, max_ {max_val}
168 {
169 BOOST_MP_ASSERT(min_ <= max_);
170 }
171
172 Integer a() const { return min_; }
173 Integer b() const { return max_; }
174 };
175
176 explicit uniform_int_distribution(Integer min_arg, Integer max_arg) : min_ {min_arg}, max_ {max_arg}
177 {
178 BOOST_MP_ASSERT(min_ <= max_);
179 }
180
181 explicit uniform_int_distribution(const param_type& param_arg) : min_ {param_arg.a()}, max_ {param_arg.b()} {}
182
183 Integer min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return min_; }
184 Integer max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return max_; }
185
186 Integer a() const { return min_; }
187 Integer b() const { return max_; }
188
189 param_type param() const { return param_type(min_, max_); }
190
191 void param(const param_type& param_arg)
192 {
193 min_ = param_arg.a();
194 max_ = param_arg.b();
195 }
196
197 template <typename Engine>
198 Integer operator() (Engine& eng) const
199 {
200 return detail::generate_uniform_int(eng, min_, max_);
201 }
202
203 template <typename Engine>
204 Integer operator() (Engine& eng, const param_type& param_arg) const
205 {
206 return detail::generate_uniform_int(eng, param_arg.a(), param_arg.b());
207 }
208};
209
210}} // Namespaces
211
212#endif // BOOST_MP_UNIFORM_INT_DISTRIBUTION_HPP
213

source code of boost/libs/multiprecision/include/boost/multiprecision/detail/uniform_int_distribution.hpp