_algo.c

MONA是为数不多的C++语言编写的一个很小的操作系统

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

_STLP_BEGIN_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))
    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;
}

template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
                     _ForwardIter2 __first2, _ForwardIter2 __last2) 
{
  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  // 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 = __first2; 
  ++__p1;

  _ForwardIter1 __current = __first1;

  while (__first1 != __last1) {
    __first1 = find(__first1, __last1, *__first2);
    if (__first1 == __last1)
      return __last1;

    _ForwardIter2 __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;
}

// 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(__check_range(__first, __last))
  if (__count <= 0)
    return __first;
  else {
    __first = find(__first, __last, __val);
    while (__first != __last) {
      _Integer __n = __count - 1;
      _ForwardIter __i = __first;
      ++__i;
      while (__i != __last && __n != 0 && *__i == __val) {
        ++__i;
        --__n;
      }
      if (__n == 0)
        return __first;
      else
        __first = find(__i, __last, __val);
    }
    return __last;
  }
}

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(__check_range(__first, __last))
  if (__count <= 0)
    return __first;
  else {
    while (__first != __last) {
      if (__binary_pred(*__first, __val))
        break;
      ++__first;
    }
    while (__first != __last) {
      _Integer __n = __count - 1;
      _ForwardIter __i = __first;
      ++__i;
      while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
        ++__i;
        --__n;
      }
      if (__n == 0)
        return __first;
      else {
        while (__i != __last) {
          if (__binary_pred(*__i, __val))
            break;
          ++__i;
        }
        __first = __i;
      }
    }
    return __last;
  }
} 

template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter1 
find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 
         _ForwardIter2 __first2, _ForwardIter2 __last2)
{
  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  return __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
                    __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))
    );
}

// unique and unique_copy
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 __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 __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 __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
}
# endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */


template <class _InputIter, class _OutputIter>
_OutputIter 
unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  if (__first == __last) return __result;
  return __unique_copy(__first, __last, __result, __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(__check_range(__first, __last))
  if (__first == __last) return __result;
  return __unique_copy(__first, __last, __result, __binary_pred,
                       _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
}

// rotate and rotate_copy, and their auxiliary functions

template <class _ForwardIter, class _Distance>
_ForwardIter __rotate(_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 {
    swap(*__first++, *__first2++);
    if (__first == __middle)
      __middle = __first2;
  } while (__first2 != __last);

  _ForwardIter __new_middle = __first;

  __first2 = __middle;

  while (__first2 != __last) {
    swap (*__first++, *__first2++);
    if (__first == __middle)
      __middle = __first2;
    else if (__first2 == __last)
      __first2 = __middle;
  }

  return __new_middle;
}

template <class _BidirectionalIter, class _Distance>
_BidirectionalIter __rotate(_BidirectionalIter __first,
                            _BidirectionalIter __middle,
                            _BidirectionalIter __last,
                            _Distance*,
                            const bidirectional_iterator_tag &) {
  if (__first == __middle)
    return __last;
  if (__last  == __middle)
    return __first;

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

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

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

template <class _RandomAccessIter, class _Distance, class _Tp>
_RandomAccessIter __rotate(_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) {
    swap_ranges(__first, __middle, __middle);
    return __result;
  }

  _Distance __d = __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(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,
         _Distance * __dis, const random_access_iterator_tag &) {
  return __rotate(__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(__first, __middle, __last,
                  _STLP_DISTANCE_TYPE(__first, _ForwardIter),
                  _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
}

// 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).

template <class _Distance>
inline _Distance __random_number(_Distance __n) {
#ifdef _STLP_NO_DRAND48
  return rand() % __n;
#else
  return lrand48() % __n;
#endif
}

template <class _RandomAccessIter>
void random_shuffle(_RandomAccessIter __first,
		    _RandomAccessIter __last) {