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