diff -r e1b950c65cb4 -r 837f303aceeb epoc32/include/stdapis/stlportv5/stl/_algo.c --- a/epoc32/include/stdapis/stlportv5/stl/_algo.c Wed Mar 31 12:27:01 2010 +0100 +++ b/epoc32/include/stdapis/stlportv5/stl/_algo.c Wed Mar 31 12:33:34 2010 +0100 @@ -9,13 +9,13 @@ * Copyright (c) 1997 * Moscow Center for SPARC Technology * - * Copyright (c) 1999 + * Copyright (c) 1999 * Boris Fomitchev * * This material is provided "as is", with absolutely no warranty expressed * or implied. Any use is at your own risk. * - * Permission to use or copy this software for any purpose is hereby granted + * Permission to use or copy this software for any purpose is hereby granted * without fee, provided the above notices are retained on all copies. * Permission to modify the code and to distribute modified code is granted, * provided the above notices are retained, and a notice that the code was @@ -24,14 +24,20 @@ */ #ifndef _STLP_ALGO_C -# define _STLP_ALGO_C +#define _STLP_ALGO_C -# if !defined (_STLP_INTERNAL_ALGO_H) +#if !defined (_STLP_INTERNAL_ALGO_H) # include <stl/_algo.h> -# endif +#endif + +#ifndef _STLP_INTERNAL_TEMPBUF_H +# include <stl/_tempbuf.h> +#endif _STLP_BEGIN_NAMESPACE +_STLP_MOVE_TO_PRIV_NAMESPACE + template <class _BidirectionalIter, class _Distance, class _Compare> void __merge_without_buffer(_BidirectionalIter __first, _BidirectionalIter __middle, @@ -50,9 +56,9 @@ _Compare __comp); template <class _Tp> -# if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 )) -inline -# endif +#if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 )) +inline +#endif const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { if (__a < __b) if (__b < __c) @@ -70,55 +76,62 @@ } template <class _Tp, class _Compare> -# if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 )) -inline -# endif +#if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 )) +inline +#endif const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { - if (__comp(__a, __b)) - if (__comp(__b, __c)) + if (__comp(__a, __b)) { + _STLP_VERBOSE_ASSERT(!__comp(__b, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) + if (__comp(__b, __c)) { + _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) return __b; - else if (__comp(__a, __c)) + } + else if (__comp(__a, __c)) { + _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) return __c; + } else return __a; - else if (__comp(__a, __c)) + } + else if (__comp(__a, __c)) { + _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) return __a; - else if (__comp(__b, __c)) + } + else if (__comp(__b, __c)) { + _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) return __c; + } else return __b; } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _ForwardIter1, class _ForwardIter2> _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, - _ForwardIter2 __first2, _ForwardIter2 __last2) -{ - _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) - _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) + _ForwardIter2 __first2, _ForwardIter2 __last2) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) // Test for empty ranges if (__first1 == __last1 || __first2 == __last2) return __first1; // Test for a pattern of length 1. - _ForwardIter2 __tmp(__first2); - ++__tmp; - if (__tmp == __last2) + _ForwardIter2 __p1(__first2); + + if ( ++__p1 == __last2 ) return find(__first1, __last1, *__first2); // General case. - _ForwardIter2 __p1 = __first2; - ++__p1; - _ForwardIter1 __current = __first1; - - while (__first1 != __last1) { + for ( ; ; ) { // __first1 != __last1 will be checked in find below __first1 = find(__first1, __last1, *__first2); if (__first1 == __last1) return __last1; _ForwardIter2 __p = __p1; - __current = __first1; + _ForwardIter1 __current = __first1; if (++__current == __last1) return __last1; @@ -134,97 +147,155 @@ return __first1; } +_STLP_MOVE_TO_PRIV_NAMESPACE + +template <class _RandomAccessIter, class _Integer, class _Tp, + class _BinaryPred, class _Distance> +_RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last, + _Integer __count, const _Tp& __val, _BinaryPred __pred, + _Distance*, const random_access_iterator_tag &) +{ + _Distance __tailSize = __last - __first; + const _Distance __pattSize = __count; + const _Distance __skipOffset = __pattSize - 1; + _RandomAccessIter __backTrack; + _Distance __remainder, __prevRemainder; + + for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) { // the main loop... + //__lookAhead here is always pointing to the last element of next possible match. + __tailSize -= __pattSize; + + while ( !__pred(*__lookAhead, __val) ) { // the skip loop... + if (__tailSize < __pattSize) + return __last; + + __lookAhead += __pattSize; + __tailSize -= __pattSize; + } + + if ( __skipOffset == 0 ) { + return (__lookAhead - __skipOffset); //Success + } + + __remainder = __skipOffset; + + for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) { + if (--__remainder == 0) + return (__lookAhead - __skipOffset); //Success + } + + if (__remainder > __tailSize) + return __last; //failure + + __lookAhead += __remainder; + __tailSize -= __remainder; + + while ( __pred(*__lookAhead, __val) ) { + __prevRemainder = __remainder; + __backTrack = __lookAhead; + + do { + if (--__remainder == 0) + return (__lookAhead - __skipOffset); //Success + } while (__pred(*--__backTrack, __val)); + + //adjust remainder for next comparison + __remainder += __pattSize - __prevRemainder; + + if (__remainder > __tailSize) + return __last; //failure + + __lookAhead += __remainder; + __tailSize -= __remainder; + } + + //__lookAhead here is always pointing to the element of the last mismatch. + } + + return __last; //failure +} + +template <class _ForwardIter, class _Integer, class _Tp, + class _Distance, class _BinaryPred> +_ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last, + _Integer __count, const _Tp& __val, _BinaryPred __pred, + _Distance*, const forward_iterator_tag &) { + for (; (__first != __last) && !__pred(*__first, __val); ++__first) {} + while (__first != __last) { + _Integer __n = __count - 1; + _ForwardIter __i = __first; + ++__i; + while (__i != __last && __n != 0 && __pred(*__i, __val)) { + ++__i; + --__n; + } + if (__n == 0) + return __first; + else if (__i != __last) + for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {} + else + break; + } + return __last; +} + +_STLP_MOVE_TO_STD_NAMESPACE + // search_n. Search for __count consecutive copies of __val. - template <class _ForwardIter, class _Integer, class _Tp> _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp& __val) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) if (__count <= 0) return __first; - else { - __first = find(__first, __last, __val); - while (__first != __last) { - _Integer __n = __count - 1; - _ForwardIter __i = __first; - ++__i; - while (__i != __last && __n != 0 && *__i == __val) { - ++__i; - --__n; - } - if (__n == 0) - return __first; - else - __first = find(__i, __last, __val); - } - return __last; - } + if (__count == 1) + //We use find when __count == 1 to use potential find overload. + return find(__first, __last, __val); + return _STLP_PRIV __search_n(__first, __last, __count, __val, equal_to<_Tp>(), + _STLP_DISTANCE_TYPE(__first, _ForwardIter), + _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); } template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred> _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp& __val, _BinaryPred __binary_pred) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) if (__count <= 0) return __first; - else { - while (__first != __last) { - if (__binary_pred(*__first, __val)) - break; - ++__first; - } - while (__first != __last) { - _Integer __n = __count - 1; - _ForwardIter __i = __first; - ++__i; - while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) { - ++__i; - --__n; - } - if (__n == 0) - return __first; - else { - while (__i != __last) { - if (__binary_pred(*__i, __val)) - break; - ++__i; - } - __first = __i; - } - } - return __last; - } -} + return _STLP_PRIV __search_n(__first, __last, __count, __val, __binary_pred, + _STLP_DISTANCE_TYPE(__first, _ForwardIter), + _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); +} template <class _ForwardIter1, class _ForwardIter2> -_ForwardIter1 -find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, - _ForwardIter2 __first2, _ForwardIter2 __last2) -{ - _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) - _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) - return __find_end(__first1, __last1, __first2, __last2, -# if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) - _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1), - _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2), -# else - forward_iterator_tag(), - forward_iterator_tag(), -# endif - __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1)) +_ForwardIter1 +find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, + _ForwardIter2 __first2, _ForwardIter2 __last2) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) + return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2, +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) + _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1), + _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2), +#else + forward_iterator_tag(), + forward_iterator_tag(), +#endif + _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1)) ); } // unique and unique_copy +_STLP_MOVE_TO_PRIV_NAMESPACE + template <class _InputIterator, class _OutputIterator, class _BinaryPredicate, - class _Tp> -_STLP_INLINE_LOOP _OutputIterator + class _Tp> +_STLP_INLINE_LOOP _OutputIterator __unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, _Tp*) { _Tp __val = *__first; - _STLP_PUSH_STACK_ITEM(_Tp, &__val) *__result = __val; while (++__first != __last) if (!__binary_pred(__val, *__first)) { @@ -235,15 +306,15 @@ } template <class _InputIter, class _OutputIter, class _BinaryPredicate> -inline _OutputIter +inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result, _BinaryPredicate __binary_pred, const output_iterator_tag &) { return __unique_copy(__first, __last, __result, __binary_pred, _STLP_VALUE_TYPE(__first, _InputIter)); } template <class _InputIter, class _ForwardIter, class _BinaryPredicate> -_STLP_INLINE_LOOP _ForwardIter -__unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, +_STLP_INLINE_LOOP _ForwardIter +__unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, _BinaryPredicate __binary_pred, const forward_iterator_tag &) { *__result = *__first; while (++__first != __last) @@ -251,9 +322,9 @@ return ++__result; } -# if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) +#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate> -inline _BidirectionalIterator +inline _BidirectionalIterator __unique_copy(_InputIterator __first, _InputIterator __last, _BidirectionalIterator __result, _BinaryPredicate __binary_pred, const bidirectional_iterator_tag &) { @@ -261,354 +332,38 @@ } template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate> -inline _RandomAccessIterator +inline _RandomAccessIterator __unique_copy(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __result, _BinaryPredicate __binary_pred, const random_access_iterator_tag &) { return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag()); } -# endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */ +#endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */ +_STLP_MOVE_TO_STD_NAMESPACE template <class _InputIter, class _OutputIter> -_OutputIter +_OutputIter unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) if (__first == __last) return __result; - return __unique_copy(__first, __last, __result, __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)), - _STLP_ITERATOR_CATEGORY(__result, _OutputIter)); + return _STLP_PRIV __unique_copy(__first, __last, __result, + _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)), + _STLP_ITERATOR_CATEGORY(__result, _OutputIter)); } template <class _InputIter, class _OutputIter, class _BinaryPredicate> -_OutputIter +_OutputIter unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result, _BinaryPredicate __binary_pred) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) if (__first == __last) return __result; - return __unique_copy(__first, __last, __result, __binary_pred, - _STLP_ITERATOR_CATEGORY(__result, _OutputIter)); + return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, + _STLP_ITERATOR_CATEGORY(__result, _OutputIter)); } // rotate and rotate_copy, and their auxiliary functions - -template <class _ForwardIter, class _Distance> -_ForwardIter __rotate(_ForwardIter __first, - _ForwardIter __middle, - _ForwardIter __last, - _Distance*, - const forward_iterator_tag &) { - if (__first == __middle) - return __last; - if (__last == __middle) - return __first; - - _ForwardIter __first2 = __middle; - do { - swap(*__first++, *__first2++); - if (__first == __middle) - __middle = __first2; - } while (__first2 != __last); - - _ForwardIter __new_middle = __first; - - __first2 = __middle; - - while (__first2 != __last) { - swap (*__first++, *__first2++); - if (__first == __middle) - __middle = __first2; - else if (__first2 == __last) - __first2 = __middle; - } - - return __new_middle; -} - -template <class _BidirectionalIter, class _Distance> -_BidirectionalIter __rotate(_BidirectionalIter __first, - _BidirectionalIter __middle, - _BidirectionalIter __last, - _Distance*, - const bidirectional_iterator_tag &) { - if (__first == __middle) - return __last; - if (__last == __middle) - return __first; - - __reverse(__first, __middle, bidirectional_iterator_tag()); - __reverse(__middle, __last, bidirectional_iterator_tag()); - - while (__first != __middle && __middle != __last) - swap (*__first++, *--__last); - - if (__first == __middle) { - __reverse(__middle, __last, bidirectional_iterator_tag()); - return __last; - } - else { - __reverse(__first, __middle, bidirectional_iterator_tag()); - return __first; - } -} - -template <class _RandomAccessIter, class _Distance, class _Tp> -_RandomAccessIter __rotate(_RandomAccessIter __first, - _RandomAccessIter __middle, - _RandomAccessIter __last, - _Distance *, _Tp *) { - - _Distance __n = __last - __first; - _Distance __k = __middle - __first; - _Distance __l = __n - __k; - _RandomAccessIter __result = __first + (__last - __middle); - - if (__k==0) /* __first == middle */ - return __last; - - if (__k == __l) { - swap_ranges(__first, __middle, __middle); - return __result; - } - - _Distance __d = __gcd(__n, __k); - - for (_Distance __i = 0; __i < __d; __i++) { - _Tp __tmp = *__first; - _STLP_PUSH_STACK_ITEM(_Tp, &__tmp) - _RandomAccessIter __p = __first; - - if (__k < __l) { - for (_Distance __j = 0; __j < __l/__d; __j++) { - if (__p > __first + __l) { - *__p = *(__p - __l); - __p -= __l; - } - - *__p = *(__p + __k); - __p += __k; - } - } - - else { - for (_Distance __j = 0; __j < __k/__d - 1; __j ++) { - if (__p < __last - __k) { - *__p = *(__p + __k); - __p += __k; - } - - *__p = * (__p - __l); - __p -= __l; - } - } - - *__p = __tmp; - ++__first; - } - - return __result; -} - -template <class _RandomAccessIter, class _Distance> -inline _RandomAccessIter -__rotate(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, - _Distance * __dis, const random_access_iterator_tag &) { - return __rotate(__first, __middle, __last, - __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter)); -} - -template <class _ForwardIter> -_ForwardIter -rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) { - _STLP_DEBUG_CHECK(__check_range(__first, __middle)) - _STLP_DEBUG_CHECK(__check_range(__middle, __last)) - return __rotate(__first, __middle, __last, - _STLP_DISTANCE_TYPE(__first, _ForwardIter), - _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); -} - -// Return a random number in the range [0, __n). This function encapsulates -// whether we're using rand (part of the standard C library) or lrand48 -// (not standard, but a much better choice whenever it's available). - -template <class _Distance> -inline _Distance __random_number(_Distance __n) { -#ifdef _STLP_NO_DRAND48 - return rand() % __n; -#else - return lrand48() % __n; -#endif -} - -template <class _RandomAccessIter> -void random_shuffle(_RandomAccessIter __first, - _RandomAccessIter __last) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - if (__first == __last) return; - for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) - iter_swap(__i, __first + __random_number((__i - __first) + 1)); -} - -template <class _RandomAccessIter, class _RandomNumberGenerator> -void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, - _RandomNumberGenerator& __rand) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - if (__first == __last) return; - for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) - iter_swap(__i, __first + __rand((__i - __first) + 1)); -} - -# ifndef _STLP_NO_EXTENSIONS - -// random_sample and random_sample_n (extensions, not part of the standard). - -template <class _ForwardIter, class _OutputIter, class _Distance> -_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, - _OutputIter __stl_out, const _Distance __n) -{ - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - _Distance __remaining = distance(__first, __last); - _Distance __m = (min) (__n, __remaining); - - while (__m > 0) { - if (__random_number(__remaining) < __m) { - *__stl_out = *__first; - ++__stl_out; - --__m; - } - - --__remaining; - ++__first; - } - return __stl_out; -} - - -template <class _ForwardIter, class _OutputIter, class _Distance, - class _RandomNumberGenerator> -_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, - _OutputIter __stl_out, const _Distance __n, - _RandomNumberGenerator& __rand) -{ - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - _Distance __remaining = distance(__first, __last); - _Distance __m = (min) (__n, __remaining); - - while (__m > 0) { - if (__rand(__remaining) < __m) { - *__stl_out = *__first; - ++__stl_out; - --__m; - } - - --__remaining; - ++__first; - } - return __stl_out; -} - -template <class _InputIter, class _RandomAccessIter, class _Distance> -_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, - _RandomAccessIter __stl_out, - const _Distance __n) -{ - _Distance __m = 0; - _Distance __t = __n; - for ( ; __first != __last && __m < __n; ++__m, ++__first) - __stl_out[__m] = *__first; - - while (__first != __last) { - ++__t; - _Distance __M = __random_number(__t); - if (__M < __n) - __stl_out[__M] = *__first; - ++__first; - } - - return __stl_out + __m; -} - -template <class _InputIter, class _RandomAccessIter, - class _RandomNumberGenerator, class _Distance> -_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, - _RandomAccessIter __stl_out, - _RandomNumberGenerator& __rand, - const _Distance __n) -{ - _Distance __m = 0; - _Distance __t = __n; - for ( ; __first != __last && __m < __n; ++__m, ++__first) - __stl_out[__m] = *__first; - - while (__first != __last) { - ++__t; - _Distance __M = __rand(__t); - if (__M < __n) - __stl_out[__M] = *__first; - ++__first; - } - - return __stl_out + __m; -} - -template <class _InputIter, class _RandomAccessIter> -_RandomAccessIter -random_sample(_InputIter __first, _InputIter __last, - _RandomAccessIter __out_first, _RandomAccessIter __out_last) -{ - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last)) - return __random_sample(__first, __last, - __out_first, __out_last - __out_first); -} - -template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator> -_RandomAccessIter -random_sample(_InputIter __first, _InputIter __last, - _RandomAccessIter __out_first, _RandomAccessIter __out_last, - _RandomNumberGenerator& __rand) -{ - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last)) - return __random_sample(__first, __last, - __out_first, __rand, - __out_last - __out_first); -} - -# endif /* _STLP_NO_EXTENSIONS */ - -// partition, stable_partition, and their auxiliary functions - -template <class _ForwardIter, class _Predicate> -_STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first, - _ForwardIter __last, - _Predicate __pred, - const forward_iterator_tag &) { - if (__first == __last) return __first; - - while (__pred(*__first)) - if (++__first == __last) return __first; - - _ForwardIter __next = __first; - - while (++__next != __last) - if (__pred(*__next)) { - swap(*__first, *__next); - ++__first; - } - return __first; -} - -/* bug fix- start*/ - -template <class _ForwardIter> -_ForwardIter -__rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) { - _STLP_DEBUG_CHECK(__check_range(__first, __middle)) - _STLP_DEBUG_CHECK(__check_range(__middle, __last)) - return __rotate_aux(__first, __middle, __last, - _STLP_DISTANCE_TYPE(__first, _ForwardIter), - _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); -} +_STLP_MOVE_TO_PRIV_NAMESPACE template <class _ForwardIter, class _Distance> _ForwardIter __rotate_aux(_ForwardIter __first, @@ -643,6 +398,356 @@ return __new_middle; } +template <class _BidirectionalIter, class _Distance> +_BidirectionalIter __rotate_aux(_BidirectionalIter __first, + _BidirectionalIter __middle, + _BidirectionalIter __last, + _Distance*, + const bidirectional_iterator_tag &) { + if (__first == __middle) + return __last; + if (__last == __middle) + return __first; + + __reverse(__first, __middle, bidirectional_iterator_tag()); + __reverse(__middle, __last, bidirectional_iterator_tag()); + + while (__first != __middle && __middle != __last) + swap (*__first++, *--__last); + + if (__first == __middle) { + __reverse(__middle, __last, bidirectional_iterator_tag()); + return __last; + } + else { + __reverse(__first, __middle, bidirectional_iterator_tag()); + return __first; + } +} + +template <class _RandomAccessIter, class _Distance, class _Tp> +_RandomAccessIter __rotate_aux(_RandomAccessIter __first, + _RandomAccessIter __middle, + _RandomAccessIter __last, + _Distance *, _Tp *) { + + _Distance __n = __last - __first; + _Distance __k = __middle - __first; + _Distance __l = __n - __k; + _RandomAccessIter __result = __first + (__last - __middle); + + if (__k == 0) /* __first == middle */ + return __last; + + if (__k == __l) { + swap_ranges(__first, __middle, __middle); + return __result; + } + + _Distance __d = __gcd(__n, __k); + + for (_Distance __i = 0; __i < __d; __i++) { + _Tp __tmp = *__first; + _RandomAccessIter __p = __first; + + if (__k < __l) { + for (_Distance __j = 0; __j < __l/__d; __j++) { + if (__p > __first + __l) { + *__p = *(__p - __l); + __p -= __l; + } + + *__p = *(__p + __k); + __p += __k; + } + } + + else { + for (_Distance __j = 0; __j < __k/__d - 1; __j ++) { + if (__p < __last - __k) { + *__p = *(__p + __k); + __p += __k; + } + + *__p = * (__p - __l); + __p -= __l; + } + } + + *__p = __tmp; + ++__first; + } + + return __result; +} + +template <class _RandomAccessIter, class _Distance> +inline _RandomAccessIter +__rotate_aux(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, + _Distance * __dis, const random_access_iterator_tag &) { + return __rotate_aux(__first, __middle, __last, + __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter)); +} + +template <class _ForwardIter> +_ForwardIter +__rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) { + _STLP_DEBUG_CHECK(__check_range(__first, __middle)) + _STLP_DEBUG_CHECK(__check_range(__middle, __last)) + return __rotate_aux(__first, __middle, __last, + _STLP_DISTANCE_TYPE(__first, _ForwardIter), + _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); +} + +_STLP_MOVE_TO_STD_NAMESPACE + +template <class _ForwardIter> +void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) { + _STLP_PRIV __rotate(__first, __middle, __last); +} + +// Return a random number in the range [0, __n). This function encapsulates +// whether we're using rand (part of the standard C library) or lrand48 +// (not standard, but a much better choice whenever it's available). +_STLP_MOVE_TO_PRIV_NAMESPACE + +template <class _Distance> +inline _Distance __random_number(_Distance __n) { +#ifdef _STLP_NO_DRAND48 + return rand() % __n; +#else + return lrand48() % __n; +#endif +} + +_STLP_MOVE_TO_STD_NAMESPACE + +template <class _RandomAccessIter> +void random_shuffle(_RandomAccessIter __first, + _RandomAccessIter __last) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + if (__first == __last) return; + for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) + iter_swap(__i, __first + _STLP_PRIV __random_number((__i - __first) + 1)); +} + +template <class _RandomAccessIter, class _RandomNumberGenerator> +void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, + _RandomNumberGenerator &__rand) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + if (__first == __last) return; + for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) + iter_swap(__i, __first + __rand((__i - __first) + 1)); +} + +#if !defined (_STLP_NO_EXTENSIONS) +// random_sample and random_sample_n (extensions, not part of the standard). +template <class _ForwardIter, class _OutputIter, class _Distance> +_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, + _OutputIter __out_ite, const _Distance __n) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + _Distance __remaining = distance(__first, __last); + _Distance __m = (min) (__n, __remaining); + + while (__m > 0) { + if (_STLP_PRIV __random_number(__remaining) < __m) { + *__out_ite = *__first; + ++__out_ite; + --__m; + } + + --__remaining; + ++__first; + } + return __out_ite; +} + + +template <class _ForwardIter, class _OutputIter, class _Distance, + class _RandomNumberGenerator> +_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, + _OutputIter __out_ite, const _Distance __n, + _RandomNumberGenerator& __rand) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + _Distance __remaining = distance(__first, __last); + _Distance __m = (min) (__n, __remaining); + + while (__m > 0) { + if (__rand(__remaining) < __m) { + *__out_ite = *__first; + ++__out_ite; + --__m; + } + + --__remaining; + ++__first; + } + return __out_ite; +} + +_STLP_MOVE_TO_PRIV_NAMESPACE + +template <class _InputIter, class _RandomAccessIter, class _Distance> +_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, + _RandomAccessIter __out_ite, + const _Distance __n) { + _Distance __m = 0; + _Distance __t = __n; + for ( ; __first != __last && __m < __n; ++__m, ++__first) + __out_ite[__m] = *__first; + + while (__first != __last) { + ++__t; + _Distance __M = __random_number(__t); + if (__M < __n) + __out_ite[__M] = *__first; + ++__first; + } + + return __out_ite + __m; +} + +template <class _InputIter, class _RandomAccessIter, + class _RandomNumberGenerator, class _Distance> +_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, + _RandomAccessIter __out_ite, + _RandomNumberGenerator& __rand, + const _Distance __n) { + _Distance __m = 0; + _Distance __t = __n; + for ( ; __first != __last && __m < __n; ++__m, ++__first) + __out_ite[__m] = *__first; + + while (__first != __last) { + ++__t; + _Distance __M = __rand(__t); + if (__M < __n) + __out_ite[__M] = *__first; + ++__first; + } + + return __out_ite + __m; +} + +_STLP_MOVE_TO_STD_NAMESPACE + +template <class _InputIter, class _RandomAccessIter> +_RandomAccessIter +random_sample(_InputIter __first, _InputIter __last, + _RandomAccessIter __out_first, _RandomAccessIter __out_last) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last)) + return _STLP_PRIV __random_sample(__first, __last, + __out_first, __out_last - __out_first); +} + +template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator> +_RandomAccessIter +random_sample(_InputIter __first, _InputIter __last, + _RandomAccessIter __out_first, _RandomAccessIter __out_last, + _RandomNumberGenerator& __rand) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last)) + return _STLP_PRIV __random_sample(__first, __last, + __out_first, __rand, + __out_last - __out_first); +} + +#endif /* _STLP_NO_EXTENSIONS */ + +// partition, stable_partition, and their auxiliary functions +_STLP_MOVE_TO_PRIV_NAMESPACE + +template <class _ForwardIter, class _Predicate> +_STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first, + _ForwardIter __last, + _Predicate __pred, + const forward_iterator_tag &) { + if (__first == __last) return __first; + + while (__pred(*__first)) + if (++__first == __last) return __first; + + _ForwardIter __next = __first; + + while (++__next != __last) { + if (__pred(*__next)) { + swap(*__first, *__next); + ++__first; + } + } + return __first; +} + +template <class _BidirectionalIter, class _Predicate> +_STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first, + _BidirectionalIter __last, + _Predicate __pred, + const bidirectional_iterator_tag &) { + for (;;) { + for (;;) { + if (__first == __last) + return __first; + else if (__pred(*__first)) + ++__first; + else + break; + } + --__last; + for (;;) { + if (__first == __last) + return __first; + else if (!__pred(*__last)) + --__last; + else + break; + } + iter_swap(__first, __last); + ++__first; + } +} + +#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) +template <class _BidirectionalIter, class _Predicate> +inline +_BidirectionalIter __partition(_BidirectionalIter __first, + _BidirectionalIter __last, + _Predicate __pred, + const random_access_iterator_tag &) { + return __partition(__first, __last, __pred, bidirectional_iterator_tag()); +} +#endif + +_STLP_MOVE_TO_STD_NAMESPACE + +template <class _ForwardIter, class _Predicate> +_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + return _STLP_PRIV __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); +} + + +/* __pred_of_first: false if we know that __pred(*__first) is false, + * true when we don't know the result of __pred(*__first). + * __not_pred_of_before_last: true if we know that __pred(*--__last) is true, + * false when we don't know the result of __pred(*--__last). + */ +_STLP_MOVE_TO_PRIV_NAMESPACE + +template <class _ForwardIter, class _Predicate, class _Distance> +_ForwardIter __inplace_stable_partition(_ForwardIter __first, + _ForwardIter __last, + _Predicate __pred, _Distance __len, + bool __pred_of_first, bool __pred_of_before_last) { + if (__len == 1) + return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first; + _ForwardIter __middle = __first; + _Distance __half_len = __len / 2; + advance(__middle, __half_len); + return __rotate(__inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false), + __middle, + __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last)); +} template <class _ForwardIter, class _Pointer, class _Predicate, class _Distance> @@ -688,23 +793,61 @@ } } - -template <class _ForwardIter, class _Predicate, class _Distance> -_ForwardIter __inplace_stable_partition(_ForwardIter __first, - _ForwardIter __last, - _Predicate __pred, _Distance __len, - bool __pred_of_first, bool __pred_of_before_last) { - if (__len == 1) - return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first; - _ForwardIter __middle = __first; - _Distance __half_len = __len / 2; - advance(__middle, __half_len); - return __rotate(__inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false), - __middle, - __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last)); +template <class _ForwardIter, class _Predicate, class _Tp, class _Distance> +inline _ForwardIter +__stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last, + _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last = false) { + _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last); + _STLP_MPWFIX_TRY //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present + return (__buf.size() > 0) ? + __stable_partition_adaptive(__first, __last, __pred, + _Distance(__buf.requested_size()), + __buf.begin(), __buf.size(), + false, __pred_of_before_last) : + __inplace_stable_partition(__first, __last, __pred, + _Distance(__buf.requested_size()), + false, __pred_of_before_last); + _STLP_MPWFIX_CATCH //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present } +template <class _ForwardIter, class _Predicate> +_ForwardIter +__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, + const forward_iterator_tag &) { + return __stable_partition_aux_aux(__first, __last, __pred, + _STLP_VALUE_TYPE(__first, _ForwardIter), + _STLP_DISTANCE_TYPE(__first, _ForwardIter)); +} +template <class _BidirectIter, class _Predicate> +_BidirectIter +__stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred, + const bidirectional_iterator_tag &) { + for (--__last;;) { + if (__first == __last) + return __first; + else if (!__pred(*__last)) + --__last; + else + break; + } + ++__last; + //Here we know that __pred(*--__last) is true + return __stable_partition_aux_aux(__first, __last, __pred, + _STLP_VALUE_TYPE(__first, _BidirectIter), + _STLP_DISTANCE_TYPE(__first, _BidirectIter), true); +} + +#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) +template <class _BidirectIter, class _Predicate> +_BidirectIter +__stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred, + const random_access_iterator_tag &) { + return __stable_partition_aux(__first, __last, __pred, bidirectional_iterator_tag()); +} +#endif + +_STLP_MOVE_TO_STD_NAMESPACE template <class _ForwardIter, class _Predicate> _ForwardIter @@ -718,180 +861,26 @@ else break; } - return __stable_partition_aux(__first, __last, __pred, + return _STLP_PRIV __stable_partition_aux(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); } +_STLP_MOVE_TO_PRIV_NAMESPACE -template <class _ForwardIter, class _Predicate, class _Tp, class _Distance> -inline _ForwardIter -__stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last, - _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last = false) { - _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last); - return (__buf.size() > 0) ? - __stable_partition_adaptive(__first, __last, __pred, - _Distance(__buf.requested_size()), - __buf.begin(), __buf.size(), - false, __pred_of_before_last) : - __inplace_stable_partition(__first, __last, __pred, - _Distance(__buf.requested_size()), - false, __pred_of_before_last); - -} - -template <class _ForwardIter, class _Predicate> -_ForwardIter -__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, - const forward_iterator_tag &) { - return __stable_partition_aux_aux(__first, __last, __pred, - _STLP_VALUE_TYPE(__first, _ForwardIter), - _STLP_DISTANCE_TYPE(__first, _ForwardIter)); -} - - -/* bug fix- end*/ - - - -template <class _BidirectionalIter, class _Predicate> -_STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first, - _BidirectionalIter __last, - _Predicate __pred, - const bidirectional_iterator_tag &) { - while (true) { - while (true) - if (__first == __last) - return __first; - else if (__pred(*__first)) - ++__first; - else - break; +template <class _RandomAccessIter, class _Tp, class _Compare> +_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, + _RandomAccessIter __last, + _Tp __pivot, _Compare __comp) { + for (;;) { + while (__comp(*__first, __pivot)) { + _STLP_VERBOSE_ASSERT(!__comp(__pivot, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) + ++__first; + } --__last; - while (true) - if (__first == __last) - return __first; - else if (!__pred(*__last)) - --__last; - else - break; - iter_swap(__first, __last); - ++__first; - } -} - -# if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) -template <class _BidirectionalIter, class _Predicate> -inline -_BidirectionalIter __partition(_BidirectionalIter __first, - _BidirectionalIter __last, - _Predicate __pred, - const random_access_iterator_tag &) { - return __partition(__first, __last, __pred, bidirectional_iterator_tag()); -} -# endif - -template <class _ForwardIter, class _Predicate> -_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - return __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); -} - -/* -template <class _ForwardIter, class _Predicate, class _Distance> -_ForwardIter __inplace_stable_partition(_ForwardIter __first, - _ForwardIter __last, - _Predicate __pred, _Distance __len) { - if (__len == 1) - return __pred(*__first) ? __last : __first; - _ForwardIter __middle = __first; - advance(__middle, __len / 2); - return rotate(__inplace_stable_partition(__first, __middle, __pred, - __len / 2), - __middle, - __inplace_stable_partition(__middle, __last, __pred, - __len - __len / 2)); -} - - -template <class _ForwardIter, class _Pointer, class _Predicate, - class _Distance> -_ForwardIter __stable_partition_adaptive(_ForwardIter __first, - _ForwardIter __last, - _Predicate __pred, _Distance __len, - _Pointer __buffer, - _Distance __buffer_size) -{ - if (__len <= __buffer_size) { - _ForwardIter __result1 = __first; - _Pointer __result2 = __buffer; - for ( ; __first != __last ; ++__first) - if (__pred(*__first)) { - *__result1 = *__first; - ++__result1; - } - else { - *__result2 = *__first; - ++__result2; - } - copy(__buffer, __result2, __result1); - return __result1; - } - else { - _ForwardIter __middle = __first; - advance(__middle, __len / 2); - return rotate(__stable_partition_adaptive( - __first, __middle, __pred, - _Distance(__len / 2), __buffer, __buffer_size), - __middle, - __stable_partition_adaptive( - __middle, __last, __pred, - _Distance(__len - __len / 2), __buffer, __buffer_size)); - } -} -*/ //bug fix -template <class _ForwardIter, class _Predicate, class _Tp, class _Distance> -inline _ForwardIter -__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, - _Predicate __pred, _Tp*, _Distance*) -{ - typedef _Temporary_buffer<_ForwardIter, _Tp> _TmpBuf; - _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last); - _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf); - - _STLP_MPWFIX_TRY //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present - return (__buf.size() > 0) ? - __stable_partition_adaptive(__first, __last, __pred, - _Distance(__buf.requested_size()), - __buf.begin(), _Distance(__buf.size())) : - __inplace_stable_partition(__first, __last, __pred, - _Distance(__buf.requested_size())); - _STLP_MPWFIX_CATCH //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present -} -/* -template <class _ForwardIter, class _Predicate> -_ForwardIter -stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - if (__first == __last) - return __first; - else - return __stable_partition_aux(__first, __last, __pred, - _STLP_VALUE_TYPE(__first, _ForwardIter), - _STLP_DISTANCE_TYPE(__first, _ForwardIter)); -} -*/ //bug fix -template <class _RandomAccessIter, class _Tp, class _Compare> -_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, - _RandomAccessIter __last, - _Tp __pivot, _Compare __comp) -{ - _STLP_PUSH_STACK_ITEM(_Tp, &__pivot) - while (true) { - while (__comp(*__first, __pivot)) - ++__first; - --__last; - while (__comp(__pivot, *__last)) + while (__comp(__pivot, *__last)) { + _STLP_VERBOSE_ASSERT(!__comp(*__last, __pivot), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) --__last; + } if (!(__first < __last)) return __first; iter_swap(__first, __last); @@ -899,17 +888,16 @@ } } -// sort() and its auxiliary functions. - -# define __stl_threshold 16 +// sort() and its auxiliary functions. +#define __stl_threshold 16 template <class _RandomAccessIter, class _Tp, class _Compare> -void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, +void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, _Compare __comp) { - _STLP_PUSH_STACK_ITEM(_Tp, &__val) _RandomAccessIter __next = __last; - --__next; + --__next; while (__comp(__val, *__next)) { + _STLP_VERBOSE_ASSERT(!__comp(*__next, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) *__last = *__next; __last = __next; --__next; @@ -918,10 +906,12 @@ } template <class _RandomAccessIter, class _Tp, class _Compare> -inline void __linear_insert(_RandomAccessIter __first, +inline void __linear_insert(_RandomAccessIter __first, _RandomAccessIter __last, _Tp __val, _Compare __comp) { - _STLP_PUSH_STACK_ITEM(_Tp, &__val) + //*TY 12/26/1998 - added __val as a paramter + // _Tp __val = *__last; //*TY 12/26/1998 - __val supplied by caller if (__comp(__val, *__first)) { + _STLP_VERBOSE_ASSERT(!__comp(*__first, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) copy_backward(__first, __last, __last + 1); *__first = __val; } @@ -929,45 +919,45 @@ __unguarded_linear_insert(__last, __val, __comp); } -template <class _RandomAccessIter, class _Compare> +template <class _RandomAccessIter, class _Tp, class _Compare> void __insertion_sort(_RandomAccessIter __first, - _RandomAccessIter __last, _Compare __comp) { + _RandomAccessIter __last, + _Tp *, _Compare __comp) { if (__first == __last) return; for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) - __linear_insert(__first, __i, *__i, __comp); //*TY 12/26/1998 - supply *__i as __val + __linear_insert<_RandomAccessIter, _Tp, _Compare>(__first, __i, *__i, __comp); //*TY 12/26/1998 - supply *__i as __val } template <class _RandomAccessIter, class _Tp, class _Compare> -void __unguarded_insertion_sort_aux(_RandomAccessIter __first, +void __unguarded_insertion_sort_aux(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, _Compare __comp) { for (_RandomAccessIter __i = __first; __i != __last; ++__i) - __unguarded_linear_insert(__i, _Tp(*__i), __comp); + __unguarded_linear_insert<_RandomAccessIter, _Tp, _Compare>(__i, *__i, __comp); } template <class _RandomAccessIter, class _Compare> -inline void __unguarded_insertion_sort(_RandomAccessIter __first, +inline void __unguarded_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp); } template <class _RandomAccessIter, class _Compare> -void __final_insertion_sort(_RandomAccessIter __first, +void __final_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { if (__last - __first > __stl_threshold) { - __insertion_sort(__first, __first + __stl_threshold, __comp); + __insertion_sort(__first, __first + __stl_threshold, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp); } else - __insertion_sort(__first, __last, __comp); + __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); } template <class _RandomAccessIter, class _Tp, class _Size, class _Compare> void __introsort_loop(_RandomAccessIter __first, _RandomAccessIter __last, _Tp*, - _Size __depth_limit, _Compare __comp) -{ + _Size __depth_limit, _Compare __comp) { while (__last - __first > __stl_threshold) { if (__depth_limit == 0) { partial_sort(__first, __last, __last, __comp); @@ -985,36 +975,40 @@ } } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _RandomAccessIter> void sort(_RandomAccessIter __first, _RandomAccessIter __last) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) if (__first != __last) { - __introsort_loop(__first, __last, - _STLP_VALUE_TYPE(__first, _RandomAccessIter), - __lg(__last - __first) * 2, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)) ); - __final_insertion_sort(__first, __last, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); + _STLP_PRIV __introsort_loop(__first, __last, + _STLP_VALUE_TYPE(__first, _RandomAccessIter), + _STLP_PRIV __lg(__last - __first) * 2, + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); + _STLP_PRIV __final_insertion_sort(__first, __last, + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); } } template <class _RandomAccessIter, class _Compare> void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) if (__first != __last) { - __introsort_loop(__first, __last, - _STLP_VALUE_TYPE(__first, _RandomAccessIter), - __lg(__last - __first) * 2, - __comp); - __final_insertion_sort(__first, __last, __comp); + _STLP_PRIV __introsort_loop(__first, __last, + _STLP_VALUE_TYPE(__first, _RandomAccessIter), + _STLP_PRIV __lg(__last - __first) * 2, __comp); + _STLP_PRIV __final_insertion_sort(__first, __last, __comp); } } // stable_sort() and its auxiliary functions. +_STLP_MOVE_TO_PRIV_NAMESPACE template <class _RandomAccessIter, class _Compare> void __inplace_stable_sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { if (__last - __first < 15) { - __insertion_sort(__first, __last, __comp); + __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); return; } _RandomAccessIter __middle = __first + (__last - __first) / 2; @@ -1029,7 +1023,7 @@ template <class _RandomAccessIter1, class _RandomAccessIter2, class _Distance, class _Compare> void __merge_sort_loop(_RandomAccessIter1 __first, - _RandomAccessIter1 __last, + _RandomAccessIter1 __last, _RandomAccessIter2 __result, _Distance __step_size, _Compare __comp) { _Distance __two_step = 2 * __step_size; @@ -1050,22 +1044,22 @@ } const int __stl_chunk_size = 7; - + template <class _RandomAccessIter, class _Distance, class _Compare> -void __chunk_insertion_sort(_RandomAccessIter __first, +void __chunk_insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last, - _Distance __chunk_size, _Compare __comp) -{ + _Distance __chunk_size, _Compare __comp) { while (__last - __first >= __chunk_size) { - __insertion_sort(__first, __first + __chunk_size, __comp); + __insertion_sort(__first, __first + __chunk_size, + _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); __first += __chunk_size; } - __insertion_sort(__first, __last, __comp); + __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); } template <class _RandomAccessIter, class _Pointer, class _Distance, class _Compare> -void __merge_sort_with_buffer(_RandomAccessIter __first, +void __merge_sort_with_buffer(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, _Distance*, _Compare __comp) { _Distance __len = __last - __first; @@ -1101,13 +1095,13 @@ return copy_backward(__buffer, __buffer_end, __last); } else - return rotate(__first, __middle, __last); + return __rotate(__first, __middle, __last); } template <class _BidirectionalIter, class _Distance, class _Pointer, class _Compare> -void __merge_adaptive(_BidirectionalIter __first, - _BidirectionalIter __middle, +void __merge_adaptive(_BidirectionalIter __first, + _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, @@ -1130,7 +1124,7 @@ __len11 = __len1 / 2; advance(__first_cut, __len11); __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); - __len22 += distance(__middle, __second_cut); + __len22 += distance(__middle, __second_cut); } else { __len22 = __len2 / 2; @@ -1148,17 +1142,17 @@ } } -template <class _RandomAccessIter, class _Pointer, class _Distance, +template <class _RandomAccessIter, class _Pointer, class _Distance, class _Compare> -void __stable_sort_adaptive(_RandomAccessIter __first, +void __stable_sort_adaptive(_RandomAccessIter __first, _RandomAccessIter __last, _Pointer __buffer, _Distance __buffer_size, _Compare __comp) { _Distance __len = (__last - __first + 1) / 2; _RandomAccessIter __middle = __first + __len; if (__len > __buffer_size) { - __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, + __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, __comp); - __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, + __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, __comp); } else { @@ -1167,86 +1161,91 @@ __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0, __comp); } - __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), + __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), _Distance(__last - __middle), __buffer, __buffer_size, __comp); } template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare> void __stable_sort_aux(_RandomAccessIter __first, - _RandomAccessIter __last, _Tp*, _Distance*, - _Compare __comp) { - - typedef _Temporary_buffer<_RandomAccessIter, _Tp> _TmpBuf; - _TmpBuf __buf(__first, __last); - _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf); - - if (__buf.begin() == 0) + _RandomAccessIter __last, _Tp*, _Distance*, + _Compare __comp) { + _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last); + if (buf.begin() == 0) __inplace_stable_sort(__first, __last, __comp); - else - __stable_sort_adaptive(__first, __last, __buf.begin(), - _Distance(__buf.size()), + else + __stable_sort_adaptive(__first, __last, buf.begin(), + _Distance(buf.size()), __comp); } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _RandomAccessIter> void stable_sort(_RandomAccessIter __first, - _RandomAccessIter __last) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - __stable_sort_aux(__first, __last, - _STLP_VALUE_TYPE(__first, _RandomAccessIter), - _STLP_DISTANCE_TYPE(__first, _RandomAccessIter), - __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); + _RandomAccessIter __last) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + _STLP_PRIV __stable_sort_aux(__first, __last, + _STLP_VALUE_TYPE(__first, _RandomAccessIter), + _STLP_DISTANCE_TYPE(__first, _RandomAccessIter), + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); } template <class _RandomAccessIter, class _Compare> void stable_sort(_RandomAccessIter __first, - _RandomAccessIter __last, _Compare __comp) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - __stable_sort_aux(__first, __last, - _STLP_VALUE_TYPE(__first, _RandomAccessIter), - _STLP_DISTANCE_TYPE(__first, _RandomAccessIter), - __comp); + _RandomAccessIter __last, _Compare __comp) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + _STLP_PRIV __stable_sort_aux(__first, __last, + _STLP_VALUE_TYPE(__first, _RandomAccessIter), + _STLP_DISTANCE_TYPE(__first, _RandomAccessIter), + __comp); } // partial_sort, partial_sort_copy, and auxiliary functions. +_STLP_MOVE_TO_PRIV_NAMESPACE template <class _RandomAccessIter, class _Tp, class _Compare> void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, _Tp*, _Compare __comp) { make_heap(__first, __middle, __comp); - for (_RandomAccessIter __i = __middle; __i < __last; ++__i) - if (__comp(*__i, *__first)) + for (_RandomAccessIter __i = __middle; __i < __last; ++__i) { + if (__comp(*__i, *__first)) { + _STLP_VERBOSE_ASSERT(!__comp(*__first, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) __pop_heap(__first, __middle, __i, _Tp(*__i), __comp, _STLP_DISTANCE_TYPE(__first, _RandomAccessIter)); + } + } sort_heap(__first, __middle, __comp); } +_STLP_MOVE_TO_STD_NAMESPACE template <class _RandomAccessIter> -void -partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, _RandomAccessIter __last) { - _STLP_DEBUG_CHECK(__check_range(__first, __middle)) - _STLP_DEBUG_CHECK(__check_range(__middle, __last)) - __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), - __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); +void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, + _RandomAccessIter __last) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last)) + _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); } template <class _RandomAccessIter, class _Compare> void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, _RandomAccessIter __last, _Compare __comp) { - _STLP_DEBUG_CHECK(__check_range(__first, __middle)) - _STLP_DEBUG_CHECK(__check_range(__middle, __last)) - __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp); + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last)) + _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp); } +_STLP_MOVE_TO_PRIV_NAMESPACE + template <class _InputIter, class _RandomAccessIter, class _Compare, class _Distance, class _Tp> _RandomAccessIter __partial_sort_copy(_InputIter __first, - _InputIter __last, - _RandomAccessIter __result_first, - _RandomAccessIter __result_last, - _Compare __comp, _Distance*, _Tp*) { + _InputIter __last, + _RandomAccessIter __result_first, + _RandomAccessIter __result_last, + _Compare __comp, _Distance*, _Tp*) { if (__result_first == __result_last) return __result_last; _RandomAccessIter __result_real_last = __result_first; while(__first != __last && __result_real_last != __result_last) { @@ -1256,27 +1255,31 @@ } make_heap(__result_first, __result_real_last, __comp); while (__first != __last) { - if (__comp(*__first, *__result_first)) + if (__comp(*__first, *__result_first)) { + _STLP_VERBOSE_ASSERT(!__comp(*__result_first, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) __adjust_heap(__result_first, _Distance(0), _Distance(__result_real_last - __result_first), _Tp(*__first), __comp); + } ++__first; } sort_heap(__result_first, __result_real_last, __comp); return __result_real_last; } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _InputIter, class _RandomAccessIter> _RandomAccessIter partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - _STLP_DEBUG_CHECK(__check_range(__result_first, __result_last)) - return __partial_sort_copy(__first, __last, __result_first, __result_last, - __less(_STLP_VALUE_TYPE(__first, _InputIter)), - _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter), - _STLP_VALUE_TYPE(__first, _InputIter)); + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last)) + return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last, + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _InputIter)), + _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter), + _STLP_VALUE_TYPE(__first, _InputIter)); } template <class _InputIter, class _RandomAccessIter, class _Compare> @@ -1284,15 +1287,16 @@ partial_sort_copy(_InputIter __first, _InputIter __last, _RandomAccessIter __result_first, _RandomAccessIter __result_last, _Compare __comp) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - _STLP_DEBUG_CHECK(__check_range(__result_first, __result_last)) - return __partial_sort_copy(__first, __last, __result_first, __result_last, - __comp, - _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter), - _STLP_VALUE_TYPE(__first, _InputIter)); + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last)) + return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last, + __comp, + _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter), + _STLP_VALUE_TYPE(__first, _InputIter)); } -// nth_element() and its auxiliary functions. +// nth_element() and its auxiliary functions. +_STLP_MOVE_TO_PRIV_NAMESPACE template <class _RandomAccessIter, class _Tp, class _Compare> void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, @@ -1301,42 +1305,44 @@ _RandomAccessIter __cut = __unguarded_partition(__first, __last, _Tp(__median(*__first, - *(__first + (__last - __first)/2), + *(__first + (__last - __first)/2), *(__last - 1), __comp)), __comp); if (__cut <= __nth) __first = __cut; - else + else __last = __cut; } - __insertion_sort(__first, __last, __comp); + __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); } +_STLP_MOVE_TO_STD_NAMESPACE template <class _RandomAccessIter> void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last) { - _STLP_DEBUG_CHECK(__check_range(__first, __nth)) - _STLP_DEBUG_CHECK(__check_range(__nth, __last)) - __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), - __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last)) + _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); } template <class _RandomAccessIter, class _Compare> void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, _RandomAccessIter __last, _Compare __comp) { - _STLP_DEBUG_CHECK(__check_range(__first, __nth)) - _STLP_DEBUG_CHECK(__check_range(__nth, __last)) - __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp); + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last)) + _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp); } // Binary search (lower_bound, upper_bound, equal_range, binary_search). +_STLP_MOVE_TO_PRIV_NAMESPACE -template <class _ForwardIter, class _Tp, class _Compare, class _Distance> -_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val, _Compare __comp, _Distance*) -{ +template <class _ForwardIter, class _Tp, + class _Compare1, class _Compare2, class _Distance> +_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, + _Compare1 __comp1, _Compare2 __comp2, _Distance*) { _Distance __len = distance(__first, __last); _Distance __half; @@ -1344,8 +1350,10 @@ __half = __len >> 1; _ForwardIter __middle = __first; advance(__middle, __half); - if (__comp(__val, *__middle)) + if (__comp2(__val, *__middle)) { + _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) __len = __half; + } else { __first = __middle; ++__first; @@ -1355,11 +1363,11 @@ return __first; } -template <class _ForwardIter, class _Tp, class _Compare, class _Distance> +template <class _ForwardIter, class _Tp, + class _Compare1, class _Compare2, class _Distance> pair<_ForwardIter, _ForwardIter> __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, - _Compare __comp, _Distance*) -{ + _Compare1 __comp1, _Compare2 __comp2, _Distance* __dist) { _Distance __len = distance(__first, __last); _Distance __half; @@ -1367,29 +1375,40 @@ __half = __len >> 1; _ForwardIter __middle = __first; advance(__middle, __half); - if (__comp(*__middle, __val)) { + if (__comp1(*__middle, __val)) { + _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) __first = __middle; ++__first; __len = __len - __half - 1; } - else if (__comp(__val, *__middle)) + else if (__comp2(__val, *__middle)) { + _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) __len = __half; + } else { - _ForwardIter __left = lower_bound(__first, __middle, __val, __comp); + _ForwardIter __left = __lower_bound(__first, __middle, __val, __comp1, __comp2, __dist); + //Small optim: If lower_bound haven't found an equivalent value + //there is no need to call upper_bound. + if (__comp1(*__left, __val)) { + _STLP_VERBOSE_ASSERT(!__comp2(__val, *__left), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) + return pair<_ForwardIter, _ForwardIter>(__left, __left); + } advance(__first, __len); - _ForwardIter __right = upper_bound(++__middle, __first, __val, __comp); + _ForwardIter __right = __upper_bound(++__middle, __first, __val, __comp1, __comp2, __dist); return pair<_ForwardIter, _ForwardIter>(__left, __right); } } return pair<_ForwardIter, _ForwardIter>(__first, __first); -} +} + +_STLP_MOVE_TO_STD_NAMESPACE template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { - _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) - _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) while (__first1 != __last1 && __first2 != __last2) { if (*__first2 < *__first1) { *__result = *__first2; @@ -1409,10 +1428,11 @@ _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { - _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) - _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) while (__first1 != __last1 && __first2 != __last2) { if (__comp(*__first2, *__first1)) { + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) *__result = *__first2; ++__first2; } @@ -1425,6 +1445,8 @@ return copy(__first2, __last2, copy(__first1, __last1, __result)); } +_STLP_MOVE_TO_PRIV_NAMESPACE + template <class _BidirectionalIter, class _Distance, class _Compare> void __merge_without_buffer(_BidirectionalIter __first, _BidirectionalIter __middle, @@ -1434,8 +1456,10 @@ if (__len1 == 0 || __len2 == 0) return; if (__len1 + __len2 == 2) { - if (__comp(*__middle, *__first)) + if (__comp(*__middle, *__first)) { + _STLP_VERBOSE_ASSERT(!__comp(*__first, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) iter_swap(__first, __middle); + } return; } _BidirectionalIter __first_cut = __first; @@ -1455,7 +1479,7 @@ __len11 +=distance(__first, __first_cut); } _BidirectionalIter __new_middle - = rotate(__first_cut, __middle, __second_cut); + = __rotate(__first_cut, __middle, __second_cut); __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22, __comp); __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11, @@ -1476,8 +1500,9 @@ return copy_backward(__first1, __last1, __result); --__last1; --__last2; - while (true) { + for (;;) { if (__comp(*__last2, *__last1)) { + _STLP_VERBOSE_ASSERT(!__comp(*__last1, *__last2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) *--__result = *__last1; if (__first1 == __last1) return copy_backward(__first2, ++__last2, __result); @@ -1492,7 +1517,7 @@ } } -template <class _BidirectionalIter, class _Tp, +template <class _BidirectionalIter, class _Tp, class _Distance, class _Compare> inline void __inplace_merge_aux(_BidirectionalIter __first, _BidirectionalIter __middle, @@ -1501,10 +1526,7 @@ _Distance __len1 = distance(__first, __middle); _Distance __len2 = distance(__middle, __last); - typedef _Temporary_buffer<_BidirectionalIter, _Tp> _TmpBuf; - _TmpBuf __buf(__first, __last); - _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf); - + _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last); if (__buf.begin() == 0) __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp); else @@ -1513,32 +1535,35 @@ __comp); } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _BidirectionalIter> void inplace_merge(_BidirectionalIter __first, - _BidirectionalIter __middle, - _BidirectionalIter __last) { - _STLP_DEBUG_CHECK(__check_range(__first, __middle)) - _STLP_DEBUG_CHECK(__check_range(__middle, __last)) + _BidirectionalIter __middle, + _BidirectionalIter __last) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last)) if (__first == __middle || __middle == __last) return; - __inplace_merge_aux(__first, __middle, __last, - _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter), - __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter))); + _STLP_PRIV __inplace_merge_aux(__first, __middle, __last, + _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter), + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter))); } template <class _BidirectionalIter, class _Compare> void inplace_merge(_BidirectionalIter __first, - _BidirectionalIter __middle, - _BidirectionalIter __last, _Compare __comp) { - _STLP_DEBUG_CHECK(__check_range(__first, __middle)) - _STLP_DEBUG_CHECK(__check_range(__middle, __last)) + _BidirectionalIter __middle, + _BidirectionalIter __last, _Compare __comp) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last)) if (__first == __middle || __middle == __last) return; - __inplace_merge_aux(__first, __middle, __last, - _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter), - __comp); + _STLP_PRIV __inplace_merge_aux(__first, __middle, __last, + _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter), + __comp); } +_STLP_MOVE_TO_PRIV_NAMESPACE template <class _InputIter1, class _InputIter2, class _Compare> bool __includes(_InputIter1 __first1, _InputIter1 __last1, @@ -1546,9 +1571,11 @@ _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) while (__first1 != __last1 && __first2 != __last2) - if (__comp(*__first2, *__first1)) + if (__comp(*__first2, *__first1)) { + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) return false; - else if(__comp(*__first1, *__first2)) + } + else if (__comp(*__first1, *__first2)) ++__first1; else ++__first1, ++__first2; @@ -1556,18 +1583,23 @@ return __first2 == __last2; } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _InputIter1, class _InputIter2, class _Compare> bool includes(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) { - return __includes(__first1, __last1, __first2, __last2, __comp); + return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, __comp); } template <class _InputIter1, class _InputIter2> bool includes(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2) { - return __includes(__first1, __last1, __first2, __last2, __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); + return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); } +_STLP_MOVE_TO_PRIV_NAMESPACE + template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1, @@ -1577,10 +1609,12 @@ _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) while (__first1 != __last1 && __first2 != __last2) { if (__comp(*__first1, *__first2)) { + _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) *__result = *__first1; ++__first1; } else if (__comp(*__first2, *__first1)) { + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) *__result = *__first2; ++__first2; } @@ -1594,11 +1628,14 @@ return copy(__first2, __last2, copy(__first1, __last1, __result)); } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { - return __set_union(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); + return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); } template <class _InputIter1, class _InputIter2, class _OutputIter, @@ -1606,9 +1643,11 @@ _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { - return __set_union(__first1, __last1, __first2, __last2, __result, __comp); + return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, __comp); } +_STLP_MOVE_TO_PRIV_NAMESPACE + template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1, @@ -1617,8 +1656,10 @@ _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) while (__first1 != __last1 && __first2 != __last2) - if (__comp(*__first1, *__first2)) + if (__comp(*__first1, *__first2)) { + _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) ++__first1; + } else if (__comp(*__first2, *__first1)) ++__first2; else { @@ -1630,11 +1671,14 @@ return __result; } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { - return __set_intersection(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); + return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); } template <class _InputIter1, class _InputIter2, class _OutputIter, @@ -1642,18 +1686,21 @@ _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { - return __set_intersection(__first1, __last1, __first2, __last2, __result, __comp); + return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, __comp); } -template <class _InputIter1, class _InputIter2, class _OutputIter, +_STLP_MOVE_TO_PRIV_NAMESPACE + +template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, + _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) while (__first1 != __last1 && __first2 != __last2) if (__comp(*__first1, *__first2)) { + _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) *__result = *__first1; ++__first1; ++__result; @@ -1667,31 +1714,36 @@ return copy(__first1, __last1, __result); } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _InputIter1, class _InputIter2, class _OutputIter> _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { - return __set_difference(__first1, __last1, __first2, __last2, __result, - __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); + return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); } -template <class _InputIter1, class _InputIter2, class _OutputIter, +template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, + _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { - return __set_difference(__first1, __last1, __first2, __last2, __result, __comp); + return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, __comp); } +_STLP_MOVE_TO_PRIV_NAMESPACE + template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> -_OutputIter +_OutputIter __set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) - while (__first1 != __last1 && __first2 != __last2) + while (__first1 != __last1 && __first2 != __last2) { if (__comp(*__first1, *__first2)) { + _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) *__result = *__first1; ++__first1; ++__result; @@ -1705,58 +1757,65 @@ ++__first1; ++__first2; } + } return copy(__first2, __last2, copy(__first1, __last1, __result)); } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _InputIter1, class _InputIter2, class _OutputIter> -_OutputIter +_OutputIter set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result) { - return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, - __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); + return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); } template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> -_OutputIter +_OutputIter set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _OutputIter __result, _Compare __comp) { - return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp); + return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp); } // min_element and max_element, with and without an explicitly supplied // comparison function. -template <class _ForwardIter, class _Compare> -_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last, - _Compare __comp) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) +template <class _ForwardIter> +_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) if (__first == __last) return __first; _ForwardIter __result = __first; - while (++__first != __last) - if (__comp(*__result, *__first)) __result = __first; - return __result; -} - -template <class _ForwardIter> -_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - if (__first == __last) return __first; - _ForwardIter __result = __first; - while (++__first != __last) + while (++__first != __last) if (*__result < *__first) __result = __first; return __result; } +template <class _ForwardIter, class _Compare> +_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last, + _Compare __comp) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + if (__first == __last) return __first; + _ForwardIter __result = __first; + while (++__first != __last) { + if (__comp(*__result, *__first)) { + _STLP_VERBOSE_ASSERT(!__comp(*__first, *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) + __result = __first; + } + } + return __result; +} + template <class _ForwardIter> _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) if (__first == __last) return __first; _ForwardIter __result = __first; - while (++__first != __last) + while (++__first != __last) if (*__first < *__result) __result = __first; return __result; @@ -1764,17 +1823,23 @@ template <class _ForwardIter, class _Compare> _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last, - _Compare __comp) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) + _Compare __comp) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) if (__first == __last) return __first; _ForwardIter __result = __first; - while (++__first != __last) - if (__comp(*__first, *__result)) __result = __first; + while (++__first != __last) { + if (__comp(*__first, *__result)) { + _STLP_VERBOSE_ASSERT(!__comp(*__result, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) + __result = __first; + } + } return __result; } -// next_permutation and prev_permutation, with and without an explicitly +// next_permutation and prev_permutation, with and without an explicitly // supplied comparison function. +_STLP_MOVE_TO_PRIV_NAMESPACE + template <class _BidirectionalIter, class _Compare> bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp) { @@ -1792,9 +1857,9 @@ _BidirectionalIter __ii = __i; --__i; if (__comp(*__i, *__ii)) { + _STLP_VERBOSE_ASSERT(!__comp(*__ii, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) _BidirectionalIter __j = __last; - while (!__comp(*__i, *--__j)) - {} + while (!__comp(*__i, *--__j)) {} iter_swap(__i, __j); reverse(__ii, __last); return true; @@ -1804,27 +1869,32 @@ return false; } } -#if defined(_STLP_NEED_UNREACHABLE_RETURN) - return 0; +#if defined (_STLP_NEED_UNREACHABLE_RETURN) + return false; #endif } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _BidirectionalIter> bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - return __next_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter))); + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + return _STLP_PRIV __next_permutation(__first, __last, + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter))); } template <class _BidirectionalIter, class _Compare> bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - return __next_permutation(__first, __last, __comp); + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + return _STLP_PRIV __next_permutation(__first, __last, __comp); } +_STLP_MOVE_TO_PRIV_NAMESPACE + template <class _BidirectionalIter, class _Compare> bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, - _Compare __comp) { + _Compare __comp) { if (__first == __last) return false; _BidirectionalIter __i = __first; @@ -1838,9 +1908,9 @@ _BidirectionalIter __ii = __i; --__i; if (__comp(*__ii, *__i)) { + _STLP_VERBOSE_ASSERT(!__comp(*__i, *__ii), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) _BidirectionalIter __j = __last; - while (!__comp(*--__j, *__i)) - {} + while (!__comp(*--__j, *__i)) {} iter_swap(__i, __j); reverse(__ii, __last); return true; @@ -1850,83 +1920,91 @@ return false; } } -#if defined(_STLP_NEED_UNREACHABLE_RETURN) - return 0; +#if defined (_STLP_NEED_UNREACHABLE_RETURN) + return false; #endif } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _BidirectionalIter> bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - return __prev_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter))); + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + return _STLP_PRIV __prev_permutation(__first, __last, + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter))); } template <class _BidirectionalIter, class _Compare> bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, _Compare __comp) { - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - return __prev_permutation(__first, __last, __comp); + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + return _STLP_PRIV __prev_permutation(__first, __last, __comp); } -# ifndef _STLP_NO_EXTENSIONS +#if !defined (_STLP_NO_EXTENSIONS) // is_heap, a predicate testing whether or not a range is // a heap. This function is an extension, not part of the C++ // standard. - +_STLP_MOVE_TO_PRIV_NAMESPACE template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering> bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp, - _Distance __n) -{ + _Distance __n) { _Distance __parent = 0; for (_Distance __child = 1; __child < __n; ++__child) { - if (__comp(__first[__parent], __first[__child])) + if (__comp(__first[__parent], __first[__child])) { + _STLP_VERBOSE_ASSERT(!__comp(__first[__child], __first[__parent]), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) return false; + } if ((__child & 1) == 0) ++__parent; } return true; } +_STLP_MOVE_TO_STD_NAMESPACE + template <class _RandomAccessIter> -bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) -{ - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - return __is_heap(__first, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first); +bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + return _STLP_PRIV __is_heap(__first, _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first); } template <class _RandomAccessIter, class _StrictWeakOrdering> bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last, - _StrictWeakOrdering __comp) -{ - _STLP_DEBUG_CHECK(__check_range(__first, __last)) - return __is_heap(__first, __comp, __last - __first); + _StrictWeakOrdering __comp) { + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) + return _STLP_PRIV __is_heap(__first, __comp, __last - __first); } +_STLP_MOVE_TO_PRIV_NAMESPACE + template <class _ForwardIter, class _StrictWeakOrdering> bool __is_sorted(_ForwardIter __first, _ForwardIter __last, - _StrictWeakOrdering __comp) -{ + _StrictWeakOrdering __comp) { _STLP_DEBUG_CHECK(__check_range(__first, __last)) if (__first == __last) return true; _ForwardIter __next = __first; for (++__next; __next != __last; __first = __next, ++__next) { - if (__comp(*__next, *__first)) + if (__comp(*__next, *__first)) { + _STLP_VERBOSE_ASSERT(!__comp(*__first, *__next), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) return false; + } } return true; } -# endif /* _STLP_NO_EXTENSIONS */ +_STLP_MOVE_TO_STD_NAMESPACE +#endif /* _STLP_NO_EXTENSIONS */ _STLP_END_NAMESPACE -# undef __stl_threshold +#undef __stl_threshold #endif /* _STLP_ALGO_C */ // Local Variables: