libstdc++
|
00001 // Class template uniform_int_distribution -*- C++ -*- 00002 00003 // Copyright (C) 2009-2019 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** 00026 * @file bits/uniform_int_dist.h 00027 * This is an internal header file, included by other library headers. 00028 * Do not attempt to use it directly. @headername{random} 00029 */ 00030 00031 #ifndef _GLIBCXX_BITS_UNIFORM_INT_DIST_H 00032 #define _GLIBCXX_BITS_UNIFORM_INT_DIST_H 00033 00034 #include <type_traits> 00035 #include <limits> 00036 00037 namespace std _GLIBCXX_VISIBILITY(default) 00038 { 00039 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00040 00041 namespace __detail 00042 { 00043 /* Determine whether number is a power of 2. */ 00044 template<typename _Tp> 00045 inline bool 00046 _Power_of_2(_Tp __x) 00047 { 00048 return ((__x - 1) & __x) == 0; 00049 } 00050 } 00051 00052 /** 00053 * @brief Uniform discrete distribution for random numbers. 00054 * A discrete random distribution on the range @f$[min, max]@f$ with equal 00055 * probability throughout the range. 00056 */ 00057 template<typename _IntType = int> 00058 class uniform_int_distribution 00059 { 00060 static_assert(std::is_integral<_IntType>::value, 00061 "template argument must be an integral type"); 00062 00063 public: 00064 /** The type of the range of the distribution. */ 00065 typedef _IntType result_type; 00066 /** Parameter type. */ 00067 struct param_type 00068 { 00069 typedef uniform_int_distribution<_IntType> distribution_type; 00070 00071 param_type() : param_type(0) { } 00072 00073 explicit 00074 param_type(_IntType __a, 00075 _IntType __b = numeric_limits<_IntType>::max()) 00076 : _M_a(__a), _M_b(__b) 00077 { 00078 __glibcxx_assert(_M_a <= _M_b); 00079 } 00080 00081 result_type 00082 a() const 00083 { return _M_a; } 00084 00085 result_type 00086 b() const 00087 { return _M_b; } 00088 00089 friend bool 00090 operator==(const param_type& __p1, const param_type& __p2) 00091 { return __p1._M_a == __p2._M_a && __p1._M_b == __p2._M_b; } 00092 00093 friend bool 00094 operator!=(const param_type& __p1, const param_type& __p2) 00095 { return !(__p1 == __p2); } 00096 00097 private: 00098 _IntType _M_a; 00099 _IntType _M_b; 00100 }; 00101 00102 public: 00103 /** 00104 * @brief Constructs a uniform distribution object. 00105 */ 00106 uniform_int_distribution() : uniform_int_distribution(0) { } 00107 00108 /** 00109 * @brief Constructs a uniform distribution object. 00110 */ 00111 explicit 00112 uniform_int_distribution(_IntType __a, 00113 _IntType __b = numeric_limits<_IntType>::max()) 00114 : _M_param(__a, __b) 00115 { } 00116 00117 explicit 00118 uniform_int_distribution(const param_type& __p) 00119 : _M_param(__p) 00120 { } 00121 00122 /** 00123 * @brief Resets the distribution state. 00124 * 00125 * Does nothing for the uniform integer distribution. 00126 */ 00127 void 00128 reset() { } 00129 00130 result_type 00131 a() const 00132 { return _M_param.a(); } 00133 00134 result_type 00135 b() const 00136 { return _M_param.b(); } 00137 00138 /** 00139 * @brief Returns the parameter set of the distribution. 00140 */ 00141 param_type 00142 param() const 00143 { return _M_param; } 00144 00145 /** 00146 * @brief Sets the parameter set of the distribution. 00147 * @param __param The new parameter set of the distribution. 00148 */ 00149 void 00150 param(const param_type& __param) 00151 { _M_param = __param; } 00152 00153 /** 00154 * @brief Returns the inclusive lower bound of the distribution range. 00155 */ 00156 result_type 00157 min() const 00158 { return this->a(); } 00159 00160 /** 00161 * @brief Returns the inclusive upper bound of the distribution range. 00162 */ 00163 result_type 00164 max() const 00165 { return this->b(); } 00166 00167 /** 00168 * @brief Generating functions. 00169 */ 00170 template<typename _UniformRandomNumberGenerator> 00171 result_type 00172 operator()(_UniformRandomNumberGenerator& __urng) 00173 { return this->operator()(__urng, _M_param); } 00174 00175 template<typename _UniformRandomNumberGenerator> 00176 result_type 00177 operator()(_UniformRandomNumberGenerator& __urng, 00178 const param_type& __p); 00179 00180 template<typename _ForwardIterator, 00181 typename _UniformRandomNumberGenerator> 00182 void 00183 __generate(_ForwardIterator __f, _ForwardIterator __t, 00184 _UniformRandomNumberGenerator& __urng) 00185 { this->__generate(__f, __t, __urng, _M_param); } 00186 00187 template<typename _ForwardIterator, 00188 typename _UniformRandomNumberGenerator> 00189 void 00190 __generate(_ForwardIterator __f, _ForwardIterator __t, 00191 _UniformRandomNumberGenerator& __urng, 00192 const param_type& __p) 00193 { this->__generate_impl(__f, __t, __urng, __p); } 00194 00195 template<typename _UniformRandomNumberGenerator> 00196 void 00197 __generate(result_type* __f, result_type* __t, 00198 _UniformRandomNumberGenerator& __urng, 00199 const param_type& __p) 00200 { this->__generate_impl(__f, __t, __urng, __p); } 00201 00202 /** 00203 * @brief Return true if two uniform integer distributions have 00204 * the same parameters. 00205 */ 00206 friend bool 00207 operator==(const uniform_int_distribution& __d1, 00208 const uniform_int_distribution& __d2) 00209 { return __d1._M_param == __d2._M_param; } 00210 00211 private: 00212 template<typename _ForwardIterator, 00213 typename _UniformRandomNumberGenerator> 00214 void 00215 __generate_impl(_ForwardIterator __f, _ForwardIterator __t, 00216 _UniformRandomNumberGenerator& __urng, 00217 const param_type& __p); 00218 00219 param_type _M_param; 00220 }; 00221 00222 template<typename _IntType> 00223 template<typename _UniformRandomNumberGenerator> 00224 typename uniform_int_distribution<_IntType>::result_type 00225 uniform_int_distribution<_IntType>:: 00226 operator()(_UniformRandomNumberGenerator& __urng, 00227 const param_type& __param) 00228 { 00229 typedef typename _UniformRandomNumberGenerator::result_type 00230 _Gresult_type; 00231 typedef typename std::make_unsigned<result_type>::type __utype; 00232 typedef typename std::common_type<_Gresult_type, __utype>::type 00233 __uctype; 00234 00235 const __uctype __urngmin = __urng.min(); 00236 const __uctype __urngmax = __urng.max(); 00237 const __uctype __urngrange = __urngmax - __urngmin; 00238 const __uctype __urange 00239 = __uctype(__param.b()) - __uctype(__param.a()); 00240 00241 __uctype __ret; 00242 00243 if (__urngrange > __urange) 00244 { 00245 // downscaling 00246 const __uctype __uerange = __urange + 1; // __urange can be zero 00247 const __uctype __scaling = __urngrange / __uerange; 00248 const __uctype __past = __uerange * __scaling; 00249 do 00250 __ret = __uctype(__urng()) - __urngmin; 00251 while (__ret >= __past); 00252 __ret /= __scaling; 00253 } 00254 else if (__urngrange < __urange) 00255 { 00256 // upscaling 00257 /* 00258 Note that every value in [0, urange] 00259 can be written uniquely as 00260 00261 (urngrange + 1) * high + low 00262 00263 where 00264 00265 high in [0, urange / (urngrange + 1)] 00266 00267 and 00268 00269 low in [0, urngrange]. 00270 */ 00271 __uctype __tmp; // wraparound control 00272 do 00273 { 00274 const __uctype __uerngrange = __urngrange + 1; 00275 __tmp = (__uerngrange * operator() 00276 (__urng, param_type(0, __urange / __uerngrange))); 00277 __ret = __tmp + (__uctype(__urng()) - __urngmin); 00278 } 00279 while (__ret > __urange || __ret < __tmp); 00280 } 00281 else 00282 __ret = __uctype(__urng()) - __urngmin; 00283 00284 return __ret + __param.a(); 00285 } 00286 00287 00288 template<typename _IntType> 00289 template<typename _ForwardIterator, 00290 typename _UniformRandomNumberGenerator> 00291 void 00292 uniform_int_distribution<_IntType>:: 00293 __generate_impl(_ForwardIterator __f, _ForwardIterator __t, 00294 _UniformRandomNumberGenerator& __urng, 00295 const param_type& __param) 00296 { 00297 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00298 typedef typename _UniformRandomNumberGenerator::result_type 00299 _Gresult_type; 00300 typedef typename std::make_unsigned<result_type>::type __utype; 00301 typedef typename std::common_type<_Gresult_type, __utype>::type 00302 __uctype; 00303 00304 const __uctype __urngmin = __urng.min(); 00305 const __uctype __urngmax = __urng.max(); 00306 const __uctype __urngrange = __urngmax - __urngmin; 00307 const __uctype __urange 00308 = __uctype(__param.b()) - __uctype(__param.a()); 00309 00310 __uctype __ret; 00311 00312 if (__urngrange > __urange) 00313 { 00314 if (__detail::_Power_of_2(__urngrange + 1) 00315 && __detail::_Power_of_2(__urange + 1)) 00316 { 00317 while (__f != __t) 00318 { 00319 __ret = __uctype(__urng()) - __urngmin; 00320 *__f++ = (__ret & __urange) + __param.a(); 00321 } 00322 } 00323 else 00324 { 00325 // downscaling 00326 const __uctype __uerange = __urange + 1; // __urange can be zero 00327 const __uctype __scaling = __urngrange / __uerange; 00328 const __uctype __past = __uerange * __scaling; 00329 while (__f != __t) 00330 { 00331 do 00332 __ret = __uctype(__urng()) - __urngmin; 00333 while (__ret >= __past); 00334 *__f++ = __ret / __scaling + __param.a(); 00335 } 00336 } 00337 } 00338 else if (__urngrange < __urange) 00339 { 00340 // upscaling 00341 /* 00342 Note that every value in [0, urange] 00343 can be written uniquely as 00344 00345 (urngrange + 1) * high + low 00346 00347 where 00348 00349 high in [0, urange / (urngrange + 1)] 00350 00351 and 00352 00353 low in [0, urngrange]. 00354 */ 00355 __uctype __tmp; // wraparound control 00356 while (__f != __t) 00357 { 00358 do 00359 { 00360 const __uctype __uerngrange = __urngrange + 1; 00361 __tmp = (__uerngrange * operator() 00362 (__urng, param_type(0, __urange / __uerngrange))); 00363 __ret = __tmp + (__uctype(__urng()) - __urngmin); 00364 } 00365 while (__ret > __urange || __ret < __tmp); 00366 *__f++ = __ret; 00367 } 00368 } 00369 else 00370 while (__f != __t) 00371 *__f++ = __uctype(__urng()) - __urngmin + __param.a(); 00372 } 00373 00374 // operator!= and operator<< and operator>> are defined in <bits/random.h> 00375 00376 _GLIBCXX_END_NAMESPACE_VERSION 00377 } // namespace std 00378 00379 #endif