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