diff options
author | Howard Hinnant <hhinnant@apple.com> | 2010-05-26 21:49:34 +0400 |
---|---|---|
committer | Howard Hinnant <hhinnant@apple.com> | 2010-05-26 21:49:34 +0400 |
commit | f9d540b0624ff755e1903a9a8a708d5ea8190386 (patch) | |
tree | f1fcffffa7b8ad195a60ecc05843f36d7c762b1a /libcxx/include/algorithm | |
parent | a19838e1076f361c3fde481c515f60a13a64b19f (diff) |
Completed [alg.random.shuffle].
llvm-svn: 104708
Diffstat (limited to 'libcxx/include/algorithm')
-rw-r--r-- | libcxx/include/algorithm | 346 |
1 files changed, 260 insertions, 86 deletions
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index c53bf3766e63..01cee60bf42c 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -254,6 +254,10 @@ template <class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand); +template<class RandomAccessIterator, class UniformRandomNumberGenerator> + void shuffle(RandomAccessIterator first, RandomAccessIterator last, + UniformRandomNumberGenerator& g); + template <class InputIterator, class Predicate> bool is_partitioned(InputIterator first, InputIterator last, Predicate pred); @@ -2277,132 +2281,286 @@ minmax_element(_ForwardIterator __first, _ForwardIterator __last) // random_shuffle -template <unsigned int _Bits> -struct __num_bits +// __independent_bits_engine + +template <unsigned long long _X, size_t _R> +struct __log2_imp { - static const int __value = 1 + __num_bits<(_Bits >> 1)>::__value; + static const size_t value = _X & ((unsigned long long)(1) << _R) ? _R + : __log2_imp<_X, _R - 1>::value; }; -template <> -struct __num_bits<0> +template <unsigned long long _X> +struct __log2_imp<_X, 0> { - static const int __value = 0; + static const size_t value = 0; }; -const int __rbits = __num_bits<RAND_MAX>::__value; -const int __lbits = static_cast<int>(sizeof(unsigned long) * __CHAR_BIT__); - -template <int _NBits, bool = _NBits <= __rbits> -struct __random_bits +template <size_t _R> +struct __log2_imp<0, _R> { - _LIBCPP_INLINE_VISIBILITY operator unsigned long () const - {return static_cast<unsigned long>(_STD::rand()) >> (__rbits - _NBits);} + static const size_t value = _R + 1; }; -template <int _NBits> -struct __random_bits<_NBits, false> +template <class _UI, _UI _X> +struct __log2 { - _LIBCPP_INLINE_VISIBILITY operator unsigned long () const - {return static_cast<unsigned long>(_STD::rand()) << (_NBits - __rbits) | __random_bits<_NBits - __rbits>();} + static const size_t value = __log2_imp<_X, + sizeof(_UI) * __CHAR_BIT__ - 1>::value; }; -template <int _NBits> -inline _LIBCPP_INLINE_VISIBILITY -unsigned long -__slab_size(unsigned long __n) +template<class _Engine, class _UIntType> +class __independent_bits_engine { - return (1UL << _NBits) / __n; -} +public: + // types + typedef _UIntType result_type; -template <> -inline _LIBCPP_INLINE_VISIBILITY -unsigned long -__slab_size<__lbits>(unsigned long __n) -{ - if (__n & 1) - return (unsigned long)(~0) / __n; - return (1UL << (__lbits-1)) / (__n >> 1); -} +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; -template <int _NBits> -inline _LIBCPP_INLINE_VISIBILITY -unsigned long -__scaled_random_number(unsigned long __n) -{ - const unsigned long __slab = __slab_size<_NBits>(__n); - const unsigned long __usable = __slab * __n; - unsigned long __raw; - do - __raw = __random_bits<_NBits>(); - while (__raw >= __usable); - return __raw / __slab; -} +public: + // constructors and seeding functions + __independent_bits_engine(_Engine& __e, size_t __w); -template <bool __b, unsigned long = __lbits/__rbits> struct __rs_default; + // generating functions + result_type operator()() {return __eval(integral_constant<bool, _R != 0>());} -template <bool __b> -struct __rs_default<__b, 1> -{ - unsigned long operator()(unsigned long __n = 0) const; +private: + result_type __eval(false_type); + result_type __eval(true_type); }; -template <bool __b> -unsigned long -__rs_default<__b, 1>::operator()(unsigned long __n) const -{ - switch (__n) +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_) { - case 0: - return __random_bits<__lbits>(); - case 1: - return 0; + ++__n_; + __w0_ = __w_ / __n_; + if (__w0_ < _WDt) + __y0_ = (_R >> __w0_) << __w0_; + else + __y0_ = 0; } - if (__n <= (1UL << __rbits)) - return __scaled_random_number<__rbits>(__n); - return __scaled_random_number<__lbits>(__n); + __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 <bool __b> -struct __rs_default<__b, 2> +template<class _Engine, class _UIntType> +inline +_UIntType +__independent_bits_engine<_Engine, _UIntType>::__eval(false_type) { - unsigned long operator()(unsigned long __n = 0) const; -}; + return static_cast<result_type>(__e_() & __mask0_); +} -template <bool __b> -unsigned long -__rs_default<__b, 2>::operator()(unsigned long __n) const +template<class _Engine, class _UIntType> +_UIntType +__independent_bits_engine<_Engine, _UIntType>::__eval(true_type) { - switch (__n) + result_type _S = 0; + for (size_t __k = 0; __k < __n0_; ++__k) { - case 0: - return __random_bits<__lbits>(); - case 1: - return 0; + _Engine_result_type __u; + do + { + __u = __e_() - _Engine::min(); + } while (__u >= __y0_); + if (__w0_ < _EDt) + _S <<= __w0_; + else + _S = 0; + _S += __u & __mask0_; } - int __nb = __rbits; - while (__nb < __lbits && __n > (1UL << __nb)) - __nb += _STD::min(__rbits, __lbits - __nb); - switch (__nb) + for (size_t __k = __n0_; __k < __n_; ++__k) { - case __rbits: - return __scaled_random_number<__rbits>(__n); - case 2*__rbits: - return __scaled_random_number<2*__rbits>(__n); + _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 __scaled_random_number<__lbits>(__n); + 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()); +} + +class __rs_default; + +__rs_default __rs_get(); + +class __rs_default +{ + static unsigned __c_; + + __rs_default(); +public: + typedef unsigned result_type; + + static const result_type _Min = 0; + static const result_type _Max = 0xFFFFFFFF; + + __rs_default(const __rs_default&); + ~__rs_default(); + + result_type operator()(); + + static const/*expr*/ result_type min() {return _Min;} + static const/*expr*/ result_type max() {return _Max;} + + friend __rs_default __rs_get(); +}; + +__rs_default __rs_get(); + template <class _RandomAccessIterator> void random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; + typedef uniform_int_distribution<ptrdiff_t> _D; + typedef typename _D::param_type _P; difference_type __d = __last - __first; if (__d > 1) { - for (--__last; __first < __last; ++__first, --__d) - swap(*__first, *(__first - + static_cast<difference_type>(__rs_default<true>()(static_cast<unsigned long>(__d))))); + _D __uid; + __rs_default __g = __rs_get(); + for (--__last, --__d; __first < __last; ++__first, --__d) + swap(*__first, *(__first + __uid(__g, _P(0, __d)))); } } @@ -2424,6 +2582,22 @@ random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, } } +template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> + void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, + _UniformRandomNumberGenerator& __g) +{ + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; + typedef uniform_int_distribution<ptrdiff_t> _D; + typedef typename _D::param_type _P; + difference_type __d = __last - __first; + if (__d > 1) + { + _D __uid; + for (--__last, --__d; __first < __last; ++__first, --__d) + swap(*__first, *(__first + __uid(__g, _P(0, __d)))); + } +} + template <class _InputIterator, class _Predicate> bool is_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred) |