1 // Class template uniform_int_distribution -*- C++ -*- 2 3 // Copyright (C) 2009-2017 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** 26 * @file bits/uniform_int_dist.h 27 * This is an internal header file, included by other library headers. 28 * Do not attempt to use it directly. @headername{random} 29 */ 30 31 #ifndef _GLIBCXX_BITS_UNIFORM_INT_DIST_H 32 #define _GLIBCXX_BITS_UNIFORM_INT_DIST_H 33 34 #include <type_traits> 35 #include <limits> 36 37 namespace std _GLIBCXX_VISIBILITY(default) 38 { 39 40 namespace __detail 41 { 42 _GLIBCXX_BEGIN_NAMESPACE_VERSION 43 /* Determine whether number is a power of 2. */ 44 template<typename _Tp> 45 inline bool 46 _Power_of_2(_Tp __x) 47 { 48 return ((__x - 1) & __x) == 0; 49 }; 50 _GLIBCXX_END_NAMESPACE_VERSION 51 } 52 53 _GLIBCXX_BEGIN_NAMESPACE_VERSION 54 55 /** 56 * @brief Uniform discrete distribution for random numbers. 57 * A discrete random distribution on the range @f$[min, max]@f$ with equal 58 * probability throughout the range. 59 */ 60 template<typename _IntType = int> 61 class uniform_int_distribution 62 { 63 static_assert(std::is_integral<_IntType>::value, 64 "template argument must be an integral type"); 65 66 public: 67 /** The type of the range of the distribution. */ 68 typedef _IntType result_type; 69 /** Parameter type. */ 70 struct param_type 71 { 72 typedef uniform_int_distribution<_IntType> distribution_type; 73 74 explicit 75 param_type(_IntType __a = 0, 76 _IntType __b = std::numeric_limits<_IntType>::max()) 77 : _M_a(__a), _M_b(__b) 78 { 79 __glibcxx_assert(_M_a <= _M_b); 80 } 81 82 result_type 83 a() const 84 { return _M_a; } 85 86 result_type 87 b() const 88 { return _M_b; } 89 90 friend bool 91 operator==(const param_type& __p1, const param_type& __p2) 92 { return __p1._M_a == __p2._M_a && __p1._M_b == __p2._M_b; } 93 94 friend bool 95 operator!=(const param_type& __p1, const param_type& __p2) 96 { return !(__p1 == __p2); } 97 98 private: 99 _IntType _M_a; 100 _IntType _M_b; 101 }; 102 103 public: 104 /** 105 * @brief Constructs a uniform distribution object. 106 */ 107 explicit 108 uniform_int_distribution(_IntType __a = 0, 109 _IntType __b = std::numeric_limits<_IntType>::max()) 110 : _M_param(__a, __b) 111 { } 112 113 explicit 114 uniform_int_distribution(const param_type& __p) 115 : _M_param(__p) 116 { } 117 118 /** 119 * @brief Resets the distribution state. 120 * 121 * Does nothing for the uniform integer distribution. 122 */ 123 void 124 reset() { } 125 126 result_type 127 a() const 128 { return _M_param.a(); } 129 130 result_type 131 b() const 132 { return _M_param.b(); } 133 134 /** 135 * @brief Returns the parameter set of the distribution. 136 */ 137 param_type 138 param() const 139 { return _M_param; } 140 141 /** 142 * @brief Sets the parameter set of the distribution. 143 * @param __param The new parameter set of the distribution. 144 */ 145 void 146 param(const param_type& __param) 147 { _M_param = __param; } 148 149 /** 150 * @brief Returns the inclusive lower bound of the distribution range. 151 */ 152 result_type 153 min() const 154 { return this->a(); } 155 156 /** 157 * @brief Returns the inclusive upper bound of the distribution range. 158 */ 159 result_type 160 max() const 161 { return this->b(); } 162 163 /** 164 * @brief Generating functions. 165 */ 166 template<typename _UniformRandomNumberGenerator> 167 result_type 168 operator()(_UniformRandomNumberGenerator& __urng) 169 { return this->operator()(__urng, _M_param); } 170 171 template<typename _UniformRandomNumberGenerator> 172 result_type 173 operator()(_UniformRandomNumberGenerator& __urng, 174 const param_type& __p); 175 176 template<typename _ForwardIterator, 177 typename _UniformRandomNumberGenerator> 178 void 179 __generate(_ForwardIterator __f, _ForwardIterator __t, 180 _UniformRandomNumberGenerator& __urng) 181 { this->__generate(__f, __t, __urng, _M_param); } 182 183 template<typename _ForwardIterator, 184 typename _UniformRandomNumberGenerator> 185 void 186 __generate(_ForwardIterator __f, _ForwardIterator __t, 187 _UniformRandomNumberGenerator& __urng, 188 const param_type& __p) 189 { this->__generate_impl(__f, __t, __urng, __p); } 190 191 template<typename _UniformRandomNumberGenerator> 192 void 193 __generate(result_type* __f, result_type* __t, 194 _UniformRandomNumberGenerator& __urng, 195 const param_type& __p) 196 { this->__generate_impl(__f, __t, __urng, __p); } 197 198 /** 199 * @brief Return true if two uniform integer distributions have 200 * the same parameters. 201 */ 202 friend bool 203 operator==(const uniform_int_distribution& __d1, 204 const uniform_int_distribution& __d2) 205 { return __d1._M_param == __d2._M_param; } 206 207 private: 208 template<typename _ForwardIterator, 209 typename _UniformRandomNumberGenerator> 210 void 211 __generate_impl(_ForwardIterator __f, _ForwardIterator __t, 212 _UniformRandomNumberGenerator& __urng, 213 const param_type& __p); 214 215 param_type _M_param; 216 }; 217 218 template<typename _IntType> 219 template<typename _UniformRandomNumberGenerator> 220 typename uniform_int_distribution<_IntType>::result_type 221 uniform_int_distribution<_IntType>:: 222 operator()(_UniformRandomNumberGenerator& __urng, 223 const param_type& __param) 224 { 225 typedef typename _UniformRandomNumberGenerator::result_type 226 _Gresult_type; 227 typedef typename std::make_unsigned<result_type>::type __utype; 228 typedef typename std::common_type<_Gresult_type, __utype>::type 229 __uctype; 230 231 const __uctype __urngmin = __urng.min(); 232 const __uctype __urngmax = __urng.max(); 233 const __uctype __urngrange = __urngmax - __urngmin; 234 const __uctype __urange 235 = __uctype(__param.b()) - __uctype(__param.a()); 236 237 __uctype __ret; 238 239 if (__urngrange > __urange) 240 { 241 // downscaling 242 const __uctype __uerange = __urange + 1; // __urange can be zero 243 const __uctype __scaling = __urngrange / __uerange; 244 const __uctype __past = __uerange * __scaling; 245 do 246 __ret = __uctype(__urng()) - __urngmin; 247 while (__ret >= __past); 248 __ret /= __scaling; 249 } 250 else if (__urngrange < __urange) 251 { 252 // upscaling 253 /* 254 Note that every value in [0, urange] 255 can be written uniquely as 256 257 (urngrange + 1) * high + low 258 259 where 260 261 high in [0, urange / (urngrange + 1)] 262 263 and 264 265 low in [0, urngrange]. 266 */ 267 __uctype __tmp; // wraparound control 268 do 269 { 270 const __uctype __uerngrange = __urngrange + 1; 271 __tmp = (__uerngrange * operator() 272 (__urng, param_type(0, __urange / __uerngrange))); 273 __ret = __tmp + (__uctype(__urng()) - __urngmin); 274 } 275 while (__ret > __urange || __ret < __tmp); 276 } 277 else 278 __ret = __uctype(__urng()) - __urngmin; 279 280 return __ret + __param.a(); 281 } 282 283 284 template<typename _IntType> 285 template<typename _ForwardIterator, 286 typename _UniformRandomNumberGenerator> 287 void 288 uniform_int_distribution<_IntType>:: 289 __generate_impl(_ForwardIterator __f, _ForwardIterator __t, 290 _UniformRandomNumberGenerator& __urng, 291 const param_type& __param) 292 { 293 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 294 typedef typename _UniformRandomNumberGenerator::result_type 295 _Gresult_type; 296 typedef typename std::make_unsigned<result_type>::type __utype; 297 typedef typename std::common_type<_Gresult_type, __utype>::type 298 __uctype; 299 300 const __uctype __urngmin = __urng.min(); 301 const __uctype __urngmax = __urng.max(); 302 const __uctype __urngrange = __urngmax - __urngmin; 303 const __uctype __urange 304 = __uctype(__param.b()) - __uctype(__param.a()); 305 306 __uctype __ret; 307 308 if (__urngrange > __urange) 309 { 310 if (__detail::_Power_of_2(__urngrange + 1) 311 && __detail::_Power_of_2(__urange + 1)) 312 { 313 while (__f != __t) 314 { 315 __ret = __uctype(__urng()) - __urngmin; 316 *__f++ = (__ret & __urange) + __param.a(); 317 } 318 } 319 else 320 { 321 // downscaling 322 const __uctype __uerange = __urange + 1; // __urange can be zero 323 const __uctype __scaling = __urngrange / __uerange; 324 const __uctype __past = __uerange * __scaling; 325 while (__f != __t) 326 { 327 do 328 __ret = __uctype(__urng()) - __urngmin; 329 while (__ret >= __past); 330 *__f++ = __ret / __scaling + __param.a(); 331 } 332 } 333 } 334 else if (__urngrange < __urange) 335 { 336 // upscaling 337 /* 338 Note that every value in [0, urange] 339 can be written uniquely as 340 341 (urngrange + 1) * high + low 342 343 where 344 345 high in [0, urange / (urngrange + 1)] 346 347 and 348 349 low in [0, urngrange]. 350 */ 351 __uctype __tmp; // wraparound control 352 while (__f != __t) 353 { 354 do 355 { 356 const __uctype __uerngrange = __urngrange + 1; 357 __tmp = (__uerngrange * operator() 358 (__urng, param_type(0, __urange / __uerngrange))); 359 __ret = __tmp + (__uctype(__urng()) - __urngmin); 360 } 361 while (__ret > __urange || __ret < __tmp); 362 *__f++ = __ret; 363 } 364 } 365 else 366 while (__f != __t) 367 *__f++ = __uctype(__urng()) - __urngmin + __param.a(); 368 } 369 370 // operator!= and operator<< and operator>> are defined in <bits/random.h> 371 372 _GLIBCXX_END_NAMESPACE_VERSION 373 } // namespace std 374 375 #endif 376