_algobase.c

来自「stl的源码」· C语言 代码 · 共 484 行 · 第 1/2 页

    return __first1;
  }

  // General case.

  for ( ; ; ) { // __first1 != __last1 will be checked below
    while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
      ++__first1;
    }
    if (__first1 == __last1) {
      return __last1;
    }
    _ForwardIter2 __p = __p1;
    _ForwardIter1 __current = __first1;
    if (++__current == __last1) return __last1;

    while (__pred(*__current, *__p)) {
      if (++__p == __last2)
        return __first1;
      if (++__current == __last1)
        return __last1;
    }
    ++__first1;
  }
  return __first1;
}

_STLP_MOVE_TO_PRIV_NAMESPACE
template <class _Tp>
struct _IsCharLikeType
{ typedef __false_type _Ret; };

_STLP_TEMPLATE_NULL struct _IsCharLikeType<char>
{ typedef __true_type _Ret; };

_STLP_TEMPLATE_NULL struct _IsCharLikeType<unsigned char>
{ typedef __true_type _Ret; };

#  ifndef _STLP_NO_SIGNED_BUILTINS
_STLP_TEMPLATE_NULL struct _IsCharLikeType<signed char>
{ typedef __true_type _Ret; };
#  endif

template <class _Tp1, class _Tp2>
inline bool __stlp_eq(_Tp1 __val1, _Tp2 __val2)
{ return __val1 == __val2; }

#if defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
template <class _Tp>
inline bool __stlp_eq(_Tp, _Tp)
{ return true; }
#endif

template <class _InputIter, class _ForwardIter, class _Tp2, class _Predicate>
inline _InputIter __find_first_of_aux2(_InputIter __first1, _InputIter __last1,
                                       _ForwardIter __first2, _ForwardIter __last2,
                                       _Tp2*, _Predicate __pred,
                                       const __true_type& /* _UseStrcspnLikeAlgo */) {
  unsigned char __hints[(UCHAR_MAX + 1) / CHAR_BIT];
  memset(__hints, 0, sizeof(__hints) / sizeof(unsigned char));
  for (; __first2 != __last2; ++__first2) {
    unsigned char __tmp = (unsigned char)*__first2;
    __hints[__tmp / CHAR_BIT] |= (1 << (__tmp % CHAR_BIT));
  }

  for (; __first1 != __last1; ++__first1) {
    _Tp2 __tmp = (_Tp2)*__first1;
    if (__stlp_eq(*__first1, __tmp) &&
        __pred((__hints[(unsigned char)__tmp / CHAR_BIT] & (1 << ((unsigned char)__tmp % CHAR_BIT))) != 0))
      break;
  }
  return __first1;
}

template <class _InputIter, class _ForwardIter, class _Tp2, class _Predicate>
inline _InputIter __find_first_of_aux2(_InputIter __first1, _InputIter __last1,
                                       _ForwardIter __first2, _ForwardIter __last2,
                                       _Tp2* /* __dummy */, _Predicate /* __pred */,
                                       const __false_type& /* _UseStrcspnLikeAlgo */) {
  return _STLP_PRIV __find_first_of(__first1, __last1, __first2, __last2,
                                    _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _InputIter)));
}

template <class _InputIter, class _ForwardIter, class _Tp1, class _Tp2>
inline _InputIter __find_first_of_aux1(_InputIter __first1, _InputIter __last1,
                                       _ForwardIter __first2, _ForwardIter __last2,
                                       _Tp1* __pt1, _Tp2* __pt2) {
  typedef _STLP_TYPENAME _STLP_STD::_IsIntegral<_Tp1>::_Ret _IsIntegral;
  typedef _STLP_TYPENAME _STLP_PRIV _IsCharLikeType<_Tp2>::_Ret _IsCharLike;
  typedef _STLP_TYPENAME _STLP_STD::_Land2<_IsIntegral, _IsCharLike>::_Ret _UseStrcspnLikeAlgo;
  return _STLP_PRIV __find_first_of_aux2(__first1, __last1,
                                         __first2, __last2,
                                         __pt2, _Identity<bool>(), _UseStrcspnLikeAlgo());
}

