From 247d8075711bc24632eb919c15524ed095485c16 Mon Sep 17 00:00:00 2001 From: Paolo Carlini Date: Fri, 19 Mar 2010 10:36:57 +0000 Subject: [PATCH] stl_algo.h (shuffle): Add, per D3056. 2010-03-19 Paolo Carlini * include/bits/stl_algo.h (shuffle): Add, per D3056. (random_shuffle): Fix signature in C++0x mode. (lower_bound, __lg): Move... * include/bits/stl_algobase.h: ... here. * include/bits/algorithmfwd.h: Adjust. * include/parallel/algorithmfwd.h: Likewise. * include/parallel/algo.h: Likewise. * include/bits/hashtable_policy.h (__lower_bound): Remove, adjust callers. * include/tr1/hashtable_policy.h (__lower_bound): Likewise. * include/bits/random.tcc (__detail::__transform): Add, adjust std::transform callers; don't include . * testsuite/25_algorithms/shuffle/1.cc: Add. * testsuite/25_algorithms/shuffle/requirements/ explicit_instantiation/2.cc: Likewise. * testsuite/25_algorithms/shuffle/requirements/ explicit_instantiation/pod.cc: Likewise. * include/bits/random.h: Add comments. From-SVN: r157564 --- libstdc++-v3/ChangeLog | 22 +++ libstdc++-v3/include/bits/algorithmfwd.h | 16 +- libstdc++-v3/include/bits/hashtable_policy.h | 35 +--- libstdc++-v3/include/bits/random.h | 138 +++++++++----- libstdc++-v3/include/bits/random.tcc | 34 ++-- libstdc++-v3/include/bits/stl_algo.h | 173 +++++------------- libstdc++-v3/include/bits/stl_algobase.h | 125 +++++++++++++ libstdc++-v3/include/parallel/algo.h | 8 +- libstdc++-v3/include/parallel/algorithmfwd.h | 9 +- libstdc++-v3/include/tr1/hashtable_policy.h | 35 +--- .../testsuite/25_algorithms/shuffle/1.cc | 67 +++++++ .../requirements/explicit_instantiation/2.cc | 38 ++++ .../explicit_instantiation/pod.cc | 37 ++++ 13 files changed, 493 insertions(+), 244 deletions(-) create mode 100644 libstdc++-v3/testsuite/25_algorithms/shuffle/1.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/2.cc create mode 100644 libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/pod.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 53ae0f99221b..1b06dae51d99 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,25 @@ +2010-03-19 Paolo Carlini + + * include/bits/stl_algo.h (shuffle): Add, per D3056. + (random_shuffle): Fix signature in C++0x mode. + (lower_bound, __lg): Move... + * include/bits/stl_algobase.h: ... here. + * include/bits/algorithmfwd.h: Adjust. + * include/parallel/algorithmfwd.h: Likewise. + * include/parallel/algo.h: Likewise. + * include/bits/hashtable_policy.h (__lower_bound): Remove, + adjust callers. + * include/tr1/hashtable_policy.h (__lower_bound): Likewise. + * include/bits/random.tcc (__detail::__transform): Add, + adjust std::transform callers; don't include . + * testsuite/25_algorithms/shuffle/1.cc: Add. + * testsuite/25_algorithms/shuffle/requirements/ + explicit_instantiation/2.cc: Likewise. + * testsuite/25_algorithms/shuffle/requirements/ + explicit_instantiation/pod.cc: Likewise. + + * include/bits/random.h: Add comments. + 2010-03-17 Jonathan Wakely * doc/xml/manual/debug_mode.xml: Correct debug headers. diff --git a/libstdc++-v3/include/bits/algorithmfwd.h b/libstdc++-v3/include/bits/algorithmfwd.h index 7625ee4af515..803fa4769475 100644 --- a/libstdc++-v3/include/bits/algorithmfwd.h +++ b/libstdc++-v3/include/bits/algorithmfwd.h @@ -1,6 +1,6 @@ // declarations -*- C++ -*- -// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the @@ -111,6 +111,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) set_intersection set_symmetric_difference set_union + shuffle (C++0x) sort sort_heap stable_partition @@ -517,6 +518,12 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // set_symmetric_difference // set_union +#if defined(__GXX_EXPERIMENTAL_CXX0X__) && defined(_GLIBCXX_USE_C99_STDINT_TR1) + template + void + shuffle(_RAIter, _RAIter, _UGenerator&&); +#endif + template void sort_heap(_RAIter, _RAIter); @@ -684,7 +691,12 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) template void - random_shuffle(_RAIter, _RAIter, _Generator&); + random_shuffle(_RAIter, _RAIter, +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + _Generator&&); +#else + _Generator&); +#endif template void diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h index 8471dfbf4ea0..142c57fd9a68 100644 --- a/libstdc++-v3/include/bits/hashtable_policy.h +++ b/libstdc++-v3/include/bits/hashtable_policy.h @@ -56,29 +56,6 @@ namespace __detail return __distance_fw(__first, __last, _Tag()); } - template - _RAIter - __lower_bound(_RAIter __first, _RAIter __last, const _Tp& __val) - { - typedef typename std::iterator_traits<_RAIter>::difference_type _DType; - - _DType __len = __last - __first; - while (__len > 0) - { - _DType __half = __len >> 1; - _RAIter __middle = __first + __half; - if (*__middle < __val) - { - __first = __middle; - ++__first; - __len = __len - __half - 1; - } - else - __len = __half; - } - return __first; - } - // Auxiliary types used for all instantiations of _Hashtable: nodes // and iterators. @@ -447,8 +424,8 @@ namespace __detail _Prime_rehash_policy:: _M_next_bkt(std::size_t __n) const { - const unsigned long* __p = __lower_bound(__prime_list, __prime_list - + _S_n_primes, __n); + const unsigned long* __p = std::lower_bound(__prime_list, __prime_list + + _S_n_primes, __n); _M_next_resize = static_cast(__builtin_ceil(*__p * _M_max_load_factor)); return *__p; @@ -461,8 +438,8 @@ namespace __detail _M_bkt_for_elements(std::size_t __n) const { const float __min_bkts = __n / _M_max_load_factor; - const unsigned long* __p = __lower_bound(__prime_list, __prime_list - + _S_n_primes, __min_bkts); + const unsigned long* __p = std::lower_bound(__prime_list, __prime_list + + _S_n_primes, __min_bkts); _M_next_resize = static_cast(__builtin_ceil(*__p * _M_max_load_factor)); return *__p; @@ -490,8 +467,8 @@ namespace __detail { __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); const unsigned long* __p = - __lower_bound(__prime_list, __prime_list + _S_n_primes, - __min_bkts); + std::lower_bound(__prime_list, __prime_list + _S_n_primes, + __min_bkts); _M_next_resize = static_cast (__builtin_ceil(*__p * _M_max_load_factor)); return std::make_pair(true, *__p); diff --git a/libstdc++-v3/include/bits/random.h b/libstdc++-v3/include/bits/random.h index 3f1a61535af4..cc950f03ae2b 100644 --- a/libstdc++-v3/include/bits/random.h +++ b/libstdc++-v3/include/bits/random.h @@ -1694,20 +1694,6 @@ namespace std b() const { return _M_param.b(); } - /** - * @brief Returns the inclusive lower bound of the distribution range. - */ - result_type - min() const - { return this->a(); } - - /** - * @brief Returns the inclusive upper bound of the distribution range. - */ - result_type - max() const - { return this->b(); } - /** * @brief Returns the parameter set of the distribution. */ @@ -1724,19 +1710,27 @@ namespace std { _M_param = __param; } /** - * Gets a uniformly distributed random number in the range - * @f$(min, max)@f$. + * @brief Returns the inclusive lower bound of the distribution range. + */ + result_type + min() const + { return this->a(); } + + /** + * @brief Returns the inclusive upper bound of the distribution range. + */ + result_type + max() const + { return this->b(); } + + /** + * @brief Generating functions. */ template result_type operator()(_UniformRandomNumberGenerator& __urng) { return this->operator()(__urng, this->param()); } - /** - * Gets a uniform random number in the range @f$[0, n)@f$. - * - * This function is aimed at use with std::random_shuffle. - */ template result_type operator()(_UniformRandomNumberGenerator& __urng, @@ -1875,6 +1869,21 @@ namespace std b() const { return _M_param.b(); } + /** + * @brief Returns the parameter set of the distribution. + */ + param_type + param() const + { return _M_param; } + + /** + * @brief Sets the parameter set of the distribution. + * @param __param The new parameter set of the distribution. + */ + void + param(const param_type& __param) + { _M_param = __param; } + /** * @brief Returns the inclusive lower bound of the distribution range. */ @@ -1890,20 +1899,8 @@ namespace std { return this->b(); } /** - * @brief Returns the parameter set of the distribution. - */ - param_type - param() const - { return _M_param; } - - /** - * @brief Sets the parameter set of the distribution. - * @param __param The new parameter set of the distribution. + * @brief Generating functions. */ - void - param(const param_type& __param) - { _M_param = __param; } - template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -2095,6 +2092,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -2265,6 +2265,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -2456,6 +2459,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -2613,6 +2619,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -2786,6 +2795,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -2959,6 +2971,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -3129,6 +3144,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -3310,7 +3328,7 @@ namespace std { return std::numeric_limits::max(); } /** - * @brief Returns the next value in the Bernoullian sequence. + * @brief Generating functions. */ template result_type @@ -3509,6 +3527,19 @@ namespace std max() const { return _M_param.t(); } + /** + * @brief Generating functions. + */ + template + result_type + operator()(_UniformRandomNumberGenerator& __urng) + { return this->operator()(__urng, this->param()); } + + template + result_type + operator()(_UniformRandomNumberGenerator& __urng, + const param_type& __p); + /** * @brief Return true if two binomial distributions have * the same parameters and the sequences that would @@ -3524,16 +3555,6 @@ namespace std { return __d1.param() == __d2.param(); } #endif - template - result_type - operator()(_UniformRandomNumberGenerator& __urng) - { return this->operator()(__urng, this->param()); } - - template - result_type - operator()(_UniformRandomNumberGenerator& __urng, - const param_type& __p); - /** * @brief Inserts a %binomial_distribution random number distribution * @p __x into the output stream @p __os. @@ -3691,6 +3712,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -3860,6 +3884,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng); @@ -4040,6 +4067,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -4219,6 +4249,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -4396,6 +4429,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -4568,6 +4604,9 @@ namespace std max() const { return std::numeric_limits::max(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -4756,6 +4795,9 @@ namespace std max() const { return this->_M_param._M_prob.size() - 1; } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -4960,6 +5002,9 @@ namespace std max() const { return this->_M_param._M_int.back(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) @@ -5168,6 +5213,9 @@ namespace std max() const { return this->_M_param._M_int.back(); } + /** + * @brief Generating functions. + */ template result_type operator()(_UniformRandomNumberGenerator& __urng) diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc index fb2879ccf355..e47b1c83c7f7 100644 --- a/libstdc++-v3/include/bits/random.tcc +++ b/libstdc++-v3/include/bits/random.tcc @@ -27,8 +27,7 @@ * You should not attempt to use it directly. */ -#include -#include +#include // std::accumulate and std::partial_sum namespace std { @@ -87,6 +86,17 @@ namespace std __calc(_Tp __x) { return __a * __x + __c; } }; + + template + _OutputIterator + __transform(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _UnaryOperation __unary_op) + { + for (; __first != __last; ++__first, ++__result) + *__result = __unary_op(*__first); + return __result; + } } // namespace __detail @@ -2177,8 +2187,8 @@ namespace std const double __sum = std::accumulate(_M_prob.begin(), _M_prob.end(), 0.0); // Now normalize the probabilites. - std::transform(_M_prob.begin(), _M_prob.end(), _M_prob.begin(), - std::bind2nd(std::divides(), __sum)); + __detail::__transform(_M_prob.begin(), _M_prob.end(), _M_prob.begin(), + std::bind2nd(std::divides(), __sum)); // Accumulate partial sums. _M_cp.reserve(_M_prob.size()); std::partial_sum(_M_prob.begin(), _M_prob.end(), @@ -2299,8 +2309,8 @@ namespace std const double __sum = std::accumulate(_M_den.begin(), _M_den.end(), 0.0); - std::transform(_M_den.begin(), _M_den.end(), _M_den.begin(), - std::bind2nd(std::divides(), __sum)); + __detail::__transform(_M_den.begin(), _M_den.end(), _M_den.begin(), + std::bind2nd(std::divides(), __sum)); _M_cp.reserve(_M_den.size()); std::partial_sum(_M_den.begin(), _M_den.end(), @@ -2499,14 +2509,14 @@ namespace std } // Now normalize the densities... - std::transform(_M_den.begin(), _M_den.end(), _M_den.begin(), - std::bind2nd(std::divides(), __sum)); + __detail::__transform(_M_den.begin(), _M_den.end(), _M_den.begin(), + std::bind2nd(std::divides(), __sum)); // ... and partial sums... - std::transform(_M_cp.begin(), _M_cp.end(), _M_cp.begin(), - std::bind2nd(std::divides(), __sum)); + __detail::__transform(_M_cp.begin(), _M_cp.end(), _M_cp.begin(), + std::bind2nd(std::divides(), __sum)); // ... and slopes. - std::transform(_M_m.begin(), _M_m.end(), _M_m.begin(), - std::bind2nd(std::divides(), __sum)); + __detail::__transform(_M_m.begin(), _M_m.end(), _M_m.begin(), + std::bind2nd(std::divides(), __sum)); // Make sure the last cumulative probablility is one. _M_cp[_M_cp.size() - 1] = 1.0; } diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 560ac1bb07bd..2f96d0670ef6 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -62,6 +62,10 @@ #include #include // for _Temporary_buffer +#ifdef __GXX_EXPERIMENTAL_CXX0X__ +#include // for std::uniform_int_distribution +#endif + // See concept_check.h for the __glibcxx_*_requires macros. _GLIBCXX_BEGIN_NAMESPACE(std) @@ -2301,29 +2305,6 @@ _GLIBCXX_BEGIN_NAMESPACE(std) } } - /// This is a helper function for the sort routines. Precondition: __n > 0. - template - inline _Size - __lg(_Size __n) - { - _Size __k; - for (__k = 0; __n != 0; __n >>= 1) - ++__k; - return __k - 1; - } - - inline int - __lg(int __n) - { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } - - inline long - __lg(long __n) - { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } - - inline long long - __lg(long long __n) - { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } - // sort template @@ -2386,106 +2367,7 @@ _GLIBCXX_BEGIN_NAMESPACE(std) // nth_element - /** - * @brief Finds the first position in which @a val could be inserted - * without changing the ordering. - * @param first An iterator. - * @param last Another iterator. - * @param val The search term. - * @return An iterator pointing to the first element not less - * than @a val, or end() if every element is less than - * @a val. - * @ingroup binary_search_algorithms - */ - template - _ForwardIterator - lower_bound(_ForwardIterator __first, _ForwardIterator __last, - const _Tp& __val) - { - typedef typename iterator_traits<_ForwardIterator>::value_type - _ValueType; - typedef typename iterator_traits<_ForwardIterator>::difference_type - _DistanceType; - - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) - __glibcxx_requires_partitioned_lower(__first, __last, __val); - - _DistanceType __len = std::distance(__first, __last); - _DistanceType __half; - _ForwardIterator __middle; - - while (__len > 0) - { - __half = __len >> 1; - __middle = __first; - std::advance(__middle, __half); - if (*__middle < __val) - { - __first = __middle; - ++__first; - __len = __len - __half - 1; - } - else - __len = __half; - } - return __first; - } - - /** - * @brief Finds the first position in which @a val could be inserted - * without changing the ordering. - * @ingroup binary_search_algorithms - * @param first An iterator. - * @param last Another iterator. - * @param val The search term. - * @param comp A functor to use for comparisons. - * @return An iterator pointing to the first element not less - * than @a val, or end() if every element is less - * than @a val. - * @ingroup binary_search_algorithms - * - * The comparison function should have the same effects on ordering as - * the function used for the initial sort. - */ - template - _ForwardIterator - lower_bound(_ForwardIterator __first, _ForwardIterator __last, - const _Tp& __val, _Compare __comp) - { - typedef typename iterator_traits<_ForwardIterator>::value_type - _ValueType; - typedef typename iterator_traits<_ForwardIterator>::difference_type - _DistanceType; - - // concept requirements - __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) - __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, - _ValueType, _Tp>) - __glibcxx_requires_partitioned_lower_pred(__first, __last, - __val, __comp); - - _DistanceType __len = std::distance(__first, __last); - _DistanceType __half; - _ForwardIterator __middle; - - while (__len > 0) - { - __half = __len >> 1; - __middle = __first; - std::advance(__middle, __half); - if (__comp(*__middle, __val)) - { - __first = __middle; - ++__first; - __len = __len - __half - 1; - } - else - __len = __half; - } - return __first; - } + // lower_bound moved to stl_algobase.h /** * @brief Finds the last position in which @a val could be inserted @@ -4179,6 +4061,47 @@ _GLIBCXX_BEGIN_NAMESPACE(std) std::minmax_element(__l.begin(), __l.end(), __comp); return std::make_pair(*__p.first, *__p.second); } + +#ifdef _GLIBCXX_USE_C99_STDINT_TR1 + /** + * @brief Shuffle the elements of a sequence using a uniform random + * number generator. + * @ingroup mutating_algorithms + * @param first A forward iterator. + * @param last A forward iterator. + * @param g A UniformRandomNumberGenerator (26.5.1.3). + * @return Nothing. + * + * Reorders the elements in the range @p [first,last) using @p g to + * provide random numbers. + */ + template + void + shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, + _UniformRandomNumberGenerator&& __g) + { + // concept requirements + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return; + + typedef typename iterator_traits<_RandomAccessIterator>::difference_type + _DistanceType; + + typedef typename std::make_unsigned<_DistanceType>::type __ud_type; + typedef typename std::uniform_int_distribution<__ud_type> __distr_type; + typedef typename __distr_type::param_type __p_type; + __distr_type __d; + + for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) + std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first))); + } +#endif + #endif // __GXX_EXPERIMENTAL_CXX0X__ _GLIBCXX_END_NAMESPACE @@ -4996,7 +4919,11 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) template void random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + _RandomNumberGenerator&& __rand) +#else _RandomNumberGenerator& __rand) +#endif { // concept requirements __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index 3575279226b9..1756966a5a1d 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -938,6 +938,131 @@ _GLIBCXX_BEGIN_NAMESPACE(std) __first2, __last2); } + /** + * @brief Finds the first position in which @a val could be inserted + * without changing the ordering. + * @param first An iterator. + * @param last Another iterator. + * @param val The search term. + * @return An iterator pointing to the first element not less + * than @a val, or end() if every element is less than + * @a val. + * @ingroup binary_search_algorithms + */ + template + _ForwardIterator + lower_bound(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __val) + { + typedef typename iterator_traits<_ForwardIterator>::value_type + _ValueType; + typedef typename iterator_traits<_ForwardIterator>::difference_type + _DistanceType; + + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>) + __glibcxx_requires_partitioned_lower(__first, __last, __val); + + _DistanceType __len = std::distance(__first, __last); + _DistanceType __half; + _ForwardIterator __middle; + + while (__len > 0) + { + __half = __len >> 1; + __middle = __first; + std::advance(__middle, __half); + if (*__middle < __val) + { + __first = __middle; + ++__first; + __len = __len - __half - 1; + } + else + __len = __half; + } + return __first; + } + + /** + * @brief Finds the first position in which @a val could be inserted + * without changing the ordering. + * @ingroup binary_search_algorithms + * @param first An iterator. + * @param last Another iterator. + * @param val The search term. + * @param comp A functor to use for comparisons. + * @return An iterator pointing to the first element not less + * than @a val, or end() if every element is less + * than @a val. + * @ingroup binary_search_algorithms + * + * The comparison function should have the same effects on ordering as + * the function used for the initial sort. + */ + template + _ForwardIterator + lower_bound(_ForwardIterator __first, _ForwardIterator __last, + const _Tp& __val, _Compare __comp) + { + typedef typename iterator_traits<_ForwardIterator>::value_type + _ValueType; + typedef typename iterator_traits<_ForwardIterator>::difference_type + _DistanceType; + + // concept requirements + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, + _ValueType, _Tp>) + __glibcxx_requires_partitioned_lower_pred(__first, __last, + __val, __comp); + + _DistanceType __len = std::distance(__first, __last); + _DistanceType __half; + _ForwardIterator __middle; + + while (__len > 0) + { + __half = __len >> 1; + __middle = __first; + std::advance(__middle, __half); + if (__comp(*__middle, __val)) + { + __first = __middle; + ++__first; + __len = __len - __half - 1; + } + else + __len = __half; + } + return __first; + } + + /// This is a helper function for the sort routines and for random.tcc. + // Precondition: __n > 0. + template + inline _Size + __lg(_Size __n) + { + _Size __k; + for (__k = 0; __n != 0; __n >>= 1) + ++__k; + return __k - 1; + } + + inline int + __lg(int __n) + { return sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); } + + inline long + __lg(long __n) + { return sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); } + + inline long long + __lg(long long __n) + { return sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); } + _GLIBCXX_END_NAMESPACE _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) diff --git a/libstdc++-v3/include/parallel/algo.h b/libstdc++-v3/include/parallel/algo.h index 43f0826d360a..aa87a48450a5 100644 --- a/libstdc++-v3/include/parallel/algo.h +++ b/libstdc++-v3/include/parallel/algo.h @@ -1645,7 +1645,7 @@ namespace __parallel // Sequential fallback. template inline void - random_shuffle(_RAIter __begin, _RAIter __end, + random_shuffle(_RAIter __begin, _RAIter __end, _RandomNumberGenerator& __rand, __gnu_parallel::sequential_tag) { _GLIBCXX_STD_P::random_shuffle(__begin, __end, __rand); } @@ -1673,8 +1673,12 @@ namespace __parallel // Parallel algorithm for random access iterators. template void - random_shuffle(_RAIter __begin, _RAIter __end, + random_shuffle(_RAIter __begin, _RAIter __end, +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + _RandomNumberGenerator&& __rand) +#else _RandomNumberGenerator& __rand) +#endif { if (__begin == __end) return; diff --git a/libstdc++-v3/include/parallel/algorithmfwd.h b/libstdc++-v3/include/parallel/algorithmfwd.h index 5c93615da26e..f2749b89eb12 100644 --- a/libstdc++-v3/include/parallel/algorithmfwd.h +++ b/libstdc++-v3/include/parallel/algorithmfwd.h @@ -1,6 +1,6 @@ // parallel extensions -*- C++ -*- -// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. +// Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms @@ -690,7 +690,12 @@ namespace __parallel template void - random_shuffle(_RAIter, _RAIter, _RandomNumberGenerator&); + random_shuffle(_RAIter, _RAIter, +#ifdef __GXX_EXPERIMENTAL_CXX0X__ + _RandomNumberGenerator&&); +#else + _RandomNumberGenerator&); +#endif template _OIter diff --git a/libstdc++-v3/include/tr1/hashtable_policy.h b/libstdc++-v3/include/tr1/hashtable_policy.h index 60a4e6449995..2a0e0ed4e1a7 100644 --- a/libstdc++-v3/include/tr1/hashtable_policy.h +++ b/libstdc++-v3/include/tr1/hashtable_policy.h @@ -55,29 +55,6 @@ namespace __detail return __distance_fw(__first, __last, _Tag()); } - template - _RAIter - __lower_bound(_RAIter __first, _RAIter __last, const _Tp& __val) - { - typedef typename std::iterator_traits<_RAIter>::difference_type _DType; - - _DType __len = __last - __first; - while (__len > 0) - { - _DType __half = __len >> 1; - _RAIter __middle = __first + __half; - if (*__middle < __val) - { - __first = __middle; - ++__first; - __len = __len - __half - 1; - } - else - __len = __half; - } - return __first; - } - // Auxiliary types used for all instantiations of _Hashtable: nodes // and iterators. @@ -440,8 +417,8 @@ namespace __detail _Prime_rehash_policy:: _M_next_bkt(std::size_t __n) const { - const unsigned long* __p = __lower_bound(__prime_list, __prime_list - + _S_n_primes, __n); + const unsigned long* __p = std::lower_bound(__prime_list, __prime_list + + _S_n_primes, __n); _M_next_resize = static_cast(__builtin_ceil(*__p * _M_max_load_factor)); return *__p; @@ -454,8 +431,8 @@ namespace __detail _M_bkt_for_elements(std::size_t __n) const { const float __min_bkts = __n / _M_max_load_factor; - const unsigned long* __p = __lower_bound(__prime_list, __prime_list - + _S_n_primes, __min_bkts); + const unsigned long* __p = std::lower_bound(__prime_list, __prime_list + + _S_n_primes, __min_bkts); _M_next_resize = static_cast(__builtin_ceil(*__p * _M_max_load_factor)); return *__p; @@ -483,8 +460,8 @@ namespace __detail { __min_bkts = std::max(__min_bkts, _M_growth_factor * __n_bkt); const unsigned long* __p = - __lower_bound(__prime_list, __prime_list + _S_n_primes, - __min_bkts); + std::lower_bound(__prime_list, __prime_list + _S_n_primes, + __min_bkts); _M_next_resize = static_cast (__builtin_ceil(*__p * _M_max_load_factor)); return std::make_pair(true, *__p); diff --git a/libstdc++-v3/testsuite/25_algorithms/shuffle/1.cc b/libstdc++-v3/testsuite/25_algorithms/shuffle/1.cc new file mode 100644 index 000000000000..b0e3574b4e0c --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/shuffle/1.cc @@ -0,0 +1,67 @@ +// { dg-options "-std=gnu++0x" } +// { dg-require-cstdint "" } + +// 2010-03-19 Paolo Carlini + +// Copyright (C) 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include +#include + +void test01() +{ + bool test __attribute__((unused)) = true; + + for (unsigned size = 0; size < 50; ++size) + { + std::vector vref(size); + std::iota(vref.begin(), vref.end(), 0); + std::vector v1(vref), v2(vref); + + std::ranlux48_base g1(size), g2(size + 1); + std::shuffle(v1.begin(), v1.end(), g1); + std::shuffle(v2.begin(), v2.end(), g2); + + if (size >= 10) + { + VERIFY( !std::equal(v1.begin(), v1.end(), vref.begin()) ); + VERIFY( !std::equal(v2.begin(), v2.end(), vref.begin()) ); + VERIFY( !std::equal(v1.begin(), v1.end(), v2.begin()) ); + } + + for (unsigned ind = 0; ind < size; ++ind) + { + auto it1 = std::find(v1.begin(), v1.end(), vref[ind]); + auto it2 = std::find(v2.begin(), v2.end(), vref[ind]); + VERIFY( it1 != v1.end() ); + VERIFY( it2 != v2.end() ); + v1.erase(it1); + v2.erase(it2); + } + VERIFY( v1.empty() ); + VERIFY( v2.empty() ); + } +} + +int main() +{ + test01(); + return 0; +} diff --git a/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/2.cc b/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/2.cc new file mode 100644 index 000000000000..4b921dca712a --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/2.cc @@ -0,0 +1,38 @@ +// { dg-do compile } +// { dg-options "-std=gnu++0x" } +// { dg-require-cstdint "" } + +// 2010-03-19 Paolo Carlini + +// Copyright (C) 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + + +#include +#include +#include + +namespace std +{ + using __gnu_test::NonDefaultConstructible; + + typedef NonDefaultConstructible value_type; + typedef value_type* iterator_type; + typedef std::mt19937_64 ugenerator_type; + + template void shuffle(iterator_type, iterator_type, ugenerator_type&&); +} diff --git a/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/pod.cc b/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/pod.cc new file mode 100644 index 000000000000..0f0a1e19ea4c --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/shuffle/requirements/explicit_instantiation/pod.cc @@ -0,0 +1,37 @@ +// { dg-do compile } +// { dg-options "-std=gnu++0x" } +// { dg-require-cstdint "" } + +// 2010-03-19 Paolo Carlini + +// Copyright (C) 2010 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +#include +#include +#include + +namespace std +{ + using __gnu_test::pod_int; + + typedef pod_int value_type; + typedef value_type* iterator_type; + typedef std::mt19937_64 ugenerator_type; + + template void shuffle(iterator_type, iterator_type, ugenerator_type&&); +} -- 2.39.2