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 
37 namespace 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