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: #ifndef _STLP_ALGOBASE_C
williamr@2: #define _STLP_ALGOBASE_C
williamr@2: 
williamr@2: # if !defined (_STLP_INTERNAL_ALGOBASE_H)
williamr@2: #  include <stl/_algobase.h>
williamr@2: # endif
williamr@2: 
williamr@2: _STLP_BEGIN_NAMESPACE
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:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:     _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:     for ( ; __first1 != __last1 && __first2 != __last2
williamr@2: 	    ; ++__first1, ++__first2) {
williamr@2:       if (*__first1 < *__first2)
williamr@2: 	return true;
williamr@2:       if (*__first2 < *__first1)
williamr@2: 	return false;
williamr@2:     }
williamr@2:   return __first1 == __last1 && __first2 != __last2;
williamr@2: }
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:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:     _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:     for ( ; __first1 != __last1 && __first2 != __last2
williamr@2: 	    ; ++__first1, ++__first2) {
williamr@2:       if (__comp(*__first1, *__first2))
williamr@2: 	return true;
williamr@2:       if (__comp(*__first2, *__first1))
williamr@2: 	return false;
williamr@2:     }
williamr@2:   return __first1 == __last1 && __first2 != __last2;
williamr@2: }
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:   while (__first1 != __last1 && __first2 != __last2) {
williamr@2:     if (*__first1 < *__first2)
williamr@2:       return -1;
williamr@2:     if (*__first2 < *__first1)
williamr@2:       return 1;
williamr@2:     ++__first1;
williamr@2:     ++__first2;
williamr@2:   }
williamr@2:   if (__first2 == __last2) {
williamr@2:     return !(__first1 == __last1);
williamr@2:   }
williamr@2:   else {
williamr@2:     return -1;
williamr@2:   }
williamr@2: }
williamr@2: 
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:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:     _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:     return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
williamr@2: }
williamr@2: # endif
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Tp>
williamr@2: _STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last,
williamr@2:                                            const _Tp& __val,
williamr@2:                                            const random_access_iterator_tag &)
williamr@2: {
williamr@2:   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
williamr@2: 
williamr@2:   for ( ; __trip_count > 0 ; --__trip_count) {
williamr@2:     if (*__first == __val) return __first;
williamr@2:     ++__first;
williamr@2: 
williamr@2:     if (*__first == __val) return __first;
williamr@2:     ++__first;
williamr@2: 
williamr@2:     if (*__first == __val) return __first;
williamr@2:     ++__first;
williamr@2: 
williamr@2:     if (*__first == __val) return __first;
williamr@2:     ++__first;
williamr@2:   }
williamr@2: 
williamr@2:   switch(__last - __first) {
williamr@2:   case 3:
williamr@2:     if (*__first == __val) return __first;
williamr@2:     ++__first;
williamr@2:   case 2:
williamr@2:     if (*__first == __val) return __first;
williamr@2:     ++__first;
williamr@2:   case 1:
williamr@2:     if (*__first == __val) return __first;
williamr@2:     ++__first;
williamr@2:   case 0:
williamr@2:   default:
williamr@2:     return __last;
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template <class _RandomAccessIter, class _Predicate>
williamr@2: _STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
williamr@2:                                               _Predicate __pred,
williamr@2:                                               const random_access_iterator_tag &)
williamr@2: {
williamr@2:   _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2;
williamr@2: 
williamr@2:   for ( ; __trip_count > 0 ; --__trip_count) {
williamr@2:     if (__pred(*__first)) return __first;
williamr@2:     ++__first;
williamr@2: 
williamr@2:     if (__pred(*__first)) return __first;
williamr@2:     ++__first;
williamr@2: 
williamr@2:     if (__pred(*__first)) return __first;
williamr@2:     ++__first;
williamr@2: 
williamr@2:     if (__pred(*__first)) return __first;
williamr@2:     ++__first;
williamr@2:   }
williamr@2: 
williamr@2:   switch(__last - __first) {
williamr@2:   case 3:
williamr@2:     if (__pred(*__first)) return __first;
williamr@2:     ++__first;
williamr@2:   case 2:
williamr@2:     if (__pred(*__first)) return __first;
williamr@2:     ++__first;
williamr@2:   case 1:
williamr@2:     if (__pred(*__first)) return __first;
williamr@2:     //    ++__first;
williamr@2:   case 0:
williamr@2:   default:
williamr@2:     return __last;
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _Tp>
williamr@2: inline _InputIter __find(_InputIter __first, _InputIter __last,
williamr@2: 			 const _Tp& __val,
williamr@2: 			 const input_iterator_tag &)
williamr@2: {
williamr@2:   while (__first != __last && !(*__first == __val))
williamr@2:     ++__first;
williamr@2:   return __first;
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _Predicate>
williamr@2: inline _InputIter __find_if(_InputIter __first, _STLP_MPW_EXTRA_CONST _InputIter __last,
williamr@2:                             _Predicate __pred,
williamr@2:                             const input_iterator_tag &)
williamr@2: {
williamr@2:   while (__first != __last && !__pred(*__first))
williamr@2:     ++__first;
williamr@2:   return __first;
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _Predicate>
williamr@2: _InputIter find_if(_InputIter __first, _InputIter __last,
williamr@2:                    _Predicate __pred) {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:     return __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _Tp>
williamr@2: _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val)
williamr@2: {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first, __last))
williamr@2:     return __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
williamr@2: }
williamr@2: 
williamr@2: template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
williamr@2: _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
williamr@2:                      _ForwardIter2 __first2, _ForwardIter2 __last2,
williamr@2:                      _BinaryPred  __predicate) 
williamr@2: {
williamr@2:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:     _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:     // Test for empty ranges
williamr@2:     if (__first1 == __last1 || __first2 == __last2)
williamr@2:       return __first1;
williamr@2: 
williamr@2:   // Test for a pattern of length 1.
williamr@2:   _ForwardIter2 __tmp(__first2);
williamr@2:   ++__tmp;
williamr@2:   if (__tmp == __last2) {
williamr@2:     while (__first1 != __last1 && !__predicate(*__first1, *__first2))
williamr@2:       ++__first1;
williamr@2:     return __first1;    
williamr@2:   }
williamr@2:   
williamr@2:   // General case.
williamr@2: 
williamr@2:   _ForwardIter2 __p1, __p;
williamr@2: 
williamr@2:   __p1 = __first2; ++__p1;
williamr@2: 
williamr@2:   //  _ForwardIter1 __current = __first1;
williamr@2: 
williamr@2:   while (__first1 != __last1) {
williamr@2:     while (__first1 != __last1) {
williamr@2:       if (__predicate(*__first1, *__first2))
williamr@2:         break;
williamr@2:       ++__first1;
williamr@2:     }
williamr@2:     while (__first1 != __last1 && !__predicate(*__first1, *__first2))
williamr@2:       ++__first1;
williamr@2:     if (__first1 == __last1)
williamr@2:       return __last1;
williamr@2: 
williamr@2:     __p = __p1;
williamr@2:     _ForwardIter1 __current = __first1; 
williamr@2:     if (++__current == __last1) return __last1;
williamr@2: 
williamr@2:     while (__predicate(*__current, *__p)) {
williamr@2:       if (++__p == __last2)
williamr@2:         return __first1;
williamr@2:       if (++__current == __last1)
williamr@2:         return __last1;
williamr@2:     }
williamr@2: 
williamr@2:     ++__first1;
williamr@2:   }
williamr@2:   return __first1;
williamr@2: }
williamr@2: 
williamr@2: // find_first_of, with and without an explicitly supplied comparison function.
williamr@2: 
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:   for ( ; __first1 != __last1; ++__first1) 
williamr@2:     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
williamr@2:       if (__comp(*__first1, *__iter))
williamr@2:         return __first1;
williamr@2:   return __last1;
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: // find_end, with and without an explicitly supplied comparison function.
williamr@2: // Search [first2, last2) as a subsequence in [first1, last1), and return
williamr@2: // the *last* possible match.  Note that find_end for bidirectional iterators
williamr@2: // is much faster than for forward iterators.
williamr@2: 
williamr@2: // find_end for forward iterators. 
williamr@2: 
williamr@2: template <class _ForwardIter1, class _ForwardIter2,
williamr@2:   class _BinaryPredicate>
williamr@2: _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
williamr@2:                          _ForwardIter2 __first2, _ForwardIter2 __last2,
williamr@2:                          const forward_iterator_tag &, const forward_iterator_tag &,
williamr@2:                          _BinaryPredicate __comp)
williamr@2: {
williamr@2:   if (__first2 == __last2)
williamr@2:     return __last1;
williamr@2:   else {
williamr@2:     _ForwardIter1 __result = __last1;
williamr@2:     while (1) {
williamr@2:       _ForwardIter1 __new_result
williamr@2:         = search(__first1, __last1, __first2, __last2, __comp);
williamr@2:       if (__new_result == __last1)
williamr@2:         return __result;
williamr@2:       else {
williamr@2:         __result = __new_result;
williamr@2:         __first1 = __new_result;
williamr@2:         ++__first1;
williamr@2:       }
williamr@2:     }
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: // find_end for bidirectional iterators.  Requires partial specialization.
williamr@2: #if defined ( _STLP_CLASS_PARTIAL_SPECIALIZATION )
williamr@2: 
williamr@2: #if ! defined (_STLP_INTERNAL_ITERATOR_H)
williamr@2: _STLP_END_NAMESPACE
williamr@2: # include <stl/_iterator.h>
williamr@2: _STLP_BEGIN_NAMESPACE 
williamr@2: #endif
williamr@2: 
williamr@2: template <class _BidirectionalIter1, class _BidirectionalIter2,
williamr@2:   class _BinaryPredicate>
williamr@2: _BidirectionalIter1
williamr@2: __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
williamr@2:            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
williamr@2:            const bidirectional_iterator_tag &, const bidirectional_iterator_tag &, 
williamr@2:            _BinaryPredicate __comp)
williamr@2: {
williamr@2:   typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
williamr@2:   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
williamr@2: 
williamr@2:   _RevIter1 __rlast1(__first1);
williamr@2:   _RevIter2 __rlast2(__first2);
williamr@2:   _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
williamr@2:                                _RevIter2(__last2), __rlast2,
williamr@2:                                __comp);
williamr@2: 
williamr@2:   if (__rresult == __rlast1)
williamr@2:     return __last1;
williamr@2:   else {
williamr@2:     _BidirectionalIter1 __result = __rresult.base();
williamr@2:     advance(__result, -distance(__first2, __last2));
williamr@2:     return __result;
williamr@2:   }
williamr@2: }
williamr@2: #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
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:   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
williamr@2:     _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
williamr@2:     return __find_end(__first1, __last1, __first2, __last2,
williamr@2: # if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
williamr@2: 		      _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
williamr@2: 		      _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
williamr@2: # else
williamr@2: 		      forward_iterator_tag(),
williamr@2: 		      forward_iterator_tag(),
williamr@2: # endif
williamr@2: 		      __comp);
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:   _Distance __len = distance(__first, __last);
williamr@2:   _Distance __half;
williamr@2:   _ForwardIter __middle;
williamr@2: 
williamr@2:   while (__len > 0) {
williamr@2:     __half = __len >> 1;
williamr@2:     __middle = __first;
williamr@2:     advance(__middle, __half);
williamr@2:     if (__comp(*__middle, __val)) {
williamr@2:       __first = __middle;
williamr@2:       ++__first;
williamr@2:       __len = __len - __half - 1;
williamr@2:     }
williamr@2:     else
williamr@2:       __len = __half;
williamr@2:   }
williamr@2:   return __first;
williamr@2: }
williamr@2: 
williamr@2: _STLP_END_NAMESPACE
williamr@2: 
williamr@2: #endif /* _STLP_ALGOBASE_C */
williamr@2: 
williamr@2: // Local Variables:
williamr@2: // mode:C++
williamr@2: // End: