_algo.c

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

}

template <class _BidirectionalIter, class _Tp, 
          class _Distance, class _Compare>
inline void __inplace_merge_aux(_BidirectionalIter __first,
                                _BidirectionalIter __middle,
                                _BidirectionalIter __last, _Tp*, _Distance*,
                                _Compare __comp) {
  _Distance __len1 = distance(__first, __middle);
  _Distance __len2 = distance(__middle, __last);

  _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
  if (__buf.begin() == 0)
    __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
  else
    __merge_adaptive(__first, __middle, __last, __len1, __len2,
                     __buf.begin(), _Distance(__buf.size()),
                     __comp);
}

template <class _BidirectionalIter>
void inplace_merge(_BidirectionalIter __first,
		   _BidirectionalIter __middle,
		   _BidirectionalIter __last) {
  _STLP_DEBUG_CHECK(__check_range(__first, __middle))
  _STLP_DEBUG_CHECK(__check_range(__middle, __last))
  if (__first == __middle || __middle == __last)
    return;
  __inplace_merge_aux(__first, __middle, __last,
                      _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
                      __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
}

template <class _BidirectionalIter, class _Compare>
void inplace_merge(_BidirectionalIter __first,
		   _BidirectionalIter __middle,
		   _BidirectionalIter __last, _Compare __comp) {
  _STLP_DEBUG_CHECK(__check_range(__first, __middle))
  _STLP_DEBUG_CHECK(__check_range(__middle, __last))
  if (__first == __middle || __middle == __last)
    return;
  __inplace_merge_aux(__first, __middle, __last,
                      _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
                      __comp);
}


template <class _InputIter1, class _InputIter2, class _Compare>
bool __includes(_InputIter1 __first1, _InputIter1 __last1,
                _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  while (__first1 != __last1 && __first2 != __last2)
    if (__comp(*__first2, *__first1))
      return false;
    else if(__comp(*__first1, *__first2)) 
      ++__first1;
    else
      ++__first1, ++__first2;

  return __first2 == __last2;
}

template <class _InputIter1, class _InputIter2, class _Compare>
bool includes(_InputIter1 __first1, _InputIter1 __last1,
              _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  return __includes(__first1, __last1, __first2, __last2, __comp);
}

template <class _InputIter1, class _InputIter2>
bool includes(_InputIter1 __first1, _InputIter1 __last1,
              _InputIter2 __first2, _InputIter2 __last2) {
  return __includes(__first1, __last1, __first2, __last2, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
}

template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,
                        _InputIter2 __first2, _InputIter2 __last2,
                        _OutputIter __result, _Compare __comp) {
  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  while (__first1 != __last1 && __first2 != __last2) {
    if (__comp(*__first1, *__first2)) {
      *__result = *__first1;
      ++__first1;
    }
    else if (__comp(*__first2, *__first1)) {
      *__result = *__first2;
      ++__first2;
    }
    else {
      *__result = *__first1;
      ++__first1;
      ++__first2;
    }
    ++__result;
  }
  return copy(__first2, __last2, copy(__first1, __last1, __result));
}

template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
                      _InputIter2 __first2, _InputIter2 __last2,
                      _OutputIter __result) {
  return __set_union(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
}

template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
                      _InputIter2 __first2, _InputIter2 __last2,
                      _OutputIter __result, _Compare __comp) {
  return __set_union(__first1, __last1, __first2, __last2, __result, __comp);
}

template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,
                               _InputIter2 __first2, _InputIter2 __last2,
                               _OutputIter __result, _Compare __comp) {
  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  while (__first1 != __last1 && __first2 != __last2)
    if (__comp(*__first1, *__first2))
      ++__first1;
    else if (__comp(*__first2, *__first1))
      ++__first2;
    else {
      *__result = *__first1;
      ++__first1;
      ++__first2;
      ++__result;
    }
  return __result;
}

template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
                             _InputIter2 __first2, _InputIter2 __last2,
                             _OutputIter __result) {
  return __set_intersection(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
}

template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
                             _InputIter2 __first2, _InputIter2 __last2,
                             _OutputIter __result, _Compare __comp) {
  return __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
}

template <class _InputIter1, class _InputIter2, class _OutputIter, 
          class _Compare>
_OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,
                             _InputIter2 __first2, _InputIter2 __last2, 
                             _OutputIter __result, _Compare __comp) {
  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  while (__first1 != __last1 && __first2 != __last2)
    if (__comp(*__first1, *__first2)) {
      *__result = *__first1;
      ++__first1;
      ++__result;
    }
    else if (__comp(*__first2, *__first1))
      ++__first2;
    else {
      ++__first1;
      ++__first2;
    }
  return copy(__first1, __last1, __result);
}

template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
                           _InputIter2 __first2, _InputIter2 __last2,
                           _OutputIter __result) {
  return __set_difference(__first1, __last1, __first2, __last2, __result, 
                          __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
}

template <class _InputIter1, class _InputIter2, class _OutputIter, 
          class _Compare>
_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
                           _InputIter2 __first2, _InputIter2 __last2, 
                           _OutputIter __result, _Compare __comp) {
  return __set_difference(__first1, __last1, __first2, __last2, __result, __comp);
}

template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
_OutputIter 
__set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
                           _InputIter2 __first2, _InputIter2 __last2,
                           _OutputIter __result, _Compare __comp) {
  _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  while (__first1 != __last1 && __first2 != __last2)
    if (__comp(*__first1, *__first2)) {
      *__result = *__first1;
      ++__first1;
      ++__result;
    }
    else if (__comp(*__first2, *__first1)) {
      *__result = *__first2;
      ++__first2;
      ++__result;
    }
    else {
      ++__first1;
      ++__first2;
    }
  return copy(__first2, __last2, copy(__first1, __last1, __result));
}

template <class _InputIter1, class _InputIter2, class _OutputIter>
_OutputIter 
set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
                         _InputIter2 __first2, _InputIter2 __last2,
                         _OutputIter __result) {
  return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
                                    __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
}

template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
_OutputIter 
set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
                         _InputIter2 __first2, _InputIter2 __last2,
                         _OutputIter __result,
                         _Compare __comp) {
  return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
}

// min_element and max_element, with and without an explicitly supplied
// comparison function.

template <class _ForwardIter, class _Compare>
_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
                            _Compare __comp) {
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  if (__first == __last) return __first;
  _ForwardIter __result = __first;
  while (++__first != __last) 
    if (__comp(*__result, *__first)) __result = __first;
  return __result;
}

template <class _ForwardIter>
_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  if (__first == __last) return __first;
  _ForwardIter __result = __first;
  while (++__first != __last) 
    if (*__result < *__first)
      __result = __first;
  return __result;
}

template <class _ForwardIter>
_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  if (__first == __last) return __first;
  _ForwardIter __result = __first;
  while (++__first != __last) 
    if (*__first < *__result)
      __result = __first;
  return __result;
}

template <class _ForwardIter, class _Compare>
_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
                            _Compare __comp) {
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  if (__first == __last) return __first;
  _ForwardIter __result = __first;
  while (++__first != __last) 
    if (__comp(*__first, *__result)) __result = __first;
  return __result;
}

// next_permutation and prev_permutation, with and without an explicitly 
// supplied comparison function.
template <class _BidirectionalIter, class _Compare>
bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
                        _Compare __comp) {
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  if (__first == __last)
    return false;
  _BidirectionalIter __i = __first;
  ++__i;
  if (__i == __last)
    return false;
  __i = __last;
  --__i;

  for(;;) {
    _BidirectionalIter __ii = __i;
    --__i;
    if (__comp(*__i, *__ii)) {
      _BidirectionalIter __j = __last;
      while (!__comp(*__i, *--__j))
        {}
      iter_swap(__i, __j);
      reverse(__ii, __last);
      return true;
    }
    if (__i == __first) {
      reverse(__first, __last);
      return false;
    }
  }
#if defined(_STLP_NEED_UNREACHABLE_RETURN)
    return 0;
#endif
}

template <class _BidirectionalIter>
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  return __next_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
}

template <class _BidirectionalIter, class _Compare>
bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
                      _Compare __comp) {
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  return __next_permutation(__first, __last, __comp);
}

template <class _BidirectionalIter, class _Compare>
bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
                      _Compare __comp) {
  if (__first == __last)
    return false;
  _BidirectionalIter __i = __first;
  ++__i;
  if (__i == __last)
    return false;
  __i = __last;
  --__i;

  for(;;) {
    _BidirectionalIter __ii = __i;
    --__i;
    if (__comp(*__ii, *__i)) {
      _BidirectionalIter __j = __last;
      while (!__comp(*--__j, *__i))
        {}
      iter_swap(__i, __j);
      reverse(__ii, __last);
      return true;
    }
    if (__i == __first) {
      reverse(__first, __last);
      return false;
    }
  }
#if defined(_STLP_NEED_UNREACHABLE_RETURN)
    return 0;
#endif
}

template <class _BidirectionalIter>
bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  return __prev_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
}

template <class _BidirectionalIter, class _Compare>
bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
                      _Compare __comp) {
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  return __prev_permutation(__first, __last, __comp);
}

# ifndef _STLP_NO_EXTENSIONS

// is_heap, a predicate testing whether or not a range is
// a heap.  This function is an extension, not part of the C++
// standard.


template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
               _Distance __n)
{
  _Distance __parent = 0;
  for (_Distance __child = 1; __child < __n; ++__child) {
    if (__comp(__first[__parent], __first[__child]))
      return false;
    if ((__child & 1) == 0)
      ++__parent;
  }
  return true;
}

template <class _RandomAccessIter>
bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
{
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  return __is_heap(__first, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first);
}

template <class _RandomAccessIter, class _StrictWeakOrdering>
bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
	     _StrictWeakOrdering __comp)
{
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  return __is_heap(__first, __comp, __last - __first);
}


template <class _ForwardIter, class _StrictWeakOrdering>
bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
                 _StrictWeakOrdering __comp)
{
  _STLP_DEBUG_CHECK(__check_range(__first, __last))
  if (__first == __last)
    return true;

  _ForwardIter __next = __first;
  for (++__next; __next != __last; __first = __next, ++__next) {
    if (__comp(*__next, *__first))
      return false;
  }

  return true;
}

# endif /* _STLP_NO_EXTENSIONS */

_STLP_END_NAMESPACE

# undef __stl_threshold

#endif /* _STLP_ALGO_C */
// Local Variables:
// mode:C++
// End: