williamr@2: /*
williamr@2:  *
williamr@2:  * Copyright (c) 1994
williamr@2:  * Hewlett-Packard Company
williamr@2:  *
williamr@2:  * Copyright (c) 1996,1997
williamr@2:  * Silicon Graphics Computer Systems, Inc.
williamr@2:  *
williamr@2:  * Copyright (c) 1997
williamr@2:  * Moscow Center for SPARC Technology
williamr@2:  *
williamr@2:  * Copyright (c) 1999 
williamr@2:  * Boris Fomitchev
williamr@2:  *
williamr@2:  * This material is provided "as is", with absolutely no warranty expressed
williamr@2:  * or implied. Any use is at your own risk.
williamr@2:  *
williamr@2:  * Permission to use or copy this software for any purpose is hereby granted 
williamr@2:  * without fee, provided the above notices are retained on all copies.
williamr@2:  * Permission to modify the code and to distribute modified code is granted,
williamr@2:  * provided the above notices are retained, and a notice that the code was
williamr@2:  * modified is included with the above copyright notice.
williamr@2:  *
williamr@2:  */
williamr@2: 
williamr@2: /* NOTE: This is an internal header file, included by other STL headers.
williamr@2:  *   You should not attempt to use it directly.
williamr@2:  */
williamr@2: 
williamr@2: 
williamr@2: #ifndef _STLP_INTERNAL_ALGOBASE_H
williamr@2: #define _STLP_INTERNAL_ALGOBASE_H
williamr@2: 
williamr@2: # if ! defined (_STLP_CSTDDEF)
williamr@2: #  include <cstddef>
williamr@2: # endif
williamr@2: 
williamr@2: #ifndef _STLP_CSTRING
williamr@2: # include <cstring>
williamr@2: #endif
williamr@2: 
williamr@2: #ifndef _STLP_CLIMITS
williamr@2: # include <climits>
williamr@2: #endif
williamr@2: 
williamr@2: # if ! defined (_STLP_CSTDLIB)
williamr@2: #  include <cstdlib>
williamr@2: # endif
williamr@2: 
williamr@2: # ifndef _STLP_INTERNAL_PAIR_H
williamr@2: #  include <stl/_pair.h>
williamr@2: # endif
williamr@2: 
williamr@2: #ifndef _STLP_INTERNAL_ITERATOR_BASE_H
williamr@2: # include <stl/_iterator_base.h>
williamr@2: #endif
williamr@2: 
williamr@2: _STLP_BEGIN_NAMESPACE
williamr@2: // swap and iter_swap
williamr@2: template <class _Tp>
williamr@2: inline void swap(_Tp& __a, _Tp& __b) {
williamr@2:   _Tp __tmp = __a;
williamr@2:   __a = __b;
williamr@2:   __b = __tmp;
williamr@2: }
williamr@2: 
williamr@2: template <class _ForwardIter1, class _ForwardIter2>
williamr@2: inline void iter_swap(_ForwardIter1 __i1, _ForwardIter2 __i2) {
williamr@2:   swap(*__i1, *__i2);
williamr@2: }
williamr@2: 
williamr@2: //--------------------------------------------------
williamr@2: // min and max
williamr@2: 
williamr@2: # if !defined (__BORLANDC__) || defined (_STLP_USE_OWN_NAMESPACE)
williamr@2: template <class _Tp>
williamr@2: inline const _Tp& (min)(const _Tp& __a, const _Tp& __b) { return __b < __a ? __b : __a; }
williamr@2: template <class _Tp>
williamr@2: inline const _Tp& (max)(const _Tp& __a, const _Tp& __b) {  return  __a < __b ? __b : __a; }
williamr@2: #endif /* __BORLANDC__ */
williamr@2: 
williamr@2: # if defined (__BORLANDC__) && ( __BORLANDC__ < 0x530 || defined (_STLP_USE_OWN_NAMESPACE))
williamr@2: inline unsigned long (min) (unsigned long __a, unsigned long __b) { return __b < __a ? __b : __a; }
williamr@2: inline unsigned long (max) (unsigned long __a, unsigned long __b) {  return  __a < __b ? __b : __a; }
williamr@2: # endif
williamr@2: 
williamr@2: template <class _Tp, class _Compare>
williamr@2: inline const _Tp& (min)(const _Tp& __a, const _Tp& __b, _Compare __comp) { 
williamr@2:   return __comp(__b, __a) ? __b : __a;
williamr@2: }
williamr@2: 
williamr@2: template <class _Tp, class _Compare>
williamr@2: inline const _Tp& (max)(const _Tp& __a, const _Tp& __b, _Compare __comp) {
williamr@2:   return __comp(__a, __b) ? __b : __a;
williamr@2: }
williamr@2: 
williamr@2: //--------------------------------------------------
williamr@2: // copy
williamr@2: 
williamr@2: // All of these auxiliary functions serve two purposes.  (1) Replace
williamr@2: // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
williamr@2: // because the input and output ranges are permitted to overlap.)
williamr@2: // (2) If we're using random access iterators, then write the loop as
williamr@2: // a for loop with an explicit count.
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter, class _Distance>
williamr@2: inline _OutputIter __copy(_InputIter __first, _InputIter __last,
williamr@2:                           _OutputIter __result,
williamr@2:                           const input_iterator_tag &, _Distance*) {
williamr@2:   for ( ; __first != __last; ++__result, ++__first)
williamr@2:     *__result = *__first;
williamr@2:   return __result;
williamr@2: }
williamr@2: 
williamr@2: # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) 
williamr@2: template <class _InputIter, class _OutputIter, class _Distance>
williamr@2: inline _OutputIter __copy(_InputIter __first, _InputIter __last,
williamr@2: 			  _OutputIter __result, const forward_iterator_tag &, _Distance* ) {
williamr@2:   for ( ; __first != __last; ++__result, ++__first)
williamr@2:     *__result = *__first;
williamr@2:   return __result;
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter, class _Distance>
williamr@2: inline _OutputIter __copy(_InputIter __first, _InputIter __last,
williamr@2: 			  _OutputIter __result, const bidirectional_iterator_tag &, _Distance* __dis) {
williamr@2:   for ( ; __first != __last; ++__result, ++__first)
williamr@2:     *__result = *__first;
williamr@2:   return __result;
williamr@2: }
williamr@2: # endif 
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _OutputIter, class _Distance>
williamr@2: inline _OutputIter
williamr@2: __copy(_RandomAccessIter __first, _RandomAccessIter __last,
williamr@2:        _OutputIter __result, const random_access_iterator_tag &, _Distance*) {
williamr@2:   for (_Distance __n = __last - __first; __n > 0; --__n) {
williamr@2:     *__result = *__first;
williamr@2:     ++__first;
williamr@2:     ++__result;
williamr@2:   }
williamr@2:   return __result;
williamr@2: }
williamr@2: 
williamr@2: inline void*
williamr@2: __copy_trivial(const void* __first, const void* __last, void* __result) {
williamr@2:   return (__last == __first) ? __result : 
williamr@2:     ((char*)memmove(__result, __first, ((const char*)__last - (const char*)__first))) + 
williamr@2:     ((const char*)__last - (const char*)__first);
williamr@2: }
williamr@2: 
williamr@2: //--------------------------------------------------
williamr@2: // copy_backward auxiliary functions
williamr@2: 
williamr@2: template <class _BidirectionalIter1, class _BidirectionalIter2, 
williamr@2:           class _Distance>
williamr@2: inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first, 
williamr@2:                                            _BidirectionalIter1 __last, 
williamr@2:                                            _BidirectionalIter2 __result,
williamr@2:                                            const bidirectional_iterator_tag &,
williamr@2:                                            _Distance*) 
williamr@2: {
williamr@2:   while (__first != __last)
williamr@2:     *--__result = *--__last;
williamr@2:   return __result;
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
williamr@2: inline _BidirectionalIter __copy_backward(_RandomAccessIter __first, 
williamr@2:                                           _RandomAccessIter __last, 
williamr@2:                                           _BidirectionalIter __result,
williamr@2:                                           const random_access_iterator_tag &,
williamr@2:                                           _Distance*)
williamr@2: {
williamr@2:   for (_Distance __n = __last - __first; __n > 0; --__n)
williamr@2:     *--__result = *--__last;
williamr@2:   return __result;
williamr@2: }
williamr@2: 
williamr@2: inline void*
williamr@2: __copy_trivial_backward(const void* __first, const void* __last, void* __result) {
williamr@2:   const ptrdiff_t _Num = (const char*)__last - (const char*)__first;
williamr@2:   return (_Num > 0) ? memmove((char*)__result - _Num, __first, _Num) : __result ;
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter>
williamr@2: inline _OutputIter __copy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type&) {
williamr@2:   return __copy(__first, __last, __result, 
williamr@2:                 _STLP_ITERATOR_CATEGORY(__first, _InputIter), 
williamr@2:                 _STLP_DISTANCE_TYPE(__first, _InputIter));
williamr@2: }
williamr@2: template <class _InputIter, class _OutputIter>
williamr@2: inline _OutputIter __copy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type&) {
williamr@2: // we know they all pointers, so this cast is OK 
williamr@2:   //  return (_OutputIter)__copy_trivial(&(*__first), &(*__last), &(*__result));
williamr@2:   return (_OutputIter)__copy_trivial(__first, __last, __result);
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter>
williamr@2: inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type&) {
williamr@2:   return __copy_ptrs(__first, __last, __result, 
williamr@2:                      _IsOKToMemCpy(_STLP_VALUE_TYPE(__first, _InputIter), 
williamr@2:                                    _STLP_VALUE_TYPE(__result, _OutputIter))._Ret());
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter>
williamr@2: inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type&) {
williamr@2:   return __copy(__first, __last, __result, 
williamr@2: 		_STLP_ITERATOR_CATEGORY(__first, _InputIter), _STLP_DISTANCE_TYPE(__first, _InputIter));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter>
williamr@2: inline _OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:     return __copy_aux(__first, __last, __result, _BothPtrType< _InputIter, _OutputIter> :: _Ret());
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter>
williamr@2: inline _OutputIter __copy_backward_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type&) {
williamr@2:   return __copy_backward(__first, __last, __result, _STLP_ITERATOR_CATEGORY(__first, _InputIter), _STLP_DISTANCE_TYPE(__first, _InputIter));
williamr@2: }
williamr@2: template <class _InputIter, class _OutputIter>
williamr@2: inline _OutputIter __copy_backward_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type&) {
williamr@2:   return (_OutputIter)__copy_trivial_backward(__first, __last, __result);  
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter>
williamr@2: inline _OutputIter __copy_backward_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type&) {
williamr@2:   return __copy_backward(__first, __last, __result, _STLP_ITERATOR_CATEGORY(__first,_InputIter), _STLP_DISTANCE_TYPE(__first, _InputIter));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter>
williamr@2: inline _OutputIter __copy_backward_aux(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type&) {
williamr@2:   return __copy_backward_ptrs(__first, __last, __result,  
williamr@2:                               _IsOKToMemCpy(_STLP_VALUE_TYPE(__first, _InputIter), 
williamr@2:                                             _STLP_VALUE_TYPE(__result, _OutputIter))._Ret());
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _OutputIter>
williamr@2: inline _OutputIter copy_backward(_InputIter __first, _InputIter __last, _OutputIter __result) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:     return __copy_backward_aux(__first, __last, __result, _BothPtrType< _InputIter, _OutputIter> :: _Ret() );
williamr@2: }
williamr@2: 
williamr@2: #if ! defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && ! defined ( _STLP_SIMULATE_PARTIAL_SPEC_FOR_TYPE_TRAITS )
williamr@2: #define _STLP_DECLARE_COPY_TRIVIAL(_Tp)                                \
williamr@2: inline _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) \
williamr@2: { return (_Tp*)__copy_trivial(__first, __last, __result); } \
williamr@2: inline _Tp* copy_backward(const _Tp* __first, const _Tp* __last, _Tp* __result) \
williamr@2: { return (_Tp*)__copy_trivial_backward(__first, __last, __result); }
williamr@2: 
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(char)
williamr@2: # ifndef _STLP_NO_SIGNED_BUILTINS
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(signed char)
williamr@2: # endif
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(unsigned char)
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(short)
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(unsigned short)
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(int)
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(unsigned int)
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(long)
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(unsigned long)
williamr@2: #if !defined(_STLP_NO_WCHAR_T) && !defined (_STLP_WCHAR_T_IS_USHORT) 
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(wchar_t)
williamr@2: #endif
williamr@2: #ifdef _STLP_LONG_LONG
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(long long)
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(unsigned long long)
williamr@2: #endif 
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(float)
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(double)
williamr@2: # ifndef _STLP_NO_LONG_DOUBLE
williamr@2: _STLP_DECLARE_COPY_TRIVIAL(long double)
williamr@2: # endif
williamr@2: #undef _STLP_DECLARE_COPY_TRIVIAL
williamr@2: #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
williamr@2: 
williamr@2: //--------------------------------------------------
williamr@2: // copy_n (not part of the C++ standard)
williamr@2: 
williamr@2: template <class _InputIter, class _Size, class _OutputIter>
williamr@2: _STLP_INLINE_LOOP 
williamr@2: pair<_InputIter, _OutputIter> __copy_n(_InputIter __first, _Size __count,
williamr@2:                                        _OutputIter __result,
williamr@2:                                        const input_iterator_tag &) {
williamr@2:   for ( ; __count > 0; --__count) {
williamr@2:     *__result = *__first;
williamr@2:     ++__first;
williamr@2:     ++__result;
williamr@2:   }
williamr@2:   return pair<_InputIter, _OutputIter>(__first, __result);
williamr@2: }
williamr@2: 
williamr@2: template <class _RAIter, class _Size, class _OutputIter>
williamr@2: inline pair<_RAIter, _OutputIter>
williamr@2: __copy_n(_RAIter __first, _Size __count,
williamr@2:          _OutputIter __result,
williamr@2:          const random_access_iterator_tag &) {
williamr@2:   _RAIter __last = __first + __count;
williamr@2:   return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _Size, class _OutputIter>
williamr@2: inline pair<_InputIter, _OutputIter>
williamr@2: __copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
williamr@2:   _STLP_FIX_LITERAL_BUG(__first)
williamr@2:   return __copy_n(__first, __count, __result, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _Size, class _OutputIter>
williamr@2: inline pair<_InputIter, _OutputIter>
williamr@2: copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
williamr@2:   _STLP_FIX_LITERAL_BUG(__first)
williamr@2:   return __copy_n(__first, __count, __result, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
williamr@2: }
williamr@2: 
williamr@2: //--------------------------------------------------
williamr@2: // fill and fill_n
williamr@2: 
williamr@2: 
williamr@2: template <class _ForwardIter, class _Tp>
williamr@2: _STLP_INLINE_LOOP
williamr@2: void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   for ( ; __first != __last; ++__first)
williamr@2:     *__first = __val;
williamr@2: }
williamr@2: 
williamr@2: template <class _OutputIter, class _Size, class _Tp>
williamr@2: _STLP_INLINE_LOOP
williamr@2: _OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __val) {
williamr@2:   _STLP_FIX_LITERAL_BUG(__first)
williamr@2:   for ( ; __n > 0; --__n, ++__first)
williamr@2:     *__first = __val;
williamr@2:   return __first;
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: // Specialization: for one-byte types we can use memset.
williamr@2: 
williamr@2: inline void fill(unsigned char* __first, unsigned char* __last,
williamr@2:                  const unsigned char& __val) {
williamr@2:   unsigned char __tmp = __val;
williamr@2:   memset(__first, __tmp, __last - __first);
williamr@2: }
williamr@2: # ifndef _STLP_NO_SIGNED_BUILTINS
williamr@2: inline void fill(signed char* __first, signed char* __last,
williamr@2:                  const signed char& __val) {
williamr@2:   signed char __tmp = __val;
williamr@2:   memset(__first, __STATIC_CAST(unsigned char,__tmp), __last - __first);
williamr@2: }
williamr@2: # endif
williamr@2: inline void fill(char* __first, char* __last, const char& __val) {
williamr@2:   char __tmp = __val;
williamr@2:   memset(__first, __STATIC_CAST(unsigned char,__tmp), __last - __first);
williamr@2: }
williamr@2: 
williamr@2: #ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER
williamr@2: 
williamr@2: template <class _Size>
williamr@2: inline unsigned char* fill_n(unsigned char* __first, _Size __n,
williamr@2:                              const unsigned char& __val) {
williamr@2:   fill(__first, __first + __n, __val);
williamr@2:   return __first + __n;
williamr@2: }
williamr@2: 
williamr@2: template <class _Size>
williamr@2: inline signed char* fill_n(char* __first, _Size __n,
williamr@2:                            const signed char& __val) {
williamr@2:   fill(__first, __first + __n, __val);
williamr@2:   return __first + __n;
williamr@2: }
williamr@2: 
williamr@2: template <class _Size>
williamr@2: inline char* fill_n(char* __first, _Size __n, const char& __val) {
williamr@2:   fill(__first, __first + __n, __val);
williamr@2:   return __first + __n;
williamr@2: }
williamr@2: 
williamr@2: #endif /* _STLP_FUNCTION_TMPL_PARTIAL_ORDER */
williamr@2: 
williamr@2: 
williamr@2: //--------------------------------------------------
williamr@2: // equal and mismatch
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2>
williamr@2: _STLP_INLINE_LOOP
williamr@2: pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
williamr@2:                                         _InputIter1 __last1,
williamr@2:                                         _InputIter2 __first2) {
williamr@2:   _STLP_FIX_LITERAL_BUG(__first2)
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   while (__first1 != __last1 && *__first1 == *__first2) {
williamr@2:     ++__first1;
williamr@2:     ++__first2;
williamr@2:   }
williamr@2:   return pair<_InputIter1, _InputIter2>(__first1, __first2);
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
williamr@2: _STLP_INLINE_LOOP
williamr@2: pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
williamr@2:                                         _InputIter1 __last1,
williamr@2:                                         _InputIter2 __first2,
williamr@2:                                         _BinaryPredicate __binary_pred) {
williamr@2:   _STLP_FIX_LITERAL_BUG(__first2)
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
williamr@2:     ++__first1;
williamr@2:     ++__first2;
williamr@2:   }
williamr@2:   return pair<_InputIter1, _InputIter2>(__first1, __first2);
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2>
williamr@2: _STLP_INLINE_LOOP
williamr@2: bool equal(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                   _InputIter2 __first2) {
williamr@2:   _STLP_FIX_LITERAL_BUG(__first1) _STLP_FIX_LITERAL_BUG(__last1)  _STLP_FIX_LITERAL_BUG(__first2)
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   for ( ; __first1 != __last1; ++__first1, ++__first2)
williamr@2:     if (!(*__first1 == *__first2))
williamr@2:       return false;
williamr@2:   return true;
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
williamr@2: _STLP_INLINE_LOOP
williamr@2: bool equal(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                   _InputIter2 __first2, _BinaryPredicate __binary_pred) {
williamr@2:   _STLP_FIX_LITERAL_BUG(__first2)
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   for ( ; __first1 != __last1; ++__first1, ++__first2)
williamr@2:     if (!__binary_pred(*__first1, *__first2))
williamr@2:       return false;
williamr@2:   return true;
williamr@2: }
williamr@2: 
williamr@2: //--------------------------------------------------
williamr@2: // lexicographical_compare and lexicographical_compare_3way.
williamr@2: // (the latter is not part of the C++ standard.)
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2>
williamr@2: bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                              _InputIter2 __first2, _InputIter2 __last2);
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2, class _Compare>
williamr@2: bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                              _InputIter2 __first2, _InputIter2 __last2,
williamr@2:                              _Compare __comp);
williamr@2: 
williamr@2: inline bool 
williamr@2: lexicographical_compare(const unsigned char* __first1,
williamr@2:                         const unsigned char* __last1,
williamr@2:                         const unsigned char* __first2,
williamr@2:                         const unsigned char* __last2)
williamr@2: {
williamr@2:   const size_t __len1 = __last1 - __first1;
williamr@2:   const size_t __len2 = __last2 - __first2;
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2: 
williamr@2:   const int __result = memcmp(__first1, __first2, (min) (__len1, __len2));
williamr@2:   return __result != 0 ? (__result < 0) : (__len1 < __len2);
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: # if !(CHAR_MAX == SCHAR_MAX)
williamr@2: inline bool lexicographical_compare(const char* __first1, const char* __last1,
williamr@2:                                     const char* __first2, const char* __last2)
williamr@2: {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) 
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2: 
williamr@2:   return lexicographical_compare((const unsigned char*) __first1,
williamr@2:                                  (const unsigned char*) __last1,
williamr@2:                                  (const unsigned char*) __first2,
williamr@2:                                  (const unsigned char*) __last2);
williamr@2: }
williamr@2: #endif /* CHAR_MAX == SCHAR_MAX */
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2>
williamr@2: int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                                    _InputIter2 __first2, _InputIter2 __last2);
williamr@2: 
williamr@2: inline int
williamr@2: __lexicographical_compare_3way(const unsigned char* __first1,
williamr@2:                                const unsigned char* __last1,
williamr@2:                                const unsigned char* __first2,
williamr@2:                                const unsigned char* __last2)
williamr@2: {
williamr@2:   const ptrdiff_t __len1 = __last1 - __first1;
williamr@2:   const ptrdiff_t __len2 = __last2 - __first2;
williamr@2:   const int __result = memcmp(__first1, __first2, (min) (__len1, __len2));
williamr@2:   return __result != 0 ? __result 
williamr@2:                        : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: # if !(CHAR_MAX == SCHAR_MAX)
williamr@2: inline int 
williamr@2: __lexicographical_compare_3way(const char* __first1, const char* __last1,
williamr@2:                                const char* __first2, const char* __last2)
williamr@2: {
williamr@2:   return __lexicographical_compare_3way((const unsigned char*) __first1,
williamr@2:                                         (const unsigned char*) __last1,
williamr@2:                                         (const unsigned char*) __first2,
williamr@2:                                         (const unsigned char*) __last2);
williamr@2: }
williamr@2: # endif
williamr@2: 
williamr@2: # ifndef _STLP_NO_EXTENSIONS
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2>
williamr@2: int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
williamr@2:                                  _InputIter2 __first2, _InputIter2 __last2);
williamr@2: 
williamr@2: # endif /* EXTENSIONS */
williamr@2: 
williamr@2: // count
williamr@2: template <class _InputIter, class _Tp>
williamr@2: _STLP_INLINE_LOOP _STLP_DIFFERENCE_TYPE(_InputIter)
williamr@2: count(_InputIter __first, _InputIter __last, const _Tp& __val) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   _STLP_DIFFERENCE_TYPE(_InputIter) __n = 0;
williamr@2:   for ( ; __first != __last; ++__first)
williamr@2:     if (*__first == __val)
williamr@2:       ++__n;
williamr@2:   return __n;
williamr@2: }
williamr@2: 
williamr@2: // find and find_if. Note find may be expressed in terms of find_if if appropriate binder was available.
williamr@2: template <class _InputIter, class _Tp>
williamr@2: _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val);
williamr@2: template <class _InputIter, class _Predicate>
williamr@2: _InputIter find_if(_InputIter __first, _InputIter __last, _Predicate __pred);
williamr@2: 
williamr@2: // search.
williamr@2: template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
williamr@2: _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
williamr@2:                      _ForwardIter2 __first2, _ForwardIter2 __last2, _BinaryPred  __predicate);
williamr@2: 
williamr@2: // find_first_of
williamr@2: template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
williamr@2: _InputIter __find_first_of(_InputIter __first1, _InputIter __last1,
williamr@2:                            _ForwardIter __first2, _ForwardIter __last2,
williamr@2:                            _BinaryPredicate __comp);
williamr@2: 
williamr@2: template <class _ForwardIter1, class _ForwardIter2, 
williamr@2:           class _BinaryPredicate>
williamr@2: _ForwardIter1 
williamr@2: find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 
williamr@2:          _ForwardIter2 __first2, _ForwardIter2 __last2,
williamr@2:          _BinaryPredicate __comp);
williamr@2: 
williamr@2: // replace
williamr@2: template <class _ForwardIter, class _Tp>
williamr@2: _STLP_INLINE_LOOP void 
williamr@2: replace(_ForwardIter __first, _ForwardIter __last,
williamr@2:         const _Tp& __old_value, const _Tp& __new_value) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:   for ( ; __first != __last; ++__first)
williamr@2:     if (*__first == __old_value)
williamr@2:       *__first = __new_value;
williamr@2: }
williamr@2: 
williamr@2: template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
williamr@2: _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
williamr@2:                               const _Tp& __val, _Compare __comp, _Distance*);
williamr@2: 
williamr@2: _STLP_END_NAMESPACE
williamr@2: 
williamr@2: # if !defined (_STLP_LINK_TIME_INSTANTIATION)
williamr@2: #  include <stl/_algobase.c>
williamr@2: # endif
williamr@2: 
williamr@2: #endif /* _STLP_INTERNAL_ALGOBASE_H */
williamr@2: 
williamr@2: // Local Variables:
williamr@2: // mode:C++
williamr@2: // End:
williamr@2: