/* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation.  Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose.  It is provided "as is" without express or implied warranty. * * * Copyright (c) 1996 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation.  Silicon Graphics makes no * representations about the suitability of this software for any * purpose.  It is provided "as is" without express or implied warranty. *//* NOTE: This is an internal header file, included by other STL headers. *   You should not attempt to use it directly. */#ifndef __SGI_STL_INTERNAL_ALGO_H#define __SGI_STL_INTERNAL_ALGO_H#include <stl_heap.h>// See concept_checks.h for the concept-checking macros // __STL_REQUIRES, __STL_CONVERTIBLE, etc.__STL_BEGIN_NAMESPACE#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)#pragma set woff 1209#endif// __median (an extension, not present in the C++ standard).template <class _Tp>inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {  __STL_REQUIRES(_Tp, _LessThanComparable);  if (__a < __b)    if (__b < __c)      return __b;    else if (__a < __c)      return __c;    else      return __a;  else if (__a < __c)    return __a;  else if (__b < __c)    return __c;  else    return __b;}template <class _Tp, class _Compare>inline const _Tp&__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {  __STL_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);  if (__comp(__a, __b))    if (__comp(__b, __c))      return __b;    else if (__comp(__a, __c))      return __c;    else      return __a;  else if (__comp(__a, __c))    return __a;  else if (__comp(__b, __c))    return __c;  else    return __b;}// for_each.  Apply a function to every element of a range.template <class _InputIter, class _Function>_Function for_each(_InputIter __first, _InputIter __last, _Function __f) {  __STL_REQUIRES(_InputIter, _InputIterator);  for ( ; __first != __last; ++__first)    __f(*__first);  return __f;}// find and find_if.template <class _InputIter, class _Tp>inline _InputIter find(_InputIter __first, _InputIter __last,                       const _Tp& __val,                       input_iterator_tag){  while (__first != __last && !(*__first == __val))    ++__first;  return __first;}template <class _InputIter, class _Predicate>inline _InputIter find_if(_InputIter __first, _InputIter __last,                          _Predicate __pred,                          input_iterator_tag){  while (__first != __last && !__pred(*__first))    ++__first;  return __first;}#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtemplate <class _RandomAccessIter, class _Tp>_RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,                       const _Tp& __val,                       random_access_iterator_tag){  typename iterator_traits<_RandomAccessIter>::difference_type __trip_count    = (__last - __first) >> 2;  for ( ; __trip_count > 0 ; --__trip_count) {    if (*__first == __val) return __first;    ++__first;    if (*__first == __val) return __first;    ++__first;    if (*__first == __val) return __first;    ++__first;    if (*__first == __val) return __first;    ++__first;  }  switch(__last - __first) {  case 3:    if (*__first == __val) return __first;    ++__first;  case 2:    if (*__first == __val) return __first;    ++__first;  case 1:    if (*__first == __val) return __first;    ++__first;  case 0:  default:    return __last;  }}template <class _RandomAccessIter, class _Predicate>_RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last,                          _Predicate __pred,                          random_access_iterator_tag){  typename iterator_traits<_RandomAccessIter>::difference_type __trip_count    = (__last - __first) >> 2;  for ( ; __trip_count > 0 ; --__trip_count) {    if (__pred(*__first)) return __first;    ++__first;    if (__pred(*__first)) return __first;    ++__first;    if (__pred(*__first)) return __first;    ++__first;    if (__pred(*__first)) return __first;    ++__first;  }  switch(__last - __first) {  case 3:    if (__pred(*__first)) return __first;    ++__first;  case 2:    if (__pred(*__first)) return __first;    ++__first;  case 1:    if (__pred(*__first)) return __first;    ++__first;  case 0:  default:    return __last;  }}#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */template <class _InputIter, class _Tp>inline _InputIter find(_InputIter __first, _InputIter __last,                       const _Tp& __val){  __STL_REQUIRES(_InputIter, _InputIterator);  __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,             typename iterator_traits<_InputIter>::value_type, _Tp);  return find(__first, __last, __val, __ITERATOR_CATEGORY(__first));}template <class _InputIter, class _Predicate>inline _InputIter find_if(_InputIter __first, _InputIter __last,                          _Predicate __pred) {  __STL_REQUIRES(_InputIter, _InputIterator);  __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,          typename iterator_traits<_InputIter>::value_type);  return find_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first));}// adjacent_find.template <class _ForwardIter>_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) {  __STL_REQUIRES(_ForwardIter, _ForwardIterator);  __STL_REQUIRES(typename iterator_traits<_ForwardIter>::value_type,                 _EqualityComparable);  if (__first == __last)    return __last;  _ForwardIter __next = __first;  while(++__next != __last) {    if (*__first == *__next)      return __first;    __first = __next;  }  return __last;}template <class _ForwardIter, class _BinaryPredicate>_ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last,                           _BinaryPredicate __binary_pred) {  __STL_REQUIRES(_ForwardIter, _ForwardIterator);  __STL_BINARY_FUNCTION_CHECK(_BinaryPredicate, bool,          typename iterator_traits<_ForwardIter>::value_type,          typename iterator_traits<_ForwardIter>::value_type);  if (__first == __last)    return __last;  _ForwardIter __next = __first;  while(++__next != __last) {    if (__binary_pred(*__first, *__next))      return __first;    __first = __next;  }  return __last;}// count and count_if.  There are two version of each, one whose return type// type is void and one (present only if we have partial specialization)// whose return type is iterator_traits<_InputIter>::difference_type.  The// C++ standard only has the latter version, but the former, which was present// in the HP STL, is retained for backward compatibility.template <class _InputIter, class _Tp, class _Size>void count(_InputIter __first, _InputIter __last, const _Tp& __value,           _Size& __n) {  __STL_REQUIRES(_InputIter, _InputIterator);  __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,                 _EqualityComparable);  __STL_REQUIRES(_Tp, _EqualityComparable);  for ( ; __first != __last; ++__first)    if (*__first == __value)      ++__n;}template <class _InputIter, class _Predicate, class _Size>void count_if(_InputIter __first, _InputIter __last, _Predicate __pred,              _Size& __n) {  __STL_REQUIRES(_InputIter, _InputIterator);  __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,                   typename iterator_traits<_InputIter>::value_type);  for ( ; __first != __last; ++__first)    if (__pred(*__first))      ++__n;}#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtemplate <class _InputIter, class _Tp>typename iterator_traits<_InputIter>::difference_typecount(_InputIter __first, _InputIter __last, const _Tp& __value) {  __STL_REQUIRES(_InputIter, _InputIterator);  __STL_REQUIRES(typename iterator_traits<_InputIter>::value_type,                 _EqualityComparable);  __STL_REQUIRES(_Tp, _EqualityComparable);  typename iterator_traits<_InputIter>::difference_type __n = 0;  for ( ; __first != __last; ++__first)    if (*__first == __value)      ++__n;  return __n;}template <class _InputIter, class _Predicate>typename iterator_traits<_InputIter>::difference_typecount_if(_InputIter __first, _InputIter __last, _Predicate __pred) {  __STL_REQUIRES(_InputIter, _InputIterator);  __STL_UNARY_FUNCTION_CHECK(_Predicate, bool,                   typename iterator_traits<_InputIter>::value_type);  typename iterator_traits<_InputIter>::difference_type __n = 0;  for ( ; __first != __last; ++__first)    if (__pred(*__first))      ++__n;  return __n;}#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */// search.template <class _ForwardIter1, class _ForwardIter2>_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,                     _ForwardIter2 __first2, _ForwardIter2 __last2) {  __STL_REQUIRES(_ForwardIter1, _ForwardIterator);  __STL_REQUIRES(_ForwardIter2, _ForwardIterator);  __STL_REQUIRES_BINARY_OP(_OP_EQUAL, bool,   typename iterator_traits<_ForwardIter1>::value_type,   typename iterator_traits<_ForwardIter2>::value_type);  // Test for empty ranges  if (__first1 == __last1 || __first2 == __last2)    return __first1;  // Test for a pattern of length 1.  _ForwardIter2 __tmp(__first2);  ++__tmp;  if (__tmp == __last2)    return find(__first1, __last1, *__first2);  // General case.  _ForwardIter2 __p1, __p;  __p1 = __first2; ++__p1;  _ForwardIter1 __current = __first1;  while (__first1 != __last1) {    __first1 = find(__first1, __last1, *__first2);    if (__first1 == __last1)      return __last1;    __p = __p1;    __current = __first1;     if (++__current == __last1)      return __last1;    while (*__current == *__p) {      if (++__p == __last2)        return __first1;      if (++__current == __last1)        return __last1;    }    ++__first1;  }  return __first1;}template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,                     _ForwardIter2 __first2, _ForwardIter2 __last2,                     _BinaryPred  __predicate) {  __STL_REQUIRES(_ForwardIter1, _ForwardIterator);  __STL_REQUIRES(_ForwardIter2, _ForwardIterator);  __STL_BINARY_FUNCTION_CHECK(_BinaryPred, bool,   typename iterator_traits<_ForwardIter1>::value_type,   typename iterator_traits<_ForwardIter2>::value_type);  // 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) {    while (__first1 != __last1 && !__predicate(*__first1, *__first2))