libstdc++-v3/include/bits/uniform_int_dist.h

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