LCOV - code coverage report
Current view: top level - usr/include/c++/7/bits - uniform_int_dist.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 33 35 94.3 %
Date: 2020-10-15 20:26:03 Functions: 6 6 100.0 %

          Line data    Source code
       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             : 
      37             : namespace 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       99894 :         param_type(_IntType __a = 0,
      76             :                    _IntType __b = std::numeric_limits<_IntType>::max())
      77       99894 :         : _M_a(__a), _M_b(__b)
      78             :         {
      79             :           __glibcxx_assert(_M_a <= _M_b);
      80       99894 :         }
      81             : 
      82             :         result_type
      83      199788 :         a() const
      84      199788 :         { return _M_a; }
      85             : 
      86             :         result_type
      87       99894 :         b() const
      88       99894 :         { 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       58738 :       uniform_int_distribution(_IntType __a = 0,
     109             :                            _IntType __b = std::numeric_limits<_IntType>::max())
     110       58738 :       : _M_param(__a, __b)
     111       58738 :       { }
     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       58738 :         operator()(_UniformRandomNumberGenerator& __urng)
     169       58738 :         { 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       99894 :       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       99894 :         const __uctype __urngmin = __urng.min();
     232       99894 :         const __uctype __urngmax = __urng.max();
     233       99894 :         const __uctype __urngrange = __urngmax - __urngmin;
     234       99894 :         const __uctype __urange
     235       99894 :           = __uctype(__param.b()) - __uctype(__param.a());
     236             : 
     237             :         __uctype __ret;
     238             : 
     239       99894 :         if (__urngrange > __urange)
     240             :           {
     241             :             // downscaling
     242       79414 :             const __uctype __uerange = __urange + 1; // __urange can be zero
     243       79414 :             const __uctype __scaling = __urngrange / __uerange;
     244       79414 :             const __uctype __past = __uerange * __scaling;
     245           0 :             do
     246       79414 :               __ret = __uctype(__urng()) - __urngmin;
     247       79414 :             while (__ret >= __past);
     248       79414 :             __ret /= __scaling;
     249             :           }
     250       20480 :         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       20676 :             do
     269             :               {
     270       41156 :                 const __uctype __uerngrange = __urngrange + 1;
     271       41156 :                 __tmp = (__uerngrange * operator()
     272       82312 :                          (__urng, param_type(0, __urange / __uerngrange)));
     273       41156 :                 __ret = __tmp + (__uctype(__urng()) - __urngmin);
     274             :               }
     275       41156 :             while (__ret > __urange || __ret < __tmp);
     276             :           }
     277             :         else
     278           0 :           __ret = __uctype(__urng()) - __urngmin;
     279             : 
     280       99894 :         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

Generated by: LCOV version 1.13