/*

 *

 * 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

#ifndef _STLP_INTERNAL_TEMPBUF_H

#  include <stl/_tempbuf.h>

#endif

_STLP_BEGIN_NAMESPACE

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _BidirectionalIter, class _Distance, class _Compare>

void __merge_without_buffer(_BidirectionalIter __first,

                            _BidirectionalIter __middle,

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

    _STLP_VERBOSE_ASSERT(!__comp(__b, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

    if (__comp(__b, __c)) {

      _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

      return __b;

    }

    else if (__comp(__a, __c)) {

      _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

      return __c;

    }

    else

      return __a;

  }

  else if (__comp(__a, __c)) {

    _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

    return __a;

  }

  else if (__comp(__b, __c)) {

    _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)

    return __c;

  }

  else

    return __b;

}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _ForwardIter1, class _ForwardIter2>

_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,

                     _ForwardIter2 __first2, _ForwardIter2 __last2) {

  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

  // Test for empty ranges

  if (__first1 == __last1 || __first2 == __last2)

    return __first1;

  // Test for a pattern of length 1.

  _ForwardIter2 __p1(__first2);

  if ( ++__p1 == __last2 )

    return find(__first1, __last1, *__first2);

  // General case.

  for ( ; ; ) { // __first1 != __last1 will be checked in find below

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

    if (__first1 == __last1)

      return __last1;

    _ForwardIter2 __p = __p1;

    _ForwardIter1 __current = __first1;

    if (++__current == __last1)

      return __last1;

    while (*__current == *__p) {

      if (++__p == __last2)

        return __first1;

      if (++__current == __last1)

        return __last1;

    }

    ++__first1;

  }

  return __first1;

}

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _RandomAccessIter, class _Integer, class _Tp,

          class _BinaryPred, class _Distance>

_RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last,

                             _Integer __count, const _Tp& __val, _BinaryPred __pred,

                             _Distance*, const random_access_iterator_tag &)

{

  _Distance __tailSize = __last - __first;

  const _Distance __pattSize = __count;

  const _Distance __skipOffset = __pattSize - 1;

  _RandomAccessIter __backTrack;

  _Distance __remainder, __prevRemainder;

  for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) { // the main loop...

    //__lookAhead here is always pointing to the last element of next possible match.

    __tailSize -= __pattSize;

    while ( !__pred(*__lookAhead, __val) ) { // the skip loop...

      if (__tailSize < __pattSize)

        return __last;

      __lookAhead += __pattSize;

      __tailSize -= __pattSize;

    }

    if ( __skipOffset == 0 ) {

      return (__lookAhead - __skipOffset); //Success

    }

    __remainder = __skipOffset;

    for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) {

      if (--__remainder == 0)

        return (__lookAhead - __skipOffset); //Success

    }

    if (__remainder > __tailSize)

      return __last; //failure

    __lookAhead += __remainder;

    __tailSize -= __remainder;

    while ( __pred(*__lookAhead, __val) ) {

      __prevRemainder = __remainder;

      __backTrack = __lookAhead;

      do {

        if (--__remainder == 0)

          return (__lookAhead - __skipOffset); //Success

      } while (__pred(*--__backTrack, __val));

      //adjust remainder for next comparison

      __remainder += __pattSize - __prevRemainder;

      if (__remainder > __tailSize)

        return __last; //failure

      __lookAhead += __remainder;

      __tailSize -= __remainder;

    }

    //__lookAhead here is always pointing to the element of the last mismatch.

  }

  return __last; //failure

}

template <class _ForwardIter, class _Integer, class _Tp,

          class _Distance, class _BinaryPred>

_ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last,

                        _Integer __count, const _Tp& __val, _BinaryPred __pred,

                        _Distance*, const forward_iterator_tag &) {

  for (; (__first != __last) && !__pred(*__first, __val); ++__first) {}

  while (__first != __last) {

    _Integer __n = __count - 1;

    _ForwardIter __i = __first;

    ++__i;

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

      ++__i;

      --__n;

    }

    if (__n == 0)

      return __first;

    else if (__i != __last)

      for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {}

    else

      break;

  }

  return __last;

}

_STLP_MOVE_TO_STD_NAMESPACE

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

template <class _ForwardIter, class _Integer, class _Tp>

_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,

                      _Integer __count, const _Tp& __val) {

  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  if (__count <= 0)

    return __first;

  if (__count == 1)

    //We use find when __count == 1 to use potential find overload.

    return find(__first, __last, __val);

  return _STLP_PRIV __search_n(__first, __last, __count, __val, equal_to<_Tp>(),

                               _STLP_DISTANCE_TYPE(__first, _ForwardIter),

                               _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

}

template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>

_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,

                      _Integer __count, const _Tp& __val,

                      _BinaryPred __binary_pred) {

  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  if (__count <= 0)

    return __first;

  return _STLP_PRIV __search_n(__first, __last, __count, __val, __binary_pred,

                               _STLP_DISTANCE_TYPE(__first, _ForwardIter),

                               _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

}

template <class _ForwardIter1, class _ForwardIter2>

_ForwardIter1

find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,

         _ForwardIter2 __first2, _ForwardIter2 __last2) {

  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))

  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))

  return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,

#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)

                               _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),

                               _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),

#else

                               forward_iterator_tag(),

                               forward_iterator_tag(),

#endif

                               _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))

    );

}

// unique and unique_copy

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,

          class _Tp>

_STLP_INLINE_LOOP _OutputIterator

__unique_copy(_InputIterator __first, _InputIterator __last,

              _OutputIterator __result,

              _BinaryPredicate __binary_pred, _Tp*) {

  _Tp __val = *__first;

  *__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 */

