/*

 *

 * Copyright (c) 1994

 * Hewlett-Packard Company

 *

 * Copyright (c) 1996,1997

 * Silicon Graphics Computer Systems, Inc.

 *

 * Copyright (c) 1997

 * Moscow Center for SPARC Technology

 *

 * Copyright (c) 1999 

 * Boris Fomitchev

 *

 * This material is provided "as is", with absolutely no warranty expressed

 * or implied. Any use is at your own risk.

 *

 * Permission to use or copy this software for any purpose is hereby granted 

 * without fee, provided the above notices are retained on all copies.

 * Permission to modify the code and to distribute modified code is granted,

 * provided the above notices are retained, and a notice that the code was

 * modified is included with the above copyright notice.

 *

 */

#ifndef _STLP_ALGO_C

# define _STLP_ALGO_C

# if !defined (_STLP_INTERNAL_ALGO_H)

#  include <stl/_algo.h>

# endif

_STLP_BEGIN_NAMESPACE

template <class _BidirectionalIter, class _Distance, class _Compare>

void __merge_without_buffer(_BidirectionalIter __first,

                            _BidirectionalIter __middle,

                            _BidirectionalIter __last,

                            _Distance __len1, _Distance __len2,

                            _Compare __comp);

template <class _BidirectionalIter1, class _BidirectionalIter2,

          class _BidirectionalIter3, class _Compare>

_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,

                                     _BidirectionalIter1 __last1,

                                     _BidirectionalIter2 __first2,

                                     _BidirectionalIter2 __last2,

                                     _BidirectionalIter3 __result,

                                     _Compare __comp);

template <class _Tp>

# if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))

inline 

# endif

const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {

  if (__a < __b)

    if (__b < __c)

      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>

# if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))

inline 

# endif

const _Tp&

__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {

  if (__comp(__a, __b))

    if (__comp(__b, __c))

      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;

}

template <class _ForwardIter1, class _ForwardIter2>

_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,

                     _ForwardIter2 __first2, _ForwardIter2 __last2) 

{

  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

  // 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 = __first2; 

  ++__p1;

  _ForwardIter1 __current = __first1;

  while (__first1 != __last1) {

    __first1 = find(__first1, __last1, *__first2);

    if (__first1 == __last1)

      return __last1;

    _ForwardIter2 __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;

}

// search_n.  Search for __count consecutive copies of __val.

template <class _ForwardIter, class _Integer, class _Tp>

_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,

                      _Integer __count, const _Tp& __val) {

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  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) {

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  if (__count <= 0)

    return __first;

  else {

    while (__first != __last) {

      if (__binary_pred(*__first, __val))

        break;

      ++__first;

    }

    while (__first != __last) {

      _Integer __n = __count - 1;

      _ForwardIter __i = __first;

      ++__i;

      while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {

        ++__i;

        --__n;

      }

      if (__n == 0)

        return __first;

      else {

        while (__i != __last) {

          if (__binary_pred(*__i, __val))

            break;

          ++__i;

        }

        __first = __i;

      }

    }

    return __last;

  }

} 

template <class _ForwardIter1, class _ForwardIter2>

_ForwardIter1 

find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 

         _ForwardIter2 __first2, _ForwardIter2 __last2)

{

  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))

  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))

  return __find_end(__first1, __last1, __first2, __last2,

# if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)

                    _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),

                    _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),

# else

		    forward_iterator_tag(),

                    forward_iterator_tag(),

# endif

                    __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))

    );

}

// unique and unique_copy

template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,

					    class _Tp>

_STLP_INLINE_LOOP _OutputIterator 

__unique_copy(_InputIterator __first, _InputIterator __last,

              _OutputIterator __result,

              _BinaryPredicate __binary_pred, _Tp*) {

  _Tp __val = *__first;

 _STLP_PUSH_STACK_ITEM(_Tp, &__val)

  *__result = __val;

  while (++__first != __last)

    if (!__binary_pred(__val, *__first)) {

      __val = *__first;

      *++__result = __val;

    }

  return ++__result;

}

