1 // Class template uniform_int_distribution -*- C++ -*- 2 3 // Copyright (C) 2009-2018 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 _GLIBCXX_BEGIN_NAMESPACE_VERSION 40 41 namespace __detail 42 { 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 } 51 52 /** 53 * @brief Uniform discrete distribution for random numbers. 54 * A discrete random distribution on the range @f$[min, max]@f$ with equal 55 * probability throughout the range. 56 */ 57 template<typename _IntType = int> 58 class uniform_int_distribution 59 { 60 static_assert(std::is_integral<_IntType>::value, 61 "template argument must be an integral type"); 62 63 public: 64 /** The type of the range of the distribution. */ 65 typedef _IntType result_type; 66 /** Parameter type. */ 67 struct param_type 68 { 69 typedef uniform_int_distribution<_IntType> distribution_type; 70 71 explicit 72 param_type(_IntType __a = 0, 73 _IntType __b = std::numeric_limits<_IntType>::max()) 74 : _M_a(__a), _M_b(__b) 75 { 76 __glibcxx_assert(_M_a <= _M_b); 77 } 78 79 result_type 80 a() const 81 { return _M_a; } 82 83 result_type 84 b() const 85 { return _M_b; } 86 87 friend bool 88 operator==(const param_type& __p1, const param_type& __p2) 89 { return __p1._M_a == __p2._M_a && __p1._M_b == __p2._M_b; } 90 91 friend bool 92 operator!=(const param_type& __p1, const param_type& __p2) 93 { return !(__p1 == __p2); } 94 95 private: 96 _IntType _M_a; 97 _IntType _M_b; 98 }; 99 100 public: 101 /** 102 * @brief Constructs a uniform distribution object. 103 */ 104 explicit 105 uniform_int_distribution(_IntType __a = 0, 106 _IntType __b = std::numeric_limits<_IntType>::max()) 107 : _M_param(__a, __b) 108 { } 109 110 explicit 111 uniform_int_distribution(const param_type& __p) 112 : _M_param(__p) 113 { } 114 115 /** 116 * @brief Resets the distribution state. 117 * 118 * Does nothing for the uniform integer distribution. 119 */ 120 void 121 reset() { } 122 123 result_type 124 a() const 125 { return _M_param.a(); } 126 127 result_type 128 b() const 129 { return _M_param.b(); } 130 131 /** 132 * @brief Returns the parameter set of the distribution. 133 */ 134 param_type 135 param() const 136 { return _M_param; } 137 138 /** 139 * @brief Sets the parameter set of the distribution. 140 * @param __param The new parameter set of the distribution. 141 */ 142 void 143 param(const param_type& __param) 144 { _M_param = __param; } 145 146 /** 147 * @brief Returns the inclusive lower bound of the distribution range. 148 */ 149 result_type 150 min() const 151 { return this->a(); } 152 153 /** 154 * @brief Returns the inclusive upper bound of the distribution range. 155 */ 156 result_type 157 max() const 158 { return this->b(); } 159 160 /** 161 * @brief Generating functions. 162 */ 163 template<typename _UniformRandomNumberGenerator> 164 result_type 165 operator()(_UniformRandomNumberGenerator& __urng) 166 { return this->operator()(__urng, _M_param); } 167 168 template<typename _UniformRandomNumberGenerator> 169 result_type 170 operator()(_UniformRandomNumberGenerator& __urng, 171 const param_type& __p); 172 173 template<typename _ForwardIterator, 174 typename _UniformRandomNumberGenerator> 175 void 176 __generate(_ForwardIterator __f, _ForwardIterator __t, 177 _UniformRandomNumberGenerator& __urng) 178 { this->__generate(__f, __t, __urng, _M_param); } 179 180 template<typename _ForwardIterator, 181 typename _UniformRandomNumberGenerator> 182 void 183 __generate(_ForwardIterator __f, _ForwardIterator __t, 184 _UniformRandomNumberGenerator& __urng, 185 const param_type& __p) 186 { this->__generate_impl(__f, __t, __urng, __p); } 187 188 template<typename _UniformRandomNumberGenerator> 189 void 190 __generate(result_type* __f, result_type* __t, 191 _UniformRandomNumberGenerator& __urng, 192 const param_type& __p) 193 { this->__generate_impl(__f, __t, __urng, __p); } 194 195 /** 196 * @brief Return true if two uniform integer distributions have 197 * the same parameters. 198 */ 199 friend bool 200 operator==(const uniform_int_distribution& __d1, 201 const uniform_int_distribution& __d2) 202 { return __d1._M_param == __d2._M_param; } 203 204 private: 205 template<typename _ForwardIterator, 206 typename _UniformRandomNumberGenerator> 207 void 208 __generate_impl(_ForwardIterator __f, _ForwardIterator __t, 209 _UniformRandomNumberGenerator& __urng, 210 const param_type& __p); 211 212 param_type _M_param; 213 }; 214 215 template<typename _IntType> 216 template<typename _UniformRandomNumberGenerator> 217 typename uniform_int_distribution<_IntType>::result_type 218 uniform_int_distribution<_IntType>:: 219 operator()(_UniformRandomNumberGenerator& __urng, 220 const param_type& __param) 221 { 222 typedef typename _UniformRandomNumberGenerator::result_type 223 _Gresult_type; 224 typedef typename std::make_unsigned<result_type>::type __utype; 225 typedef typename std::common_type<_Gresult_type, __utype>::type 226 __uctype; 227 228 const __uctype __urngmin = __urng.min(); 229 const __uctype __urngmax = __urng.max(); 230 const __uctype __urngrange = __urngmax - __urngmin; 231 const __uctype __urange 232 = __uctype(__param.b()) - __uctype(__param.a()); 233 234 __uctype __ret; 235 236 if (__urngrange > __urange) 237 { 238 // downscaling 239 const __uctype __uerange = __urange + 1; // __urange can be zero 240 const __uctype __scaling = __urngrange / __uerange; 241 const __uctype __past = __uerange * __scaling; 242 do 243 __ret = __uctype(__urng()) - __urngmin; 244 while (__ret >= __past); 245 __ret /= __scaling; 246 } 247 else if (__urngrange < __urange) 248 { 249 // upscaling 250 /* 251 Note that every value in [0, urange] 252 can be written uniquely as 253 254 (urngrange + 1) * high + low 255 256 where 257 258 high in [0, urange / (urngrange + 1)] 259 260 and 261 262 low in [0, urngrange]. 263 */ 264 __uctype __tmp; // wraparound control 265 do 266 { 267 const __uctype __uerngrange = __urngrange + 1; 268 __tmp = (__uerngrange * operator() 269 (__urng, param_type(0, __urange / __uerngrange))); 270 __ret = __tmp + (__uctype(__urng()) - __urngmin); 271 } 272 while (__ret > __urange || __ret < __tmp); 273 } 274 else 275 __ret = __uctype(__urng()) - __urngmin; 276 277 return __ret + __param.a(); 278 } 279 280 281 template<typename _IntType> 282 template<typename _ForwardIterator, 283 typename _UniformRandomNumberGenerator> 284 void 285 uniform_int_distribution<_IntType>:: 286 __generate_impl(_ForwardIterator __f, _ForwardIterator __t, 287 _UniformRandomNumberGenerator& __urng, 288 const param_type& __param) 289 { 290 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) 291 typedef typename _UniformRandomNumberGenerator::result_type 292 _Gresult_type; 293 typedef typename std::make_unsigned<result_type>::type __utype; 294 typedef typename std::common_type<_Gresult_type, __utype>::type 295 __uctype; 296 297 const __uctype __urngmin = __urng.min(); 298 const __uctype __urngmax = __urng.max(); 299 const __uctype __urngrange = __urngmax - __urngmin; 300 const __uctype __urange 301 = __uctype(__param.b()) - __uctype(__param.a()); 302 303 __uctype __ret; 304 305 if (__urngrange > __urange) 306 { 307 if (__detail::_Power_of_2(__urngrange + 1) 308 && __detail::_Power_of_2(__urange + 1)) 309 { 310 while (__f != __t) 311 { 312 __ret = __uctype(__urng()) - __urngmin; 313 *__f++ = (__ret & __urange) + __param.a(); 314 } 315 } 316 else 317 { 318 // downscaling 319 const __uctype __uerange = __urange + 1; // __urange can be zero 320 const __uctype __scaling = __urngrange / __uerange; 321 const __uctype __past = __uerange * __scaling; 322 while (__f != __t) 323 { 324 do 325 __ret = __uctype(__urng()) - __urngmin; 326 while (__ret >= __past); 327 *__f++ = __ret / __scaling + __param.a(); 328 } 329 } 330 } 331 else if (__urngrange < __urange) 332 { 333 // upscaling 334 /* 335 Note that every value in [0, urange] 336 can be written uniquely as 337 338 (urngrange + 1) * high + low 339 340 where 341 342 high in [0, urange / (urngrange + 1)] 343 344 and 345 346 low in [0, urngrange]. 347 */ 348 __uctype __tmp; // wraparound control 349 while (__f != __t) 350 { 351 do 352 { 353 const __uctype __uerngrange = __urngrange + 1; 354 __tmp = (__uerngrange * operator() 355 (__urng, param_type(0, __urange / __uerngrange))); 356 __ret = __tmp + (__uctype(__urng()) - __urngmin); 357 } 358 while (__ret > __urange || __ret < __tmp); 359 *__f++ = __ret; 360 } 361 } 362 else 363 while (__f != __t) 364 *__f++ = __uctype(__urng()) - __urngmin + __param.a(); 365 } 366 367 // operator!= and operator<< and operator>> are defined in <bits/random.h> 368 369 _GLIBCXX_END_NAMESPACE_VERSION 370 } // namespace std 371 372 #endif 373