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