template <class _InputIter, class _OutputIter, class _BinaryPredicate>

inline _OutputIter 

__unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,

              _BinaryPredicate __binary_pred, const output_iterator_tag &) {

  return __unique_copy(__first, __last, __result, __binary_pred, _STLP_VALUE_TYPE(__first, _InputIter));

}

template <class _InputIter, class _ForwardIter, class _BinaryPredicate>

_STLP_INLINE_LOOP _ForwardIter 

__unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, 

              _BinaryPredicate __binary_pred, const forward_iterator_tag &) {

  *__result = *__first;

  while (++__first != __last)

    if (!__binary_pred(*__result, *__first)) *++__result = *__first;

  return ++__result;

}

# if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)

template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate>

inline _BidirectionalIterator 

__unique_copy(_InputIterator __first, _InputIterator __last,

              _BidirectionalIterator __result, _BinaryPredicate __binary_pred,

              const bidirectional_iterator_tag &) {

  return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());

}

template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate>

inline _RandomAccessIterator 

__unique_copy(_InputIterator __first, _InputIterator __last,

              _RandomAccessIterator __result, _BinaryPredicate __binary_pred,

              const random_access_iterator_tag &) {

  return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());

}

# endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */

template <class _InputIter, class _OutputIter>

_OutputIter 

unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  if (__first == __last) return __result;

  return __unique_copy(__first, __last, __result, __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),

                       _STLP_ITERATOR_CATEGORY(__result, _OutputIter));

}

template <class _InputIter, class _OutputIter, class _BinaryPredicate>

_OutputIter 

unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,

            _BinaryPredicate __binary_pred) {

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  if (__first == __last) return __result;

  return __unique_copy(__first, __last, __result, __binary_pred,

                       _STLP_ITERATOR_CATEGORY(__result, _OutputIter));

}

// rotate and rotate_copy, and their auxiliary functions

template <class _ForwardIter, class _Distance>

_ForwardIter __rotate(_ForwardIter __first,

                      _ForwardIter __middle,

                      _ForwardIter __last,

                      _Distance*,

                      const forward_iterator_tag &) {

  if (__first == __middle)

    return __last;

  if (__last  == __middle)

    return __first;

  _ForwardIter __first2 = __middle;

  do {

    swap(*__first++, *__first2++);

    if (__first == __middle)

      __middle = __first2;

  } while (__first2 != __last);

  _ForwardIter __new_middle = __first;

  __first2 = __middle;

  while (__first2 != __last) {

    swap (*__first++, *__first2++);

    if (__first == __middle)

      __middle = __first2;

    else if (__first2 == __last)

      __first2 = __middle;

  }

  return __new_middle;

}

template <class _BidirectionalIter, class _Distance>

_BidirectionalIter __rotate(_BidirectionalIter __first,

                            _BidirectionalIter __middle,

                            _BidirectionalIter __last,

                            _Distance*,

                            const bidirectional_iterator_tag &) {

  if (__first == __middle)

    return __last;

  if (__last  == __middle)

    return __first;

  __reverse(__first,  __middle, bidirectional_iterator_tag());

  __reverse(__middle, __last,   bidirectional_iterator_tag());

  while (__first != __middle && __middle != __last)

    swap (*__first++, *--__last);

  if (__first == __middle) {

    __reverse(__middle, __last,   bidirectional_iterator_tag());

    return __last;

  }

  else {

    __reverse(__first,  __middle, bidirectional_iterator_tag());

    return __first;

  }

}

template <class _RandomAccessIter, class _Distance, class _Tp>

