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