template <class _InputIter, class _ForwardIter>
inline _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
                                  _ForwardIter __first2, _ForwardIter __last2) {
  return _STLP_PRIV __find_first_of_aux1(__first1, __last1, __first2, __last2,
                                         _STLP_VALUE_TYPE(__first1, _InputIter),
                                         _STLP_VALUE_TYPE(__first2, _ForwardIter));
}

// find_first_of, with and without an explicitly supplied comparison function.
template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
_InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
                           _ForwardIter __first2, _ForwardIter __last2,
                           _BinaryPredicate __comp) {
  for ( ; __first1 != __last1; ++__first1) {
    for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) {
      if (__comp(*__first1, *__iter)) {
        return __first1;
      }
    }
  }
  return __last1;
}

// find_end, with and without an explicitly supplied comparison function.
// Search [first2, last2) as a subsequence in [first1, last1), and return
// the *last* possible match.  Note that find_end for bidirectional iterators
// is much faster than for forward iterators.

// find_end for forward iterators.
template <class _ForwardIter1, class _ForwardIter2,
  class _BinaryPredicate>
_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
                         _ForwardIter2 __first2, _ForwardIter2 __last2,
                         const forward_iterator_tag &, const forward_iterator_tag &,
                         _BinaryPredicate __comp) {
  if (__first2 == __last2)
    return __last1;
  else {
    _ForwardIter1 __result = __last1;
    for (;;) {
      _ForwardIter1 __new_result = _STLP_STD::search(__first1, __last1, __first2, __last2, __comp);
      if (__new_result == __last1)
        return __result;
      else {
        __result = __new_result;
        __first1 = __new_result;
        ++__first1;
      }
    }
  }
}

_STLP_MOVE_TO_STD_NAMESPACE

// find_end for bidirectional iterators.  Requires partial specialization.
#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)

#  ifndef _STLP_INTERNAL_ITERATOR_H
_STLP_END_NAMESPACE
#    include <stl/_iterator.h>
_STLP_BEGIN_NAMESPACE
#  endif /*_STLP_INTERNAL_ITERATOR_H*/

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _BidirectionalIter1, class _BidirectionalIter2,
          class _BinaryPredicate>
_BidirectionalIter1
__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
           _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
           const bidirectional_iterator_tag &, const bidirectional_iterator_tag &,
           _BinaryPredicate __comp) {
  typedef _STLP_STD::reverse_iterator<_BidirectionalIter1> _RevIter1;
  typedef _STLP_STD::reverse_iterator<_BidirectionalIter2> _RevIter2;

  _RevIter1 __rlast1(__first1);
  _RevIter2 __rlast2(__first2);
  _RevIter1 __rresult = _STLP_STD::search(_RevIter1(__last1), __rlast1,
                                          _RevIter2(__last2), __rlast2,
                                          __comp);

  if (__rresult == __rlast1)
    return __last1;
  else {
    _BidirectionalIter1 __result = __rresult.base();
    _STLP_STD::advance(__result, -_STLP_STD::distance(__first2, __last2));
    return __result;
  }
}

_STLP_MOVE_TO_STD_NAMESPACE
#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */

template <class _ForwardIter1, class _ForwardIter2,
          class _BinaryPredicate>
_ForwardIter1
find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
         _ForwardIter2 __first2, _ForwardIter2 __last2,
         _BinaryPredicate __comp) {
  _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
                               __comp);
}

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
                           _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
  _Distance __len = _STLP_STD::distance(__first, __last);
  _Distance __half;
  _ForwardIter __middle;

  while (__len > 0) {
    __half = __len >> 1;
    __middle = __first;
    _STLP_STD::advance(__middle, __half);
    if (__comp1(*__middle, __val)) {
      _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
      __first = __middle;
      ++__first;
      __len = __len - __half - 1;
    }
    else
      __len = __half;
  }
  return __first;
}

_STLP_MOVE_TO_STD_NAMESPACE

_STLP_END_NAMESPACE

#endif /* _STLP_ALGOBASE_C */

// Local Variables:
// mode:C++
// End: