diff -r 2fe1408b6811 -r e1b950c65cb4 epoc32/include/stdapis/stlportv5/stl/_algobase.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/epoc32/include/stdapis/stlportv5/stl/_algobase.c Wed Mar 31 12:27:01 2010 +0100 @@ -0,0 +1,392 @@ +/* + * + * 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 + +# if !defined (_STLP_INTERNAL_ALGOBASE_H) +# include +# endif + +_STLP_BEGIN_NAMESPACE + +template +bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1, + _InputIter2 __first2, _InputIter2 __last2) { + _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) + _STLP_DEBUG_CHECK(__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 +bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1, + _InputIter2 __first2, _InputIter2 __last2, + _Compare __comp) { + _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) + _STLP_DEBUG_CHECK(__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; +} + +# ifndef _STLP_NO_EXTENSIONS + +template +int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, + _InputIter2 __first2, _InputIter2 __last2) +{ + while (__first1 != __last1 && __first2 != __last2) { + if (*__first1 < *__first2) + return -1; + if (*__first2 < *__first1) + return 1; + ++__first1; + ++__first2; + } + if (__first2 == __last2) { + return !(__first1 == __last1); + } + else { + return -1; + } +} + + +template +int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, + _InputIter2 __first2, _InputIter2 __last2) +{ + _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) + _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) + return __lexicographical_compare_3way(__first1, __last1, __first2, __last2); +} +# endif + +template +_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; + } +} + +template +_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 +inline _InputIter __find(_InputIter __first, _InputIter __last, + const _Tp& __val, + const input_iterator_tag &) +{ + while (__first != __last && !(*__first == __val)) + ++__first; + return __first; +} + +template +inline _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; +} + +template +_InputIter find_if(_InputIter __first, _InputIter __last, + _Predicate __pred) { + _STLP_DEBUG_CHECK(__check_range(__first, __last)) + return __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter)); +} + +template +_InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) +{ + _STLP_DEBUG_CHECK(__check_range(__first, __last)) + return __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter)); +} + +template +_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, + _ForwardIter2 __first2, _ForwardIter2 __last2, + _BinaryPred __predicate) +{ + _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) + _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) + // Test for empty ranges + if (__first1 == __last1 || __first2 == __last2) + return __first1; + + // Test for a pattern of length 1. + _ForwardIter2 __tmp(__first2); + ++__tmp; + if (__tmp == __last2) { + while (__first1 != __last1 && !__predicate(*__first1, *__first2)) + ++__first1; + return __first1; + } + + // General case. + + _ForwardIter2 __p1, __p; + + __p1 = __first2; ++__p1; + + // _ForwardIter1 __current = __first1; + + while (__first1 != __last1) { + while (__first1 != __last1) { + if (__predicate(*__first1, *__first2)) + break; + ++__first1; + } + while (__first1 != __last1 && !__predicate(*__first1, *__first2)) + ++__first1; + if (__first1 == __last1) + return __last1; + + __p = __p1; + _ForwardIter1 __current = __first1; + if (++__current == __last1) return __last1; + + while (__predicate(*__current, *__p)) { + if (++__p == __last2) + return __first1; + if (++__current == __last1) + return __last1; + } + + ++__first1; + } + return __first1; +} + +// find_first_of, with and without an explicitly supplied comparison function. + +template +_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 +_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; + while (1) { + _ForwardIter1 __new_result + = search(__first1, __last1, __first2, __last2, __comp); + if (__new_result == __last1) + return __result; + else { + __result = __new_result; + __first1 = __new_result; + ++__first1; + } + } + } +} + +// find_end for bidirectional iterators. Requires partial specialization. +#if defined ( _STLP_CLASS_PARTIAL_SPECIALIZATION ) + +#if ! defined (_STLP_INTERNAL_ITERATOR_H) +_STLP_END_NAMESPACE +# include +_STLP_BEGIN_NAMESPACE +#endif + +template +_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; + } +} +#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ + +template +_ForwardIter1 +find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, + _ForwardIter2 __first2, _ForwardIter2 __last2, + _BinaryPredicate __comp) +{ + _STLP_DEBUG_CHECK(__check_range(__first1, __last1)) + _STLP_DEBUG_CHECK(__check_range(__first2, __last2)) + return __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); +} + +template +_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, + const _Tp& __val, _Compare __comp, _Distance*) +{ + _Distance __len = distance(__first, __last); + _Distance __half; + _ForwardIter __middle; + + while (__len > 0) { + __half = __len >> 1; + __middle = __first; + advance(__middle, __half); + if (__comp(*__middle, __val)) { + __first = __middle; + ++__first; + __len = __len - __half - 1; + } + else + __len = __half; + } + return __first; +} + +_STLP_END_NAMESPACE + +#endif /* _STLP_ALGOBASE_C */ + +// Local Variables: +// mode:C++ +// End: