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