_algo.c

来自「stl的源码」· C语言 代码 · 共 1,735 行 · 第 1/5 页

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