_STLP_MOVE_TO_STD_NAMESPACE

template <class _InputIter, class _OutputIter>

_OutputIter

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

  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  if (__first == __last) return __result;

  return _STLP_PRIV __unique_copy(__first, __last, __result,

                                  _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),

                                  _STLP_ITERATOR_CATEGORY(__result, _OutputIter));

}

template <class _InputIter, class _OutputIter, class _BinaryPredicate>

_OutputIter

unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,

            _BinaryPredicate __binary_pred) {

  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))

  if (__first == __last) return __result;

  return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred,

                                  _STLP_ITERATOR_CATEGORY(__result, _OutputIter));

}

// rotate and rotate_copy, and their auxiliary functions

_STLP_MOVE_TO_PRIV_NAMESPACE

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 _BidirectionalIter, class _Distance>

_BidirectionalIter __rotate_aux(_BidirectionalIter __first,

                                _BidirectionalIter __middle,

                                _BidirectionalIter __last,

                                _Distance*,

                                const bidirectional_iterator_tag &) {

  if (__first == __middle)

    return __last;

  if (__last  == __middle)

    return __first;

  __reverse(__first,  __middle, bidirectional_iterator_tag());

  __reverse(__middle, __last,   bidirectional_iterator_tag());

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

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

  if (__first == __middle) {

    __reverse(__middle, __last,   bidirectional_iterator_tag());

    return __last;

  }

  else {

    __reverse(__first,  __middle, bidirectional_iterator_tag());

    return __first;

  }

}

template <class _RandomAccessIter, class _Distance, class _Tp>

_RandomAccessIter __rotate_aux(_RandomAccessIter __first,

                               _RandomAccessIter __middle,

                               _RandomAccessIter __last,

                               _Distance *, _Tp *) {

  _Distance __n = __last   - __first;

  _Distance __k = __middle - __first;

  _Distance __l = __n - __k;

  _RandomAccessIter __result = __first + (__last - __middle);

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

    return __last;

  if (__k == __l) {

    swap_ranges(__first, __middle, __middle);

    return __result;

  }

  _Distance __d = __gcd(__n, __k);

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

    _Tp __tmp = *__first;

    _RandomAccessIter __p = __first;

    if (__k < __l) {

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

        if (__p > __first + __l) {

          *__p = *(__p - __l);

          __p -= __l;

        }

        *__p = *(__p + __k);

        __p += __k;

      }

    }

    else {

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

        if (__p < __last - __k) {

          *__p = *(__p + __k);

          __p += __k;

        }

        *__p = * (__p - __l);

        __p -= __l;

      }

    }

    *__p = __tmp;

    ++__first;

  }

  return __result;

}

template <class _RandomAccessIter, class _Distance>

inline _RandomAccessIter

__rotate_aux(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,

             _Distance * __dis, const random_access_iterator_tag &) {

  return __rotate_aux(__first, __middle, __last,

                      __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));

}

template <class _ForwardIter>

_ForwardIter

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

  _STLP_DEBUG_CHECK(__check_range(__first, __middle))

  _STLP_DEBUG_CHECK(__check_range(__middle, __last))

  return __rotate_aux(__first, __middle, __last,

                      _STLP_DISTANCE_TYPE(__first, _ForwardIter),

                      _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));

}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _ForwardIter>

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

  _STLP_PRIV __rotate(__first, __middle, __last);

}

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

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

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

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _Distance>

inline _Distance __random_number(_Distance __n) {

#ifdef _STLP_NO_DRAND48

  return rand() % __n;

#else

  return lrand48() % __n;

#endif

}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _RandomAccessIter>

void random_shuffle(_RandomAccessIter __first,

                    _RandomAccessIter __last) {

  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))