31 #ifndef _GLIBCXX_BITS_UNIFORM_INT_DIST_H
32 #define _GLIBCXX_BITS_UNIFORM_INT_DIST_H
36 #if __cplusplus > 201703L
40 namespace std _GLIBCXX_VISIBILITY(default)
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
44 #ifdef __cpp_lib_concepts
46 template<
typename _Gen>
47 concept uniform_random_bit_generator
48 = invocable<_Gen&> && unsigned_integral<invoke_result_t<_Gen&>>
51 {
_Gen::min() } -> same_as<invoke_result_t<_Gen&>>;
52 {
_Gen::max() } -> same_as<invoke_result_t<_Gen&>>;
62 template<
typename _Tp>
66 return ((__x - 1) & __x) == 0;
75 template<
typename _IntType =
int>
79 "template argument must be an integral type");
94 : _M_a(__a), _M_b(__b)
96 __glibcxx_assert(_M_a <= _M_b);
109 {
return __p1._M_a == __p2._M_a && __p1._M_b == __p2._M_b; }
113 {
return !(__p1 == __p2); }
151 {
return _M_param.a(); }
155 {
return _M_param.b(); }
170 { _M_param = __param; }
177 {
return this->a(); }
184 {
return this->b(); }
189 template<
typename _UniformRandomBitGenerator>
192 {
return this->
operator()(__urng, _M_param); }
194 template<
typename _UniformRandomBitGenerator>
196 operator()(_UniformRandomBitGenerator& __urng,
197 const param_type& __p);
199 template<
typename _ForwardIterator,
200 typename _UniformRandomBitGenerator>
202 __generate(_ForwardIterator __f, _ForwardIterator __t,
203 _UniformRandomBitGenerator& __urng)
204 { this->__generate(__f, __t, __urng, _M_param); }
206 template<
typename _ForwardIterator,
207 typename _UniformRandomBitGenerator>
209 __generate(_ForwardIterator __f, _ForwardIterator __t,
210 _UniformRandomBitGenerator& __urng,
211 const param_type& __p)
212 { this->__generate_impl(__f, __t, __urng, __p); }
214 template<
typename _UniformRandomBitGenerator>
217 _UniformRandomBitGenerator& __urng,
218 const param_type& __p)
219 { this->__generate_impl(__f, __t, __urng, __p); }
228 {
return __d1._M_param == __d2._M_param; }
231 template<
typename _ForwardIterator,
232 typename _UniformRandomBitGenerator>
234 __generate_impl(_ForwardIterator __f, _ForwardIterator __t,
235 _UniformRandomBitGenerator& __urng,
236 const param_type& __p);
243 template<
typename _Wp,
typename _Urbg,
typename _Up>
245 _S_nd(_Urbg& __g, _Up __range)
249 static_assert(!_Up_traits::__is_signed,
"U must be unsigned");
250 static_assert(!_Wp_traits::__is_signed,
"W must be unsigned");
251 static_assert(_Wp_traits::__digits == (2 * _Up_traits::__digits),
252 "W must be twice as wide as U");
257 _Wp __product = _Wp(__g()) * _Wp(__range);
258 _Up __low = _Up(__product);
261 _Up __threshold = -__range % __range;
262 while (__low < __threshold)
264 __product = _Wp(__g()) * _Wp(__range);
265 __low = _Up(__product);
268 return __product >> _Up_traits::__digits;
272 template<
typename _IntType>
273 template<
typename _UniformRandomBitGenerator>
276 operator()(_UniformRandomBitGenerator& __urng,
277 const param_type& __param)
279 typedef typename _UniformRandomBitGenerator::result_type _Gresult_type;
280 typedef typename make_unsigned<result_type>::type __utype;
281 typedef typename common_type<_Gresult_type, __utype>::type __uctype;
285 static_assert( __urngmin < __urngmax,
286 "Uniform random bit generator must define min() < max()");
287 constexpr __uctype __urngrange = __urngmax - __urngmin;
289 const __uctype __urange
290 = __uctype(__param.b()) - __uctype(__param.a());
293 if (__urngrange > __urange)
297 const __uctype __uerange = __urange + 1;
299 #if defined __UINT64_TYPE__ && defined __UINT32_TYPE__
300 #if __SIZEOF_INT128__
301 if _GLIBCXX17_CONSTEXPR (__urngrange == __UINT64_MAX__)
305 __UINT64_TYPE__ __u64erange = __uerange;
306 __ret = _S_nd<unsigned __int128>(__urng, __u64erange);
310 if _GLIBCXX17_CONSTEXPR (__urngrange == __UINT32_MAX__)
314 __UINT32_TYPE__ __u32erange = __uerange;
315 __ret = _S_nd<__UINT64_TYPE__>(__urng, __u32erange);
321 const __uctype __scaling = __urngrange / __uerange;
322 const __uctype __past = __uerange * __scaling;
324 __ret = __uctype(__urng()) - __urngmin;
325 while (__ret >= __past);
329 else if (__urngrange < __urange)
349 const __uctype __uerngrange = __urngrange + 1;
350 __tmp = (__uerngrange * operator()
351 (__urng, param_type(0, __urange / __uerngrange)));
352 __ret = __tmp + (__uctype(__urng()) - __urngmin);
354 while (__ret > __urange || __ret < __tmp);
357 __ret = __uctype(__urng()) - __urngmin;
359 return __ret + __param.a();
363 template<
typename _IntType>
364 template<
typename _ForwardIterator,
365 typename _UniformRandomBitGenerator>
367 uniform_int_distribution<_IntType>::
368 __generate_impl(_ForwardIterator __f, _ForwardIterator __t,
369 _UniformRandomBitGenerator& __urng,
370 const param_type& __param)
372 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
373 typedef typename _UniformRandomBitGenerator::result_type _Gresult_type;
374 typedef typename make_unsigned<result_type>::type __utype;
375 typedef typename common_type<_Gresult_type, __utype>::type __uctype;
377 static_assert( __urng.min() < __urng.max(),
378 "Uniform random bit generator must define min() < max()");
380 constexpr __uctype __urngmin = __urng.min();
381 constexpr __uctype __urngmax = __urng.max();
382 constexpr __uctype __urngrange = __urngmax - __urngmin;
383 const __uctype __urange
384 = __uctype(__param.b()) - __uctype(__param.a());
388 if (__urngrange > __urange)
390 if (__detail::_Power_of_2(__urngrange + 1)
391 && __detail::_Power_of_2(__urange + 1))
395 __ret = __uctype(__urng()) - __urngmin;
396 *__f++ = (__ret & __urange) + __param.a();
402 const __uctype __uerange = __urange + 1;
403 const __uctype __scaling = __urngrange / __uerange;
404 const __uctype __past = __uerange * __scaling;
408 __ret = __uctype(__urng()) - __urngmin;
409 while (__ret >= __past);
410 *__f++ = __ret / __scaling + __param.a();
414 else if (__urngrange < __urange)
436 constexpr __uctype __uerngrange = __urngrange + 1;
437 __tmp = (__uerngrange * operator()
438 (__urng, param_type(0, __urange / __uerngrange)));
439 __ret = __tmp + (__uctype(__urng()) - __urngmin);
441 while (__ret > __urange || __ret < __tmp);
447 *__f++ = __uctype(__urng()) - __urngmin + __param.a();
452 _GLIBCXX_END_NAMESPACE_VERSION