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

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