1 // Class template uniform_int_distribution -*- C++ -*-
2
3 // Copyright (C) 2009-2020 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /**
26 * @file bits/uniform_int_dist.h
27 * This is an internal header file, included by other library headers.
28 * Do not attempt to use it directly. @headername{random}
29 */
30
31 #ifndef _GLIBCXX_BITS_UNIFORM_INT_DIST_H
32 #define _GLIBCXX_BITS_UNIFORM_INT_DIST_H
33
34 #include <type_traits>
35 #include <limits>
36 #if __cplusplus > 201703L
37 # include <concepts>
38 #endif
39
_GLIBCXX_VISIBILITY(default)40 namespace std _GLIBCXX_VISIBILITY(default)
41 {
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
43
44 #ifdef __cpp_lib_concepts
45 /// Requirements for a uniform random bit generator.
46 template<typename _Gen>
47 concept uniform_random_bit_generator
48 = invocable<_Gen&> && unsigned_integral<invoke_result_t<_Gen&>>
49 && requires
50 {
51 { _Gen::min() } -> same_as<invoke_result_t<_Gen&>>;
52 { _Gen::max() } -> same_as<invoke_result_t<_Gen&>>;
53 requires bool_constant<(_Gen::min() < _Gen::max())>::value;
54 };
55 #endif
56
57 namespace __detail
58 {
59 /* Determine whether number is a power of 2. */
60 template<typename _Tp>
61 inline bool
62 _Power_of_2(_Tp __x)
63 {
64 return ((__x - 1) & __x) == 0;
65 }
66 }
67
68 /**
69 * @brief Uniform discrete distribution for random numbers.
70 * A discrete random distribution on the range @f$[min, max]@f$ with equal
71 * probability throughout the range.
72 */
73 template<typename _IntType = int>
74 class uniform_int_distribution
75 {
76 static_assert(std::is_integral<_IntType>::value,
77 "template argument must be an integral type");
78
79 public:
80 /** The type of the range of the distribution. */
81 typedef _IntType result_type;
82 /** Parameter type. */
83 struct param_type
84 {
85 typedef uniform_int_distribution<_IntType> distribution_type;
86
87 param_type() : param_type(0) { }
88
89 explicit
90 param_type(_IntType __a,
91 _IntType __b = numeric_limits<_IntType>::max())
92 : _M_a(__a), _M_b(__b)
93 {
94 __glibcxx_assert(_M_a <= _M_b);
95 }
96
97 result_type
98 a() const
99 { return _M_a; }
100
101 result_type
102 b() const
103 { return _M_b; }
104
105 friend bool
106 operator==(const param_type& __p1, const param_type& __p2)
107 { return __p1._M_a == __p2._M_a && __p1._M_b == __p2._M_b; }
108
109 friend bool
110 operator!=(const param_type& __p1, const param_type& __p2)
111 { return !(__p1 == __p2); }
112
113 private:
114 _IntType _M_a;
115 _IntType _M_b;
116 };
117
118 public:
119 /**
120 * @brief Constructs a uniform distribution object.
121 */
122 uniform_int_distribution() : uniform_int_distribution(0) { }
123
124 /**
125 * @brief Constructs a uniform distribution object.
126 */
127 explicit
128 uniform_int_distribution(_IntType __a,
129 _IntType __b = numeric_limits<_IntType>::max())
130 : _M_param(__a, __b)
131 { }
132
133 explicit
134 uniform_int_distribution(const param_type& __p)
135 : _M_param(__p)
136 { }
137
138 /**
139 * @brief Resets the distribution state.
140 *
141 * Does nothing for the uniform integer distribution.
142 */
143 void
144 reset() { }
145
146 result_type
147 a() const
148 { return _M_param.a(); }
149
150 result_type
151 b() const
152 { return _M_param.b(); }
153
154 /**
155 * @brief Returns the parameter set of the distribution.
156 */
157 param_type
158 param() const
159 { return _M_param; }
160
161 /**
162 * @brief Sets the parameter set of the distribution.
163 * @param __param The new parameter set of the distribution.
164 */
165 void
166 param(const param_type& __param)
167 { _M_param = __param; }
168
169 /**
170 * @brief Returns the inclusive lower bound of the distribution range.
171 */
172 result_type
173 min() const
174 { return this->a(); }
175
176 /**
177 * @brief Returns the inclusive upper bound of the distribution range.
178 */
179 result_type
180 max() const
181 { return this->b(); }
182
183 /**
184 * @brief Generating functions.
185 */
186 template<typename _UniformRandomNumberGenerator>
187 result_type
188 operator()(_UniformRandomNumberGenerator& __urng)
189 { return this->operator()(__urng, _M_param); }
190
191 template<typename _UniformRandomNumberGenerator>
192 result_type
193 operator()(_UniformRandomNumberGenerator& __urng,
194 const param_type& __p);
195
196 template<typename _ForwardIterator,
197 typename _UniformRandomNumberGenerator>
198 void
199 __generate(_ForwardIterator __f, _ForwardIterator __t,
200 _UniformRandomNumberGenerator& __urng)
201 { this->__generate(__f, __t, __urng, _M_param); }
202
203 template<typename _ForwardIterator,
204 typename _UniformRandomNumberGenerator>
205 void
206 __generate(_ForwardIterator __f, _ForwardIterator __t,
207 _UniformRandomNumberGenerator& __urng,
208 const param_type& __p)
209 { this->__generate_impl(__f, __t, __urng, __p); }
210
211 template<typename _UniformRandomNumberGenerator>
212 void
213 __generate(result_type* __f, result_type* __t,
214 _UniformRandomNumberGenerator& __urng,
215 const param_type& __p)
216 { this->__generate_impl(__f, __t, __urng, __p); }
217
218 /**
219 * @brief Return true if two uniform integer distributions have
220 * the same parameters.
221 */
222 friend bool
223 operator==(const uniform_int_distribution& __d1,
224 const uniform_int_distribution& __d2)
225 { return __d1._M_param == __d2._M_param; }
226
227 private:
228 template<typename _ForwardIterator,
229 typename _UniformRandomNumberGenerator>
230 void
231 __generate_impl(_ForwardIterator __f, _ForwardIterator __t,
232 _UniformRandomNumberGenerator& __urng,
233 const param_type& __p);
234
235 param_type _M_param;
236 };
237
238 template<typename _IntType>
239 template<typename _UniformRandomNumberGenerator>
240 typename uniform_int_distribution<_IntType>::result_type
241 uniform_int_distribution<_IntType>::
242 operator()(_UniformRandomNumberGenerator& __urng,
243 const param_type& __param)
244 {
245 typedef typename _UniformRandomNumberGenerator::result_type
246 _Gresult_type;
247 typedef typename std::make_unsigned<result_type>::type __utype;
248 typedef typename std::common_type<_Gresult_type, __utype>::type
249 __uctype;
250
251 const __uctype __urngmin = __urng.min();
252 const __uctype __urngmax = __urng.max();
253 const __uctype __urngrange = __urngmax - __urngmin;
254 const __uctype __urange
255 = __uctype(__param.b()) - __uctype(__param.a());
256
257 __uctype __ret;
258
259 if (__urngrange > __urange)
260 {
261 // downscaling
262 const __uctype __uerange = __urange + 1; // __urange can be zero
263 const __uctype __scaling = __urngrange / __uerange;
264 const __uctype __past = __uerange * __scaling;
265 do
266 __ret = __uctype(__urng()) - __urngmin;
267 while (__ret >= __past);
268 __ret /= __scaling;
269 }
270 else if (__urngrange < __urange)
271 {
272 // upscaling
273 /*
274 Note that every value in [0, urange]
275 can be written uniquely as
276
277 (urngrange + 1) * high + low
278
279 where
280
281 high in [0, urange / (urngrange + 1)]
282
283 and
284
285 low in [0, urngrange].
286 */
287 __uctype __tmp; // wraparound control
288 do
289 {
290 const __uctype __uerngrange = __urngrange + 1;
291 __tmp = (__uerngrange * operator()
292 (__urng, param_type(0, __urange / __uerngrange)));
293 __ret = __tmp + (__uctype(__urng()) - __urngmin);
294 }
295 while (__ret > __urange || __ret < __tmp);
296 }
297 else
298 __ret = __uctype(__urng()) - __urngmin;
299
300 return __ret + __param.a();
301 }
302
303
304 template<typename _IntType>
305 template<typename _ForwardIterator,
306 typename _UniformRandomNumberGenerator>
307 void
308 uniform_int_distribution<_IntType>::
309 __generate_impl(_ForwardIterator __f, _ForwardIterator __t,
310 _UniformRandomNumberGenerator& __urng,
311 const param_type& __param)
312 {
313 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
314 typedef typename _UniformRandomNumberGenerator::result_type
315 _Gresult_type;
316 typedef typename std::make_unsigned<result_type>::type __utype;
317 typedef typename std::common_type<_Gresult_type, __utype>::type
318 __uctype;
319
320 const __uctype __urngmin = __urng.min();
321 const __uctype __urngmax = __urng.max();
322 const __uctype __urngrange = __urngmax - __urngmin;
323 const __uctype __urange
324 = __uctype(__param.b()) - __uctype(__param.a());
325
326 __uctype __ret;
327
328 if (__urngrange > __urange)
329 {
330 if (__detail::_Power_of_2(__urngrange + 1)
331 && __detail::_Power_of_2(__urange + 1))
332 {
333 while (__f != __t)
334 {
335 __ret = __uctype(__urng()) - __urngmin;
336 *__f++ = (__ret & __urange) + __param.a();
337 }
338 }
339 else
340 {
341 // downscaling
342 const __uctype __uerange = __urange + 1; // __urange can be zero
343 const __uctype __scaling = __urngrange / __uerange;
344 const __uctype __past = __uerange * __scaling;
345 while (__f != __t)
346 {
347 do
348 __ret = __uctype(__urng()) - __urngmin;
349 while (__ret >= __past);
350 *__f++ = __ret / __scaling + __param.a();
351 }
352 }
353 }
354 else if (__urngrange < __urange)
355 {
356 // upscaling
357 /*
358 Note that every value in [0, urange]
359 can be written uniquely as
360
361 (urngrange + 1) * high + low
362
363 where
364
365 high in [0, urange / (urngrange + 1)]
366
367 and
368
369 low in [0, urngrange].
370 */
371 __uctype __tmp; // wraparound control
372 while (__f != __t)
373 {
374 do
375 {
376 const __uctype __uerngrange = __urngrange + 1;
377 __tmp = (__uerngrange * operator()
378 (__urng, param_type(0, __urange / __uerngrange)));
379 __ret = __tmp + (__uctype(__urng()) - __urngmin);
380 }
381 while (__ret > __urange || __ret < __tmp);
382 *__f++ = __ret;
383 }
384 }
385 else
386 while (__f != __t)
387 *__f++ = __uctype(__urng()) - __urngmin + __param.a();
388 }
389
390 // operator!= and operator<< and operator>> are defined in <bits/random.h>
391
392 _GLIBCXX_END_NAMESPACE_VERSION
393 } // namespace std
394
395 #endif
396