Completed [alg.random.shuffle].
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@104708 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/random b/include/random
index adefa8b..f3e6656 100644
--- a/include/random
+++ b/include/random
@@ -2793,32 +2793,6 @@
// independent_bits_engine
-template <unsigned long long _X, size_t _R>
-struct __log2_imp
-{
- static const size_t value = _X & ((unsigned long long)(1) << _R) ? _R
- : __log2_imp<_X, _R - 1>::value;
-};
-
-template <unsigned long long _X>
-struct __log2_imp<_X, 0>
-{
- static const size_t value = 0;
-};
-
-template <size_t _R>
-struct __log2_imp<0, _R>
-{
- static const size_t value = _R + 1;
-};
-
-template <class _UI, _UI _X>
-struct __log2
-{
- static const size_t value = __log2_imp<_X,
- sizeof(_UI) * __CHAR_BIT__ - 1>::value;
-};
-
template<class _Engine, size_t __w, class _UIntType>
class independent_bits_engine
{
@@ -3396,217 +3370,9 @@
return _S / __base;
}
-// __independent_bits_engine
-
-template<class _Engine, class _UIntType>
-class __independent_bits_engine
-{
-public:
- // types
- typedef _UIntType result_type;
-
-private:
- typedef typename _Engine::result_type _Engine_result_type;
- typedef typename conditional
- <
- sizeof(_Engine_result_type) <= sizeof(result_type),
- result_type,
- _Engine_result_type
- >::type _Working_result_type;
-
- _Engine& __e_;
- size_t __w_;
- size_t __w0_;
- size_t __n_;
- size_t __n0_;
- _Working_result_type __y0_;
- _Working_result_type __y1_;
- _Engine_result_type __mask0_;
- _Engine_result_type __mask1_;
-
- static const _Working_result_type _R = _Engine::_Max - _Engine::_Min
- + _Working_result_type(1);
- static const size_t __m = __log2<_Working_result_type, _R>::value;
- static const size_t _WDt = numeric_limits<_Working_result_type>::digits;
- static const size_t _EDt = numeric_limits<_Engine_result_type>::digits;
-
-public:
- // constructors and seeding functions
- __independent_bits_engine(_Engine& __e, size_t __w);
-
- // generating functions
- result_type operator()() {return __eval(integral_constant<bool, _R != 0>());}
-
-private:
- result_type __eval(false_type);
- result_type __eval(true_type);
-};
-
-template<class _Engine, class _UIntType>
-__independent_bits_engine<_Engine, _UIntType>
- ::__independent_bits_engine(_Engine& __e, size_t __w)
- : __e_(__e),
- __w_(__w)
-{
- __n_ = __w_ / __m + (__w_ % __m != 0);
- __w0_ = __w_ / __n_;
- if (_R == 0)
- __y0_ = _R;
- else if (__w0_ < _WDt)
- __y0_ = (_R >> __w0_) << __w0_;
- else
- __y0_ = 0;
- if (_R - __y0_ > __y0_ / __n_)
- {
- ++__n_;
- __w0_ = __w_ / __n_;
- if (__w0_ < _WDt)
- __y0_ = (_R >> __w0_) << __w0_;
- else
- __y0_ = 0;
- }
- __n0_ = __n_ - __w_ % __n_;
- if (__w0_ < _WDt - 1)
- __y1_ = (_R >> (__w0_ + 1)) << (__w0_ + 1);
- else
- __y1_ = 0;
- __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) :
- _Engine_result_type(0);
- __mask1_ = __w0_ < _EDt - 1 ?
- _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) :
- _Engine_result_type(~0);
-}
-
-template<class _Engine, class _UIntType>
-inline
-_UIntType
-__independent_bits_engine<_Engine, _UIntType>::__eval(false_type)
-{
- return static_cast<result_type>(__e_() & __mask0_);
-}
-
-template<class _Engine, class _UIntType>
-_UIntType
-__independent_bits_engine<_Engine, _UIntType>::__eval(true_type)
-{
- result_type _S = 0;
- for (size_t __k = 0; __k < __n0_; ++__k)
- {
- _Engine_result_type __u;
- do
- {
- __u = __e_() - _Engine::min();
- } while (__u >= __y0_);
- if (__w0_ < _EDt)
- _S <<= __w0_;
- else
- _S = 0;
- _S += __u & __mask0_;
- }
- for (size_t __k = __n0_; __k < __n_; ++__k)
- {
- _Engine_result_type __u;
- do
- {
- __u = __e_() - _Engine::min();
- } while (__u >= __y1_);
- if (__w0_ < _EDt - 1)
- _S <<= __w0_ + 1;
- else
- _S = 0;
- _S += __u & __mask1_;
- }
- return _S;
-}
-
// uniform_int_distribution
-template<class _IntType = int>
-class uniform_int_distribution
-{
-public:
- // types
- typedef _IntType result_type;
-
- class param_type
- {
- result_type __a_;
- result_type __b_;
- public:
- typedef uniform_int_distribution distribution_type;
-
- explicit param_type(result_type __a = 0,
- result_type __b = numeric_limits<result_type>::max())
- : __a_(__a), __b_(__b) {}
-
- result_type a() const {return __a_;}
- result_type b() const {return __b_;}
-
- friend bool operator==(const param_type& __x, const param_type& __y)
- {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;}
- friend bool operator!=(const param_type& __x, const param_type& __y)
- {return !(__x == __y);}
- };
-
-private:
- param_type __p_;
-
-public:
- // constructors and reset functions
- explicit uniform_int_distribution(result_type __a = 0,
- result_type __b = numeric_limits<result_type>::max())
- : __p_(param_type(__a, __b)) {}
- explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {}
- void reset() {}
-
- // generating functions
- template<class _URNG> result_type operator()(_URNG& __g)
- {return (*this)(__g, __p_);}
- template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p);
-
- // property functions
- result_type a() const {return __p_.a();}
- result_type b() const {return __p_.b();}
-
- param_type param() const {return __p_;}
- void param(const param_type& __p) {__p_ = __p;}
-
- result_type min() const {return a();}
- result_type max() const {return b();}
-
- friend bool operator==(const uniform_int_distribution& __x,
- const uniform_int_distribution& __y)
- {return __x.__p_ == __y.__p_;}
- friend bool operator!=(const uniform_int_distribution& __x,
- const uniform_int_distribution& __y)
- {return !(__x == __y);}
-};
-
-template<class _IntType>
-template<class _URNG>
-typename uniform_int_distribution<_IntType>::result_type
-uniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p)
-{
- typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t),
- uint32_t, uint64_t>::type _UIntType;
- const _UIntType _R = __p.b() - __p.a() + _UIntType(1);
- if (_R == 1)
- return __p.a();
- const size_t _Dt = numeric_limits<_UIntType>::digits;
- typedef __independent_bits_engine<_URNG, _UIntType> _Eng;
- if (_R == 0)
- return static_cast<result_type>(_Eng(__g, _Dt)());
- size_t __w = _Dt - __clz(_R) - 1;
- if ((_R & (_UIntType(~0) >> (_Dt - __w))) != 0)
- ++__w;
- _Eng __e(__g, __w);
- _UIntType __u;
- do
- {
- __u = __e();
- } while (__u >= _R);
- return static_cast<result_type>(__u + __p.a());
-}
+// in <algorithm>
template <class _CharT, class _Traits, class _IT>
basic_ostream<_CharT, _Traits>&