_RandomAccessIter __rotate(_RandomAccessIter __first,

                           _RandomAccessIter __middle,

                           _RandomAccessIter __last,

                           _Distance *, _Tp *) {

  _Distance __n = __last   - __first;

  _Distance __k = __middle - __first;

  _Distance __l = __n - __k;

  _RandomAccessIter __result = __first + (__last - __middle);

  if (__k==0)  /* __first == middle */

    return __last;

  if (__k == __l) {

    swap_ranges(__first, __middle, __middle);

    return __result;

  }

  _Distance __d = __gcd(__n, __k);

  for (_Distance __i = 0; __i < __d; __i++) {

    _Tp __tmp = *__first;

    _STLP_PUSH_STACK_ITEM(_Tp, &__tmp)

    _RandomAccessIter __p = __first;

    if (__k < __l) {

      for (_Distance __j = 0; __j < __l/__d; __j++) {

	if (__p > __first + __l) {

          *__p = *(__p - __l);

          __p -= __l;

        }

        *__p = *(__p + __k);

        __p += __k;

      }

    }

    else {

      for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {

        if (__p < __last - __k) {

          *__p = *(__p + __k);

          __p += __k;

        }

        *__p = * (__p - __l);

        __p -= __l;

      }

    }

    *__p = __tmp;

    ++__first;

  }

  return __result;

}

template <class _RandomAccessIter, class _Distance>

inline _RandomAccessIter 

__rotate(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,

         _Distance * __dis, const random_access_iterator_tag &) {

  return __rotate(__first, __middle, __last,

                  __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));

}

template <class _ForwardIter>

_ForwardIter 

rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {

  _STLP_DEBUG_CHECK(__check_range(__first, __middle))

  _STLP_DEBUG_CHECK(__check_range(__middle, __last))

  return __rotate(__first, __middle, __last,

                  _STLP_DISTANCE_TYPE(__first, _ForwardIter),

                  _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

}

// Return a random number in the range [0, __n).  This function encapsulates

// whether we're using rand (part of the standard C library) or lrand48

// (not standard, but a much better choice whenever it's available).

template <class _Distance>

inline _Distance __random_number(_Distance __n) {

#ifdef _STLP_NO_DRAND48

  return rand() % __n;

#else

  return lrand48() % __n;

#endif

}

template <class _RandomAccessIter>

void random_shuffle(_RandomAccessIter __first,

		    _RandomAccessIter __last) {

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  if (__first == __last) return;

  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)

    iter_swap(__i, __first + __random_number((__i - __first) + 1));

}

template <class _RandomAccessIter, class _RandomNumberGenerator>

void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,

                    _RandomNumberGenerator& __rand) {

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  if (__first == __last) return;

  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)

    iter_swap(__i, __first + __rand((__i - __first) + 1));

}

# ifndef _STLP_NO_EXTENSIONS

// random_sample and random_sample_n (extensions, not part of the standard).

template <class _ForwardIter, class _OutputIter, class _Distance>

_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,

                            _OutputIter __stl_out, const _Distance __n)

{

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  _Distance __remaining = distance(__first, __last);

  _Distance __m = (min) (__n, __remaining);

  while (__m > 0) {

    if (__random_number(__remaining) < __m) {

      *__stl_out = *__first;

      ++__stl_out;

      --__m;

    }

    --__remaining;

    ++__first;

  }

  return __stl_out;

}

template <class _ForwardIter, class _OutputIter, class _Distance,

          class _RandomNumberGenerator>

_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,

                            _OutputIter __stl_out, const _Distance __n,

                            _RandomNumberGenerator& __rand)

{

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  _Distance __remaining = distance(__first, __last);

  _Distance __m = (min) (__n, __remaining);

  while (__m > 0) {

    if (__rand(__remaining) < __m) {

      *__stl_out = *__first;

      ++__stl_out;

      --__m;

    }

    --__remaining;

    ++__first;

  }

  return __stl_out;

}

template <class _InputIter, class _RandomAccessIter, class _Distance>

_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,

                                  _RandomAccessIter __stl_out,

                                  const _Distance __n)

{

  _Distance __m = 0;

  _Distance __t = __n;

  for ( ; __first != __last && __m < __n; ++__m, ++__first) 

    __stl_out[__m] = *__first;

  while (__first != __last) {

    ++__t;

    _Distance __M = __random_number(__t);

    if (__M < __n)

      __stl_out[__M] = *__first;

    ++__first;

  }

  return __stl_out + __m;

}

template <class _InputIter, class _RandomAccessIter,

          class _RandomNumberGenerator, class _Distance>

_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,

                                  _RandomAccessIter __stl_out,

                                  _RandomNumberGenerator& __rand,

                                  const _Distance __n)

{

  _Distance __m = 0;

  _Distance __t = __n;

  for ( ; __first != __last && __m < __n; ++__m, ++__first)

    __stl_out[__m] = *__first;

  while (__first != __last) {

    ++__t;

    _Distance __M = __rand(__t);

    if (__M < __n)

      __stl_out[__M] = *__first;

    ++__first;

  }

  return __stl_out + __m;

}

template <class _InputIter, class _RandomAccessIter>

_RandomAccessIter

random_sample(_InputIter __first, _InputIter __last,

              _RandomAccessIter __out_first, _RandomAccessIter __out_last) 

{

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last))

  return __random_sample(__first, __last,

                         __out_first, __out_last - __out_first);

}

template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>

_RandomAccessIter

random_sample(_InputIter __first, _InputIter __last,

              _RandomAccessIter __out_first, _RandomAccessIter __out_last,

              _RandomNumberGenerator& __rand) 

{

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last))

  return __random_sample(__first, __last,

                         __out_first, __rand,

                         __out_last - __out_first);

}

# endif /* _STLP_NO_EXTENSIONS */

// partition, stable_partition, and their auxiliary functions

template <class _ForwardIter, class _Predicate>

_STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,

                                           _ForwardIter __last,

                                           _Predicate   __pred,

                                           const forward_iterator_tag &) {

  if (__first == __last) return __first;

  while (__pred(*__first))

    if (++__first == __last) return __first;

  _ForwardIter __next = __first;

  while (++__next != __last)

    if (__pred(*__next)) {

      swap(*__first, *__next);

      ++__first;

    }

  return __first;

}

/* bug fix- start*/

template <class _ForwardIter>

_ForwardIter

__rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {

  _STLP_DEBUG_CHECK(__check_range(__first, __middle))

  _STLP_DEBUG_CHECK(__check_range(__middle, __last))

  return __rotate_aux(__first, __middle, __last,

                      _STLP_DISTANCE_TYPE(__first, _ForwardIter),

                      _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

}

template <class _ForwardIter, class _Distance>

_ForwardIter __rotate_aux(_ForwardIter __first,

                          _ForwardIter __middle,

                          _ForwardIter __last,

                          _Distance*,

                          const forward_iterator_tag &) {

  if (__first == __middle)

    return __last;

  if (__last  == __middle)

    return __first;

  _ForwardIter __first2 = __middle;

  do {

    swap(*__first++, *__first2++);

    if (__first == __middle)

      __middle = __first2;

  } while (__first2 != __last);

  _ForwardIter __new_middle = __first;

  __first2 = __middle;

  while (__first2 != __last) {

    swap (*__first++, *__first2++);

    if (__first == __middle)

      __middle = __first2;

    else if (__first2 == __last)

      __first2 = __middle;

  }

  return __new_middle;

}

template <class _ForwardIter, class _Pointer, class _Predicate,

          class _Distance>

_ForwardIter __stable_partition_adaptive(_ForwardIter __first,

                                         _ForwardIter __last,

                                         _Predicate __pred, _Distance __len,

                                         _Pointer __buffer, _Distance __buffer_size,

                                         bool __pred_of_first, bool __pred_of_before_last) {

  if (__len <= __buffer_size) {

    _ForwardIter __result1 = __first;

    _Pointer __result2 = __buffer;

    if ((__first != __last) && (!__pred_of_first || __pred(*__first))) {

      *__result2 = *__first;

      ++__result2; ++__first; --__len;

    }

    for (; __first != __last ; ++__first, --__len) {

      if (((__len == 1) && (__pred_of_before_last || __pred(*__first))) ||

          ((__len != 1) && __pred(*__first))){

        *__result1 = *__first;

        ++__result1;

      }

      else {

        *__result2 = *__first;

        ++__result2;

      }

    }

    copy(__buffer, __result2, __result1);

    return __result1;

  }

  else {

    _ForwardIter __middle = __first;

    _Distance __half_len = __len / 2;

    advance(__middle, __half_len);

    return __rotate(__stable_partition_adaptive(

                          __first, __middle, __pred,

                          __half_len, __buffer, __buffer_size,

                          __pred_of_first, false),

                    __middle,

                    __stable_partition_adaptive(

                          __middle, __last, __pred,

                          __len - __half_len, __buffer, __buffer_size,

                          true, __pred_of_before_last));

  }

}

template <class _ForwardIter, class _Predicate, class _Distance>

_ForwardIter __inplace_stable_partition(_ForwardIter __first,

                                        _ForwardIter __last,

                                        _Predicate __pred, _Distance __len,

                                        bool __pred_of_first, bool __pred_of_before_last) {

  if (__len == 1)

    return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first;

  _ForwardIter __middle = __first;

  _Distance __half_len = __len / 2;

  advance(__middle, __half_len);

  return __rotate(__inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false),

                  __middle,

                  __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last));

}

