diff options
Diffstat (limited to 'contrib/libstdc++/stl/stl_algo.h')
| -rw-r--r-- | contrib/libstdc++/stl/stl_algo.h | 2894 |
1 files changed, 0 insertions, 2894 deletions
diff --git a/contrib/libstdc++/stl/stl_algo.h b/contrib/libstdc++/stl/stl_algo.h deleted file mode 100644 index e9beaee..0000000 --- a/contrib/libstdc++/stl/stl_algo.h +++ /dev/null @@ -1,2894 +0,0 @@ -/* - * - * Copyright (c) 1994 - * Hewlett-Packard Company - * - * Permission to use, copy, modify, distribute and sell this software - * and its documentation for any purpose is hereby granted without fee, - * provided that the above copyright notice appear in all copies and - * that both that copyright notice and this permission notice appear - * in supporting documentation. Hewlett-Packard Company makes no - * representations about the suitability of this software for any - * purpose. It is provided "as is" without express or implied warranty. - * - * - * Copyright (c) 1996 - * Silicon Graphics Computer Systems, Inc. - * - * Permission to use, copy, modify, distribute and sell this software - * and its documentation for any purpose is hereby granted without fee, - * provided that the above copyright notice appear in all copies and - * that both that copyright notice and this permission notice appear - * in supporting documentation. Silicon Graphics makes no - * representations about the suitability of this software for any - * purpose. It is provided "as is" without express or implied warranty. - */ - -/* NOTE: This is an internal header file, included by other STL headers. - * You should not attempt to use it directly. - */ - -#ifndef __SGI_STL_INTERNAL_ALGO_H -#define __SGI_STL_INTERNAL_ALGO_H - -#include <stl_heap.h> - -__STL_BEGIN_NAMESPACE - -#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) -#pragma set woff 1209 -#endif - -// __median (an extension, not present in the C++ standard). - -template <class _Tp> -inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { - if (__a < __b) - if (__b < __c) - return __b; - else if (__a < __c) - return __c; - else - return __a; - else if (__a < __c) - return __a; - else if (__b < __c) - return __c; - else - return __b; -} - -template <class _Tp, class _Compare> -inline const _Tp& -__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { - if (__comp(__a, __b)) - if (__comp(__b, __c)) - return __b; - else if (__comp(__a, __c)) - return __c; - else - return __a; - else if (__comp(__a, __c)) - return __a; - else if (__comp(__b, __c)) - return __c; - else - return __b; -} - -// for_each. Apply a function to every element of a range. -template <class _InputIter, class _Function> -_Function for_each(_InputIter __first, _InputIter __last, _Function __f) { - for ( ; __first != __last; ++__first) - __f(*__first); - return __f; -} - -// find and find_if. - -template <class _InputIter, class _Tp> -inline _InputIter find(_InputIter __first, _InputIter __last, - const _Tp& __val, - input_iterator_tag) -{ - while (__first != __last && *__first != __val) - ++__first; - return __first; -} - -template <class _InputIter, class _Predicate> -inline _InputIter find_if(_InputIter __first, _InputIter __last, - _Predicate __pred, - input_iterator_tag) -{ - while (__first != __last && !__pred(*__first)) - ++__first; - return __first; -} - -#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION - -template <class _RandomAccessIter, class _Tp> -_RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last, - const _Tp& __val, - random_access_iterator_tag) -{ - typename iterator_traits<_RandomAccessIter>::difference_type __trip_count - = (__last - __first) >> 2; - - for ( ; __trip_count > 0 ; --__trip_count) { - if (*__first == __val) return __first; - ++__first; - - if (*__first == __val) return __first; - ++__first; - - if (*__first == __val) return __first; - ++__first; - - if (*__first == __val) return __first; - ++__first; - } - - switch(__last - __first) { - case 3: - if (*__first == __val) return __first; - ++__first; - case 2: - if (*__first == __val) return __first; - ++__first; - case 1: - if (*__first == __val) return __first; - ++__first; - case 0: - default: - return __last; - } -} - -template <class _RandomAccessIter, class _Predicate> -_RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last, - _Predicate __pred, - random_access_iterator_tag) -{ - typename iterator_traits<_RandomAccessIter>::difference_type __trip_count - = (__last - __first) >> 2; - - for ( ; __trip_count > 0 ; --__trip_count) { - if (__pred(*__first)) return __first; - ++__first; - - if (__pred(*__first)) return __first; - ++__first; - - if (__pred(*__first)) return __first; - ++__first; - - if (__pred(*__first)) return __first; - ++__first; - } - - switch(__last - __first) { - case 3: - if (__pred(*__first)) return __first; - ++__first; - case 2: - if (__pred(*__first)) return __first; - ++__first; - case 1: - if (__pred(*__first)) return __first; - ++__first; - case 0: - default: - return __last; - } -} - -#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ - -template <class _InputIter, class _Tp> -inline _InputIter find(_InputIter __first, _InputIter __last, - const _Tp& __val) -{ - return find(__first, __last, __val, __ITERATOR_CATEGORY(__first)); -} - -template <class _InputIter, class _Predicate> -inline _InputIter find_if(_InputIter __first, _InputIter __last, - _Predicate __pred) { - return find_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first)); -} - -// adjacent_find. - -template <class _ForwardIter> -_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) { - if (__first == __last) - return __last; - _ForwardIter __next = __first; - while(++__next != __last) { - if (*__first == *__next) - return __first; - __first = __next; - } - return __last; -} - -template <class _ForwardIter, class _BinaryPredicate> -_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last, - _BinaryPredicate __binary_pred) { - if (__first == __last) - return __last; - _ForwardIter __next = __first; - while(++__next != __last) { - if (__binary_pred(*__first, *__next)) - return __first; - __first = __next; - } - return __last; -} - -// count and count_if. There are two version of each, one whose return type -// type is void and one (present only if we have partial specialization) -// whose return type is iterator_traits<_InputIter>::difference_type. The -// C++ standard only has the latter version, but the former, which was present -// in the HP STL, is retained for backward compatibility. - -template <class _InputIter, class _Tp, class _Size> -void count(_InputIter __first, _InputIter __last, const _Tp& __value, - _Size& __n) { - for ( ; __first != __last; ++__first) - if (*__first == __value) - ++__n; -} - -template <class _InputIter, class _Predicate, class _Size> -void count_if(_InputIter __first, _InputIter __last, _Predicate __pred, - _Size& __n) { - for ( ; __first != __last; ++__first) - if (__pred(*__first)) - ++__n; -} - -#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION - -template <class _InputIter, class _Tp> -typename iterator_traits<_InputIter>::difference_type -count(_InputIter __first, _InputIter __last, const _Tp& __value) { - typename iterator_traits<_InputIter>::difference_type __n = 0; - for ( ; __first != __last; ++__first) - if (*__first == __value) - ++__n; - return __n; -} - -template <class _InputIter, class _Predicate> -typename iterator_traits<_InputIter>::difference_type -count_if(_InputIter __first, _InputIter __last, _Predicate __pred) { - typename iterator_traits<_InputIter>::difference_type __n = 0; - for ( ; __first != __last; ++__first) - if (__pred(*__first)) - ++__n; - return __n; -} - - -#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ - -// search. - -template <class _ForwardIter1, class _ForwardIter2> -_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, - _ForwardIter2 __first2, _ForwardIter2 __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) - return find(__first1, __last1, *__first2); - - // General case. - - _ForwardIter2 __p1, __p; - - __p1 = __first2; ++__p1; - - _ForwardIter1 __current = __first1; - - while (__first1 != __last1) { - __first1 = find(__first1, __last1, *__first2); - if (__first1 == __last1) - return __last1; - - __p = __p1; - __current = __first1; - if (++__current == __last1) - return __last1; - - while (*__current == *__p) { - if (++__p == __last2) - return __first1; - if (++__current == __last1) - return __last1; - } - - ++__first1; - } - return __first1; -} - -template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred> -_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, - _ForwardIter2 __first2, _ForwardIter2 __last2, - _BinaryPred __predicate) -{ - // 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) - return find(__first1, __last1, *__first2); - - // General case. - - _ForwardIter2 __p1, __p; - - __p1 = __first2; ++__p1; - - _ForwardIter1 __current = __first1; - - while (__first1 != __last1) { - while (__first1 != __last1) { - if (__predicate(*__first1, *__first2)) - break; - ++__first1; - } - while (__first1 != __last1 && !__predicate(*__first1, *__first2)) - ++__first1; - if (__first1 == __last1) - return __last1; - - __p = __p1; - __current = __first1; - if (++__current == __last1) return __last1; - - while (__predicate(*__current, *__p)) { - if (++__p == __last2) - return __first1; - if (++__current == __last1) - return __last1; - } - - ++__first1; - } - return __first1; -} - -// 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) { - 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; - } -} - -template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred> -_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, - _Integer __count, const _Tp& __val, - _BinaryPred __binary_pred) { - 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; - } -} - -// swap_ranges - -template <class _ForwardIter1, class _ForwardIter2> -_ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1, - _ForwardIter2 __first2) { - for ( ; __first1 != __last1; ++__first1, ++__first2) - iter_swap(__first1, __first2); - return __first2; -} - -// transform - -template <class _InputIter, class _OutputIter, class _UnaryOperation> -_OutputIter transform(_InputIter __first, _InputIter __last, - _OutputIter __result, _UnaryOperation __oper) { - for ( ; __first != __last; ++__first, ++__result) - *__result = __oper(*__first); - return __result; -} - -template <class _InputIter1, class _InputIter2, class _OutputIter, - class _BinaryOperation> -_OutputIter transform(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _OutputIter __result, - _BinaryOperation __binary_op) { - for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result) - *__result = __binary_op(*__first1, *__first2); - return __result; -} - -// replace, replace_if, replace_copy, replace_copy_if - -template <class _ForwardIter, class _Tp> -void replace(_ForwardIter __first, _ForwardIter __last, - const _Tp& __old_value, const _Tp& __new_value) { - for ( ; __first != __last; ++__first) - if (*__first == __old_value) - *__first = __new_value; -} - -template <class _ForwardIter, class _Predicate, class _Tp> -void replace_if(_ForwardIter __first, _ForwardIter __last, - _Predicate __pred, const _Tp& __new_value) { - for ( ; __first != __last; ++__first) - if (__pred(*__first)) - *__first = __new_value; -} - -template <class _InputIter, class _OutputIter, class _Tp> -_OutputIter replace_copy(_InputIter __first, _InputIter __last, - _OutputIter __result, - const _Tp& __old_value, const _Tp& __new_value) { - for ( ; __first != __last; ++__first, ++__result) - *__result = *__first == __old_value ? __new_value : *__first; - return __result; -} - -template <class Iterator, class _OutputIter, class _Predicate, class _Tp> -_OutputIter replace_copy_if(Iterator __first, Iterator __last, - _OutputIter __result, - _Predicate __pred, const _Tp& __new_value) { - for ( ; __first != __last; ++__first, ++__result) - *__result = __pred(*__first) ? __new_value : *__first; - return __result; -} - -// generate and generate_n - -template <class _ForwardIter, class _Generator> -void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) { - for ( ; __first != __last; ++__first) - *__first = __gen(); -} - -template <class _OutputIter, class _Size, class _Generator> -_OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) { - for ( ; __n > 0; --__n, ++__first) - *__first = __gen(); - return __first; -} - -// remove, remove_if, remove_copy, remove_copy_if - -template <class _InputIter, class _OutputIter, class _Tp> -_OutputIter remove_copy(_InputIter __first, _InputIter __last, - _OutputIter __result, const _Tp& __value) { - for ( ; __first != __last; ++__first) - if (*__first != __value) { - *__result = *__first; - ++__result; - } - return __result; -} - -template <class _InputIter, class _OutputIter, class _Predicate> -_OutputIter remove_copy_if(_InputIter __first, _InputIter __last, - _OutputIter __result, _Predicate __pred) { - for ( ; __first != __last; ++__first) - if (!__pred(*__first)) { - *__result = *__first; - ++__result; - } - return __result; -} - -template <class _ForwardIter, class _Tp> -_ForwardIter remove(_ForwardIter __first, _ForwardIter __last, - const _Tp& __value) { - __first = find(__first, __last, __value); - _ForwardIter __i = __first; - return __first == __last ? __first - : remove_copy(++__i, __last, __first, __value); -} - -template <class _ForwardIter, class _Predicate> -_ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last, - _Predicate __pred) { - __first = find_if(__first, __last, __pred); - _ForwardIter __i = __first; - return __first == __last ? __first - : remove_copy_if(++__i, __last, __first, __pred); -} - -// unique and unique_copy - -template <class _InputIter, class _OutputIter, class _Tp> -_OutputIter __unique_copy(_InputIter __first, _InputIter __last, - _OutputIter __result, _Tp*) { - _Tp __value = *__first; - *__result = __value; - while (++__first != __last) - if (__value != *__first) { - __value = *__first; - *++__result = __value; - } - return ++__result; -} - -template <class _InputIter, class _OutputIter> -inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last, - _OutputIter __result, - output_iterator_tag) { - return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first)); -} - -template <class _InputIter, class _ForwardIter> -_ForwardIter __unique_copy(_InputIter __first, _InputIter __last, - _ForwardIter __result, forward_iterator_tag) { - *__result = *__first; - while (++__first != __last) - if (*__result != *__first) *++__result = *__first; - return ++__result; -} - -template <class _InputIter, class _OutputIter> -inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, - _OutputIter __result) { - if (__first == __last) return __result; - return __unique_copy(__first, __last, __result, - __ITERATOR_CATEGORY(__result)); -} - -template <class _InputIter, class _OutputIter, class _BinaryPredicate, - class _Tp> -_OutputIter __unique_copy(_InputIter __first, _InputIter __last, - _OutputIter __result, - _BinaryPredicate __binary_pred, _Tp*) { - _Tp __value = *__first; - *__result = __value; - while (++__first != __last) - if (!__binary_pred(__value, *__first)) { - __value = *__first; - *++__result = __value; - } - return ++__result; -} - -template <class _InputIter, class _OutputIter, class _BinaryPredicate> -inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last, - _OutputIter __result, - _BinaryPredicate __binary_pred, - output_iterator_tag) { - return __unique_copy(__first, __last, __result, __binary_pred, - __VALUE_TYPE(__first)); -} - -template <class _InputIter, class _ForwardIter, class _BinaryPredicate> -_ForwardIter __unique_copy(_InputIter __first, _InputIter __last, - _ForwardIter __result, - _BinaryPredicate __binary_pred, - forward_iterator_tag) { - *__result = *__first; - while (++__first != __last) - if (!__binary_pred(*__result, *__first)) *++__result = *__first; - return ++__result; -} - -template <class _InputIter, class _OutputIter, class _BinaryPredicate> -inline _OutputIter unique_copy(_InputIter __first, _InputIter __last, - _OutputIter __result, - _BinaryPredicate __binary_pred) { - if (__first == __last) return __result; - return __unique_copy(__first, __last, __result, __binary_pred, - __ITERATOR_CATEGORY(__result)); -} - -template <class _ForwardIter> -_ForwardIter unique(_ForwardIter __first, _ForwardIter __last) { - __first = adjacent_find(__first, __last); - return unique_copy(__first, __last, __first); -} - -template <class _ForwardIter, class _BinaryPredicate> -_ForwardIter unique(_ForwardIter __first, _ForwardIter __last, - _BinaryPredicate __binary_pred) { - __first = adjacent_find(__first, __last, __binary_pred); - return unique_copy(__first, __last, __first, __binary_pred); -} - -// reverse and reverse_copy, and their auxiliary functions - -template <class _BidirectionalIter> -void __reverse(_BidirectionalIter __first, _BidirectionalIter __last, - bidirectional_iterator_tag) { - while (true) - if (__first == __last || __first == --__last) - return; - else - iter_swap(__first++, __last); -} - -template <class _RandomAccessIter> -void __reverse(_RandomAccessIter __first, _RandomAccessIter __last, - random_access_iterator_tag) { - while (__first < __last) - iter_swap(__first++, --__last); -} - -template <class _BidirectionalIter> -inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) { - __reverse(__first, __last, __ITERATOR_CATEGORY(__first)); -} - -template <class _BidirectionalIter, class _OutputIter> -_OutputIter reverse_copy(_BidirectionalIter __first, - _BidirectionalIter __last, - _OutputIter __result) { - while (__first != __last) { - --__last; - *__result = *__last; - ++__result; - } - return __result; -} - -// rotate and rotate_copy, and their auxiliary functions - -template <class _EuclideanRingElement> -_EuclideanRingElement __gcd(_EuclideanRingElement __m, - _EuclideanRingElement __n) -{ - while (__n != 0) { - _EuclideanRingElement __t = __m % __n; - __m = __n; - __n = __t; - } - return __m; -} - -template <class _ForwardIter, class _Distance> -_ForwardIter __rotate(_ForwardIter __first, - _ForwardIter __middle, - _ForwardIter __last, - _Distance*, - 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*, - 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 == __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 _ForwardIter> -inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle, - _ForwardIter __last) { - return __rotate(__first, __middle, __last, - __DISTANCE_TYPE(__first), - __ITERATOR_CATEGORY(__first)); -} - -template <class _ForwardIter, class _OutputIter> -_OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle, - _ForwardIter __last, _OutputIter __result) { - return copy(__first, __middle, copy(__middle, __last, __result)); -} - -// 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 __STL_NO_DRAND48 - return rand() % __n; -#else - return lrand48() % __n; -#endif -} - -// random_shuffle - -template <class _RandomAccessIter> -inline void random_shuffle(_RandomAccessIter __first, - _RandomAccessIter __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) { - if (__first == __last) return; - for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) - iter_swap(__i, __first + __rand((__i - __first) + 1)); -} - -// 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, const _Distance __n) -{ - _Distance __remaining = 0; - distance(__first, __last, __remaining); - _Distance __m = min(__n, __remaining); - - while (__m > 0) { - if (__random_number(__remaining) < __m) { - *__out = *__first; - ++__out; - --__m; - } - - --__remaining; - ++__first; - } - return __out; -} - -template <class _ForwardIter, class _OutputIter, class _Distance, - class _RandomNumberGenerator> -_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, - _OutputIter __out, const _Distance __n, - _RandomNumberGenerator& __rand) -{ - _Distance __remaining = 0; - distance(__first, __last, __remaining); - _Distance __m = min(__n, __remaining); - - while (__m > 0) { - if (__rand(__remaining) < __m) { - *__out = *__first; - ++__out; - --__m; - } - - --__remaining; - ++__first; - } - return __out; -} - -template <class _InputIter, class _RandomAccessIter, class _Distance> -_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, - _RandomAccessIter __out, - const _Distance __n) -{ - _Distance __m = 0; - _Distance __t = __n; - for ( ; __first != __last && __m < __n; ++__m, ++__first) - __out[__m] = *__first; - - while (__first != __last) { - ++__t; - _Distance __M = __random_number(__t); - if (__M < __n) - __out[__M] = *__first; - ++__first; - } - - return __out + __m; -} - -template <class _InputIter, class _RandomAccessIter, - class _RandomNumberGenerator, class _Distance> -_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, - _RandomAccessIter __out, - _RandomNumberGenerator& __rand, - const _Distance __n) -{ - _Distance __m = 0; - _Distance __t = __n; - for ( ; __first != __last && __m < __n; ++__m, ++__first) - __out[__m] = *__first; - - while (__first != __last) { - ++__t; - _Distance __M = __rand(__t); - if (__M < __n) - __out[__M] = *__first; - ++__first; - } - - return __out + __m; -} - -template <class _InputIter, class _RandomAccessIter> -inline _RandomAccessIter -random_sample(_InputIter __first, _InputIter __last, - _RandomAccessIter __out_first, _RandomAccessIter __out_last) -{ - return __random_sample(__first, __last, - __out_first, __out_last - __out_first); -} - - -template <class _InputIter, class _RandomAccessIter, - class _RandomNumberGenerator> -inline _RandomAccessIter -random_sample(_InputIter __first, _InputIter __last, - _RandomAccessIter __out_first, _RandomAccessIter __out_last, - _RandomNumberGenerator& __rand) -{ - return __random_sample(__first, __last, - __out_first, __rand, - __out_last - __out_first); -} - -// partition, stable_partition, and their auxiliary functions - -template <class _ForwardIter, class _Predicate> -_ForwardIter __partition(_ForwardIter __first, - _ForwardIter __last, - _Predicate __pred, - 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> -_BidirectionalIter __partition(_BidirectionalIter __first, - _BidirectionalIter __last, - _Predicate __pred, - bidirectional_iterator_tag) { - while (true) { - while (true) - if (__first == __last) - return __first; - else if (__pred(*__first)) - ++__first; - else - break; - --__last; - while (true) - if (__first == __last) - return __first; - else if (!__pred(*__last)) - --__last; - else - break; - iter_swap(__first, __last); - ++__first; - } -} - -template <class _ForwardIter, class _Predicate> -inline _ForwardIter partition(_ForwardIter __first, - _ForwardIter __last, - _Predicate __pred) { - return __partition(__first, __last, __pred, __ITERATOR_CATEGORY(__first)); -} - - -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, - __len / 2, __buffer, __buffer_size), - __middle, - __stable_partition_adaptive( - __middle, __last, __pred, - __len - __len / 2, __buffer, __buffer_size)); - } -} - -template <class _ForwardIter, class _Predicate, class _Tp, class _Distance> -inline _ForwardIter -__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, - _Predicate __pred, _Tp*, _Distance*) -{ - _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last); - if (__buf.size() > 0) - return __stable_partition_adaptive(__first, __last, __pred, - _Distance(__buf.requested_size()), - __buf.begin(), __buf.size()); - else - return __inplace_stable_partition(__first, __last, __pred, - _Distance(__buf.requested_size())); -} - -template <class _ForwardIter, class _Predicate> -inline _ForwardIter stable_partition(_ForwardIter __first, - _ForwardIter __last, - _Predicate __pred) { - if (__first == __last) - return __first; - else - return __stable_partition_aux(__first, __last, __pred, - __VALUE_TYPE(__first), - __DISTANCE_TYPE(__first)); -} - -template <class _RandomAccessIter, class _Tp> -_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, - _RandomAccessIter __last, - _Tp __pivot) -{ - while (true) { - while (*__first < __pivot) - ++__first; - --__last; - while (__pivot < *__last) - --__last; - if (!(__first < __last)) - return __first; - iter_swap(__first, __last); - ++__first; - } -} - -template <class _RandomAccessIter, class _Tp, class _Compare> -_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, - _RandomAccessIter __last, - _Tp __pivot, _Compare __comp) -{ - while (true) { - while (__comp(*__first, __pivot)) - ++__first; - --__last; - while (__comp(__pivot, *__last)) - --__last; - if (!(__first < __last)) - return __first; - iter_swap(__first, __last); - ++__first; - } -} - -const int __stl_threshold = 16; - -// sort() and its auxiliary functions. - -template <class _RandomAccessIter, class _Tp> -void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) { - _RandomAccessIter __next = __last; - --__next; - while (__val < *__next) { - *__last = *__next; - __last = __next; - --__next; - } - *__last = __val; -} - -template <class _RandomAccessIter, class _Tp, class _Compare> -void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, - _Compare __comp) { - _RandomAccessIter __next = __last; - --__next; - while (__comp(__val, *__next)) { - *__last = *__next; - __last = __next; - --__next; - } - *__last = __val; -} - -template <class _RandomAccessIter, class _Tp> -inline void __linear_insert(_RandomAccessIter __first, - _RandomAccessIter __last, _Tp*) { - _Tp __val = *__last; - if (__val < *__first) { - copy_backward(__first, __last, __last + 1); - *__first = __val; - } - else - __unguarded_linear_insert(__last, __val); -} - -template <class _RandomAccessIter, class _Tp, class _Compare> -inline void __linear_insert(_RandomAccessIter __first, - _RandomAccessIter __last, _Tp*, _Compare __comp) { - _Tp __val = *__last; - if (__comp(__val, *__first)) { - copy_backward(__first, __last, __last + 1); - *__first = __val; - } - else - __unguarded_linear_insert(__last, __val, __comp); -} - -template <class _RandomAccessIter> -void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) { - if (__first == __last) return; - for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) - __linear_insert(__first, __i, __VALUE_TYPE(__first)); -} - -template <class _RandomAccessIter, class _Compare> -void __insertion_sort(_RandomAccessIter __first, - _RandomAccessIter __last, _Compare __comp) { - if (__first == __last) return; - for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) - __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp); -} - -template <class _RandomAccessIter, class _Tp> -void __unguarded_insertion_sort_aux(_RandomAccessIter __first, - _RandomAccessIter __last, _Tp*) { - for (_RandomAccessIter __i = __first; __i != __last; ++__i) - __unguarded_linear_insert(__i, _Tp(*__i)); -} - -template <class _RandomAccessIter> -inline void __unguarded_insertion_sort(_RandomAccessIter __first, - _RandomAccessIter __last) { - __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first)); -} - -template <class _RandomAccessIter, class _Tp, class _Compare> -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); -} - -template <class _RandomAccessIter, class _Compare> -inline void __unguarded_insertion_sort(_RandomAccessIter __first, - _RandomAccessIter __last, - _Compare __comp) { - __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first), - __comp); -} - -template <class _RandomAccessIter> -void __final_insertion_sort(_RandomAccessIter __first, - _RandomAccessIter __last) { - if (__last - __first > __stl_threshold) { - __insertion_sort(__first, __first + __stl_threshold); - __unguarded_insertion_sort(__first + __stl_threshold, __last); - } - else - __insertion_sort(__first, __last); -} - -template <class _RandomAccessIter, class _Compare> -void __final_insertion_sort(_RandomAccessIter __first, - _RandomAccessIter __last, _Compare __comp) { - if (__last - __first > __stl_threshold) { - __insertion_sort(__first, __first + __stl_threshold, __comp); - __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp); - } - else - __insertion_sort(__first, __last, __comp); -} - -template <class _Size> -inline _Size __lg(_Size __n) { - _Size __k; - for (__k = 0; __n != 1; __n >>= 1) ++__k; - return __k; -} - -template <class _RandomAccessIter, class _Tp, class _Size> -void __introsort_loop(_RandomAccessIter __first, - _RandomAccessIter __last, _Tp*, - _Size __depth_limit) -{ - while (__last - __first > __stl_threshold) { - if (__depth_limit == 0) { - partial_sort(__first, __last, __last); - return; - } - --__depth_limit; - _RandomAccessIter __cut = - __unguarded_partition(__first, __last, - _Tp(__median(*__first, - *(__first + (__last - __first)/2), - *(__last - 1)))); - __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit); - __last = __cut; - } -} - -template <class _RandomAccessIter, class _Tp, class _Size, class _Compare> -void __introsort_loop(_RandomAccessIter __first, - _RandomAccessIter __last, _Tp*, - _Size __depth_limit, _Compare __comp) -{ - while (__last - __first > __stl_threshold) { - if (__depth_limit == 0) { - partial_sort(__first, __last, __last, __comp); - return; - } - --__depth_limit; - _RandomAccessIter __cut = - __unguarded_partition(__first, __last, - _Tp(__median(*__first, - *(__first + (__last - __first)/2), - *(__last - 1), __comp)), - __comp); - __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp); - __last = __cut; - } -} - -template <class _RandomAccessIter> -inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) { - if (__first != __last) { - __introsort_loop(__first, __last, - __VALUE_TYPE(__first), - __lg(__last - __first) * 2); - __final_insertion_sort(__first, __last); - } -} - -template <class _RandomAccessIter, class _Compare> -inline void sort(_RandomAccessIter __first, _RandomAccessIter __last, - _Compare __comp) { - if (__first != __last) { - __introsort_loop(__first, __last, - __VALUE_TYPE(__first), - __lg(__last - __first) * 2, - __comp); - __final_insertion_sort(__first, __last, __comp); - } -} - -// stable_sort() and its auxiliary functions. - -template <class _RandomAccessIter> -void __inplace_stable_sort(_RandomAccessIter __first, - _RandomAccessIter __last) { - if (__last - __first < 15) { - __insertion_sort(__first, __last); - return; - } - _RandomAccessIter __middle = __first + (__last - __first) / 2; - __inplace_stable_sort(__first, __middle); - __inplace_stable_sort(__middle, __last); - __merge_without_buffer(__first, __middle, __last, - __middle - __first, - __last - __middle); -} - -template <class _RandomAccessIter, class _Compare> -void __inplace_stable_sort(_RandomAccessIter __first, - _RandomAccessIter __last, _Compare __comp) { - if (__last - __first < 15) { - __insertion_sort(__first, __last, __comp); - return; - } - _RandomAccessIter __middle = __first + (__last - __first) / 2; - __inplace_stable_sort(__first, __middle, __comp); - __inplace_stable_sort(__middle, __last, __comp); - __merge_without_buffer(__first, __middle, __last, - __middle - __first, - __last - __middle, - __comp); -} - -template <class _RandomAccessIter1, class _RandomAccessIter2, - class _Distance> -void __merge_sort_loop(_RandomAccessIter1 __first, - _RandomAccessIter1 __last, - _RandomAccessIter2 __result, _Distance __step_size) { - _Distance __two_step = 2 * __step_size; - - while (__last - __first >= __two_step) { - __result = merge(__first, __first + __step_size, - __first + __step_size, __first + __two_step, - __result); - __first += __two_step; - } - - __step_size = min(_Distance(__last - __first), __step_size); - merge(__first, __first + __step_size, __first + __step_size, __last, - __result); -} - -template <class _RandomAccessIter1, class _RandomAccessIter2, - class _Distance, class _Compare> -void __merge_sort_loop(_RandomAccessIter1 __first, - _RandomAccessIter1 __last, - _RandomAccessIter2 __result, _Distance __step_size, - _Compare __comp) { - _Distance __two_step = 2 * __step_size; - - while (__last - __first >= __two_step) { - __result = merge(__first, __first + __step_size, - __first + __step_size, __first + __two_step, - __result, - __comp); - __first += __two_step; - } - __step_size = min(_Distance(__last - __first), __step_size); - - merge(__first, __first + __step_size, - __first + __step_size, __last, - __result, - __comp); -} - -const int __stl_chunk_size = 7; - -template <class _RandomAccessIter, class _Distance> -void __chunk_insertion_sort(_RandomAccessIter __first, - _RandomAccessIter __last, _Distance __chunk_size) -{ - while (__last - __first >= __chunk_size) { - __insertion_sort(__first, __first + __chunk_size); - __first += __chunk_size; - } - __insertion_sort(__first, __last); -} - -template <class _RandomAccessIter, class _Distance, class _Compare> -void __chunk_insertion_sort(_RandomAccessIter __first, - _RandomAccessIter __last, - _Distance __chunk_size, _Compare __comp) -{ - while (__last - __first >= __chunk_size) { - __insertion_sort(__first, __first + __chunk_size, __comp); - __first += __chunk_size; - } - __insertion_sort(__first, __last, __comp); -} - -template <class _RandomAccessIter, class _Pointer, class _Distance> -void __merge_sort_with_buffer(_RandomAccessIter __first, - _RandomAccessIter __last, - _Pointer __buffer, _Distance*) { - _Distance __len = __last - __first; - _Pointer __buffer_last = __buffer + __len; - - _Distance __step_size = __stl_chunk_size; - __chunk_insertion_sort(__first, __last, __step_size); - - while (__step_size < __len) { - __merge_sort_loop(__first, __last, __buffer, __step_size); - __step_size *= 2; - __merge_sort_loop(__buffer, __buffer_last, __first, __step_size); - __step_size *= 2; - } -} - -template <class _RandomAccessIter, class _Pointer, class _Distance, - class _Compare> -void __merge_sort_with_buffer(_RandomAccessIter __first, - _RandomAccessIter __last, _Pointer __buffer, - _Distance*, _Compare __comp) { - _Distance __len = __last - __first; - _Pointer __buffer_last = __buffer + __len; - - _Distance __step_size = __stl_chunk_size; - __chunk_insertion_sort(__first, __last, __step_size, __comp); - - while (__step_size < __len) { - __merge_sort_loop(__first, __last, __buffer, __step_size, __comp); - __step_size *= 2; - __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp); - __step_size *= 2; - } -} - -template <class _RandomAccessIter, class _Pointer, class _Distance> -void __stable_sort_adaptive(_RandomAccessIter __first, - _RandomAccessIter __last, _Pointer __buffer, - _Distance __buffer_size) { - _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(__middle, __last, __buffer, __buffer_size); - } - else { - __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0); - __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0); - } - __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), - _Distance(__last - __middle), __buffer, __buffer_size); -} - -template <class _RandomAccessIter, class _Pointer, class _Distance, - class _Compare> -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, - __comp); - __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, - __comp); - } - else { - __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0, - __comp); - __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0, - __comp); - } - __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), - _Distance(__last - __middle), __buffer, __buffer_size, - __comp); -} - -template <class _RandomAccessIter, class _Tp, class _Distance> -inline void __stable_sort_aux(_RandomAccessIter __first, - _RandomAccessIter __last, _Tp*, _Distance*) { - _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last); - if (buf.begin() == 0) - __inplace_stable_sort(__first, __last); - else - __stable_sort_adaptive(__first, __last, buf.begin(), - _Distance(buf.size())); -} - -template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare> -inline void __stable_sort_aux(_RandomAccessIter __first, - _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()), - __comp); -} - -template <class _RandomAccessIter> -inline void stable_sort(_RandomAccessIter __first, - _RandomAccessIter __last) { - __stable_sort_aux(__first, __last, - __VALUE_TYPE(__first), - __DISTANCE_TYPE(__first)); -} - -template <class _RandomAccessIter, class _Compare> -inline void stable_sort(_RandomAccessIter __first, - _RandomAccessIter __last, _Compare __comp) { - __stable_sort_aux(__first, __last, - __VALUE_TYPE(__first), - __DISTANCE_TYPE(__first), - __comp); -} - -// partial_sort, partial_sort_copy, and auxiliary functions. - -template <class _RandomAccessIter, class _Tp> -void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, - _RandomAccessIter __last, _Tp*) { - make_heap(__first, __middle); - for (_RandomAccessIter __i = __middle; __i < __last; ++__i) - if (*__i < *__first) - __pop_heap(__first, __middle, __i, _Tp(*__i), - __DISTANCE_TYPE(__first)); - sort_heap(__first, __middle); -} - -template <class _RandomAccessIter> -inline void partial_sort(_RandomAccessIter __first, - _RandomAccessIter __middle, - _RandomAccessIter __last) { - __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first)); -} - -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)) - __pop_heap(__first, __middle, __i, _Tp(*__i), __comp, - __DISTANCE_TYPE(__first)); - sort_heap(__first, __middle, __comp); -} - -template <class _RandomAccessIter, class _Compare> -inline void partial_sort(_RandomAccessIter __first, - _RandomAccessIter __middle, - _RandomAccessIter __last, _Compare __comp) { - __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp); -} - -template <class _InputIter, class _RandomAccessIter, class _Distance, - class _Tp> -_RandomAccessIter __partial_sort_copy(_InputIter __first, - _InputIter __last, - _RandomAccessIter __result_first, - _RandomAccessIter __result_last, - _Distance*, _Tp*) { - if (__result_first == __result_last) return __result_last; - _RandomAccessIter __result_real_last = __result_first; - while(__first != __last && __result_real_last != __result_last) { - *__result_real_last = *__first; - ++__result_real_last; - ++__first; - } - make_heap(__result_first, __result_real_last); - while (__first != __last) { - if (*__first < *__result_first) - __adjust_heap(__result_first, _Distance(0), - _Distance(__result_real_last - __result_first), - _Tp(*__first)); - ++__first; - } - sort_heap(__result_first, __result_real_last); - return __result_real_last; -} - -template <class _InputIter, class _RandomAccessIter> -inline _RandomAccessIter -partial_sort_copy(_InputIter __first, _InputIter __last, - _RandomAccessIter __result_first, - _RandomAccessIter __result_last) { - return __partial_sort_copy(__first, __last, __result_first, __result_last, - __DISTANCE_TYPE(__result_first), - __VALUE_TYPE(__first)); -} - -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*) { - if (__result_first == __result_last) return __result_last; - _RandomAccessIter __result_real_last = __result_first; - while(__first != __last && __result_real_last != __result_last) { - *__result_real_last = *__first; - ++__result_real_last; - ++__first; - } - make_heap(__result_first, __result_real_last, __comp); - while (__first != __last) { - if (__comp(*__first, *__result_first)) - __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; -} - -template <class _InputIter, class _RandomAccessIter, class _Compare> -inline _RandomAccessIter -partial_sort_copy(_InputIter __first, _InputIter __last, - _RandomAccessIter __result_first, - _RandomAccessIter __result_last, _Compare __comp) { - return __partial_sort_copy(__first, __last, __result_first, __result_last, - __comp, - __DISTANCE_TYPE(__result_first), - __VALUE_TYPE(__first)); -} - -// nth_element() and its auxiliary functions. - -template <class _RandomAccessIter, class _Tp> -void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, - _RandomAccessIter __last, _Tp*) { - while (__last - __first > 3) { - _RandomAccessIter __cut = - __unguarded_partition(__first, __last, - _Tp(__median(*__first, - *(__first + (__last - __first)/2), - *(__last - 1)))); - if (__cut <= __nth) - __first = __cut; - else - __last = __cut; - } - __insertion_sort(__first, __last); -} - -template <class _RandomAccessIter> -inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, - _RandomAccessIter __last) { - __nth_element(__first, __nth, __last, __VALUE_TYPE(__first)); -} - -template <class _RandomAccessIter, class _Tp, class _Compare> -void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, - _RandomAccessIter __last, _Tp*, _Compare __comp) { - while (__last - __first > 3) { - _RandomAccessIter __cut = - __unguarded_partition(__first, __last, - _Tp(__median(*__first, - *(__first + (__last - __first)/2), - *(__last - 1), - __comp)), - __comp); - if (__cut <= __nth) - __first = __cut; - else - __last = __cut; - } - __insertion_sort(__first, __last, __comp); -} - -template <class _RandomAccessIter, class _Compare> -inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, - _RandomAccessIter __last, _Compare __comp) { - __nth_element(__first, __nth, __last, __VALUE_TYPE(__first), __comp); -} - - -// Binary search (lower_bound, upper_bound, equal_range, binary_search). - -template <class _ForwardIter, class _Tp, class _Distance> -_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val, _Distance*) -{ - _Distance __len = 0; - distance(__first, __last, __len); - _Distance __half; - _ForwardIter __middle; - - while (__len > 0) { - __half = __len >> 1; - __middle = __first; - advance(__middle, __half); - if (*__middle < __val) { - __first = __middle; - ++__first; - __len = __len - __half - 1; - } - else - __len = __half; - } - return __first; -} - -template <class _ForwardIter, class _Tp> -inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val) { - return __lower_bound(__first, __last, __val, - __DISTANCE_TYPE(__first)); -} - -template <class _ForwardIter, class _Tp, class _Compare, class _Distance> -_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val, _Compare __comp, _Distance*) -{ - _Distance __len = 0; - distance(__first, __last, __len); - _Distance __half; - _ForwardIter __middle; - - while (__len > 0) { - __half = __len >> 1; - __middle = __first; - advance(__middle, __half); - if (__comp(*__middle, __val)) { - __first = __middle; - ++__first; - __len = __len - __half - 1; - } - else - __len = __half; - } - return __first; -} - -template <class _ForwardIter, class _Tp, class _Compare> -inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val, _Compare __comp) { - return __lower_bound(__first, __last, __val, __comp, - __DISTANCE_TYPE(__first)); -} - -template <class _ForwardIter, class _Tp, class _Distance> -_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val, _Distance*) -{ - _Distance __len = 0; - distance(__first, __last, __len); - _Distance __half; - _ForwardIter __middle; - - while (__len > 0) { - __half = __len >> 1; - __middle = __first; - advance(__middle, __half); - if (__val < *__middle) - __len = __half; - else { - __first = __middle; - ++__first; - __len = __len - __half - 1; - } - } - return __first; -} - -template <class _ForwardIter, class _Tp> -inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val) { - return __upper_bound(__first, __last, __val, - __DISTANCE_TYPE(__first)); -} - -template <class _ForwardIter, class _Tp, class _Compare, class _Distance> -_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val, _Compare __comp, _Distance*) -{ - _Distance __len = 0; - distance(__first, __last, __len); - _Distance __half; - _ForwardIter __middle; - - while (__len > 0) { - __half = __len >> 1; - __middle = __first; - advance(__middle, __half); - if (__comp(__val, *__middle)) - __len = __half; - else { - __first = __middle; - ++__first; - __len = __len - __half - 1; - } - } - return __first; -} - -template <class _ForwardIter, class _Tp, class _Compare> -inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val, _Compare __comp) { - return __upper_bound(__first, __last, __val, __comp, - __DISTANCE_TYPE(__first)); -} - -template <class _ForwardIter, class _Tp, class _Distance> -pair<_ForwardIter, _ForwardIter> -__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, - _Distance*) -{ - _Distance __len = 0; - distance(__first, __last, __len); - _Distance __half; - _ForwardIter __middle, __left, __right; - - while (__len > 0) { - __half = __len >> 1; - __middle = __first; - advance(__middle, __half); - if (*__middle < __val) { - __first = __middle; - ++__first; - __len = __len - __half - 1; - } - else if (__val < *__middle) - __len = __half; - else { - __left = lower_bound(__first, __middle, __val); - advance(__first, __len); - __right = upper_bound(++__middle, __first, __val); - return pair<_ForwardIter, _ForwardIter>(__left, __right); - } - } - return pair<_ForwardIter, _ForwardIter>(__first, __first); -} - -template <class _ForwardIter, class _Tp> -inline pair<_ForwardIter, _ForwardIter> -equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) { - return __equal_range(__first, __last, __val, - __DISTANCE_TYPE(__first)); -} - -template <class _ForwardIter, class _Tp, class _Compare, class _Distance> -pair<_ForwardIter, _ForwardIter> -__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, - _Compare __comp, _Distance*) -{ - _Distance __len = 0; - distance(__first, __last, __len); - _Distance __half; - _ForwardIter __middle, __left, __right; - - while (__len > 0) { - __half = __len >> 1; - __middle = __first; - advance(__middle, __half); - if (__comp(*__middle, __val)) { - __first = __middle; - ++__first; - __len = __len - __half - 1; - } - else if (__comp(__val, *__middle)) - __len = __half; - else { - __left = lower_bound(__first, __middle, __val, __comp); - advance(__first, __len); - __right = upper_bound(++__middle, __first, __val, __comp); - return pair<_ForwardIter, _ForwardIter>(__left, __right); - } - } - return pair<_ForwardIter, _ForwardIter>(__first, __first); -} - -template <class _ForwardIter, class _Tp, class _Compare> -inline pair<_ForwardIter, _ForwardIter> -equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, - _Compare __comp) { - return __equal_range(__first, __last, __val, __comp, - __DISTANCE_TYPE(__first)); -} - -template <class _ForwardIter, class _Tp> -bool binary_search(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val) { - _ForwardIter __i = lower_bound(__first, __last, __val); - return __i != __last && !(__val < *__i); -} - -template <class _ForwardIter, class _Tp, class _Compare> -bool binary_search(_ForwardIter __first, _ForwardIter __last, - const _Tp& __val, - _Compare __comp) { - _ForwardIter __i = lower_bound(__first, __last, __val, __comp); - return __i != __last && !__comp(__val, *__i); -} - -// merge, with and without an explicitly supplied comparison function. - -template <class _InputIter1, class _InputIter2, class _OutputIter> -_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result) { - while (__first1 != __last1 && __first2 != __last2) { - if (*__first2 < *__first1) { - *__result = *__first2; - ++__first2; - } - else { - *__result = *__first1; - ++__first1; - } - ++__result; - } - return copy(__first2, __last2, copy(__first1, __last1, __result)); -} - -template <class _InputIter1, class _InputIter2, class _OutputIter, - class _Compare> -_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result, _Compare __comp) { - while (__first1 != __last1 && __first2 != __last2) { - if (__comp(*__first2, *__first1)) { - *__result = *__first2; - ++__first2; - } - else { - *__result = *__first1; - ++__first1; - } - ++__result; - } - return copy(__first2, __last2, copy(__first1, __last1, __result)); -} - -// inplace_merge and its auxiliary functions. - -template <class _BidirectionalIter, class _Distance> -void __merge_without_buffer(_BidirectionalIter __first, - _BidirectionalIter __middle, - _BidirectionalIter __last, - _Distance __len1, _Distance __len2) { - if (__len1 == 0 || __len2 == 0) - return; - if (__len1 + __len2 == 2) { - if (*__middle < *__first) - iter_swap(__first, __middle); - return; - } - _BidirectionalIter __first_cut = __first; - _BidirectionalIter __second_cut = __middle; - _Distance __len11 = 0; - _Distance __len22 = 0; - if (__len1 > __len2) { - __len11 = __len1 / 2; - advance(__first_cut, __len11); - __second_cut = lower_bound(__middle, __last, *__first_cut); - distance(__middle, __second_cut, __len22); - } - else { - __len22 = __len2 / 2; - advance(__second_cut, __len22); - __first_cut = upper_bound(__first, __middle, *__second_cut); - distance(__first, __first_cut, __len11); - } - _BidirectionalIter __new_middle - = rotate(__first_cut, __middle, __second_cut); - __merge_without_buffer(__first, __first_cut, __new_middle, - __len11, __len22); - __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11, - __len2 - __len22); -} - -template <class _BidirectionalIter, class _Distance, class _Compare> -void __merge_without_buffer(_BidirectionalIter __first, - _BidirectionalIter __middle, - _BidirectionalIter __last, - _Distance __len1, _Distance __len2, - _Compare __comp) { - if (__len1 == 0 || __len2 == 0) - return; - if (__len1 + __len2 == 2) { - if (__comp(*__middle, *__first)) - iter_swap(__first, __middle); - return; - } - _BidirectionalIter __first_cut = __first; - _BidirectionalIter __second_cut = __middle; - _Distance __len11 = 0; - _Distance __len22 = 0; - if (__len1 > __len2) { - __len11 = __len1 / 2; - advance(__first_cut, __len11); - __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); - distance(__middle, __second_cut, __len22); - } - else { - __len22 = __len2 / 2; - advance(__second_cut, __len22); - __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); - distance(__first, __first_cut, __len11); - } - _BidirectionalIter __new_middle - = 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, - __len2 - __len22, __comp); -} - -template <class _BidirectionalIter1, class _BidirectionalIter2, - class _Distance> -_BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first, - _BidirectionalIter1 __middle, - _BidirectionalIter1 __last, - _Distance __len1, _Distance __len2, - _BidirectionalIter2 __buffer, - _Distance __buffer_size) { - _BidirectionalIter2 __buffer_end; - if (__len1 > __len2 && __len2 <= __buffer_size) { - __buffer_end = copy(__middle, __last, __buffer); - copy_backward(__first, __middle, __last); - return copy(__buffer, __buffer_end, __first); - } - else if (__len1 <= __buffer_size) { - __buffer_end = copy(__first, __middle, __buffer); - copy(__middle, __last, __first); - return copy_backward(__buffer, __buffer_end, __last); - } - else - return rotate(__first, __middle, __last); -} - -template <class _BidirectionalIter1, class _BidirectionalIter2, - class _BidirectionalIter3> -_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, - _BidirectionalIter1 __last1, - _BidirectionalIter2 __first2, - _BidirectionalIter2 __last2, - _BidirectionalIter3 __result) { - if (__first1 == __last1) - return copy_backward(__first2, __last2, __result); - if (__first2 == __last2) - return copy_backward(__first1, __last1, __result); - --__last1; - --__last2; - while (true) { - if (*__last2 < *__last1) { - *--__result = *__last1; - if (__first1 == __last1) - return copy_backward(__first2, ++__last2, __result); - --__last1; - } - else { - *--__result = *__last2; - if (__first2 == __last2) - return copy_backward(__first1, ++__last1, __result); - --__last2; - } - } -} - -template <class _BidirectionalIter1, class _BidirectionalIter2, - class _BidirectionalIter3, class _Compare> -_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, - _BidirectionalIter1 __last1, - _BidirectionalIter2 __first2, - _BidirectionalIter2 __last2, - _BidirectionalIter3 __result, - _Compare __comp) { - if (__first1 == __last1) - return copy_backward(__first2, __last2, __result); - if (__first2 == __last2) - return copy_backward(__first1, __last1, __result); - --__last1; - --__last2; - while (true) { - if (__comp(*__last2, *__last1)) { - *--__result = *__last1; - if (__first1 == __last1) - return copy_backward(__first2, ++__last2, __result); - --__last1; - } - else { - *--__result = *__last2; - if (__first2 == __last2) - return copy_backward(__first1, ++__last1, __result); - --__last2; - } - } -} - -template <class _BidirectionalIter, class _Distance, class _Pointer> -void __merge_adaptive(_BidirectionalIter __first, - _BidirectionalIter __middle, - _BidirectionalIter __last, - _Distance __len1, _Distance __len2, - _Pointer __buffer, _Distance __buffer_size) { - if (__len1 <= __len2 && __len1 <= __buffer_size) { - _Pointer __buffer_end = copy(__first, __middle, __buffer); - merge(__buffer, __buffer_end, __middle, __last, __first); - } - else if (__len2 <= __buffer_size) { - _Pointer __buffer_end = copy(__middle, __last, __buffer); - __merge_backward(__first, __middle, __buffer, __buffer_end, __last); - } - else { - _BidirectionalIter __first_cut = __first; - _BidirectionalIter __second_cut = __middle; - _Distance __len11 = 0; - _Distance __len22 = 0; - if (__len1 > __len2) { - __len11 = __len1 / 2; - advance(__first_cut, __len11); - __second_cut = lower_bound(__middle, __last, *__first_cut); - distance(__middle, __second_cut, __len22); - } - else { - __len22 = __len2 / 2; - advance(__second_cut, __len22); - __first_cut = upper_bound(__first, __middle, *__second_cut); - distance(__first, __first_cut, __len11); - } - _BidirectionalIter __new_middle = - __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11, - __len22, __buffer, __buffer_size); - __merge_adaptive(__first, __first_cut, __new_middle, __len11, - __len22, __buffer, __buffer_size); - __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, - __len2 - __len22, __buffer, __buffer_size); - } -} - -template <class _BidirectionalIter, class _Distance, class _Pointer, - class _Compare> -void __merge_adaptive(_BidirectionalIter __first, - _BidirectionalIter __middle, - _BidirectionalIter __last, - _Distance __len1, _Distance __len2, - _Pointer __buffer, _Distance __buffer_size, - _Compare __comp) { - if (__len1 <= __len2 && __len1 <= __buffer_size) { - _Pointer __buffer_end = copy(__first, __middle, __buffer); - merge(__buffer, __buffer_end, __middle, __last, __first, __comp); - } - else if (__len2 <= __buffer_size) { - _Pointer __buffer_end = copy(__middle, __last, __buffer); - __merge_backward(__first, __middle, __buffer, __buffer_end, __last, - __comp); - } - else { - _BidirectionalIter __first_cut = __first; - _BidirectionalIter __second_cut = __middle; - _Distance __len11 = 0; - _Distance __len22 = 0; - if (__len1 > __len2) { - __len11 = __len1 / 2; - advance(__first_cut, __len11); - __second_cut = lower_bound(__middle, __last, *__first_cut, __comp); - distance(__middle, __second_cut, __len22); - } - else { - __len22 = __len2 / 2; - advance(__second_cut, __len22); - __first_cut = upper_bound(__first, __middle, *__second_cut, __comp); - distance(__first, __first_cut, __len11); - } - _BidirectionalIter __new_middle = - __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11, - __len22, __buffer, __buffer_size); - __merge_adaptive(__first, __first_cut, __new_middle, __len11, - __len22, __buffer, __buffer_size, __comp); - __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, - __len2 - __len22, __buffer, __buffer_size, __comp); - } -} - -template <class _BidirectionalIter, class _Tp, class _Distance> -inline void __inplace_merge_aux(_BidirectionalIter __first, - _BidirectionalIter __middle, - _BidirectionalIter __last, _Tp*, _Distance*) { - _Distance __len1 = 0; - distance(__first, __middle, __len1); - _Distance __len2 = 0; - distance(__middle, __last, __len2); - - _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last); - if (__buf.begin() == 0) - __merge_without_buffer(__first, __middle, __last, __len1, __len2); - else - __merge_adaptive(__first, __middle, __last, __len1, __len2, - __buf.begin(), _Distance(__buf.size())); -} - -template <class _BidirectionalIter, class _Tp, - class _Distance, class _Compare> -inline void __inplace_merge_aux(_BidirectionalIter __first, - _BidirectionalIter __middle, - _BidirectionalIter __last, _Tp*, _Distance*, - _Compare __comp) { - _Distance __len1 = 0; - distance(__first, __middle, __len1); - _Distance __len2 = 0; - distance(__middle, __last, __len2); - - _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last); - if (__buf.begin() == 0) - __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp); - else - __merge_adaptive(__first, __middle, __last, __len1, __len2, - __buf.begin(), _Distance(__buf.size()), - __comp); -} - -template <class _BidirectionalIter> -inline void inplace_merge(_BidirectionalIter __first, - _BidirectionalIter __middle, - _BidirectionalIter __last) { - if (__first == __middle || __middle == __last) - return; - __inplace_merge_aux(__first, __middle, __last, - __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); -} - -template <class _BidirectionalIter, class _Compare> -inline void inplace_merge(_BidirectionalIter __first, - _BidirectionalIter __middle, - _BidirectionalIter __last, _Compare __comp) { - if (__first == __middle || __middle == __last) - return; - __inplace_merge_aux(__first, __middle, __last, - __VALUE_TYPE(__first), __DISTANCE_TYPE(__first), - __comp); -} - -// Set algorithms: includes, set_union, set_intersection, set_difference, -// set_symmetric_difference. All of these algorithms have the precondition -// that their input ranges are sorted and the postcondition that their output -// ranges are sorted. - -template <class _InputIter1, class _InputIter2> -bool includes(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2) { - while (__first1 != __last1 && __first2 != __last2) - if (*__first2 < *__first1) - return false; - else if(*__first1 < *__first2) - ++__first1; - else - ++__first1, ++__first2; - - return __first2 == __last2; -} - -template <class _InputIter1, class _InputIter2, class _Compare> -bool includes(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) { - while (__first1 != __last1 && __first2 != __last2) - if (__comp(*__first2, *__first1)) - return false; - else if(__comp(*__first1, *__first2)) - ++__first1; - else - ++__first1, ++__first2; - - return __first2 == __last2; -} - -template <class _InputIter1, class _InputIter2, class _OutputIter> -_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result) { - while (__first1 != __last1 && __first2 != __last2) { - if (*__first1 < *__first2) { - *__result = *__first1; - ++__first1; - } - else if (*__first2 < *__first1) { - *__result = *__first2; - ++__first2; - } - else { - *__result = *__first1; - ++__first1; - ++__first2; - } - ++__result; - } - return copy(__first2, __last2, copy(__first1, __last1, __result)); -} - -template <class _InputIter1, class _InputIter2, class _OutputIter, - class _Compare> -_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result, _Compare __comp) { - while (__first1 != __last1 && __first2 != __last2) { - if (__comp(*__first1, *__first2)) { - *__result = *__first1; - ++__first1; - } - else if (__comp(*__first2, *__first1)) { - *__result = *__first2; - ++__first2; - } - else { - *__result = *__first1; - ++__first1; - ++__first2; - } - ++__result; - } - return copy(__first2, __last2, copy(__first1, __last1, __result)); -} - -template <class _InputIter1, class _InputIter2, class _OutputIter> -_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result) { - while (__first1 != __last1 && __first2 != __last2) - if (*__first1 < *__first2) - ++__first1; - else if (*__first2 < *__first1) - ++__first2; - else { - *__result = *__first1; - ++__first1; - ++__first2; - ++__result; - } - return __result; -} - -template <class _InputIter1, class _InputIter2, class _OutputIter, - class _Compare> -_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result, _Compare __comp) { - while (__first1 != __last1 && __first2 != __last2) - if (__comp(*__first1, *__first2)) - ++__first1; - else if (__comp(*__first2, *__first1)) - ++__first2; - else { - *__result = *__first1; - ++__first1; - ++__first2; - ++__result; - } - return __result; -} - -template <class _InputIter1, class _InputIter2, class _OutputIter> -_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result) { - while (__first1 != __last1 && __first2 != __last2) - if (*__first1 < *__first2) { - *__result = *__first1; - ++__first1; - ++__result; - } - else if (*__first2 < *__first1) - ++__first2; - else { - ++__first1; - ++__first2; - } - return copy(__first1, __last1, __result); -} - -template <class _InputIter1, class _InputIter2, class _OutputIter, - class _Compare> -_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result, _Compare __comp) { - while (__first1 != __last1 && __first2 != __last2) - if (__comp(*__first1, *__first2)) { - *__result = *__first1; - ++__first1; - ++__result; - } - else if (__comp(*__first2, *__first1)) - ++__first2; - else { - ++__first1; - ++__first2; - } - return copy(__first1, __last1, __result); -} - -template <class _InputIter1, class _InputIter2, class _OutputIter> -_OutputIter -set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result) { - while (__first1 != __last1 && __first2 != __last2) - if (*__first1 < *__first2) { - *__result = *__first1; - ++__first1; - ++__result; - } - else if (*__first2 < *__first1) { - *__result = *__first2; - ++__first2; - ++__result; - } - else { - ++__first1; - ++__first2; - } - return copy(__first2, __last2, copy(__first1, __last1, __result)); -} - -template <class _InputIter1, class _InputIter2, class _OutputIter, - class _Compare> -_OutputIter -set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, - _InputIter2 __first2, _InputIter2 __last2, - _OutputIter __result, - _Compare __comp) { - while (__first1 != __last1 && __first2 != __last2) - if (__comp(*__first1, *__first2)) { - *__result = *__first1; - ++__first1; - ++__result; - } - else if (__comp(*__first2, *__first1)) { - *__result = *__first2; - ++__first2; - ++__result; - } - else { - ++__first1; - ++__first2; - } - return copy(__first2, __last2, copy(__first1, __last1, __result)); -} - -// min_element and max_element, with and without an explicitly supplied -// comparison function. - -template <class _ForwardIter> -_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) { - if (__first == __last) return __first; - _ForwardIter __result = __first; - while (++__first != __last) - if (*__result < *__first) - __result = __first; - return __result; -} - -template <class _ForwardIter, class _Compare> -_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last, - _Compare __comp) { - if (__first == __last) return __first; - _ForwardIter __result = __first; - while (++__first != __last) - if (__comp(*__result, *__first)) __result = __first; - return __result; -} - -template <class _ForwardIter> -_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) { - if (__first == __last) return __first; - _ForwardIter __result = __first; - while (++__first != __last) - if (*__first < *__result) - __result = __first; - return __result; -} - -template <class _ForwardIter, class _Compare> -_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last, - _Compare __comp) { - if (__first == __last) return __first; - _ForwardIter __result = __first; - while (++__first != __last) - if (__comp(*__first, *__result)) - __result = __first; - return __result; -} - -// next_permutation and prev_permutation, with and without an explicitly -// supplied comparison function. - -template <class _BidirectionalIter> -bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { - if (__first == __last) - return false; - _BidirectionalIter __i = __first; - ++__i; - if (__i == __last) - return false; - __i = __last; - --__i; - - for(;;) { - _BidirectionalIter __ii = __i; - --__i; - if (*__i < *__ii) { - _BidirectionalIter __j = __last; - while (!(*__i < *--__j)) - {} - iter_swap(__i, __j); - reverse(__ii, __last); - return true; - } - if (__i == __first) { - reverse(__first, __last); - return false; - } - } -} - -template <class _BidirectionalIter, class _Compare> -bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, - _Compare __comp) { - if (__first == __last) - return false; - _BidirectionalIter __i = __first; - ++__i; - if (__i == __last) - return false; - __i = __last; - --__i; - - for(;;) { - _BidirectionalIter __ii = __i; - --__i; - if (__comp(*__i, *__ii)) { - _BidirectionalIter __j = __last; - while (!__comp(*__i, *--__j)) - {} - iter_swap(__i, __j); - reverse(__ii, __last); - return true; - } - if (__i == __first) { - reverse(__first, __last); - return false; - } - } -} - -template <class _BidirectionalIter> -bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { - if (__first == __last) - return false; - _BidirectionalIter __i = __first; - ++__i; - if (__i == __last) - return false; - __i = __last; - --__i; - - for(;;) { - _BidirectionalIter __ii = __i; - --__i; - if (*__ii < *__i) { - _BidirectionalIter __j = __last; - while (!(*--__j < *__i)) - {} - iter_swap(__i, __j); - reverse(__ii, __last); - return true; - } - if (__i == __first) { - reverse(__first, __last); - return false; - } - } -} - -template <class _BidirectionalIter, class _Compare> -bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, - _Compare __comp) { - if (__first == __last) - return false; - _BidirectionalIter __i = __first; - ++__i; - if (__i == __last) - return false; - __i = __last; - --__i; - - for(;;) { - _BidirectionalIter __ii = __i; - --__i; - if (__comp(*__ii, *__i)) { - _BidirectionalIter __j = __last; - while (!__comp(*--__j, *__i)) - {} - iter_swap(__i, __j); - reverse(__ii, __last); - return true; - } - if (__i == __first) { - reverse(__first, __last); - return false; - } - } -} - -// find_first_of, with and without an explicitly supplied comparison function. - -template <class _InputIter, class _ForwardIter> -_InputIter find_first_of(_InputIter __first1, _InputIter __last1, - _ForwardIter __first2, _ForwardIter __last2) -{ - for ( ; __first1 != __last1; ++__first1) - for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) - if (*__first1 == *__iter) - return __first1; - return __last1; -} - -template <class _InputIter, class _ForwardIter, class _BinaryPredicate> -_InputIter find_first_of(_InputIter __first1, _InputIter __last1, - _ForwardIter __first2, _ForwardIter __last2, - _BinaryPredicate __comp) -{ - for ( ; __first1 != __last1; ++__first1) - for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) - if (__comp(*__first1, *__iter)) - return __first1; - return __last1; -} - - -// find_end, with and without an explicitly supplied comparison function. -// Search [first2, last2) as a subsequence in [first1, last1), and return -// the *last* possible match. Note that find_end for bidirectional iterators -// is much faster than for forward iterators. - -// find_end for forward iterators. -template <class _ForwardIter1, class _ForwardIter2> -_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, - _ForwardIter2 __first2, _ForwardIter2 __last2, - forward_iterator_tag, forward_iterator_tag) -{ - if (__first2 == __last2) - return __last1; - else { - _ForwardIter1 __result = __last1; - while (1) { - _ForwardIter1 __new_result - = search(__first1, __last1, __first2, __last2); - if (__new_result == __last1) - return __result; - else { - __result = __new_result; - __first1 = __new_result; - ++__first1; - } - } - } -} - -template <class _ForwardIter1, class _ForwardIter2, - class _BinaryPredicate> -_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, - _ForwardIter2 __first2, _ForwardIter2 __last2, - forward_iterator_tag, forward_iterator_tag, - _BinaryPredicate __comp) -{ - if (__first2 == __last2) - return __last1; - else { - _ForwardIter1 __result = __last1; - while (1) { - _ForwardIter1 __new_result - = search(__first1, __last1, __first2, __last2, __comp); - if (__new_result == __last1) - return __result; - else { - __result = __new_result; - __first1 = __new_result; - ++__first1; - } - } - } -} - -// find_end for bidirectional iterators. Requires partial specialization. -#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION - -template <class _BidirectionalIter1, class _BidirectionalIter2> -_BidirectionalIter1 -__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, - _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, - bidirectional_iterator_tag, bidirectional_iterator_tag) -{ - typedef reverse_iterator<_BidirectionalIter1> _RevIter1; - typedef reverse_iterator<_BidirectionalIter2> _RevIter2; - - _RevIter1 __rlast1(__first1); - _RevIter2 __rlast2(__first2); - _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, - _RevIter2(__last2), __rlast2); - - if (__rresult == __rlast1) - return __last1; - else { - _BidirectionalIter1 __result = __rresult.base(); - advance(__result, -distance(__first2, __last2)); - return __result; - } -} - -template <class _BidirectionalIter1, class _BidirectionalIter2, - class _BinaryPredicate> -_BidirectionalIter1 -__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, - _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, - bidirectional_iterator_tag, bidirectional_iterator_tag, - _BinaryPredicate __comp) -{ - typedef reverse_iterator<_BidirectionalIter1> _RevIter1; - typedef reverse_iterator<_BidirectionalIter2> _RevIter2; - - _RevIter1 __rlast1(__first1); - _RevIter2 __rlast2(__first2); - _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1, - _RevIter2(__last2), __rlast2, - __comp); - - if (__rresult == __rlast1) - return __last1; - else { - _BidirectionalIter1 __result = __rresult.base(); - advance(__result, -distance(__first2, __last2)); - return __result; - } -} -#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ - -// Dispatching functions for find_end. - -template <class _ForwardIter1, class _ForwardIter2> -inline _ForwardIter1 -find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, - _ForwardIter2 __first2, _ForwardIter2 __last2) -{ - return __find_end(__first1, __last1, __first2, __last2, - __ITERATOR_CATEGORY(__first1), - __ITERATOR_CATEGORY(__first2)); -} - -template <class _ForwardIter1, class _ForwardIter2, - class _BinaryPredicate> -inline _ForwardIter1 -find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, - _ForwardIter2 __first2, _ForwardIter2 __last2, - _BinaryPredicate __comp) -{ - return __find_end(__first1, __last1, __first2, __last2, - __ITERATOR_CATEGORY(__first1), - __ITERATOR_CATEGORY(__first2), - __comp); -} - -// 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 <class _RandomAccessIter, class _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 <class _RandomAccessIter, class _Distance, class _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; -} - -template <class _RandomAccessIter> -inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) -{ - return __is_heap(__first, __last - __first); -} - - -template <class _RandomAccessIter, class _StrictWeakOrdering> -inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last, - _StrictWeakOrdering __comp) -{ - return __is_heap(__first, __comp, __last - __first); -} - -// is_sorted, a predicated testing whether a range is sorted in -// nondescending order. This is an extension, not part of the C++ -// standard. - -template <class _ForwardIter> -bool is_sorted(_ForwardIter __first, _ForwardIter __last) -{ - if (__first == __last) - return true; - - _ForwardIter __next = __first; - for (++__next; __next != __last; __first = __next, ++__next) { - if (*__next < *__first) - return false; - } - - return true; -} - -template <class _ForwardIter, class _StrictWeakOrdering> -bool is_sorted(_ForwardIter __first, _ForwardIter __last, - _StrictWeakOrdering __comp) -{ - if (__first == __last) - return true; - - _ForwardIter __next = __first; - for (++__next; __next != __last; __first = __next, ++__next) { - if (__comp(*__next, *__first)) - return false; - } - - return true; -} - -#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32) -#pragma reset woff 1209 -#endif - -__STL_END_NAMESPACE - -#endif /* __SGI_STL_INTERNAL_ALGO_H */ - -// Local Variables: -// mode:C++ -// End: |
