Clang Project

include/c++/7/bits/uniform_int_dist.h
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
37namespace 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
std::uniform_int_distribution::param_type
std::uniform_int_distribution::param_type::a
std::uniform_int_distribution::param_type::b
std::uniform_int_distribution::param_type::_M_a
std::uniform_int_distribution::param_type::_M_b
std::uniform_int_distribution::reset
std::uniform_int_distribution::a
std::uniform_int_distribution::b
std::uniform_int_distribution::param
std::uniform_int_distribution::param
std::uniform_int_distribution::min
std::uniform_int_distribution::max
std::uniform_int_distribution::__generate
std::uniform_int_distribution::__generate
std::uniform_int_distribution::__generate
std::uniform_int_distribution::__generate_impl
std::uniform_int_distribution::_M_param
std::uniform_int_distribution::__generate_impl
CodeThinker, Enjoy your reading code