libstdc++
|
00001 // Class template uniform_int_distribution -*- C++ -*- 00002 00003 // Copyright (C) 2009-2018 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 explicit 00072 param_type(_IntType __a = 0, 00073 _IntType __b = std::numeric_limits<_IntType>::max()) 00074 : _M_a(__a), _M_b(__b) 00075 { 00076 __glibcxx_assert(_M_a <= _M_b); 00077 } 00078 00079 result_type 00080 a() const 00081 { return _M_a; } 00082 00083 result_type 00084 b() const 00085 { return _M_b; } 00086 00087 friend bool 00088 operator==(const param_type& __p1, const param_type& __p2) 00089 { return __p1._M_a == __p2._M_a && __p1._M_b == __p2._M_b; } 00090 00091 friend bool 00092 operator!=(const param_type& __p1, const param_type& __p2) 00093 { return !(__p1 == __p2); } 00094 00095 private: 00096 _IntType _M_a; 00097 _IntType _M_b; 00098 }; 00099 00100 public: 00101 /** 00102 * @brief Constructs a uniform distribution object. 00103 */ 00104 explicit 00105 uniform_int_distribution(_IntType __a = 0, 00106 _IntType __b = std::numeric_limits<_IntType>::max()) 00107 : _M_param(__a, __b) 00108 { } 00109 00110 explicit 00111 uniform_int_distribution(const param_type& __p) 00112 : _M_param(__p) 00113 { } 00114 00115 /** 00116 * @brief Resets the distribution state. 00117 * 00118 * Does nothing for the uniform integer distribution. 00119 */ 00120 void 00121 reset() { } 00122 00123 result_type 00124 a() const 00125 { return _M_param.a(); } 00126 00127 result_type 00128 b() const 00129 { return _M_param.b(); } 00130 00131 /** 00132 * @brief Returns the parameter set of the distribution. 00133 */ 00134 param_type 00135 param() const 00136 { return _M_param; } 00137 00138 /** 00139 * @brief Sets the parameter set of the distribution. 00140 * @param __param The new parameter set of the distribution. 00141 */ 00142 void 00143 param(const param_type& __param) 00144 { _M_param = __param; } 00145 00146 /** 00147 * @brief Returns the inclusive lower bound of the distribution range. 00148 */ 00149 result_type 00150 min() const 00151 { return this->a(); } 00152 00153 /** 00154 * @brief Returns the inclusive upper bound of the distribution range. 00155 */ 00156 result_type 00157 max() const 00158 { return this->b(); } 00159 00160 /** 00161 * @brief Generating functions. 00162 */ 00163 template<typename _UniformRandomNumberGenerator> 00164 result_type 00165 operator()(_UniformRandomNumberGenerator& __urng) 00166 { return this->operator()(__urng, _M_param); } 00167 00168 template<typename _UniformRandomNumberGenerator> 00169 result_type 00170 operator()(_UniformRandomNumberGenerator& __urng, 00171 const param_type& __p); 00172 00173 template<typename _ForwardIterator, 00174 typename _UniformRandomNumberGenerator> 00175 void 00176 __generate(_ForwardIterator __f, _ForwardIterator __t, 00177 _UniformRandomNumberGenerator& __urng) 00178 { this->__generate(__f, __t, __urng, _M_param); } 00179 00180 template<typename _ForwardIterator, 00181 typename _UniformRandomNumberGenerator> 00182 void 00183 __generate(_ForwardIterator __f, _ForwardIterator __t, 00184 _UniformRandomNumberGenerator& __urng, 00185 const param_type& __p) 00186 { this->__generate_impl(__f, __t, __urng, __p); } 00187 00188 template<typename _UniformRandomNumberGenerator> 00189 void 00190 __generate(result_type* __f, result_type* __t, 00191 _UniformRandomNumberGenerator& __urng, 00192 const param_type& __p) 00193 { this->__generate_impl(__f, __t, __urng, __p); } 00194 00195 /** 00196 * @brief Return true if two uniform integer distributions have 00197 * the same parameters. 00198 */ 00199 friend bool 00200 operator==(const uniform_int_distribution& __d1, 00201 const uniform_int_distribution& __d2) 00202 { return __d1._M_param == __d2._M_param; } 00203 00204 private: 00205 template<typename _ForwardIterator, 00206 typename _UniformRandomNumberGenerator> 00207 void 00208 __generate_impl(_ForwardIterator __f, _ForwardIterator __t, 00209 _UniformRandomNumberGenerator& __urng, 00210 const param_type& __p); 00211 00212 param_type _M_param; 00213 }; 00214 00215 template<typename _IntType> 00216 template<typename _UniformRandomNumberGenerator> 00217 typename uniform_int_distribution<_IntType>::result_type 00218 uniform_int_distribution<_IntType>:: 00219 operator()(_UniformRandomNumberGenerator& __urng, 00220 const param_type& __param) 00221 { 00222 typedef typename _UniformRandomNumberGenerator::result_type 00223 _Gresult_type; 00224 typedef typename std::make_unsigned<result_type>::type __utype; 00225 typedef typename std::common_type<_Gresult_type, __utype>::type 00226 __uctype; 00227 00228 const __uctype __urngmin = __urng.min(); 00229 const __uctype __urngmax = __urng.max(); 00230 const __uctype __urngrange = __urngmax - __urngmin; 00231 const __uctype __urange 00232 = __uctype(__param.b()) - __uctype(__param.a()); 00233 00234 __uctype __ret; 00235 00236 if (__urngrange > __urange) 00237 { 00238 // downscaling 00239 const __uctype __uerange = __urange + 1; // __urange can be zero 00240 const __uctype __scaling = __urngrange / __uerange; 00241 const __uctype __past = __uerange * __scaling; 00242 do 00243 __ret = __uctype(__urng()) - __urngmin; 00244 while (__ret >= __past); 00245 __ret /= __scaling; 00246 } 00247 else if (__urngrange < __urange) 00248 { 00249 // upscaling 00250 /* 00251 Note that every value in [0, urange] 00252 can be written uniquely as 00253 00254 (urngrange + 1) * high + low 00255 00256 where 00257 00258 high in [0, urange / (urngrange + 1)] 00259 00260 and 00261 00262 low in [0, urngrange]. 00263 */ 00264 __uctype __tmp; // wraparound control 00265 do 00266 { 00267 const __uctype __uerngrange = __urngrange + 1; 00268 __tmp = (__uerngrange * operator() 00269 (__urng, param_type(0, __urange / __uerngrange))); 00270 __ret = __tmp + (__uctype(__urng()) - __urngmin); 00271 } 00272 while (__ret > __urange || __ret < __tmp); 00273 } 00274 else 00275 __ret = __uctype(__urng()) - __urngmin; 00276 00277 return __ret + __param.a(); 00278 } 00279 00280 00281 template<typename _IntType> 00282 template<typename _ForwardIterator, 00283 typename _UniformRandomNumberGenerator> 00284 void 00285 uniform_int_distribution<_IntType>:: 00286 __generate_impl(_ForwardIterator __f, _ForwardIterator __t, 00287 _UniformRandomNumberGenerator& __urng, 00288 const param_type& __param) 00289 { 00290 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 00291 typedef typename _UniformRandomNumberGenerator::result_type 00292 _Gresult_type; 00293 typedef typename std::make_unsigned<result_type>::type __utype; 00294 typedef typename std::common_type<_Gresult_type, __utype>::type 00295 __uctype; 00296 00297 const __uctype __urngmin = __urng.min(); 00298 const __uctype __urngmax = __urng.max(); 00299 const __uctype __urngrange = __urngmax - __urngmin; 00300 const __uctype __urange 00301 = __uctype(__param.b()) - __uctype(__param.a()); 00302 00303 __uctype __ret; 00304 00305 if (__urngrange > __urange) 00306 { 00307 if (__detail::_Power_of_2(__urngrange + 1) 00308 && __detail::_Power_of_2(__urange + 1)) 00309 { 00310 while (__f != __t) 00311 { 00312 __ret = __uctype(__urng()) - __urngmin; 00313 *__f++ = (__ret & __urange) + __param.a(); 00314 } 00315 } 00316 else 00317 { 00318 // downscaling 00319 const __uctype __uerange = __urange + 1; // __urange can be zero 00320 const __uctype __scaling = __urngrange / __uerange; 00321 const __uctype __past = __uerange * __scaling; 00322 while (__f != __t) 00323 { 00324 do 00325 __ret = __uctype(__urng()) - __urngmin; 00326 while (__ret >= __past); 00327 *__f++ = __ret / __scaling + __param.a(); 00328 } 00329 } 00330 } 00331 else if (__urngrange < __urange) 00332 { 00333 // upscaling 00334 /* 00335 Note that every value in [0, urange] 00336 can be written uniquely as 00337 00338 (urngrange + 1) * high + low 00339 00340 where 00341 00342 high in [0, urange / (urngrange + 1)] 00343 00344 and 00345 00346 low in [0, urngrange]. 00347 */ 00348 __uctype __tmp; // wraparound control 00349 while (__f != __t) 00350 { 00351 do 00352 { 00353 const __uctype __uerngrange = __urngrange + 1; 00354 __tmp = (__uerngrange * operator() 00355 (__urng, param_type(0, __urange / __uerngrange))); 00356 __ret = __tmp + (__uctype(__urng()) - __urngmin); 00357 } 00358 while (__ret > __urange || __ret < __tmp); 00359 *__f++ = __ret; 00360 } 00361 } 00362 else 00363 while (__f != __t) 00364 *__f++ = __uctype(__urng()) - __urngmin + __param.a(); 00365 } 00366 00367 // operator!= and operator<< and operator>> are defined in <bits/random.h> 00368 00369 _GLIBCXX_END_NAMESPACE_VERSION 00370 } // namespace std 00371 00372 #endif