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