1// Class template uniform_int_distribution -*- C++ -*-
2
3// Copyright (C) 2009-2018 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
37namespace std _GLIBCXX_VISIBILITY(default)
38{
39_GLIBCXX_BEGIN_NAMESPACE_VERSION
40
41 namespace __detail
42 {
43 /* Determine whether number is a power of 2. */
44 template<typename _Tp>
45 inline bool
46 _Power_of_2(_Tp __x)
47 {
48 return ((__x - 1) & __x) == 0;
49 }
50 }
51
52 /**
53 * @brief Uniform discrete distribution for random numbers.
54 * A discrete random distribution on the range @f$[min, max]@f$ with equal
55 * probability throughout the range.
56 */
57 template<typename _IntType = int>
58 class uniform_int_distribution
59 {
60 static_assert(std::is_integral<_IntType>::value,
61 "template argument must be an integral type");
62
63 public:
64 /** The type of the range of the distribution. */
65 typedef _IntType result_type;
66 /** Parameter type. */
67 struct param_type
68 {
69 typedef uniform_int_distribution<_IntType> distribution_type;
70
71 explicit
72 param_type(_IntType __a = 0,
73 _IntType __b = std::numeric_limits<_IntType>::max())
74 : _M_a(__a), _M_b(__b)
75 {
76 __glibcxx_assert(_M_a <= _M_b);
77 }
78
79 result_type
80 a() const
81 { return _M_a; }
82
83 result_type
84 b() const
85 { return _M_b; }
86
87 friend bool
88 operator==(const param_type& __p1, const param_type& __p2)
89 { return __p1._M_a == __p2._M_a && __p1._M_b == __p2._M_b; }
90
91 friend bool
92 operator!=(const param_type& __p1, const param_type& __p2)
93 { return !(__p1 == __p2); }
94
95 private:
96 _IntType _M_a;
97 _IntType _M_b;
98 };
99
100 public:
101 /**
102 * @brief Constructs a uniform distribution object.
103 */
104 explicit
105 uniform_int_distribution(_IntType __a = 0,
106 _IntType __b = std::numeric_limits<_IntType>::max())
107 : _M_param(__a, __b)
108 { }
109
110 explicit
111 uniform_int_distribution(const param_type& __p)
112 : _M_param(__p)
113 { }
114
115 /**
116 * @brief Resets the distribution state.
117 *
118 * Does nothing for the uniform integer distribution.
119 */
120 void
121 reset() { }
122
123 result_type
124 a() const
125 { return _M_param.a(); }
126
127 result_type
128 b() const
129 { return _M_param.b(); }
130
131 /**
132 * @brief Returns the parameter set of the distribution.
133 */
134 param_type
135 param() const
136 { return _M_param; }
137
138 /**
139 * @brief Sets the parameter set of the distribution.
140 * @param __param The new parameter set of the distribution.
141 */
142 void
143 param(const param_type& __param)
144 { _M_param = __param; }
145
146 /**
147 * @brief Returns the inclusive lower bound of the distribution range.
148 */
149 result_type
150 min() const
151 { return this->a(); }
152
153 /**
154 * @brief Returns the inclusive upper bound of the distribution range.
155 */
156 result_type
157 max() const
158 { return this->b(); }
159
160 /**
161 * @brief Generating functions.
162 */
163 template<typename _UniformRandomNumberGenerator>
164 result_type
165 operator()(_UniformRandomNumberGenerator& __urng)
166 { return this->operator()(__urng, _M_param); }
167
168 template<typename _UniformRandomNumberGenerator>
169 result_type
170 operator()(_UniformRandomNumberGenerator& __urng,
171 const param_type& __p);
172
173 template<typename _ForwardIterator,
174 typename _UniformRandomNumberGenerator>
175 void
176 __generate(_ForwardIterator __f, _ForwardIterator __t,
177 _UniformRandomNumberGenerator& __urng)
178 { this->__generate(__f, __t, __urng, _M_param); }
179
180 template<typename _ForwardIterator,
181 typename _UniformRandomNumberGenerator>
182 void
183 __generate(_ForwardIterator __f, _ForwardIterator __t,
184 _UniformRandomNumberGenerator& __urng,
185 const param_type& __p)
186 { this->__generate_impl(__f, __t, __urng, __p); }
187
188 template<typename _UniformRandomNumberGenerator>
189 void
190 __generate(result_type* __f, result_type* __t,
191 _UniformRandomNumberGenerator& __urng,
192 const param_type& __p)
193 { this->__generate_impl(__f, __t, __urng, __p); }
194
195 /**
196 * @brief Return true if two uniform integer distributions have
197 * the same parameters.
198 */
199 friend bool
200 operator==(const uniform_int_distribution& __d1,
201 const uniform_int_distribution& __d2)
202 { return __d1._M_param == __d2._M_param; }
203
204 private:
205 template<typename _ForwardIterator,
206 typename _UniformRandomNumberGenerator>
207 void
208 __generate_impl(_ForwardIterator __f, _ForwardIterator __t,
209 _UniformRandomNumberGenerator& __urng,
210 const param_type& __p);
211
212 param_type _M_param;
213 };
214
215 template<typename _IntType>
216 template<typename _UniformRandomNumberGenerator>
217 typename uniform_int_distribution<_IntType>::result_type
218 uniform_int_distribution<_IntType>::
219 operator()(_UniformRandomNumberGenerator& __urng,
220 const param_type& __param)
221 {
222 typedef typename _UniformRandomNumberGenerator::result_type
223 _Gresult_type;
224 typedef typename std::make_unsigned<result_type>::type __utype;
225 typedef typename std::common_type<_Gresult_type, __utype>::type
226 __uctype;
227
228 const __uctype __urngmin = __urng.min();
229 const __uctype __urngmax = __urng.max();
230 const __uctype __urngrange = __urngmax - __urngmin;
231 const __uctype __urange
232 = __uctype(__param.b()) - __uctype(__param.a());
233
234 __uctype __ret;
235
236 if (__urngrange > __urange)
237 {
238 // downscaling
239 const __uctype __uerange = __urange + 1; // __urange can be zero
240 const __uctype __scaling = __urngrange / __uerange;
241 const __uctype __past = __uerange * __scaling;
242 do
243 __ret = __uctype(__urng()) - __urngmin;
244 while (__ret >= __past);
245 __ret /= __scaling;
246 }
247 else if (__urngrange < __urange)
248 {
249 // upscaling
250 /*
251 Note that every value in [0, urange]
252 can be written uniquely as
253
254 (urngrange + 1) * high + low
255
256 where
257
258 high in [0, urange / (urngrange + 1)]
259
260 and
261
262 low in [0, urngrange].
263 */
264 __uctype __tmp; // wraparound control
265 do
266 {
267 const __uctype __uerngrange = __urngrange + 1;
268 __tmp = (__uerngrange * operator()
269 (__urng, param_type(0, __urange / __uerngrange)));
270 __ret = __tmp + (__uctype(__urng()) - __urngmin);
271 }
272 while (__ret > __urange || __ret < __tmp);
273 }
274 else
275 __ret = __uctype(__urng()) - __urngmin;
276
277 return __ret + __param.a();
278 }
279
280
281 template<typename _IntType>
282 template<typename _ForwardIterator,
283 typename _UniformRandomNumberGenerator>
284 void
285 uniform_int_distribution<_IntType>::
286 __generate_impl(_ForwardIterator __f, _ForwardIterator __t,
287 _UniformRandomNumberGenerator& __urng,
288 const param_type& __param)
289 {
290 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
291 typedef typename _UniformRandomNumberGenerator::result_type
292 _Gresult_type;
293 typedef typename std::make_unsigned<result_type>::type __utype;
294 typedef typename std::common_type<_Gresult_type, __utype>::type
295 __uctype;
296
297 const __uctype __urngmin = __urng.min();
298 const __uctype __urngmax = __urng.max();
299 const __uctype __urngrange = __urngmax - __urngmin;
300 const __uctype __urange
301 = __uctype(__param.b()) - __uctype(__param.a());
302
303 __uctype __ret;
304
305 if (__urngrange > __urange)
306 {
307 if (__detail::_Power_of_2(__urngrange + 1)
308 && __detail::_Power_of_2(__urange + 1))
309 {
310 while (__f != __t)
311 {
312 __ret = __uctype(__urng()) - __urngmin;
313 *__f++ = (__ret & __urange) + __param.a();
314 }
315 }
316 else
317 {
318 // downscaling
319 const __uctype __uerange = __urange + 1; // __urange can be zero
320 const __uctype __scaling = __urngrange / __uerange;
321 const __uctype __past = __uerange * __scaling;
322 while (__f != __t)
323 {
324 do
325 __ret = __uctype(__urng()) - __urngmin;
326 while (__ret >= __past);
327 *__f++ = __ret / __scaling + __param.a();
328 }
329 }
330 }
331 else if (__urngrange < __urange)
332 {
333 // upscaling
334 /*
335 Note that every value in [0, urange]
336 can be written uniquely as
337
338 (urngrange + 1) * high + low
339
340 where
341
342 high in [0, urange / (urngrange + 1)]
343
344 and
345
346 low in [0, urngrange].
347 */
348 __uctype __tmp; // wraparound control
349 while (__f != __t)
350 {
351 do
352 {
353 const __uctype __uerngrange = __urngrange + 1;
354 __tmp = (__uerngrange * operator()
355 (__urng, param_type(0, __urange / __uerngrange)));
356 __ret = __tmp + (__uctype(__urng()) - __urngmin);
357 }
358 while (__ret > __urange || __ret < __tmp);
359 *__f++ = __ret;
360 }
361 }
362 else
363 while (__f != __t)
364 *__f++ = __uctype(__urng()) - __urngmin + __param.a();
365 }
366
367 // operator!= and operator<< and operator>> are defined in <bits/random.h>
368
369_GLIBCXX_END_NAMESPACE_VERSION
370} // namespace std
371
372#endif
373