williamr@2: /*
williamr@2:  *
williamr@2:  * Copyright (c) 1994
williamr@2:  * Hewlett-Packard Company
williamr@2:  *
williamr@2:  * Copyright (c) 1996,1997
williamr@2:  * Silicon Graphics Computer Systems, Inc.
williamr@2:  *
williamr@2:  * Copyright (c) 1997
williamr@2:  * Moscow Center for SPARC Technology
williamr@2:  *
williamr@2:  * Copyright (c) 1999 
williamr@2:  * Boris Fomitchev
williamr@2:  *
williamr@2:  * This material is provided "as is", with absolutely no warranty expressed
williamr@2:  * or implied. Any use is at your own risk.
williamr@2:  *
williamr@2:  * Permission to use or copy this software for any purpose is hereby granted 
williamr@2:  * without fee, provided the above notices are retained on all copies.
williamr@2:  * Permission to modify the code and to distribute modified code is granted,
williamr@2:  * provided the above notices are retained, and a notice that the code was
williamr@2:  * modified is included with the above copyright notice.
williamr@2:  *
williamr@2:  */
williamr@2: 
williamr@2: #ifndef _STLP_ALGO_C
williamr@2: # define _STLP_ALGO_C
williamr@2: 
williamr@2: # if !defined (_STLP_INTERNAL_ALGO_H)
williamr@2: #  include <stl/_algo.h>
williamr@2: # endif
williamr@2: 
williamr@2: _STLP_BEGIN_NAMESPACE
williamr@2: 
williamr@2: template <class _BidirectionalIter, class _Distance, class _Compare>
williamr@2: void __merge_without_buffer(_BidirectionalIter __first,
williamr@2:                             _BidirectionalIter __middle,
williamr@2:                             _BidirectionalIter __last,
williamr@2:                             _Distance __len1, _Distance __len2,
williamr@2:                             _Compare __comp);
williamr@2: 
williamr@2: 
williamr@2: template <class _BidirectionalIter1, class _BidirectionalIter2,
williamr@2:           class _BidirectionalIter3, class _Compare>
williamr@2: _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
williamr@2:                                      _BidirectionalIter1 __last1,
williamr@2:                                      _BidirectionalIter2 __first2,
williamr@2:                                      _BidirectionalIter2 __last2,
williamr@2:                                      _BidirectionalIter3 __result,
williamr@2:                                      _Compare __comp);
williamr@2: 
williamr@2: template <class _Tp>
williamr@2: # if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
williamr@2: inline 
williamr@2: # endif
williamr@2: const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
williamr@2:   if (__a < __b)
williamr@2:     if (__b < __c)
williamr@2:       return __b;
williamr@2:     else if (__a < __c)
williamr@2:       return __c;
williamr@2:     else
williamr@2:       return __a;
williamr@2:   else if (__a < __c)
williamr@2:     return __a;
williamr@2:   else if (__b < __c)
williamr@2:     return __c;
williamr@2:   else
williamr@2:     return __b;
williamr@2: }
williamr@2: 
williamr@2: template <class _Tp, class _Compare>
williamr@2: # if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
williamr@2: inline 
williamr@2: # endif
williamr@2: const _Tp&
williamr@2: __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
williamr@2:   if (__comp(__a, __b))
williamr@2:     if (__comp(__b, __c))
williamr@2:       return __b;
williamr@2:     else if (__comp(__a, __c))
williamr@2:       return __c;
williamr@2:     else
williamr@2:       return __a;
williamr@2:   else if (__comp(__a, __c))
williamr@2:     return __a;
williamr@2:   else if (__comp(__b, __c))
williamr@2:     return __c;
williamr@2:   else
williamr@2:     return __b;
williamr@2: }
williamr@2: 
williamr@2: template <class _ForwardIter1, class _ForwardIter2>
williamr@2: _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
williamr@2:                      _ForwardIter2 __first2, _ForwardIter2 __last2) 
williamr@2: {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:   // Test for empty ranges
williamr@2:   if (__first1 == __last1 || __first2 == __last2)
williamr@2:     return __first1;
williamr@2: 
williamr@2:   // Test for a pattern of length 1.
williamr@2:   _ForwardIter2 __tmp(__first2);
williamr@2:   ++__tmp;
williamr@2:   if (__tmp == __last2)
williamr@2:     return find(__first1, __last1, *__first2);
williamr@2: 
williamr@2:   // General case.
williamr@2:   _ForwardIter2 __p1 = __first2; 
williamr@2:   ++__p1;
williamr@2: 
williamr@2:   _ForwardIter1 __current = __first1;
williamr@2: 
williamr@2:   while (__first1 != __last1) {
williamr@2:     __first1 = find(__first1, __last1, *__first2);
williamr@2:     if (__first1 == __last1)
williamr@2:       return __last1;
williamr@2: 
williamr@2:     _ForwardIter2 __p = __p1;
williamr@2:     __current = __first1; 
williamr@2:     if (++__current == __last1)
williamr@2:       return __last1;
williamr@2: 
williamr@2:     while (*__current == *__p) {
williamr@2:       if (++__p == __last2)
williamr@2:         return __first1;
williamr@2:       if (++__current == __last1)
williamr@2:         return __last1;
williamr@2:     }
williamr@2: 
williamr@2:     ++__first1;
williamr@2:   }
williamr@2:   return __first1;
williamr@2: }
williamr@2: 
williamr@2: // search_n.  Search for __count consecutive copies of __val.
williamr@2: 
williamr@2: template <class _ForwardIter, class _Integer, class _Tp>
williamr@2: _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
williamr@2:                       _Integer __count, const _Tp& __val) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__count <= 0)
williamr@2:     return __first;
williamr@2:   else {
williamr@2:     __first = find(__first, __last, __val);
williamr@2:     while (__first != __last) {
williamr@2:       _Integer __n = __count - 1;
williamr@2:       _ForwardIter __i = __first;
williamr@2:       ++__i;
williamr@2:       while (__i != __last && __n != 0 && *__i == __val) {
williamr@2:         ++__i;
williamr@2:         --__n;
williamr@2:       }
williamr@2:       if (__n == 0)
williamr@2:         return __first;
williamr@2:       else
williamr@2:         __first = find(__i, __last, __val);
williamr@2:     }
williamr@2:     return __last;
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
williamr@2: _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
williamr@2:                       _Integer __count, const _Tp& __val,
williamr@2:                       _BinaryPred __binary_pred) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__count <= 0)
williamr@2:     return __first;
williamr@2:   else {
williamr@2:     while (__first != __last) {
williamr@2:       if (__binary_pred(*__first, __val))
williamr@2:         break;
williamr@2:       ++__first;
williamr@2:     }
williamr@2:     while (__first != __last) {
williamr@2:       _Integer __n = __count - 1;
williamr@2:       _ForwardIter __i = __first;
williamr@2:       ++__i;
williamr@2:       while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
williamr@2:         ++__i;
williamr@2:         --__n;
williamr@2:       }
williamr@2:       if (__n == 0)
williamr@2:         return __first;
williamr@2:       else {
williamr@2:         while (__i != __last) {
williamr@2:           if (__binary_pred(*__i, __val))
williamr@2:             break;
williamr@2:           ++__i;
williamr@2:         }
williamr@2:         __first = __i;
williamr@2:       }
williamr@2:     }
williamr@2:     return __last;
williamr@2:   }
williamr@2: } 
williamr@2: 
williamr@2: template <class _ForwardIter1, class _ForwardIter2>
williamr@2: _ForwardIter1 
williamr@2: find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 
williamr@2:          _ForwardIter2 __first2, _ForwardIter2 __last2)
williamr@2: {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:   return __find_end(__first1, __last1, __first2, __last2,
williamr@2: # if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
williamr@2:                     _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
williamr@2:                     _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
williamr@2: # else
williamr@2: 		    forward_iterator_tag(),
williamr@2:                     forward_iterator_tag(),
williamr@2: # endif
williamr@2:                     __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))
williamr@2:     );
williamr@2: }
williamr@2: 
williamr@2: // unique and unique_copy
williamr@2: template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,
williamr@2: 					    class _Tp>
williamr@2: _STLP_INLINE_LOOP _OutputIterator 
williamr@2: __unique_copy(_InputIterator __first, _InputIterator __last,
williamr@2:               _OutputIterator __result,
williamr@2:               _BinaryPredicate __binary_pred, _Tp*) {
williamr@2:   _Tp __val = *__first;
williamr@2:  _STLP_PUSH_STACK_ITEM(_Tp, &__val)
williamr@2:   *__result = __val;
williamr@2:   while (++__first != __last)
williamr@2:     if (!__binary_pred(__val, *__first)) {
williamr@2:       __val = *__first;
williamr@2:       *++__result = __val;
williamr@2:     }
williamr@2:   return ++__result;
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter, class _BinaryPredicate>
williamr@2: inline _OutputIter 
williamr@2: __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
williamr@2:               _BinaryPredicate __binary_pred, const output_iterator_tag &) {
williamr@2:   return __unique_copy(__first, __last, __result, __binary_pred, _STLP_VALUE_TYPE(__first, _InputIter));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
williamr@2: _STLP_INLINE_LOOP _ForwardIter 
williamr@2: __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, 
williamr@2:               _BinaryPredicate __binary_pred, const forward_iterator_tag &) {
williamr@2:   *__result = *__first;
williamr@2:   while (++__first != __last)
williamr@2:     if (!__binary_pred(*__result, *__first)) *++__result = *__first;
williamr@2:   return ++__result;
williamr@2: }
williamr@2: 
williamr@2: # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
williamr@2: template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate>
williamr@2: inline _BidirectionalIterator 
williamr@2: __unique_copy(_InputIterator __first, _InputIterator __last,
williamr@2:               _BidirectionalIterator __result, _BinaryPredicate __binary_pred,
williamr@2:               const bidirectional_iterator_tag &) {
williamr@2:   return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate>
williamr@2: inline _RandomAccessIterator 
williamr@2: __unique_copy(_InputIterator __first, _InputIterator __last,
williamr@2:               _RandomAccessIterator __result, _BinaryPredicate __binary_pred,
williamr@2:               const random_access_iterator_tag &) {
williamr@2:   return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
williamr@2: }
williamr@2: # endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */
williamr@2: 
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter>
williamr@2: _OutputIter 
williamr@2: unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first == __last) return __result;
williamr@2:   return __unique_copy(__first, __last, __result, __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),
williamr@2:                        _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter, class _BinaryPredicate>
williamr@2: _OutputIter 
williamr@2: unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
williamr@2:             _BinaryPredicate __binary_pred) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first == __last) return __result;
williamr@2:   return __unique_copy(__first, __last, __result, __binary_pred,
williamr@2:                        _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
williamr@2: }
williamr@2: 
williamr@2: // rotate and rotate_copy, and their auxiliary functions
williamr@2: 
williamr@2: template <class _ForwardIter, class _Distance>
williamr@2: _ForwardIter __rotate(_ForwardIter __first,
williamr@2:                       _ForwardIter __middle,
williamr@2:                       _ForwardIter __last,
williamr@2:                       _Distance*,
williamr@2:                       const forward_iterator_tag &) {
williamr@2:   if (__first == __middle)
williamr@2:     return __last;
williamr@2:   if (__last  == __middle)
williamr@2:     return __first;
williamr@2: 
williamr@2:   _ForwardIter __first2 = __middle;
williamr@2:   do {
williamr@2:     swap(*__first++, *__first2++);
williamr@2:     if (__first == __middle)
williamr@2:       __middle = __first2;
williamr@2:   } while (__first2 != __last);
williamr@2: 
williamr@2:   _ForwardIter __new_middle = __first;
williamr@2: 
williamr@2:   __first2 = __middle;
williamr@2: 
williamr@2:   while (__first2 != __last) {
williamr@2:     swap (*__first++, *__first2++);
williamr@2:     if (__first == __middle)
williamr@2:       __middle = __first2;
williamr@2:     else if (__first2 == __last)
williamr@2:       __first2 = __middle;
williamr@2:   }
williamr@2: 
williamr@2:   return __new_middle;
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter, class _Distance>
williamr@2: _BidirectionalIter __rotate(_BidirectionalIter __first,
williamr@2:                             _BidirectionalIter __middle,
williamr@2:                             _BidirectionalIter __last,
williamr@2:                             _Distance*,
williamr@2:                             const bidirectional_iterator_tag &) {
williamr@2:   if (__first == __middle)
williamr@2:     return __last;
williamr@2:   if (__last  == __middle)
williamr@2:     return __first;
williamr@2: 
williamr@2:   __reverse(__first,  __middle, bidirectional_iterator_tag());
williamr@2:   __reverse(__middle, __last,   bidirectional_iterator_tag());
williamr@2: 
williamr@2:   while (__first != __middle && __middle != __last)
williamr@2:     swap (*__first++, *--__last);
williamr@2: 
williamr@2:   if (__first == __middle) {
williamr@2:     __reverse(__middle, __last,   bidirectional_iterator_tag());
williamr@2:     return __last;
williamr@2:   }
williamr@2:   else {
williamr@2:     __reverse(__first,  __middle, bidirectional_iterator_tag());
williamr@2:     return __first;
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Distance, class _Tp>
williamr@2: _RandomAccessIter __rotate(_RandomAccessIter __first,
williamr@2:                            _RandomAccessIter __middle,
williamr@2:                            _RandomAccessIter __last,
williamr@2:                            _Distance *, _Tp *) {
williamr@2: 
williamr@2:   _Distance __n = __last   - __first;
williamr@2:   _Distance __k = __middle - __first;
williamr@2:   _Distance __l = __n - __k;
williamr@2:   _RandomAccessIter __result = __first + (__last - __middle);
williamr@2: 
williamr@2:   if (__k==0)  /* __first == middle */
williamr@2:     return __last;
williamr@2: 
williamr@2:   if (__k == __l) {
williamr@2:     swap_ranges(__first, __middle, __middle);
williamr@2:     return __result;
williamr@2:   }
williamr@2: 
williamr@2:   _Distance __d = __gcd(__n, __k);
williamr@2: 
williamr@2:   for (_Distance __i = 0; __i < __d; __i++) {
williamr@2:     _Tp __tmp = *__first;
williamr@2:     _STLP_PUSH_STACK_ITEM(_Tp, &__tmp)
williamr@2:     _RandomAccessIter __p = __first;
williamr@2: 
williamr@2:     if (__k < __l) {
williamr@2:       for (_Distance __j = 0; __j < __l/__d; __j++) {
williamr@2: 	if (__p > __first + __l) {
williamr@2:           *__p = *(__p - __l);
williamr@2:           __p -= __l;
williamr@2:         }
williamr@2: 
williamr@2:         *__p = *(__p + __k);
williamr@2:         __p += __k;
williamr@2:       }
williamr@2:     }
williamr@2: 
williamr@2:     else {
williamr@2:       for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
williamr@2:         if (__p < __last - __k) {
williamr@2:           *__p = *(__p + __k);
williamr@2:           __p += __k;
williamr@2:         }
williamr@2: 
williamr@2:         *__p = * (__p - __l);
williamr@2:         __p -= __l;
williamr@2:       }
williamr@2:     }
williamr@2: 
williamr@2:     *__p = __tmp;
williamr@2:     ++__first;
williamr@2:   }
williamr@2: 
williamr@2:   return __result;
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Distance>
williamr@2: inline _RandomAccessIter 
williamr@2: __rotate(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,
williamr@2:          _Distance * __dis, const random_access_iterator_tag &) {
williamr@2:   return __rotate(__first, __middle, __last,
williamr@2:                   __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));
williamr@2: }
williamr@2: 
williamr@2: template <class _ForwardIter>
williamr@2: _ForwardIter 
williamr@2: rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
williamr@2:   return __rotate(__first, __middle, __last,
williamr@2:                   _STLP_DISTANCE_TYPE(__first, _ForwardIter),
williamr@2:                   _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
williamr@2: }
williamr@2: 
williamr@2: // Return a random number in the range [0, __n).  This function encapsulates
williamr@2: // whether we're using rand (part of the standard C library) or lrand48
williamr@2: // (not standard, but a much better choice whenever it's available).
williamr@2: 
williamr@2: template <class _Distance>
williamr@2: inline _Distance __random_number(_Distance __n) {
williamr@2: #ifdef _STLP_NO_DRAND48
williamr@2:   return rand() % __n;
williamr@2: #else
williamr@2:   return lrand48() % __n;
williamr@2: #endif
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter>
williamr@2: void random_shuffle(_RandomAccessIter __first,
williamr@2: 		    _RandomAccessIter __last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first == __last) return;
williamr@2:   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
williamr@2:     iter_swap(__i, __first + __random_number((__i - __first) + 1));
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _RandomNumberGenerator>
williamr@2: void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
williamr@2:                     _RandomNumberGenerator& __rand) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first == __last) return;
williamr@2:   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
williamr@2:     iter_swap(__i, __first + __rand((__i - __first) + 1));
williamr@2: }
williamr@2: 
williamr@2: # ifndef _STLP_NO_EXTENSIONS
williamr@2: 
williamr@2: // random_sample and random_sample_n (extensions, not part of the standard).
williamr@2: 
williamr@2: template <class _ForwardIter, class _OutputIter, class _Distance>
williamr@2: _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
williamr@2:                             _OutputIter __stl_out, const _Distance __n)
williamr@2: {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   _Distance __remaining = distance(__first, __last);
williamr@2:   _Distance __m = (min) (__n, __remaining);
williamr@2: 
williamr@2:   while (__m > 0) {
williamr@2:     if (__random_number(__remaining) < __m) {
williamr@2:       *__stl_out = *__first;
williamr@2:       ++__stl_out;
williamr@2:       --__m;
williamr@2:     }
williamr@2: 
williamr@2:     --__remaining;
williamr@2:     ++__first;
williamr@2:   }
williamr@2:   return __stl_out;
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <class _ForwardIter, class _OutputIter, class _Distance,
williamr@2:           class _RandomNumberGenerator>
williamr@2: _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
williamr@2:                             _OutputIter __stl_out, const _Distance __n,
williamr@2:                             _RandomNumberGenerator& __rand)
williamr@2: {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   _Distance __remaining = distance(__first, __last);
williamr@2:   _Distance __m = (min) (__n, __remaining);
williamr@2: 
williamr@2:   while (__m > 0) {
williamr@2:     if (__rand(__remaining) < __m) {
williamr@2:       *__stl_out = *__first;
williamr@2:       ++__stl_out;
williamr@2:       --__m;
williamr@2:     }
williamr@2: 
williamr@2:     --__remaining;
williamr@2:     ++__first;
williamr@2:   }
williamr@2:   return __stl_out;
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _RandomAccessIter, class _Distance>
williamr@2: _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
williamr@2:                                   _RandomAccessIter __stl_out,
williamr@2:                                   const _Distance __n)
williamr@2: {
williamr@2:   _Distance __m = 0;
williamr@2:   _Distance __t = __n;
williamr@2:   for ( ; __first != __last && __m < __n; ++__m, ++__first) 
williamr@2:     __stl_out[__m] = *__first;
williamr@2: 
williamr@2:   while (__first != __last) {
williamr@2:     ++__t;
williamr@2:     _Distance __M = __random_number(__t);
williamr@2:     if (__M < __n)
williamr@2:       __stl_out[__M] = *__first;
williamr@2:     ++__first;
williamr@2:   }
williamr@2: 
williamr@2:   return __stl_out + __m;
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _RandomAccessIter,
williamr@2:           class _RandomNumberGenerator, class _Distance>
williamr@2: _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
williamr@2:                                   _RandomAccessIter __stl_out,
williamr@2:                                   _RandomNumberGenerator& __rand,
williamr@2:                                   const _Distance __n)
williamr@2: {
williamr@2:   _Distance __m = 0;
williamr@2:   _Distance __t = __n;
williamr@2:   for ( ; __first != __last && __m < __n; ++__m, ++__first)
williamr@2:     __stl_out[__m] = *__first;
williamr@2: 
williamr@2:   while (__first != __last) {
williamr@2:     ++__t;
williamr@2:     _Distance __M = __rand(__t);
williamr@2:     if (__M < __n)
williamr@2:       __stl_out[__M] = *__first;
williamr@2:     ++__first;
williamr@2:   }
williamr@2: 
williamr@2:   return __stl_out + __m;
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _RandomAccessIter>
williamr@2: _RandomAccessIter
williamr@2: random_sample(_InputIter __first, _InputIter __last,
williamr@2:               _RandomAccessIter __out_first, _RandomAccessIter __out_last) 
williamr@2: {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last))
williamr@2:   return __random_sample(__first, __last,
williamr@2:                          __out_first, __out_last - __out_first);
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>
williamr@2: _RandomAccessIter
williamr@2: random_sample(_InputIter __first, _InputIter __last,
williamr@2:               _RandomAccessIter __out_first, _RandomAccessIter __out_last,
williamr@2:               _RandomNumberGenerator& __rand) 
williamr@2: {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last))
williamr@2:   return __random_sample(__first, __last,
williamr@2:                          __out_first, __rand,
williamr@2:                          __out_last - __out_first);
williamr@2: }
williamr@2: 
williamr@2: # endif /* _STLP_NO_EXTENSIONS */
williamr@2: 
williamr@2: // partition, stable_partition, and their auxiliary functions
williamr@2: 
williamr@2: template <class _ForwardIter, class _Predicate>
williamr@2: _STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,
williamr@2:                                            _ForwardIter __last,
williamr@2:                                            _Predicate   __pred,
williamr@2:                                            const forward_iterator_tag &) {
williamr@2:   if (__first == __last) return __first;
williamr@2: 
williamr@2:   while (__pred(*__first))
williamr@2:     if (++__first == __last) return __first;
williamr@2: 
williamr@2:   _ForwardIter __next = __first;
williamr@2: 
williamr@2:   while (++__next != __last)
williamr@2:     if (__pred(*__next)) {
williamr@2:       swap(*__first, *__next);
williamr@2:       ++__first;
williamr@2:     }
williamr@2:   return __first;
williamr@2: }
williamr@2: 
williamr@2: /* bug fix- start*/
williamr@2: 
williamr@2: template <class _ForwardIter>
williamr@2: _ForwardIter
williamr@2: __rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
williamr@2:   return __rotate_aux(__first, __middle, __last,
williamr@2:                       _STLP_DISTANCE_TYPE(__first, _ForwardIter),
williamr@2:                       _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
williamr@2: }
williamr@2: 
williamr@2: template <class _ForwardIter, class _Distance>
williamr@2: _ForwardIter __rotate_aux(_ForwardIter __first,
williamr@2:                           _ForwardIter __middle,
williamr@2:                           _ForwardIter __last,
williamr@2:                           _Distance*,
williamr@2:                           const forward_iterator_tag &) {
williamr@2:   if (__first == __middle)
williamr@2:     return __last;
williamr@2:   if (__last  == __middle)
williamr@2:     return __first;
williamr@2: 
williamr@2:   _ForwardIter __first2 = __middle;
williamr@2:   do {
williamr@2:     swap(*__first++, *__first2++);
williamr@2:     if (__first == __middle)
williamr@2:       __middle = __first2;
williamr@2:   } while (__first2 != __last);
williamr@2: 
williamr@2:   _ForwardIter __new_middle = __first;
williamr@2: 
williamr@2:   __first2 = __middle;
williamr@2: 
williamr@2:   while (__first2 != __last) {
williamr@2:     swap (*__first++, *__first2++);
williamr@2:     if (__first == __middle)
williamr@2:       __middle = __first2;
williamr@2:     else if (__first2 == __last)
williamr@2:       __first2 = __middle;
williamr@2:   }
williamr@2: 
williamr@2:   return __new_middle;
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <class _ForwardIter, class _Pointer, class _Predicate,
williamr@2:           class _Distance>
williamr@2: _ForwardIter __stable_partition_adaptive(_ForwardIter __first,
williamr@2:                                          _ForwardIter __last,
williamr@2:                                          _Predicate __pred, _Distance __len,
williamr@2:                                          _Pointer __buffer, _Distance __buffer_size,
williamr@2:                                          bool __pred_of_first, bool __pred_of_before_last) {
williamr@2:   if (__len <= __buffer_size) {
williamr@2:     _ForwardIter __result1 = __first;
williamr@2:     _Pointer __result2 = __buffer;
williamr@2:     if ((__first != __last) && (!__pred_of_first || __pred(*__first))) {
williamr@2:       *__result2 = *__first;
williamr@2:       ++__result2; ++__first; --__len;
williamr@2:     }
williamr@2:     for (; __first != __last ; ++__first, --__len) {
williamr@2:       if (((__len == 1) && (__pred_of_before_last || __pred(*__first))) ||
williamr@2:           ((__len != 1) && __pred(*__first))){
williamr@2:         *__result1 = *__first;
williamr@2:         ++__result1;
williamr@2:       }
williamr@2:       else {
williamr@2:         *__result2 = *__first;
williamr@2:         ++__result2;
williamr@2:       }
williamr@2:     }
williamr@2:     copy(__buffer, __result2, __result1);
williamr@2:     return __result1;
williamr@2:   }
williamr@2:   else {
williamr@2:     _ForwardIter __middle = __first;
williamr@2:     _Distance __half_len = __len / 2;
williamr@2:     advance(__middle, __half_len);
williamr@2:     return __rotate(__stable_partition_adaptive(
williamr@2:                           __first, __middle, __pred,
williamr@2:                           __half_len, __buffer, __buffer_size,
williamr@2:                           __pred_of_first, false),
williamr@2:                     __middle,
williamr@2:                     __stable_partition_adaptive(
williamr@2:                           __middle, __last, __pred,
williamr@2:                           __len - __half_len, __buffer, __buffer_size,
williamr@2:                           true, __pred_of_before_last));
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <class _ForwardIter, class _Predicate, class _Distance>
williamr@2: _ForwardIter __inplace_stable_partition(_ForwardIter __first,
williamr@2:                                         _ForwardIter __last,
williamr@2:                                         _Predicate __pred, _Distance __len,
williamr@2:                                         bool __pred_of_first, bool __pred_of_before_last) {
williamr@2:   if (__len == 1)
williamr@2:     return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first;
williamr@2:   _ForwardIter __middle = __first;
williamr@2:   _Distance __half_len = __len / 2;
williamr@2:   advance(__middle, __half_len);
williamr@2:   return __rotate(__inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false),
williamr@2:                   __middle,
williamr@2:                   __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last));
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: 
williamr@2: template <class _ForwardIter, class _Predicate>
williamr@2: _ForwardIter
williamr@2: stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
williamr@2:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@2:   for (;;) {
williamr@2:     if (__first == __last)
williamr@2:       return __first;
williamr@2:     else if (__pred(*__first))
williamr@2:       ++__first;
williamr@2:     else
williamr@2:       break;
williamr@2:   }
williamr@2:   return  __stable_partition_aux(__first, __last, __pred,
williamr@2:                                            _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
williamr@2: inline _ForwardIter
williamr@2: __stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,
williamr@2:                            _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last = false) {
williamr@2:   _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
williamr@2:   return (__buf.size() > 0) ?
williamr@2:     __stable_partition_adaptive(__first, __last, __pred,
williamr@2:                                 _Distance(__buf.requested_size()),
williamr@2:                                 __buf.begin(), __buf.size(),
williamr@2:                                 false, __pred_of_before_last)  :
williamr@2:     __inplace_stable_partition(__first, __last, __pred,
williamr@2:                                _Distance(__buf.requested_size()),
williamr@2:                                false, __pred_of_before_last);
williamr@2: 
williamr@2: }
williamr@2: 
williamr@2: template <class _ForwardIter, class _Predicate>
williamr@2: _ForwardIter
williamr@2: __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred,
williamr@2:                        const forward_iterator_tag &) {
williamr@2:   return __stable_partition_aux_aux(__first, __last, __pred,
williamr@2:                                     _STLP_VALUE_TYPE(__first, _ForwardIter),
williamr@2:                                     _STLP_DISTANCE_TYPE(__first, _ForwardIter));
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: /* bug fix- end*/
williamr@2: 
williamr@2: 
williamr@2: 
williamr@2: template <class _BidirectionalIter, class _Predicate>
williamr@2: _STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,
williamr@2:                                                  _BidirectionalIter __last,
williamr@2:                                                  _Predicate __pred,
williamr@2:                                                  const bidirectional_iterator_tag &) {
williamr@2:   while (true) {
williamr@2:     while (true)
williamr@2:       if (__first == __last)
williamr@2:         return __first;
williamr@2:       else if (__pred(*__first))
williamr@2:         ++__first;
williamr@2:       else
williamr@2:         break;
williamr@2:     --__last;
williamr@2:     while (true)
williamr@2:       if (__first == __last)
williamr@2:         return __first;
williamr@2:       else if (!__pred(*__last))
williamr@2:         --__last;
williamr@2:       else
williamr@2:         break;
williamr@2:     iter_swap(__first, __last);
williamr@2:     ++__first;
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
williamr@2: template <class _BidirectionalIter, class _Predicate>
williamr@2: inline
williamr@2: _BidirectionalIter __partition(_BidirectionalIter __first,
williamr@2:                                _BidirectionalIter __last,
williamr@2: 			       _Predicate __pred,
williamr@2: 			       const random_access_iterator_tag &) {
williamr@2:   return __partition(__first, __last, __pred, bidirectional_iterator_tag());
williamr@2: }
williamr@2: # endif
williamr@2: 
williamr@2: template <class _ForwardIter, class _Predicate>
williamr@2: _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate   __pred) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   return __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
williamr@2: }
williamr@2: 
williamr@2: /*
williamr@2: template <class _ForwardIter, class _Predicate, class _Distance>
williamr@2: _ForwardIter __inplace_stable_partition(_ForwardIter __first,
williamr@2:                                         _ForwardIter __last,
williamr@2:                                         _Predicate __pred, _Distance __len) {
williamr@2:   if (__len == 1)
williamr@2:     return __pred(*__first) ? __last : __first;
williamr@2:   _ForwardIter __middle = __first;
williamr@2:   advance(__middle, __len / 2);
williamr@2:   return rotate(__inplace_stable_partition(__first, __middle, __pred, 
williamr@2:                                            __len / 2),
williamr@2:                 __middle,
williamr@2:                 __inplace_stable_partition(__middle, __last, __pred,
williamr@2:                                            __len - __len / 2));
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <class _ForwardIter, class _Pointer, class _Predicate, 
williamr@2:           class _Distance>
williamr@2: _ForwardIter __stable_partition_adaptive(_ForwardIter __first,
williamr@2:                                          _ForwardIter __last,
williamr@2:                                          _Predicate __pred, _Distance __len,
williamr@2:                                          _Pointer __buffer,
williamr@2:                                          _Distance __buffer_size) 
williamr@2: {
williamr@2:   if (__len <= __buffer_size) {
williamr@2:     _ForwardIter __result1 = __first;
williamr@2:     _Pointer __result2 = __buffer;
williamr@2:     for ( ; __first != __last ; ++__first)
williamr@2:       if (__pred(*__first)) {
williamr@2:         *__result1 = *__first;
williamr@2:         ++__result1;
williamr@2:       }
williamr@2:       else {
williamr@2:         *__result2 = *__first;
williamr@2:         ++__result2;
williamr@2:       }
williamr@2:     copy(__buffer, __result2, __result1);
williamr@2:     return __result1;
williamr@2:   }
williamr@2:   else {
williamr@2:     _ForwardIter __middle = __first;
williamr@2:     advance(__middle, __len / 2);
williamr@2:     return rotate(__stable_partition_adaptive(
williamr@2:                           __first, __middle, __pred,
williamr@2:                           _Distance(__len / 2), __buffer, __buffer_size),
williamr@2:                     __middle,
williamr@2:                     __stable_partition_adaptive(
williamr@2:                           __middle, __last, __pred,
williamr@2:                           _Distance(__len - __len / 2), __buffer, __buffer_size));
williamr@2:   }
williamr@2: }
williamr@2: */ //bug fix
williamr@2: template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
williamr@2: inline _ForwardIter
williamr@2: __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, 
williamr@2:                        _Predicate __pred, _Tp*, _Distance*)
williamr@2: {
williamr@2:   typedef _Temporary_buffer<_ForwardIter, _Tp> _TmpBuf;
williamr@2:   _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
williamr@2:   _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);
williamr@2: 
williamr@2:   _STLP_MPWFIX_TRY		//*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
williamr@2:   return (__buf.size() > 0) ?
williamr@2:     __stable_partition_adaptive(__first, __last, __pred,
williamr@2: 				_Distance(__buf.requested_size()),
williamr@2: 				__buf.begin(), _Distance(__buf.size()))  :
williamr@2:     __inplace_stable_partition(__first, __last, __pred, 
williamr@2: 			       _Distance(__buf.requested_size()));
williamr@2:   _STLP_MPWFIX_CATCH	//*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
williamr@2: }
williamr@2: /*
williamr@2: template <class _ForwardIter, class _Predicate>
williamr@2: _ForwardIter 
williamr@2: stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first == __last)
williamr@2:     return __first;
williamr@2:   else
williamr@2:     return __stable_partition_aux(__first, __last, __pred,
williamr@2:                                   _STLP_VALUE_TYPE(__first, _ForwardIter),
williamr@2:                                   _STLP_DISTANCE_TYPE(__first, _ForwardIter));
williamr@2: }
williamr@2: */ //bug fix
williamr@2: template <class _RandomAccessIter, class _Tp, class _Compare>
williamr@2: _RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 
williamr@2:                                         _RandomAccessIter __last, 
williamr@2:                                         _Tp __pivot, _Compare __comp) 
williamr@2: {
williamr@2:   _STLP_PUSH_STACK_ITEM(_Tp, &__pivot)
williamr@2:   while (true) {
williamr@2:     while (__comp(*__first, __pivot))
williamr@2:       ++__first;
williamr@2:     --__last;
williamr@2:     while (__comp(__pivot, *__last))
williamr@2:       --__last;
williamr@2:     if (!(__first < __last))
williamr@2:       return __first;
williamr@2:     iter_swap(__first, __last);
williamr@2:     ++__first;
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: // sort() and its auxiliary functions. 
williamr@2: 
williamr@2: # define  __stl_threshold  16
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Tp, class _Compare>
williamr@2: void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, 
williamr@2:                                _Compare __comp) {
williamr@2:    _STLP_PUSH_STACK_ITEM(_Tp, &__val)
williamr@2:   _RandomAccessIter __next = __last;
williamr@2:   --__next;  
williamr@2:   while (__comp(__val, *__next)) {
williamr@2:     *__last = *__next;
williamr@2:     __last = __next;
williamr@2:     --__next;
williamr@2:   }
williamr@2:   *__last = __val;
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Tp, class _Compare>
williamr@2: inline void __linear_insert(_RandomAccessIter __first, 
williamr@2:                             _RandomAccessIter __last, _Tp __val, _Compare __comp) {
williamr@2:   _STLP_PUSH_STACK_ITEM(_Tp, &__val)
williamr@2:   if (__comp(__val, *__first)) {
williamr@2:     copy_backward(__first, __last, __last + 1);
williamr@2:     *__first = __val;
williamr@2:   }
williamr@2:   else
williamr@2:     __unguarded_linear_insert(__last, __val, __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Compare>
williamr@2: void __insertion_sort(_RandomAccessIter __first,
williamr@2:                       _RandomAccessIter __last, _Compare __comp) {
williamr@2:   if (__first == __last) return;
williamr@2:   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
williamr@2:     __linear_insert(__first, __i, *__i, __comp);	//*TY 12/26/1998 - supply *__i as __val
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Tp, class _Compare>
williamr@2: void __unguarded_insertion_sort_aux(_RandomAccessIter __first, 
williamr@2:                                     _RandomAccessIter __last,
williamr@2:                                     _Tp*, _Compare __comp) {
williamr@2:   for (_RandomAccessIter __i = __first; __i != __last; ++__i)
williamr@2:     __unguarded_linear_insert(__i, _Tp(*__i), __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Compare>
williamr@2: inline void __unguarded_insertion_sort(_RandomAccessIter __first, 
williamr@2:                                        _RandomAccessIter __last,
williamr@2:                                        _Compare __comp) {
williamr@2:   __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Compare>
williamr@2: void __final_insertion_sort(_RandomAccessIter __first, 
williamr@2:                             _RandomAccessIter __last, _Compare __comp) {
williamr@2:   if (__last - __first > __stl_threshold) {
williamr@2:     __insertion_sort(__first, __first + __stl_threshold, __comp);
williamr@2:     __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
williamr@2:   }
williamr@2:   else
williamr@2:     __insertion_sort(__first, __last, __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
williamr@2: void __introsort_loop(_RandomAccessIter __first,
williamr@2:                       _RandomAccessIter __last, _Tp*,
williamr@2:                       _Size __depth_limit, _Compare __comp)
williamr@2: {
williamr@2:   while (__last - __first > __stl_threshold) {
williamr@2:     if (__depth_limit == 0) {
williamr@2:       partial_sort(__first, __last, __last, __comp);
williamr@2:       return;
williamr@2:     }
williamr@2:     --__depth_limit;
williamr@2:     _RandomAccessIter __cut =
williamr@2:       __unguarded_partition(__first, __last,
williamr@2:                             _Tp(__median(*__first,
williamr@2:                                          *(__first + (__last - __first)/2),
williamr@2:                                          *(__last - 1), __comp)),
williamr@2:        __comp);
williamr@2:     __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
williamr@2:     __last = __cut;
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter>
williamr@2: void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first != __last) {
williamr@2:     __introsort_loop(__first, __last,
williamr@2:                      _STLP_VALUE_TYPE(__first, _RandomAccessIter),
williamr@2:                      __lg(__last - __first) * 2, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)) );
williamr@2:     __final_insertion_sort(__first, __last, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Compare>
williamr@2: void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first != __last) {
williamr@2:     __introsort_loop(__first, __last,
williamr@2:                      _STLP_VALUE_TYPE(__first, _RandomAccessIter),
williamr@2:                      __lg(__last - __first) * 2,
williamr@2:                      __comp);
williamr@2:     __final_insertion_sort(__first, __last, __comp);
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: // stable_sort() and its auxiliary functions.
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Compare>
williamr@2: void __inplace_stable_sort(_RandomAccessIter __first,
williamr@2:                            _RandomAccessIter __last, _Compare __comp) {
williamr@2:   if (__last - __first < 15) {
williamr@2:     __insertion_sort(__first, __last, __comp);
williamr@2:     return;
williamr@2:   }
williamr@2:   _RandomAccessIter __middle = __first + (__last - __first) / 2;
williamr@2:   __inplace_stable_sort(__first, __middle, __comp);
williamr@2:   __inplace_stable_sort(__middle, __last, __comp);
williamr@2:   __merge_without_buffer(__first, __middle, __last,
williamr@2:                          __middle - __first,
williamr@2:                          __last - __middle,
williamr@2:                          __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter1, class _RandomAccessIter2,
williamr@2:           class _Distance, class _Compare>
williamr@2: void __merge_sort_loop(_RandomAccessIter1 __first,
williamr@2:                        _RandomAccessIter1 __last, 
williamr@2:                        _RandomAccessIter2 __result, _Distance __step_size,
williamr@2:                        _Compare __comp) {
williamr@2:   _Distance __two_step = 2 * __step_size;
williamr@2: 
williamr@2:   while (__last - __first >= __two_step) {
williamr@2:     __result = merge(__first, __first + __step_size,
williamr@2:                      __first + __step_size, __first + __two_step,
williamr@2:                      __result,
williamr@2:                      __comp);
williamr@2:     __first += __two_step;
williamr@2:   }
williamr@2:   __step_size = (min) (_Distance(__last - __first), __step_size);
williamr@2: 
williamr@2:   merge(__first, __first + __step_size,
williamr@2:         __first + __step_size, __last,
williamr@2:         __result,
williamr@2:         __comp);
williamr@2: }
williamr@2: 
williamr@2: const int __stl_chunk_size = 7;
williamr@2:         
williamr@2: template <class _RandomAccessIter, class _Distance, class _Compare>
williamr@2: void __chunk_insertion_sort(_RandomAccessIter __first, 
williamr@2:                             _RandomAccessIter __last,
williamr@2:                             _Distance __chunk_size, _Compare __comp)
williamr@2: {
williamr@2:   while (__last - __first >= __chunk_size) {
williamr@2:     __insertion_sort(__first, __first + __chunk_size, __comp);
williamr@2:     __first += __chunk_size;
williamr@2:   }
williamr@2:   __insertion_sort(__first, __last, __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Pointer, class _Distance,
williamr@2:           class _Compare>
williamr@2: void __merge_sort_with_buffer(_RandomAccessIter __first, 
williamr@2:                               _RandomAccessIter __last, _Pointer __buffer,
williamr@2:                               _Distance*, _Compare __comp) {
williamr@2:   _Distance __len = __last - __first;
williamr@2:   _Pointer __buffer_last = __buffer + __len;
williamr@2: 
williamr@2:   _Distance __step_size = __stl_chunk_size;
williamr@2:   __chunk_insertion_sort(__first, __last, __step_size, __comp);
williamr@2: 
williamr@2:   while (__step_size < __len) {
williamr@2:     __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
williamr@2:     __step_size *= 2;
williamr@2:     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
williamr@2:     __step_size *= 2;
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter1, class _BidirectionalIter2,
williamr@2:           class _Distance>
williamr@2: _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
williamr@2:                                       _BidirectionalIter1 __middle,
williamr@2:                                       _BidirectionalIter1 __last,
williamr@2:                                       _Distance __len1, _Distance __len2,
williamr@2:                                       _BidirectionalIter2 __buffer,
williamr@2:                                       _Distance __buffer_size) {
williamr@2:   if (__len1 > __len2 && __len2 <= __buffer_size) {
williamr@2:     _BidirectionalIter2 __buffer_end = copy(__middle, __last, __buffer);
williamr@2:     copy_backward(__first, __middle, __last);
williamr@2:     return copy(__buffer, __buffer_end, __first);
williamr@2:   }
williamr@2:   else if (__len1 <= __buffer_size) {
williamr@2:     _BidirectionalIter2 __buffer_end = copy(__first, __middle, __buffer);
williamr@2:     copy(__middle, __last, __first);
williamr@2:     return copy_backward(__buffer, __buffer_end, __last);
williamr@2:   }
williamr@2:   else
williamr@2:     return rotate(__first, __middle, __last);
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter, class _Distance, class _Pointer,
williamr@2:           class _Compare>
williamr@2: void __merge_adaptive(_BidirectionalIter __first, 
williamr@2:                       _BidirectionalIter __middle, 
williamr@2:                       _BidirectionalIter __last,
williamr@2:                       _Distance __len1, _Distance __len2,
williamr@2:                       _Pointer __buffer, _Distance __buffer_size,
williamr@2:                       _Compare __comp) {
williamr@2:   if (__len1 <= __len2 && __len1 <= __buffer_size) {
williamr@2:     _Pointer __buffer_end = copy(__first, __middle, __buffer);
williamr@2:     merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
williamr@2:   }
williamr@2:   else if (__len2 <= __buffer_size) {
williamr@2:     _Pointer __buffer_end = copy(__middle, __last, __buffer);
williamr@2:     __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
williamr@2:                      __comp);
williamr@2:   }
williamr@2:   else {
williamr@2:     _BidirectionalIter __first_cut = __first;
williamr@2:     _BidirectionalIter __second_cut = __middle;
williamr@2:     _Distance __len11 = 0;
williamr@2:     _Distance __len22 = 0;
williamr@2:     if (__len1 > __len2) {
williamr@2:       __len11 = __len1 / 2;
williamr@2:       advance(__first_cut, __len11);
williamr@2:       __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
williamr@2:       __len22 += distance(__middle, __second_cut);   
williamr@2:     }
williamr@2:     else {
williamr@2:       __len22 = __len2 / 2;
williamr@2:       advance(__second_cut, __len22);
williamr@2:       __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
williamr@2:       __len11 += distance(__first, __first_cut);
williamr@2:     }
williamr@2:     _BidirectionalIter __new_middle =
williamr@2:       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
williamr@2:                         __len22, __buffer, __buffer_size);
williamr@2:     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
williamr@2:                      __len22, __buffer, __buffer_size, __comp);
williamr@2:     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
williamr@2:                      __len2 - __len22, __buffer, __buffer_size, __comp);
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Pointer, class _Distance, 
williamr@2:           class _Compare>
williamr@2: void __stable_sort_adaptive(_RandomAccessIter __first, 
williamr@2:                             _RandomAccessIter __last, _Pointer __buffer,
williamr@2:                             _Distance __buffer_size, _Compare __comp) {
williamr@2:   _Distance __len = (__last - __first + 1) / 2;
williamr@2:   _RandomAccessIter __middle = __first + __len;
williamr@2:   if (__len > __buffer_size) {
williamr@2:     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, 
williamr@2:                            __comp);
williamr@2:     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, 
williamr@2:                            __comp);
williamr@2:   }
williamr@2:   else {
williamr@2:     __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
williamr@2:                                __comp);
williamr@2:     __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
williamr@2:                                __comp);
williamr@2:   }
williamr@2:   __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 
williamr@2:                    _Distance(__last - __middle), __buffer, __buffer_size,
williamr@2:                    __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
williamr@2: void __stable_sort_aux(_RandomAccessIter __first,
williamr@2: 			      _RandomAccessIter __last, _Tp*, _Distance*,
williamr@2: 			      _Compare __comp) {
williamr@2: 
williamr@2:   typedef _Temporary_buffer<_RandomAccessIter, _Tp> _TmpBuf;
williamr@2:   _TmpBuf __buf(__first, __last);
williamr@2:   _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);
williamr@2: 
williamr@2:   if (__buf.begin() == 0)
williamr@2:     __inplace_stable_sort(__first, __last, __comp);
williamr@2:   else 
williamr@2:     __stable_sort_adaptive(__first, __last, __buf.begin(),
williamr@2:                            _Distance(__buf.size()),
williamr@2:                            __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter>
williamr@2: void stable_sort(_RandomAccessIter __first,
williamr@2: 		 _RandomAccessIter __last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   __stable_sort_aux(__first, __last,
williamr@2:                     _STLP_VALUE_TYPE(__first, _RandomAccessIter),
williamr@2:                     _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
williamr@2:                     __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Compare>
williamr@2: void stable_sort(_RandomAccessIter __first,
williamr@2: 		 _RandomAccessIter __last, _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   __stable_sort_aux(__first, __last,
williamr@2:                     _STLP_VALUE_TYPE(__first, _RandomAccessIter),
williamr@2:                     _STLP_DISTANCE_TYPE(__first, _RandomAccessIter), 
williamr@2:                     __comp);
williamr@2: }
williamr@2: 
williamr@2: // partial_sort, partial_sort_copy, and auxiliary functions.
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Tp, class _Compare>
williamr@2: void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
williamr@2:                     _RandomAccessIter __last, _Tp*, _Compare __comp) {
williamr@2:   make_heap(__first, __middle, __comp);
williamr@2:   for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
williamr@2:     if (__comp(*__i, *__first))
williamr@2:       __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
williamr@2:                  _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));
williamr@2:   sort_heap(__first, __middle, __comp);
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <class _RandomAccessIter>
williamr@2: void 
williamr@2: partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, _RandomAccessIter __last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
williamr@2:   __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), 
williamr@2:                  __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Compare>
williamr@2: void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
williamr@2:                   _RandomAccessIter __last, _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
williamr@2:   __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _RandomAccessIter, class _Compare,
williamr@2:           class _Distance, class _Tp>
williamr@2: _RandomAccessIter __partial_sort_copy(_InputIter __first,
williamr@2:                                          _InputIter __last,
williamr@2:                                          _RandomAccessIter __result_first,
williamr@2:                                          _RandomAccessIter __result_last,
williamr@2:                                          _Compare __comp, _Distance*, _Tp*) {
williamr@2:   if (__result_first == __result_last) return __result_last;
williamr@2:   _RandomAccessIter __result_real_last = __result_first;
williamr@2:   while(__first != __last && __result_real_last != __result_last) {
williamr@2:     *__result_real_last = *__first;
williamr@2:     ++__result_real_last;
williamr@2:     ++__first;
williamr@2:   }
williamr@2:   make_heap(__result_first, __result_real_last, __comp);
williamr@2:   while (__first != __last) {
williamr@2:     if (__comp(*__first, *__result_first))
williamr@2:       __adjust_heap(__result_first, _Distance(0),
williamr@2:                     _Distance(__result_real_last - __result_first),
williamr@2:                     _Tp(*__first),
williamr@2:                     __comp);
williamr@2:     ++__first;
williamr@2:   }
williamr@2:   sort_heap(__result_first, __result_real_last, __comp);
williamr@2:   return __result_real_last;
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _RandomAccessIter>
williamr@2: _RandomAccessIter
williamr@2: partial_sort_copy(_InputIter __first, _InputIter __last,
williamr@2:                   _RandomAccessIter __result_first, _RandomAccessIter __result_last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__result_first, __result_last))
williamr@2:   return __partial_sort_copy(__first, __last, __result_first, __result_last, 
williamr@2:                              __less(_STLP_VALUE_TYPE(__first, _InputIter)),
williamr@2:                              _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
williamr@2:                              _STLP_VALUE_TYPE(__first, _InputIter));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _RandomAccessIter, class _Compare>
williamr@2: _RandomAccessIter
williamr@2: partial_sort_copy(_InputIter __first, _InputIter __last,
williamr@2:                   _RandomAccessIter __result_first,
williamr@2:                   _RandomAccessIter __result_last, _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__result_first, __result_last))
williamr@2:   return __partial_sort_copy(__first, __last, __result_first, __result_last,
williamr@2:                              __comp,
williamr@2:                              _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
williamr@2:                              _STLP_VALUE_TYPE(__first, _InputIter));
williamr@2: }
williamr@2: 
williamr@2: // nth_element() and its auxiliary functions.  
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Tp, class _Compare>
williamr@2: void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
williamr@2:                    _RandomAccessIter __last, _Tp*, _Compare __comp) {
williamr@2:   while (__last - __first > 3) {
williamr@2:     _RandomAccessIter __cut =
williamr@2:       __unguarded_partition(__first, __last,
williamr@2:                             _Tp(__median(*__first,
williamr@2:                                          *(__first + (__last - __first)/2), 
williamr@2:                                          *(__last - 1),
williamr@2:                                          __comp)),
williamr@2:                             __comp);
williamr@2:     if (__cut <= __nth)
williamr@2:       __first = __cut;
williamr@2:     else 
williamr@2:       __last = __cut;
williamr@2:   }
williamr@2:   __insertion_sort(__first, __last, __comp);
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <class _RandomAccessIter>
williamr@2: void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
williamr@2:                  _RandomAccessIter __last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __nth))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__nth, __last))
williamr@2:   __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), 
williamr@2:                 __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Compare>
williamr@2: void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
williamr@2:                  _RandomAccessIter __last, _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __nth))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__nth, __last))
williamr@2:   __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
williamr@2: }
williamr@2: 
williamr@2: // Binary search (lower_bound, upper_bound, equal_range, binary_search).
williamr@2: 
williamr@2: template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
williamr@2: _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
williamr@2:                            const _Tp& __val, _Compare __comp, _Distance*)
williamr@2: {
williamr@2:   _Distance __len = distance(__first, __last);
williamr@2:   _Distance __half;
williamr@2: 
williamr@2:   while (__len > 0) {
williamr@2:     __half = __len >> 1;
williamr@2:     _ForwardIter __middle = __first;
williamr@2:     advance(__middle, __half);
williamr@2:     if (__comp(__val, *__middle))
williamr@2:       __len = __half;
williamr@2:     else {
williamr@2:       __first = __middle;
williamr@2:       ++__first;
williamr@2:       __len = __len - __half - 1;
williamr@2:     }
williamr@2:   }
williamr@2:   return __first;
williamr@2: }
williamr@2: 
williamr@2: template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
williamr@2: pair<_ForwardIter, _ForwardIter>
williamr@2: __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
williamr@2:               _Compare __comp, _Distance*)
williamr@2: {
williamr@2:   _Distance __len = distance(__first, __last);
williamr@2:   _Distance __half;
williamr@2: 
williamr@2:   while (__len > 0) {
williamr@2:     __half = __len >> 1;
williamr@2:     _ForwardIter __middle = __first;
williamr@2:     advance(__middle, __half);
williamr@2:     if (__comp(*__middle, __val)) {
williamr@2:       __first = __middle;
williamr@2:       ++__first;
williamr@2:       __len = __len - __half - 1;
williamr@2:     }
williamr@2:     else if (__comp(__val, *__middle))
williamr@2:       __len = __half;
williamr@2:     else {
williamr@2:       _ForwardIter __left = lower_bound(__first, __middle, __val, __comp);
williamr@2:       advance(__first, __len);
williamr@2:       _ForwardIter __right = upper_bound(++__middle, __first, __val, __comp);
williamr@2:       return pair<_ForwardIter, _ForwardIter>(__left, __right);
williamr@2:     }
williamr@2:   }
williamr@2:   return pair<_ForwardIter, _ForwardIter>(__first, __first);
williamr@2: }           
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter>
williamr@2: _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                   _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                   _OutputIter __result) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:   while (__first1 != __last1 && __first2 != __last2) {
williamr@2:     if (*__first2 < *__first1) {
williamr@2:       *__result = *__first2;
williamr@2:       ++__first2;
williamr@2:     }
williamr@2:     else {
williamr@2:       *__result = *__first1;
williamr@2:       ++__first1;
williamr@2:     }
williamr@2:     ++__result;
williamr@2:   }
williamr@2:   return copy(__first2, __last2, copy(__first1, __last1, __result));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter,
williamr@2:           class _Compare>
williamr@2: _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                   _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                   _OutputIter __result, _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:   while (__first1 != __last1 && __first2 != __last2) {
williamr@2:     if (__comp(*__first2, *__first1)) {
williamr@2:       *__result = *__first2;
williamr@2:       ++__first2;
williamr@2:     }
williamr@2:     else {
williamr@2:       *__result = *__first1;
williamr@2:       ++__first1;
williamr@2:     }
williamr@2:     ++__result;
williamr@2:   }
williamr@2:   return copy(__first2, __last2, copy(__first1, __last1, __result));
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter, class _Distance, class _Compare>
williamr@2: void __merge_without_buffer(_BidirectionalIter __first,
williamr@2:                             _BidirectionalIter __middle,
williamr@2:                             _BidirectionalIter __last,
williamr@2:                             _Distance __len1, _Distance __len2,
williamr@2:                             _Compare __comp) {
williamr@2:   if (__len1 == 0 || __len2 == 0)
williamr@2:     return;
williamr@2:   if (__len1 + __len2 == 2) {
williamr@2:     if (__comp(*__middle, *__first))
williamr@2:       iter_swap(__first, __middle);
williamr@2:     return;
williamr@2:   }
williamr@2:   _BidirectionalIter __first_cut = __first;
williamr@2:   _BidirectionalIter __second_cut = __middle;
williamr@2:   _Distance __len11 = 0;
williamr@2:   _Distance __len22 = 0;
williamr@2:   if (__len1 > __len2) {
williamr@2:     __len11 = __len1 / 2;
williamr@2:     advance(__first_cut, __len11);
williamr@2:     __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
williamr@2:     __len22 += distance(__middle, __second_cut);
williamr@2:   }
williamr@2:   else {
williamr@2:     __len22 = __len2 / 2;
williamr@2:     advance(__second_cut, __len22);
williamr@2:     __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
williamr@2:     __len11 +=distance(__first, __first_cut);
williamr@2:   }
williamr@2:   _BidirectionalIter __new_middle
williamr@2:     = rotate(__first_cut, __middle, __second_cut);
williamr@2:   __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
williamr@2:                          __comp);
williamr@2:   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
williamr@2:                          __len2 - __len22, __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter1, class _BidirectionalIter2,
williamr@2:           class _BidirectionalIter3, class _Compare>
williamr@2: _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
williamr@2:                                      _BidirectionalIter1 __last1,
williamr@2:                                      _BidirectionalIter2 __first2,
williamr@2:                                      _BidirectionalIter2 __last2,
williamr@2:                                      _BidirectionalIter3 __result,
williamr@2:                                      _Compare __comp) {
williamr@2:   if (__first1 == __last1)
williamr@2:     return copy_backward(__first2, __last2, __result);
williamr@2:   if (__first2 == __last2)
williamr@2:     return copy_backward(__first1, __last1, __result);
williamr@2:   --__last1;
williamr@2:   --__last2;
williamr@2:   while (true) {
williamr@2:     if (__comp(*__last2, *__last1)) {
williamr@2:       *--__result = *__last1;
williamr@2:       if (__first1 == __last1)
williamr@2:         return copy_backward(__first2, ++__last2, __result);
williamr@2:       --__last1;
williamr@2:     }
williamr@2:     else {
williamr@2:       *--__result = *__last2;
williamr@2:       if (__first2 == __last2)
williamr@2:         return copy_backward(__first1, ++__last1, __result);
williamr@2:       --__last2;
williamr@2:     }
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter, class _Tp, 
williamr@2:           class _Distance, class _Compare>
williamr@2: inline void __inplace_merge_aux(_BidirectionalIter __first,
williamr@2:                                 _BidirectionalIter __middle,
williamr@2:                                 _BidirectionalIter __last, _Tp*, _Distance*,
williamr@2:                                 _Compare __comp) {
williamr@2:   _Distance __len1 = distance(__first, __middle);
williamr@2:   _Distance __len2 = distance(__middle, __last);
williamr@2: 
williamr@2:   typedef _Temporary_buffer<_BidirectionalIter, _Tp> _TmpBuf;
williamr@2:   _TmpBuf __buf(__first, __last);
williamr@2:   _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);
williamr@2: 
williamr@2:   if (__buf.begin() == 0)
williamr@2:     __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
williamr@2:   else
williamr@2:     __merge_adaptive(__first, __middle, __last, __len1, __len2,
williamr@2:                      __buf.begin(), _Distance(__buf.size()),
williamr@2:                      __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter>
williamr@2: void inplace_merge(_BidirectionalIter __first,
williamr@2: 		   _BidirectionalIter __middle,
williamr@2: 		   _BidirectionalIter __last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
williamr@2:   if (__first == __middle || __middle == __last)
williamr@2:     return;
williamr@2:   __inplace_merge_aux(__first, __middle, __last,
williamr@2:                       _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
williamr@2:                       __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter, class _Compare>
williamr@2: void inplace_merge(_BidirectionalIter __first,
williamr@2: 		   _BidirectionalIter __middle,
williamr@2: 		   _BidirectionalIter __last, _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
williamr@2:   if (__first == __middle || __middle == __last)
williamr@2:     return;
williamr@2:   __inplace_merge_aux(__first, __middle, __last,
williamr@2:                       _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
williamr@2:                       __comp);
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _Compare>
williamr@2: bool __includes(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:   while (__first1 != __last1 && __first2 != __last2)
williamr@2:     if (__comp(*__first2, *__first1))
williamr@2:       return false;
williamr@2:     else if(__comp(*__first1, *__first2)) 
williamr@2:       ++__first1;
williamr@2:     else
williamr@2:       ++__first1, ++__first2;
williamr@2: 
williamr@2:   return __first2 == __last2;
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _Compare>
williamr@2: bool includes(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
williamr@2:   return __includes(__first1, __last1, __first2, __last2, __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2>
williamr@2: bool includes(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:               _InputIter2 __first2, _InputIter2 __last2) {
williamr@2:   return __includes(__first1, __last1, __first2, __last2, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter,
williamr@2:           class _Compare>
williamr@2: _OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                         _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                         _OutputIter __result, _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:   while (__first1 != __last1 && __first2 != __last2) {
williamr@2:     if (__comp(*__first1, *__first2)) {
williamr@2:       *__result = *__first1;
williamr@2:       ++__first1;
williamr@2:     }
williamr@2:     else if (__comp(*__first2, *__first1)) {
williamr@2:       *__result = *__first2;
williamr@2:       ++__first2;
williamr@2:     }
williamr@2:     else {
williamr@2:       *__result = *__first1;
williamr@2:       ++__first1;
williamr@2:       ++__first2;
williamr@2:     }
williamr@2:     ++__result;
williamr@2:   }
williamr@2:   return copy(__first2, __last2, copy(__first1, __last1, __result));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter>
williamr@2: _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                       _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                       _OutputIter __result) {
williamr@2:   return __set_union(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter,
williamr@2:           class _Compare>
williamr@2: _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                       _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                       _OutputIter __result, _Compare __comp) {
williamr@2:   return __set_union(__first1, __last1, __first2, __last2, __result, __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter,
williamr@2:           class _Compare>
williamr@2: _OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                                _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                                _OutputIter __result, _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:   while (__first1 != __last1 && __first2 != __last2)
williamr@2:     if (__comp(*__first1, *__first2))
williamr@2:       ++__first1;
williamr@2:     else if (__comp(*__first2, *__first1))
williamr@2:       ++__first2;
williamr@2:     else {
williamr@2:       *__result = *__first1;
williamr@2:       ++__first1;
williamr@2:       ++__first2;
williamr@2:       ++__result;
williamr@2:     }
williamr@2:   return __result;
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter>
williamr@2: _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                              _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                              _OutputIter __result) {
williamr@2:   return __set_intersection(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter,
williamr@2:           class _Compare>
williamr@2: _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                              _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                              _OutputIter __result, _Compare __comp) {
williamr@2:   return __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter, 
williamr@2:           class _Compare>
williamr@2: _OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                              _InputIter2 __first2, _InputIter2 __last2, 
williamr@2:                              _OutputIter __result, _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:   while (__first1 != __last1 && __first2 != __last2)
williamr@2:     if (__comp(*__first1, *__first2)) {
williamr@2:       *__result = *__first1;
williamr@2:       ++__first1;
williamr@2:       ++__result;
williamr@2:     }
williamr@2:     else if (__comp(*__first2, *__first1))
williamr@2:       ++__first2;
williamr@2:     else {
williamr@2:       ++__first1;
williamr@2:       ++__first2;
williamr@2:     }
williamr@2:   return copy(__first1, __last1, __result);
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter>
williamr@2: _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                            _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                            _OutputIter __result) {
williamr@2:   return __set_difference(__first1, __last1, __first2, __last2, __result, 
williamr@2:                           __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter, 
williamr@2:           class _Compare>
williamr@2: _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                            _InputIter2 __first2, _InputIter2 __last2, 
williamr@2:                            _OutputIter __result, _Compare __comp) {
williamr@2:   return __set_difference(__first1, __last1, __first2, __last2, __result, __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
williamr@2: _OutputIter 
williamr@2: __set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                            _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                            _OutputIter __result, _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:   while (__first1 != __last1 && __first2 != __last2)
williamr@2:     if (__comp(*__first1, *__first2)) {
williamr@2:       *__result = *__first1;
williamr@2:       ++__first1;
williamr@2:       ++__result;
williamr@2:     }
williamr@2:     else if (__comp(*__first2, *__first1)) {
williamr@2:       *__result = *__first2;
williamr@2:       ++__first2;
williamr@2:       ++__result;
williamr@2:     }
williamr@2:     else {
williamr@2:       ++__first1;
williamr@2:       ++__first2;
williamr@2:     }
williamr@2:   return copy(__first2, __last2, copy(__first1, __last1, __result));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter>
williamr@2: _OutputIter 
williamr@2: set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                          _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                          _OutputIter __result) {
williamr@2:   return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
williamr@2:                                     __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
williamr@2: _OutputIter 
williamr@2: set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                          _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                          _OutputIter __result,
williamr@2:                          _Compare __comp) {
williamr@2:   return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
williamr@2: }
williamr@2: 
williamr@2: // min_element and max_element, with and without an explicitly supplied
williamr@2: // comparison function.
williamr@2: 
williamr@2: template <class _ForwardIter, class _Compare>
williamr@2: _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
williamr@2:                             _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first == __last) return __first;
williamr@2:   _ForwardIter __result = __first;
williamr@2:   while (++__first != __last) 
williamr@2:     if (__comp(*__result, *__first)) __result = __first;
williamr@2:   return __result;
williamr@2: }
williamr@2: 
williamr@2: template <class _ForwardIter>
williamr@2: _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first == __last) return __first;
williamr@2:   _ForwardIter __result = __first;
williamr@2:   while (++__first != __last) 
williamr@2:     if (*__result < *__first)
williamr@2:       __result = __first;
williamr@2:   return __result;
williamr@2: }
williamr@2: 
williamr@2: template <class _ForwardIter>
williamr@2: _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first == __last) return __first;
williamr@2:   _ForwardIter __result = __first;
williamr@2:   while (++__first != __last) 
williamr@2:     if (*__first < *__result)
williamr@2:       __result = __first;
williamr@2:   return __result;
williamr@2: }
williamr@2: 
williamr@2: template <class _ForwardIter, class _Compare>
williamr@2: _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
williamr@2:                             _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first == __last) return __first;
williamr@2:   _ForwardIter __result = __first;
williamr@2:   while (++__first != __last) 
williamr@2:     if (__comp(*__first, *__result)) __result = __first;
williamr@2:   return __result;
williamr@2: }
williamr@2: 
williamr@2: // next_permutation and prev_permutation, with and without an explicitly 
williamr@2: // supplied comparison function.
williamr@2: template <class _BidirectionalIter, class _Compare>
williamr@2: bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
williamr@2:                         _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first == __last)
williamr@2:     return false;
williamr@2:   _BidirectionalIter __i = __first;
williamr@2:   ++__i;
williamr@2:   if (__i == __last)
williamr@2:     return false;
williamr@2:   __i = __last;
williamr@2:   --__i;
williamr@2: 
williamr@2:   for(;;) {
williamr@2:     _BidirectionalIter __ii = __i;
williamr@2:     --__i;
williamr@2:     if (__comp(*__i, *__ii)) {
williamr@2:       _BidirectionalIter __j = __last;
williamr@2:       while (!__comp(*__i, *--__j))
williamr@2:         {}
williamr@2:       iter_swap(__i, __j);
williamr@2:       reverse(__ii, __last);
williamr@2:       return true;
williamr@2:     }
williamr@2:     if (__i == __first) {
williamr@2:       reverse(__first, __last);
williamr@2:       return false;
williamr@2:     }
williamr@2:   }
williamr@2: #if defined(_STLP_NEED_UNREACHABLE_RETURN)
williamr@2:     return 0;
williamr@2: #endif
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter>
williamr@2: bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   return __next_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter, class _Compare>
williamr@2: bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
williamr@2:                       _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   return __next_permutation(__first, __last, __comp);
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter, class _Compare>
williamr@2: bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
williamr@2:                       _Compare __comp) {
williamr@2:   if (__first == __last)
williamr@2:     return false;
williamr@2:   _BidirectionalIter __i = __first;
williamr@2:   ++__i;
williamr@2:   if (__i == __last)
williamr@2:     return false;
williamr@2:   __i = __last;
williamr@2:   --__i;
williamr@2: 
williamr@2:   for(;;) {
williamr@2:     _BidirectionalIter __ii = __i;
williamr@2:     --__i;
williamr@2:     if (__comp(*__ii, *__i)) {
williamr@2:       _BidirectionalIter __j = __last;
williamr@2:       while (!__comp(*--__j, *__i))
williamr@2:         {}
williamr@2:       iter_swap(__i, __j);
williamr@2:       reverse(__ii, __last);
williamr@2:       return true;
williamr@2:     }
williamr@2:     if (__i == __first) {
williamr@2:       reverse(__first, __last);
williamr@2:       return false;
williamr@2:     }
williamr@2:   }
williamr@2: #if defined(_STLP_NEED_UNREACHABLE_RETURN)
williamr@2:     return 0;
williamr@2: #endif
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter>
williamr@2: bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   return __prev_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
williamr@2: }
williamr@2: 
williamr@2: template <class _BidirectionalIter, class _Compare>
williamr@2: bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
williamr@2:                       _Compare __comp) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   return __prev_permutation(__first, __last, __comp);
williamr@2: }
williamr@2: 
williamr@2: # ifndef _STLP_NO_EXTENSIONS
williamr@2: 
williamr@2: // is_heap, a predicate testing whether or not a range is
williamr@2: // a heap.  This function is an extension, not part of the C++
williamr@2: // standard.
williamr@2: 
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
williamr@2: bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
williamr@2:                _Distance __n)
williamr@2: {
williamr@2:   _Distance __parent = 0;
williamr@2:   for (_Distance __child = 1; __child < __n; ++__child) {
williamr@2:     if (__comp(__first[__parent], __first[__child]))
williamr@2:       return false;
williamr@2:     if ((__child & 1) == 0)
williamr@2:       ++__parent;
williamr@2:   }
williamr@2:   return true;
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter>
williamr@2: bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
williamr@2: {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   return __is_heap(__first, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first);
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _StrictWeakOrdering>
williamr@2: bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
williamr@2: 	     _StrictWeakOrdering __comp)
williamr@2: {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   return __is_heap(__first, __comp, __last - __first);
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <class _ForwardIter, class _StrictWeakOrdering>
williamr@2: bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
williamr@2:                  _StrictWeakOrdering __comp)
williamr@2: {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   if (__first == __last)
williamr@2:     return true;
williamr@2: 
williamr@2:   _ForwardIter __next = __first;
williamr@2:   for (++__next; __next != __last; __first = __next, ++__next) {
williamr@2:     if (__comp(*__next, *__first))
williamr@2:       return false;
williamr@2:   }
williamr@2: 
williamr@2:   return true;
williamr@2: }
williamr@2: 
williamr@2: # endif /* _STLP_NO_EXTENSIONS */
williamr@2: 
williamr@2: _STLP_END_NAMESPACE
williamr@2: 
williamr@2: # undef __stl_threshold
williamr@2: 
williamr@2: #endif /* _STLP_ALGO_C */
williamr@2: // Local Variables:
williamr@2: // mode:C++
williamr@2: // End: