stl_algo.h

来自「ARM Linux Tool 各种代码包括MTD」· C头文件 代码 · 共 2,009 行 · 第 1/5 页

/*
 *
 * 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 <bits/stl_heap.h>

// See concept_check.h for the __glibcpp_*_requires macros.

namespace std
{

// __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)
{
  // concept requirements
  __glibcpp_function_requires(_LessThanComparableConcept<_Tp>);
  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)
{
  // concept requirements
  __glibcpp_function_requires(_BinaryFunctionConcept<_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)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  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;
}

template <class _RandomAccessIter, class _Tp>
_RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,
                       const _Tp& __val,
                       random_access_iterator_tag)
{
  typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
    = (__last - __first) >> 2;

  for ( ; __trip_count > 0 ; --__trip_count) {
    if (*__first == __val) return __first;
    ++__first;

    if (*__first == __val) return __first;
    ++__first;

    if (*__first == __val) return __first;
    ++__first;

    if (*__first == __val) return __first;
    ++__first;
  }

  switch(__last - __first) {
  case 3:
    if (*__first == __val) return __first;
    ++__first;
  case 2:
    if (*__first == __val) return __first;
    ++__first;
  case 1:
    if (*__first == __val) return __first;
    ++__first;
  case 0:
  default:
    return __last;
  }
}

template <class _RandomAccessIter, class _Predicate>
_RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last,
                          _Predicate __pred,
                          random_access_iterator_tag)
{
  typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
    = (__last - __first) >> 2;

  for ( ; __trip_count > 0 ; --__trip_count) {
    if (__pred(*__first)) return __first;
    ++__first;

    if (__pred(*__first)) return __first;
    ++__first;

    if (__pred(*__first)) return __first;
    ++__first;

    if (__pred(*__first)) return __first;
    ++__first;
  }

  switch(__last - __first) {
  case 3:
    if (__pred(*__first)) return __first;
    ++__first;
  case 2:
    if (__pred(*__first)) return __first;
    ++__first;
  case 1:
    if (__pred(*__first)) return __first;
    ++__first;
  case 0:
  default:
    return __last;
  }
}

template <class _InputIter, class _Tp>
inline _InputIter find(_InputIter __first, _InputIter __last,
                       const _Tp& __val)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  __glibcpp_function_requires(_EqualOpConcept<
            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)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
          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)
{
  // concept requirements
  __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_EqualityComparableConcept<
  	typename iterator_traits<_ForwardIter>::value_type>);
  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)
{
  // concept requirements
  __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>);
  __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
        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)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  __glibcpp_function_requires(_EqualityComparableConcept<
        typename iterator_traits<_InputIter>::value_type >);
  __glibcpp_function_requires(_EqualityComparableConcept<_Tp>);
  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)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
        typename iterator_traits<_InputIter>::value_type>);
  for ( ; __first != __last; ++__first)
    if (__pred(*__first))
      ++__n;
}

template <class _InputIter, class _Tp>
typename iterator_traits<_InputIter>::difference_type
count(_InputIter __first, _InputIter __last, const _Tp& __value)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  __glibcpp_function_requires(_EqualityComparableConcept<
        typename iterator_traits<_InputIter>::value_type >);
  __glibcpp_function_requires(_EqualityComparableConcept<_Tp>);
  typename iterator_traits<_InputIter>::difference_type __n = 0;
  for ( ; __first != __last; ++__first)
    if (*__first == __value)
      ++__n;
  return __n;
}

template <class _InputIter, class _Predicate>
typename iterator_traits<_InputIter>::difference_type
count_if(_InputIter __first, _InputIter __last, _Predicate __pred)
{
  // concept requirements
  __glibcpp_function_requires(_InputIteratorConcept<_InputIter>);
  __glibcpp_function_requires(_UnaryPredicateConcept<_Predicate,
        typename iterator_traits<_InputIter>::value_type>);
  typename iterator_traits<_InputIter>::difference_type __n = 0;
  for ( ; __first != __last; ++__first)
    if (__pred(*__first))
      ++__n;
  return __n;
}


// search.

template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
                     _ForwardIter2 __first2, _ForwardIter2 __last2) 
{
  // concept requirements
  __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>);
  __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>);
  __glibcpp_function_requires(_EqualOpConcept<
        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) 
{
  // concept requirements
  __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter1>);
  __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter2>);
  __glibcpp_function_requires(_BinaryPredicateConcept<_BinaryPred,
        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))
      ++__first1;
    return __first1;    
  }

  // General case.

  _ForwardIter2 __p1, __p;

  __p1 = __first2; ++__p1;