stl/_algobase.c - platform/external/stlport - Git at Google

 /*
  *
  * 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_ALGOBASE_C
 #define _STLP_ALGOBASE_C

 #ifndef _STLP_INTERNAL_ALGOBASE_H
 #  include <stl/_algobase.h>
 #endif

 _STLP_BEGIN_NAMESPACE

 template <class _InputIter1, class _InputIter2>
 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
                              _InputIter2 __first2, _InputIter2 __last2) {
   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
   for ( ; __first1 != __last1 && __first2 != __last2
         ; ++__first1, ++__first2) {
     if (*__first1 < *__first2) {
       return true;
     }
     if (*__first2 < *__first1)
       return false;
   }
   return __first1 == __last1 && __first2 != __last2;
 }

 template <class _InputIter1, class _InputIter2, class _Compare>
 bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
                              _InputIter2 __first2, _InputIter2 __last2,
                              _Compare __comp) {
   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
   for ( ; __first1 != __last1 && __first2 != __last2
         ; ++__first1, ++__first2) {
     if (__comp(*__first1, *__first2)) {
       return true;
     }
     if (__comp(*__first2, *__first1))
       return false;
   }
   return __first1 == __last1 && __first2 != __last2;
 }

 #if !defined (_STLP_NO_EXTENSIONS)
 _STLP_MOVE_TO_PRIV_NAMESPACE

 template <class _InputIter1, class _InputIter2>
 int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
                                    _InputIter2 __first2, _InputIter2 __last2) {
   while (__first1 != __last1 && __first2 != __last2) {
     if (*__first1 < *__first2) {
       _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
       return -1;
     }
     if (*__first2 < *__first1)
       return 1;
     ++__first1;
     ++__first2;
   }
   if (__first2 == __last2) {
     return !(__first1 == __last1);
   }
   else {
     return -1;
   }
 }

 _STLP_MOVE_TO_STD_NAMESPACE

 template <class _InputIter1, class _InputIter2>
 int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
                                  _InputIter2 __first2, _InputIter2 __last2) {
   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
   return _STLP_PRIV __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
 }
 #endif

 _STLP_MOVE_TO_PRIV_NAMESPACE

 template <class _RandomAccessIter, class _Tp>
 _STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,
                                            const _Tp& __val,
                                            const random_access_iterator_tag &) {
   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;

   for ( ; __trip_count > 0 ; --__trip_count) {
     if (*__first == __val) return __first;
     ++__first;

     if (*__first == __val) return __first;
     ++__first;

     if (*__first == __val) return __first;
     ++__first;

     if (*__first == __val) return __first;
     ++__first;
   }

   switch (__last - __first) {
   case 3:
     if (*__first == __val) return __first;
     ++__first;
   case 2:
     if (*__first == __val) return __first;
     ++__first;
   case 1:
     if (*__first == __val) return __first;
     //++__first;
   case 0:
   default:
     return __last;
   }
 }

 inline char*
 __find(char* __first, char* __last, char __val, const random_access_iterator_tag &) {
   void *res =  memchr(__first, __val, __last - __first);
   return res != 0 ? __STATIC_CAST(char*, res) : __last;
 }
 inline const char*
 __find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) {
   const void *res =  memchr(__first, __val, __last - __first);
   return res != 0 ? __STATIC_CAST(const char*, res) : __last;
 }

 template <class _RandomAccessIter, class _Predicate>
 _STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
                                               _Predicate __pred,
                                               const random_access_iterator_tag &) {
   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;

   for ( ; __trip_count > 0 ; --__trip_count) {
     if (__pred(*__first)) return __first;
     ++__first;

     if (__pred(*__first)) return __first;
     ++__first;

     if (__pred(*__first)) return __first;
     ++__first;

     if (__pred(*__first)) return __first;
     ++__first;
   }

   switch(__last - __first) {
   case 3:
     if (__pred(*__first)) return __first;
     ++__first;
   case 2:
     if (__pred(*__first)) return __first;
     ++__first;
   case 1:
     if (__pred(*__first)) return __first;
       //++__first;
   case 0:
   default:
     return __last;
   }
 }

 template <class _InputIter, class _Tp>
 _STLP_INLINE_LOOP _InputIter __find(_InputIter __first, _InputIter __last,
                                     const _Tp& __val,
                                     const input_iterator_tag &) {
   while (__first != __last && !(*__first == __val)) ++__first;
   return __first;
 }

 template <class _InputIter, class _Predicate>
 _STLP_INLINE_LOOP _InputIter __find_if(_InputIter __first, _STLP_MPW_EXTRA_CONST _InputIter __last,
                                        _Predicate __pred,
                                        const input_iterator_tag &) {
   while (__first != __last && !__pred(*__first))
     ++__first;
   return __first;
 }

 _STLP_MOVE_TO_STD_NAMESPACE

 template <class _InputIter, class _Predicate>
 _InputIter find_if(_InputIter __first, _InputIter __last,
                    _Predicate __pred) {
   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   return _STLP_PRIV __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
 }

 template <class _InputIter, class _Tp>
 _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) {
   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
   return _STLP_PRIV __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
 }

 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
                      _ForwardIter2 __first2, _ForwardIter2 __last2,
                      _BinaryPred  __pred) {
   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
   // Test for empty ranges
   if (__first1 == __last1 || __first2 == __last2)
     return __first1;

   // Test for a pattern of length 1.
   _ForwardIter2 __p1(__first2);

   if ( ++__p1 == __last2 ) {
     while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
       ++__first1;
     }
     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

 // 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 = 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 reverse_iterator<_BidirectionalIter1> _RevIter1;
   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;

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

   if (__rresult == __rlast1)
     return __last1;
   else {
     _BidirectionalIter1 __result = __rresult.base();
     advance(__result, -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 = distance(__first, __last);
   _Distance __half;
   _ForwardIter __middle;

   while (__len > 0) {
     __half = __len >> 1;
     __middle = __first;
     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:
	/*
	*
	* 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_ALGOBASE_C
	#define _STLP_ALGOBASE_C

	#ifndef _STLP_INTERNAL_ALGOBASE_H
	# include <stl/_algobase.h>
	#endif

	_STLP_BEGIN_NAMESPACE

	template <class _InputIter1, class _InputIter2>
	bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
	_InputIter2 __first2, _InputIter2 __last2) {
	_STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
	_STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
	for ( ; __first1 != __last1 && __first2 != __last2
	; ++__first1, ++__first2) {
	if (__first1 < __first2) {
	return true;
	}
	if (__first2 < __first1)
	return false;
	}
	return __first1 == __last1 && __first2 != __last2;
	}

	template <class _InputIter1, class _InputIter2, class _Compare>
	bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
	_InputIter2 __first2, _InputIter2 __last2,
	_Compare __comp) {
	_STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
	_STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
	for ( ; __first1 != __last1 && __first2 != __last2
	; ++__first1, ++__first2) {
	if (__comp(__first1, __first2)) {
	return true;
	}
	if (__comp(__first2, __first1))
	return false;
	}
	return __first1 == __last1 && __first2 != __last2;
	}

	#if !defined (_STLP_NO_EXTENSIONS)
	_STLP_MOVE_TO_PRIV_NAMESPACE

	template <class _InputIter1, class _InputIter2>
	int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
	_InputIter2 __first2, _InputIter2 __last2) {
	while (__first1 != __last1 && __first2 != __last2) {
	if (__first1 < __first2) {
	_STLP_VERBOSE_ASSERT(!(__first2 < __first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
	return -1;
	}
	if (__first2 < __first1)
	return 1;
	++__first1;
	++__first2;
	}
	if (__first2 == __last2) {
	return !(__first1 == __last1);
	}
	else {
	return -1;
	}
	}

	_STLP_MOVE_TO_STD_NAMESPACE

	template <class _InputIter1, class _InputIter2>
	int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
	_InputIter2 __first2, _InputIter2 __last2) {
	_STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
	_STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
	return _STLP_PRIV __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
	}
	#endif

	_STLP_MOVE_TO_PRIV_NAMESPACE

	template <class _RandomAccessIter, class _Tp>
	_STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,
	const _Tp& __val,
	const random_access_iterator_tag &) {
	_STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;

	for ( ; __trip_count > 0 ; --__trip_count) {
	if (*__first == __val) return __first;
	++__first;

	if (*__first == __val) return __first;
	++__first;

	if (*__first == __val) return __first;
	++__first;

	if (*__first == __val) return __first;
	++__first;
	}

	switch (__last - __first) {
	case 3:
	if (*__first == __val) return __first;
	++__first;
	case 2:
	if (*__first == __val) return __first;
	++__first;
	case 1:
	if (*__first == __val) return __first;
	//++__first;
	case 0:
	default:
	return __last;
	}
	}

	inline char*
	__find(char* __first, char* __last, char __val, const random_access_iterator_tag &) {
	void *res = memchr(__first, __val, __last - __first);
	return res != 0 ? __STATIC_CAST(char*, res) : __last;
	}
	inline const char*
	__find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) {
	const void *res = memchr(__first, __val, __last - __first);
	return res != 0 ? __STATIC_CAST(const char*, res) : __last;
	}

	template <class _RandomAccessIter, class _Predicate>
	_STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
	_Predicate __pred,
	const random_access_iterator_tag &) {
	_STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;

	for ( ; __trip_count > 0 ; --__trip_count) {
	if (__pred(*__first)) return __first;
	++__first;

	if (__pred(*__first)) return __first;
	++__first;

	if (__pred(*__first)) return __first;
	++__first;

	if (__pred(*__first)) return __first;
	++__first;
	}

	switch(__last - __first) {
	case 3:
	if (__pred(*__first)) return __first;
	++__first;
	case 2:
	if (__pred(*__first)) return __first;
	++__first;
	case 1:
	if (__pred(*__first)) return __first;
	//++__first;
	case 0:
	default:
	return __last;
	}
	}

	template <class _InputIter, class _Tp>
	_STLP_INLINE_LOOP _InputIter __find(_InputIter __first, _InputIter __last,
	const _Tp& __val,
	const input_iterator_tag &) {
	while (__first != __last && !(*__first == __val)) ++__first;
	return __first;
	}

	template <class _InputIter, class _Predicate>
	_STLP_INLINE_LOOP _InputIter __find_if(_InputIter __first, _STLP_MPW_EXTRA_CONST _InputIter __last,
	_Predicate __pred,
	const input_iterator_tag &) {
	while (__first != __last && !__pred(*__first))
	++__first;
	return __first;
	}

	_STLP_MOVE_TO_STD_NAMESPACE

	template <class _InputIter, class _Predicate>
	_InputIter find_if(_InputIter __first, _InputIter __last,
	_Predicate __pred) {
	_STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
	return _STLP_PRIV __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
	}

	template <class _InputIter, class _Tp>
	_InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) {
	_STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
	return _STLP_PRIV __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
	}

	template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
	_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
	_ForwardIter2 __first2, _ForwardIter2 __last2,
	_BinaryPred __pred) {
	_STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
	_STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
	// Test for empty ranges
	if (__first1 == __last1 \|\| __first2 == __last2)
	return __first1;

	// Test for a pattern of length 1.
	_ForwardIter2 __p1(__first2);

	if ( ++__p1 == __last2 ) {
	while (__first1 != __last1 && !__pred(__first1, __first2)) {
	++__first1;
	}
	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

	// 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 = 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 reverse_iterator<_BidirectionalIter1> _RevIter1;
	typedef reverse_iterator<_BidirectionalIter2> _RevIter2;

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

	if (__rresult == __rlast1)
	return __last1;
	else {
	_BidirectionalIter1 __result = __rresult.base();
	advance(__result, -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 = distance(__first, __last);
	_Distance __half;
	_ForwardIter __middle;

	while (__len > 0) {
	__half = __len >> 1;
	__middle = __first;
	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: