_algo.c

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

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 {
    _STLP_STD::swap(*__first++, *__first2++);
    if (__first == __middle)
      __middle = __first2;
  } while (__first2 != __last);

  _ForwardIter __new_middle = __first;

  __first2 = __middle;

  while (__first2 != __last) {
    _STLP_STD::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;

  _STLP_PRIV __reverse(__first,  __middle, bidirectional_iterator_tag());
  _STLP_PRIV __reverse(__middle, __last,   bidirectional_iterator_tag());

  while (__first != __middle && __middle != __last)
    _STLP_STD::swap(*__first++, *--__last);

  if (__first == __middle) {
    _STLP_PRIV __reverse(__middle, __last,   bidirectional_iterator_tag());
    return __last;
  }
  else {
    _STLP_PRIV __reverse(__first,  __middle, bidirectional_iterator_tag());
    return __first;
  }
}

// rotate and rotate_copy, and their auxiliary functions
template <class _EuclideanRingElement>
_STLP_INLINE_LOOP
_EuclideanRingElement __gcd(_EuclideanRingElement __m,
                            _EuclideanRingElement __n) {
  while (__n != 0) {
    _EuclideanRingElement __t = __m % __n;
    __m = __n;
    __n = __t;
  }
  return __m;
}

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) {
    _STLP_STD::swap_ranges(__first, __middle, __middle);
    return __result;
  }

  _Distance __d = _STLP_PRIV __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 _STLP_PRIV __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))
  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    iter_swap(__i, __first + _STLP_PRIV __random_number((__i - __first) + 1));
}

template <class _RandomAccessIter, class _RandomNumberGenerator>
void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
                    _RandomNumberGenerator &__rand) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    iter_swap(__i, __first + __rand((__i - __first) + 1));
}

#if !defined (_STLP_NO_EXTENSIONS)
// random_sample and random_sample_n (extensions, not part of the standard).
template <class _ForwardIter, class _OutputIter, class _Distance>
_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
                            _OutputIter __out_ite, const _Distance __n) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  _Distance __remaining = _STLP_STD::distance(__first, __last);
  _Distance __m = (min) (__n, __remaining);

  while (__m > 0) {
    if (_STLP_PRIV __random_number(__remaining) < __m) {
      *__out_ite = *__first;
      ++__out_ite;
      --__m;
    }

    --__remaining;
    ++__first;
  }
  return __out_ite;
}


template <class _ForwardIter, class _OutputIter, class _Distance,
          class _RandomNumberGenerator>
_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
                            _OutputIter __out_ite, const _Distance __n,
                            _RandomNumberGenerator& __rand) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  _Distance __remaining = _STLP_STD::distance(__first, __last);
  _Distance __m = (min) (__n, __remaining);

  while (__m > 0) {
    if (__rand(__remaining) < __m) {
      *__out_ite = *__first;
      ++__out_ite;
      --__m;
    }

    --__remaining;
    ++__first;
  }
  return __out_ite;
}

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _InputIter, class _RandomAccessIter, class _Distance>
_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
                                  _RandomAccessIter __out_ite,
                                  const _Distance __n) {
  _Distance __m = 0;
  _Distance __t = __n;
  for ( ; __first != __last && __m < __n; ++__m, ++__first)
    __out_ite[__m] = *__first;

  while (__first != __last) {
    ++__t;
    _Distance __M = __random_number(__t);
    if (__M < __n)
      __out_ite[__M] = *__first;
    ++__first;
  }

  return __out_ite + __m;
}

template <class _InputIter, class _RandomAccessIter,
          class _RandomNumberGenerator, class _Distance>
_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
                                  _RandomAccessIter __out_ite,
                                  _RandomNumberGenerator& __rand,
                                  const _Distance __n) {
  _Distance __m = 0;
  _Distance __t = __n;
  for ( ; __first != __last && __m < __n; ++__m, ++__first)
    __out_ite[__m] = *__first;

  while (__first != __last) {
    ++__t;
    _Distance __M = __rand(__t);
    if (__M < __n)
      __out_ite[__M] = *__first;
    ++__first;
  }

  return __out_ite + __m;
}

_STLP_MOVE_TO_STD_NAMESPACE

template <class _InputIter, class _RandomAccessIter>
_RandomAccessIter
random_sample(_InputIter __first, _InputIter __last,
              _RandomAccessIter __out_first, _RandomAccessIter __out_last) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
  return _STLP_PRIV __random_sample(__first, __last,
                                    __out_first, __out_last - __out_first);
}

template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>
_RandomAccessIter
random_sample(_InputIter __first, _InputIter __last,
              _RandomAccessIter __out_first, _RandomAccessIter __out_last,
              _RandomNumberGenerator& __rand) {
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
  return _STLP_PRIV __random_sample(__first, __last,
                                    __out_first, __rand,
                                    __out_last - __out_first);
}

#endif /* _STLP_NO_EXTENSIONS */

// partition, stable_partition, and their auxiliary functions
_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _ForwardIter, class _Predicate>
_STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,
                                           _ForwardIter __last,
                                           _Predicate   __pred,
                                           const forward_iterator_tag &) {
  if (__first == __last) return __first;

  while (__pred(*__first))
    if (++__first == __last) return __first;

  _ForwardIter __next = __first;

  while (++__next != __last) {
    if (__pred(*__next)) {
      _STLP_STD::swap(*__first, *__next);
      ++__first;
    }
  }
  return __first;
}