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