template <class _ForwardIter, class _Predicate>

_ForwardIter

stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {

  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  for (;;) {

    if (__first == __last)

      return __first;

    else if (__pred(*__first))

      ++__first;

    else

      break;

  }

  return  __stable_partition_aux(__first, __last, __pred,

                                           _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

}

template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>

inline _ForwardIter

__stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,

                           _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last = false) {

  _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);

  return (__buf.size() > 0) ?

    __stable_partition_adaptive(__first, __last, __pred,

                                _Distance(__buf.requested_size()),

                                __buf.begin(), __buf.size(),

                                false, __pred_of_before_last)  :

    __inplace_stable_partition(__first, __last, __pred,

                               _Distance(__buf.requested_size()),

                               false, __pred_of_before_last);

}

template <class _ForwardIter, class _Predicate>

_ForwardIter

__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred,

                       const forward_iterator_tag &) {

  return __stable_partition_aux_aux(__first, __last, __pred,

                                    _STLP_VALUE_TYPE(__first, _ForwardIter),

                                    _STLP_DISTANCE_TYPE(__first, _ForwardIter));

}

/* bug fix- end*/

template <class _BidirectionalIter, class _Predicate>

_STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,

                                                 _BidirectionalIter __last,

                                                 _Predicate __pred,

                                                 const bidirectional_iterator_tag &) {

  while (true) {

    while (true)

      if (__first == __last)

        return __first;

      else if (__pred(*__first))

        ++__first;

      else

        break;

    --__last;

    while (true)

      if (__first == __last)

        return __first;

      else if (!__pred(*__last))

        --__last;

      else

        break;

    iter_swap(__first, __last);

    ++__first;

  }

}

# if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)

template <class _BidirectionalIter, class _Predicate>

inline

_BidirectionalIter __partition(_BidirectionalIter __first,

                               _BidirectionalIter __last,

			       _Predicate __pred,

			       const random_access_iterator_tag &) {

  return __partition(__first, __last, __pred, bidirectional_iterator_tag());

}

# endif

template <class _ForwardIter, class _Predicate>

_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate   __pred) {

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  return __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

}

