libstdc++
uniform_int_dist.h
Go to the documentation of this file.
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
40namespace 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>
75 {
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. */
84 {
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
98 a() const
99 { return _M_a; }
100
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 */
123
124 /**
125 * @brief Constructs a uniform distribution object.
126 */
127 explicit
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
147 a() const
148 { return _M_param.a(); }
149
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 */
173 min() const
174 { return this->a(); }
175
176 /**
177 * @brief Returns the inclusive upper bound of the distribution range.
178 */
180 max() const
181 { return this->b(); }
182
183 /**
184 * @brief Generating functions.
185 */
186 template<typename _UniformRandomNumberGenerator>
188 operator()(_UniformRandomNumberGenerator& __urng)
189 { return this->operator()(__urng, _M_param); }
190
191 template<typename _UniformRandomNumberGenerator>
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
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>
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;
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;
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
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:254
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:230
ISO C++ entities toplevel namespace is std.
Properties of fundamental types.
Definition: limits:313
is_integral
Definition: type_traits:367
common_type
Definition: type_traits:2215
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...
void reset()
Resets the distribution state.
uniform_int_distribution()
Constructs a uniform distribution object.
result_type operator()(_UniformRandomNumberGenerator &__urng)
Generating functions.
void param(const param_type &__param)
Sets the parameter set of the distribution.
result_type min() const
Returns the inclusive lower bound of the distribution range.
friend bool operator==(const uniform_int_distribution &__d1, const uniform_int_distribution &__d2)
Return true if two uniform integer distributions have the same parameters.
uniform_int_distribution(_IntType __a, _IntType __b=numeric_limits< _IntType >::max())
Constructs a uniform distribution object.
result_type max() const
Returns the inclusive upper bound of the distribution range.
param_type param() const
Returns the parameter set of the distribution.