diff options
Diffstat (limited to 'contrib/libstdc++/include/ext/algorithm')
| -rw-r--r-- | contrib/libstdc++/include/ext/algorithm | 274 |
1 files changed, 128 insertions, 146 deletions
diff --git a/contrib/libstdc++/include/ext/algorithm b/contrib/libstdc++/include/ext/algorithm index b35d36f..07ac4cb 100644 --- a/contrib/libstdc++/include/ext/algorithm +++ b/contrib/libstdc++/include/ext/algorithm @@ -60,9 +60,10 @@ */ #ifndef _EXT_ALGORITHM -#define _EXT_ALGORITHM +#define _EXT_ALGORITHM 1 #pragma GCC system_header + #include <algorithm> namespace __gnu_cxx @@ -77,10 +78,10 @@ namespace __gnu_cxx //-------------------------------------------------- // copy_n (not part of the C++ standard) - template<typename _InputIter, typename _Size, typename _OutputIter> - pair<_InputIter, _OutputIter> - __copy_n(_InputIter __first, _Size __count, - _OutputIter __result, + template<typename _InputIterator, typename _Size, typename _OutputIterator> + pair<_InputIterator, _OutputIterator> + __copy_n(_InputIterator __first, _Size __count, + _OutputIterator __result, input_iterator_tag) { for ( ; __count > 0; --__count) { @@ -88,17 +89,17 @@ namespace __gnu_cxx ++__first; ++__result; } - return pair<_InputIter, _OutputIter>(__first, __result); + return pair<_InputIterator, _OutputIterator>(__first, __result); } - template<typename _RAIter, typename _Size, typename _OutputIter> - inline pair<_RAIter, _OutputIter> - __copy_n(_RAIter __first, _Size __count, - _OutputIter __result, + template<typename _RAIterator, typename _Size, typename _OutputIterator> + inline pair<_RAIterator, _OutputIterator> + __copy_n(_RAIterator __first, _Size __count, + _OutputIterator __result, random_access_iterator_tag) { - _RAIter __last = __first + __count; - return pair<_RAIter, _OutputIter>(__last, + _RAIterator __last = __first + __count; + return pair<_RAIterator, _OutputIterator>(__last, std::copy(__first, __last, __result)); } @@ -116,23 +117,23 @@ namespace __gnu_cxx * optimizations such as unrolling). * @ingroup SGIextensions */ - template<typename _InputIter, typename _Size, typename _OutputIter> - inline pair<_InputIter, _OutputIter> - copy_n(_InputIter __first, _Size __count, _OutputIter __result) + template<typename _InputIterator, typename _Size, typename _OutputIterator> + inline pair<_InputIterator, _OutputIterator> + copy_n(_InputIterator __first, _Size __count, _OutputIterator __result) { // concept requirements - __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) - __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, - typename iterator_traits<_InputIter>::value_type>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + typename iterator_traits<_InputIterator>::value_type>) return __copy_n(__first, __count, __result, std::__iterator_category(__first)); } - template<typename _InputIter1, typename _InputIter2> + template<typename _InputIterator1, typename _InputIterator2> int - __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2) + __lexicographical_compare_3way(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2) { while (__first1 != __last1 && __first2 != __last2) { if (*__first1 < *__first2) @@ -159,11 +160,11 @@ namespace __gnu_cxx const ptrdiff_t __len1 = __last1 - __first1; const ptrdiff_t __len2 = __last2 - __first2; const int __result = std::memcmp(__first1, __first2, min(__len1, __len2)); - return __result != 0 ? __result + return __result != 0 ? __result : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1)); } - inline int + inline int __lexicographical_compare_3way(const char* __first1, const char* __last1, const char* __first2, const char* __last2) { @@ -195,18 +196,20 @@ namespace __gnu_cxx * This is an SGI extension. * @ingroup SGIextensions */ - template<typename _InputIter1, typename _InputIter2> + template<typename _InputIterator1, typename _InputIterator2> int - lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2) + lexicographical_compare_3way(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2) { // concept requirements - __glibcpp_function_requires(_InputIteratorConcept<_InputIter1>) - __glibcpp_function_requires(_InputIteratorConcept<_InputIter2>) - __glibcpp_function_requires(_LessThanComparableConcept< - typename iterator_traits<_InputIter1>::value_type>) - __glibcpp_function_requires(_LessThanComparableConcept< - typename iterator_traits<_InputIter2>::value_type>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_InputIterator1>::value_type>) + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_InputIterator2>::value_type>) + __glibcxx_requires_valid_range(__first1, __last1); + __glibcxx_requires_valid_range(__first2, __last2); return __lexicographical_compare_3way(__first1, __last1, __first2, __last2); } @@ -214,32 +217,36 @@ namespace __gnu_cxx // count and count_if: this version, whose return type is void, was present // in the HP STL, and is retained as an extension for backward compatibility. - template<typename _InputIter, typename _Tp, typename _Size> + template<typename _InputIterator, typename _Tp, typename _Size> void - count(_InputIter __first, _InputIter __last, + count(_InputIterator __first, _InputIterator __last, const _Tp& __value, _Size& __n) { // concept requirements - __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) - __glibcpp_function_requires(_EqualityComparableConcept< - typename iterator_traits<_InputIter>::value_type >) - __glibcpp_function_requires(_EqualityComparableConcept<_Tp>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_EqualityComparableConcept< + typename iterator_traits<_InputIterator>::value_type >) + __glibcxx_function_requires(_EqualityComparableConcept<_Tp>) + __glibcxx_requires_valid_range(__first, __last); + for ( ; __first != __last; ++__first) if (*__first == __value) ++__n; } - template<typename _InputIter, typename _Predicate, typename _Size> + template<typename _InputIterator, typename _Predicate, typename _Size> void - count_if(_InputIter __first, _InputIter __last, + count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, _Size& __n) { // concept requirements - __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) - __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate, - typename iterator_traits<_InputIter>::value_type>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, + typename iterator_traits<_InputIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); + for ( ; __first != __last; ++__first) if (__pred(*__first)) ++__n; @@ -252,21 +259,22 @@ namespace __gnu_cxx * @ingroup SGIextensions * @doctodo */ - template<typename _ForwardIter, typename _OutputIter, typename _Distance> - _OutputIter - random_sample_n(_ForwardIter __first, _ForwardIter __last, - _OutputIter __out, const _Distance __n) + template<typename _ForwardIterator, typename _OutputIterator, typename _Distance> + _OutputIterator + random_sample_n(_ForwardIterator __first, _ForwardIterator __last, + _OutputIterator __out, const _Distance __n) { // concept requirements - __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) - __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, - typename iterator_traits<_ForwardIter>::value_type>) + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); _Distance __remaining = std::distance(__first, __last); _Distance __m = min(__n, __remaining); while (__m > 0) { - if (std::__random_number(__remaining) < __m) { + if ((std::rand() % __remaining) < __m) { *__out = *__first; ++__out; --__m; @@ -283,19 +291,20 @@ namespace __gnu_cxx * @ingroup SGIextensions * @doctodo */ - template<typename _ForwardIter, typename _OutputIter, typename _Distance, + template<typename _ForwardIterator, typename _OutputIterator, typename _Distance, typename _RandomNumberGenerator> - _OutputIter - random_sample_n(_ForwardIter __first, _ForwardIter __last, - _OutputIter __out, const _Distance __n, + _OutputIterator + random_sample_n(_ForwardIterator __first, _ForwardIterator __last, + _OutputIterator __out, const _Distance __n, _RandomNumberGenerator& __rand) { // concept requirements - __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) - __glibcpp_function_requires(_OutputIteratorConcept<_OutputIter, - typename iterator_traits<_ForwardIter>::value_type>) - __glibcpp_function_requires(_UnaryFunctionConcept< + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_function_requires(_UnaryFunctionConcept< _RandomNumberGenerator, _Distance, _Distance>) + __glibcxx_requires_valid_range(__first, __last); _Distance __remaining = std::distance(__first, __last); _Distance __m = min(__n, __remaining); @@ -313,20 +322,20 @@ namespace __gnu_cxx return __out; } - template<typename _InputIter, typename _RandomAccessIter, typename _Distance> - _RandomAccessIter - __random_sample(_InputIter __first, _InputIter __last, - _RandomAccessIter __out, + template<typename _InputIterator, typename _RandomAccessIterator, typename _Distance> + _RandomAccessIterator + __random_sample(_InputIterator __first, _InputIterator __last, + _RandomAccessIterator __out, const _Distance __n) { _Distance __m = 0; _Distance __t = __n; - for ( ; __first != __last && __m < __n; ++__m, ++__first) + for ( ; __first != __last && __m < __n; ++__m, ++__first) __out[__m] = *__first; while (__first != __last) { ++__t; - _Distance __M = std::__random_number(__t); + _Distance __M = std::rand() % (__t); if (__M < __n) __out[__M] = *__first; ++__first; @@ -335,16 +344,16 @@ namespace __gnu_cxx return __out + __m; } - template<typename _InputIter, typename _RandomAccessIter, + template<typename _InputIterator, typename _RandomAccessIterator, typename _RandomNumberGenerator, typename _Distance> - _RandomAccessIter - __random_sample(_InputIter __first, _InputIter __last, - _RandomAccessIter __out, + _RandomAccessIterator + __random_sample(_InputIterator __first, _InputIterator __last, + _RandomAccessIterator __out, _RandomNumberGenerator& __rand, const _Distance __n) { // concept requirements - __glibcpp_function_requires(_UnaryFunctionConcept< + __glibcxx_function_requires(_UnaryFunctionConcept< _RandomNumberGenerator, _Distance, _Distance>) _Distance __m = 0; @@ -368,15 +377,17 @@ namespace __gnu_cxx * @ingroup SGIextensions * @doctodo */ - template<typename _InputIter, typename _RandomAccessIter> - inline _RandomAccessIter - random_sample(_InputIter __first, _InputIter __last, - _RandomAccessIter __out_first, _RandomAccessIter __out_last) + template<typename _InputIterator, typename _RandomAccessIterator> + inline _RandomAccessIterator + random_sample(_InputIterator __first, _InputIterator __last, + _RandomAccessIterator __out_first, _RandomAccessIterator __out_last) { // concept requirements - __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) - __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIter>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_valid_range(__out_first, __out_last); return __random_sample(__first, __last, __out_first, __out_last - __out_first); @@ -387,72 +398,41 @@ namespace __gnu_cxx * @ingroup SGIextensions * @doctodo */ - template<typename _InputIter, typename _RandomAccessIter, + template<typename _InputIterator, typename _RandomAccessIterator, typename _RandomNumberGenerator> - inline _RandomAccessIter - random_sample(_InputIter __first, _InputIter __last, - _RandomAccessIter __out_first, _RandomAccessIter __out_last, - _RandomNumberGenerator& __rand) + inline _RandomAccessIterator + random_sample(_InputIterator __first, _InputIterator __last, + _RandomAccessIterator __out_first, _RandomAccessIterator __out_last, + _RandomNumberGenerator& __rand) { // concept requirements - __glibcpp_function_requires(_InputIteratorConcept<_InputIter>) - __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< - _RandomAccessIter>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< + _RandomAccessIterator>) + __glibcxx_requires_valid_range(__first, __last); + __glibcxx_requires_valid_range(__out_first, __out_last); return __random_sample(__first, __last, __out_first, __rand, __out_last - __out_first); } - - // is_heap, a predicate testing whether or not a range is - // a heap. This function is an extension, not part of the C++ - // standard. - - template<typename _RandomAccessIter, typename _Distance> - bool - __is_heap(_RandomAccessIter __first, _Distance __n) - { - _Distance __parent = 0; - for (_Distance __child = 1; __child < __n; ++__child) { - if (__first[__parent] < __first[__child]) - return false; - if ((__child & 1) == 0) - ++__parent; - } - return true; - } - - template<typename _RandomAccessIter, typename _Distance, - typename _StrictWeakOrdering> - bool - __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp, - _Distance __n) - { - _Distance __parent = 0; - for (_Distance __child = 1; __child < __n; ++__child) { - if (__comp(__first[__parent], __first[__child])) - return false; - if ((__child & 1) == 0) - ++__parent; - } - return true; - } /** * This is an SGI extension. * @ingroup SGIextensions * @doctodo */ - template<typename _RandomAccessIter> + template<typename _RandomAccessIterator> inline bool - is_heap(_RandomAccessIter __first, _RandomAccessIter __last) + is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { // concept requirements - __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>) - __glibcpp_function_requires(_LessThanComparableConcept< - typename iterator_traits<_RandomAccessIter>::value_type>) + __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>) + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_RandomAccessIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); - return __is_heap(__first, __last - __first); + return std::__is_heap(__first, __last - __first); } /** @@ -460,18 +440,19 @@ namespace __gnu_cxx * @ingroup SGIextensions * @doctodo */ - template<typename _RandomAccessIter, typename _StrictWeakOrdering> + template<typename _RandomAccessIterator, typename _StrictWeakOrdering> inline bool - is_heap(_RandomAccessIter __first, _RandomAccessIter __last, + is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _StrictWeakOrdering __comp) { // concept requirements - __glibcpp_function_requires(_RandomAccessIteratorConcept<_RandomAccessIter>) - __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, - typename iterator_traits<_RandomAccessIter>::value_type, - typename iterator_traits<_RandomAccessIter>::value_type>) + __glibcxx_function_requires(_RandomAccessIteratorConcept<_RandomAccessIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, + typename iterator_traits<_RandomAccessIterator>::value_type, + typename iterator_traits<_RandomAccessIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); - return __is_heap(__first, __comp, __last - __first); + return std::__is_heap(__first, __comp, __last - __first); } // is_sorted, a predicated testing whether a range is sorted in @@ -483,19 +464,20 @@ namespace __gnu_cxx * @ingroup SGIextensions * @doctodo */ - template<typename _ForwardIter> + template<typename _ForwardIterator> bool - is_sorted(_ForwardIter __first, _ForwardIter __last) + is_sorted(_ForwardIterator __first, _ForwardIterator __last) { // concept requirements - __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) - __glibcpp_function_requires(_LessThanComparableConcept< - typename iterator_traits<_ForwardIter>::value_type>) + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_LessThanComparableConcept< + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); if (__first == __last) return true; - _ForwardIter __next = __first; + _ForwardIterator __next = __first; for (++__next; __next != __last; __first = __next, ++__next) { if (*__next < *__first) return false; @@ -509,20 +491,21 @@ namespace __gnu_cxx * @ingroup SGIextensions * @doctodo */ - template<typename _ForwardIter, typename _StrictWeakOrdering> + template<typename _ForwardIterator, typename _StrictWeakOrdering> bool - is_sorted(_ForwardIter __first, _ForwardIter __last, _StrictWeakOrdering __comp) + is_sorted(_ForwardIterator __first, _ForwardIterator __last, _StrictWeakOrdering __comp) { // concept requirements - __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>) - __glibcpp_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, - typename iterator_traits<_ForwardIter>::value_type, - typename iterator_traits<_ForwardIter>::value_type>) + __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) + __glibcxx_function_requires(_BinaryPredicateConcept<_StrictWeakOrdering, + typename iterator_traits<_ForwardIterator>::value_type, + typename iterator_traits<_ForwardIterator>::value_type>) + __glibcxx_requires_valid_range(__first, __last); if (__first == __last) return true; - _ForwardIter __next = __first; + _ForwardIterator __next = __first; for (++__next; __next != __last; __first = __next, ++__next) { if (__comp(*__next, *__first)) return false; @@ -530,7 +513,6 @@ namespace __gnu_cxx return true; } - } // namespace __gnu_cxx #endif /* _EXT_ALGORITHM */ |
