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