/*

template <class _ForwardIter, class _Predicate, class _Distance>

_ForwardIter __inplace_stable_partition(_ForwardIter __first,

                                        _ForwardIter __last,

                                        _Predicate __pred, _Distance __len) {

  if (__len == 1)

    return __pred(*__first) ? __last : __first;

  _ForwardIter __middle = __first;

  advance(__middle, __len / 2);

  return rotate(__inplace_stable_partition(__first, __middle, __pred, 

                                           __len / 2),

                __middle,

                __inplace_stable_partition(__middle, __last, __pred,

                                           __len - __len / 2));

}

template <class _ForwardIter, class _Pointer, class _Predicate, 

          class _Distance>

_ForwardIter __stable_partition_adaptive(_ForwardIter __first,

                                         _ForwardIter __last,

                                         _Predicate __pred, _Distance __len,

                                         _Pointer __buffer,

                                         _Distance __buffer_size) 

{

  if (__len <= __buffer_size) {

    _ForwardIter __result1 = __first;

    _Pointer __result2 = __buffer;

    for ( ; __first != __last ; ++__first)

      if (__pred(*__first)) {

        *__result1 = *__first;

        ++__result1;

      }

      else {

        *__result2 = *__first;

        ++__result2;

      }

    copy(__buffer, __result2, __result1);

    return __result1;

  }

  else {

    _ForwardIter __middle = __first;

    advance(__middle, __len / 2);

    return rotate(__stable_partition_adaptive(

                          __first, __middle, __pred,

                          _Distance(__len / 2), __buffer, __buffer_size),

                    __middle,

                    __stable_partition_adaptive(

                          __middle, __last, __pred,

                          _Distance(__len - __len / 2), __buffer, __buffer_size));

  }

}

*/ //bug fix

template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>

inline _ForwardIter

__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, 

                       _Predicate __pred, _Tp*, _Distance*)

{

  typedef _Temporary_buffer<_ForwardIter, _Tp> _TmpBuf;

  _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);

  _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);

  _STLP_MPWFIX_TRY		//*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present

  return (__buf.size() > 0) ?

    __stable_partition_adaptive(__first, __last, __pred,

				_Distance(__buf.requested_size()),

				__buf.begin(), _Distance(__buf.size()))  :

    __inplace_stable_partition(__first, __last, __pred, 

			       _Distance(__buf.requested_size()));

  _STLP_MPWFIX_CATCH	//*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present

}

/*

template <class _ForwardIter, class _Predicate>

_ForwardIter 

stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  if (__first == __last)

    return __first;

  else

    return __stable_partition_aux(__first, __last, __pred,

                                  _STLP_VALUE_TYPE(__first, _ForwardIter),

                                  _STLP_DISTANCE_TYPE(__first, _ForwardIter));

}

*/ //bug fix

template <class _RandomAccessIter, class _Tp, class _Compare>

_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 

                                        _RandomAccessIter __last, 

                                        _Tp __pivot, _Compare __comp) 

{

  _STLP_PUSH_STACK_ITEM(_Tp, &__pivot)

  while (true) {

    while (__comp(*__first, __pivot))

      ++__first;

    --__last;

    while (__comp(__pivot, *__last))

      --__last;

    if (!(__first < __last))

      return __first;

    iter_swap(__first, __last);

    ++__first;

  }

}

// sort() and its auxiliary functions. 

# define  __stl_threshold  16

template <class _RandomAccessIter, class _Tp, class _Compare>

void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, 

                               _Compare __comp) {

   _STLP_PUSH_STACK_ITEM(_Tp, &__val)

  _RandomAccessIter __next = __last;

  --__next;  

  while (__comp(__val, *__next)) {

    *__last = *__next;

    __last = __next;

    --__next;

  }

  *__last = __val;

}

template <class _RandomAccessIter, class _Tp, class _Compare>

inline void __linear_insert(_RandomAccessIter __first, 

                            _RandomAccessIter __last, _Tp __val, _Compare __comp) {

  _STLP_PUSH_STACK_ITEM(_Tp, &__val)

  if (__comp(__val, *__first)) {

    copy_backward(__first, __last, __last + 1);

    *__first = __val;

  }

  else

    __unguarded_linear_insert(__last, __val, __comp);

}

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, *__i, __comp);	//*TY 12/26/1998 - supply *__i as __val

}

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, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);

}

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 _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>

void sort(_RandomAccessIter __first, _RandomAccessIter __last) {

  _STLP_DEBUG_CHECK(__check_range(__first, __last))

  if (__first != __last) {

    __introsort_loop(__first, __last,

                     _STLP_VALUE_TYPE(__first, _RandomAccessIter),

                     __lg(__last - __first) * 2, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)) );