williamr@2: /*
williamr@2:  *
williamr@4:  * Portions Copyright (c) 2008 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.
williamr@4:  *
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@4:  * 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@4:  * 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@4: #ifndef _STLP_INTERNAL_ALGOBASE_H
williamr@2: #  include <stl/_algobase.h>
williamr@4: #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@4:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
williamr@4:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
williamr@4:   for ( ; __first1 != __last1 && __first2 != __last2
williamr@4:         ; ++__first1, ++__first2) {
williamr@4:     if (*__first1 < *__first2) {
williamr@4:       return true;
williamr@2:     }
williamr@4:     if (*__first2 < *__first1)
williamr@4:       return false;
williamr@4:   }
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@4:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
williamr@4:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
williamr@4:   for ( ; __first1 != __last1 && __first2 != __last2
williamr@4:         ; ++__first1, ++__first2) {
williamr@4:     if (__comp(*__first1, *__first2)) {
williamr@4:       return true;
williamr@2:     }
williamr@4:     if (__comp(*__first2, *__first1))
williamr@4:       return false;
williamr@4:   }
williamr@2:   return __first1 == __last1 && __first2 != __last2;
williamr@2: }
williamr@2: 
williamr@4: #if !defined (_STLP_NO_EXTENSIONS)
williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2>
williamr@2: int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
williamr@4:                                    _InputIter2 __first2, _InputIter2 __last2) {
williamr@2:   while (__first1 != __last1 && __first2 != __last2) {
williamr@4:     if (*__first1 < *__first2) {
williamr@4:       _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
williamr@2:       return -1;
williamr@4:     }
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@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@2: 
williamr@2: template <class _InputIter1, class _InputIter2>
williamr@2: int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
williamr@4:                                  _InputIter2 __first2, _InputIter2 __last2) {
williamr@4:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
williamr@4:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
williamr@4:   return _STLP_PRIV __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
williamr@2: }
williamr@4: #endif
williamr@4: 
williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE
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@4:                                            const random_access_iterator_tag &) {
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@4:   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@4:     //++__first;
williamr@2:   case 0:
williamr@2:   default:
williamr@2:     return __last;
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@4: inline char*
williamr@4: __find(char* __first, char* __last, char __val, const random_access_iterator_tag &) {
williamr@4:   void *res =  memchr(__first, __val, __last - __first);
williamr@4:   return res != 0 ? __STATIC_CAST(char*, res) : __last;
williamr@4: }
williamr@4: inline const char*
williamr@4: __find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) {
williamr@4:   const void *res =  memchr(__first, __val, __last - __first);
williamr@4:   return res != 0 ? __STATIC_CAST(const char*, res) : __last;
williamr@4: }
williamr@4: 
williamr@2: template <class _RandomAccessIter, class _Predicate>
williamr@2: _STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last,
williamr@2:                                               _Predicate __pred,
williamr@4:                                               const random_access_iterator_tag &) {
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@4:       //++__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@4: _STLP_INLINE_LOOP _InputIter __find(_InputIter __first, _InputIter __last,
williamr@4:                                     const _Tp& __val,
williamr@4:                                     const input_iterator_tag &) {
williamr@4:   while (__first != __last && !(*__first == __val)) ++__first;
williamr@2:   return __first;
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _Predicate>
williamr@4: _STLP_INLINE_LOOP _InputIter __find_if(_InputIter __first, _STLP_MPW_EXTRA_CONST _InputIter __last,
williamr@4:                                        _Predicate __pred,
williamr@4:                                        const input_iterator_tag &) {
williamr@2:   while (__first != __last && !__pred(*__first))
williamr@2:     ++__first;
williamr@2:   return __first;
williamr@2: }
williamr@2: 
williamr@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@4: 
williamr@2: template <class _InputIter, class _Predicate>
williamr@2: _InputIter find_if(_InputIter __first, _InputIter __last,
williamr@2:                    _Predicate __pred) {
williamr@4:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4:   return _STLP_PRIV __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
williamr@2: }
williamr@2: 
williamr@2: template <class _InputIter, class _Tp>
williamr@4: _InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) {
williamr@4:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
williamr@4:   return _STLP_PRIV __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@4:                      _BinaryPred  __pred) {
williamr@4:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
williamr@4:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
williamr@4:   // Test for empty ranges
williamr@4:   if (__first1 == __last1 || __first2 == __last2)
williamr@4:     return __first1;
williamr@2: 
williamr@2:   // Test for a pattern of length 1.
williamr@4:   _ForwardIter2 __p1(__first2);
williamr@4: 
williamr@4:   if ( ++__p1 == __last2 ) {
williamr@4:     while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
williamr@2:       ++__first1;
williamr@4:     }
williamr@4:     return __first1;
williamr@2:   }
williamr@4: 
williamr@2:   // General case.
williamr@2: 
williamr@4:   for ( ; ; ) { // __first1 != __last1 will be checked below
williamr@4:     while (__first1 != __last1 && !__pred(*__first1, *__first2)) {
williamr@2:       ++__first1;
williamr@2:     }
williamr@4:     if (__first1 == __last1) {
williamr@2:       return __last1;
williamr@4:     }
williamr@4:     _ForwardIter2 __p = __p1;
williamr@4:     _ForwardIter1 __current = __first1;
williamr@2:     if (++__current == __last1) return __last1;
williamr@2: 
williamr@4:     while (__pred(*__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@4: _STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4: 
williamr@2: // find_first_of, with and without an explicitly supplied comparison function.
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@4:   for ( ; __first1 != __last1; ++__first1) {
williamr@4:     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) {
williamr@4:       if (__comp(*__first1, *__iter)) {
williamr@2:         return __first1;
williamr@4:       }
williamr@4:     }
williamr@4:   }
williamr@2:   return __last1;
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@4: // find_end for forward iterators.
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@4:                          _BinaryPredicate __comp) {
williamr@2:   if (__first2 == __last2)
williamr@2:     return __last1;
williamr@2:   else {
williamr@2:     _ForwardIter1 __result = __last1;
williamr@4:     for (;;) {
williamr@4:       _ForwardIter1 __new_result = 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@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@4: 
williamr@2: // find_end for bidirectional iterators.  Requires partial specialization.
williamr@4: #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
williamr@2: 
williamr@4: #  ifndef _STLP_INTERNAL_ITERATOR_H
williamr@2: _STLP_END_NAMESPACE
williamr@4: #    include <stl/_iterator.h>
williamr@4: _STLP_BEGIN_NAMESPACE
williamr@4: #  endif /*_STLP_INTERNAL_ITERATOR_H*/
williamr@4: 
williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE
williamr@2: 
williamr@2: template <class _BidirectionalIter1, class _BidirectionalIter2,
williamr@4:           class _BinaryPredicate>
williamr@2: _BidirectionalIter1
williamr@2: __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
williamr@2:            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
williamr@4:            const bidirectional_iterator_tag &, const bidirectional_iterator_tag &,
williamr@4:            _BinaryPredicate __comp) {
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@4: 
williamr@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@2: #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
williamr@2: 
williamr@4: template <class _ForwardIter1, class _ForwardIter2,
williamr@4:           class _BinaryPredicate>
williamr@4: _ForwardIter1
williamr@4: find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
williamr@2:          _ForwardIter2 __first2, _ForwardIter2 __last2,
williamr@4:          _BinaryPredicate __comp) {
williamr@4:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
williamr@4:   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
williamr@4:   return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
williamr@4: #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
williamr@4:                                _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
williamr@4:                                _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
williamr@4: #else
williamr@4:                                forward_iterator_tag(),
williamr@4:                                forward_iterator_tag(),
williamr@4: #endif
williamr@4:                                __comp);
williamr@2: }
williamr@2: 
williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4: 
williamr@4: template <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance>
williamr@4: _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
williamr@4:                            _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
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@4:     if (__comp1(*__middle, __val)) {
williamr@4:       _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
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@4:   if (&__comp2) {/* do nothing. to avoid warnings */} 
williamr@2:   return __first;
williamr@2: }
williamr@2: 
williamr@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@4: 
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: