STLport

/* * * 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_ALGO_C #define _STLP_ALGO_C #if !defined (_STLP_INTERNAL_ALGO_H) # include <stl/_algo.h> #endif #ifndef _STLP_INTERNAL_TEMPBUF_H # include <stl/_tempbuf.h> #endif _STLP_BEGIN_NAMESPACE _STLP_MOVE_TO_PRIV_NAMESPACE template <class _BidirectionalIter, class _Distance, class _Compare> void __merge_without_buffer(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last, _Distance __len1, _Distance __len2, _Compare __comp); template <class _BidirectionalIter1, class _BidirectionalIter2, class _BidirectionalIter3, class _Compare> _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, _BidirectionalIter3 __result, _Compare __comp); template <class _Tp> #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 )) inline #endif const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { if (__a < __b) if (__b < __c) return __b; else if (__a < __c) return __c; else return __a; else if (__a < __c) return __a; else if (__b < __c) return __c; else return __b; } template <class _Tp, class _Compare> #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 )) inline #endif const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { if (__comp(__a, __b)) { _STLP_VERBOSE_ASSERT(!__comp(__b, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) if (__comp(__b, __c)) { _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) return __b; } else if (__comp(__a, __c)) { _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) return __c; } else return __a; } else if (__comp(__a, __c)) { _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) return __a; } else if (__comp(__b, __c)) { _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) return __c; } else return __b; } _STLP_MOVE_TO_STD_NAMESPACE template <class _ForwardIter1, class _ForwardIter2> _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, _ForwardIter2 __first2, _ForwardIter2 __last2) { _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 ) return find(__first1, __last1, *__first2); // General case. for ( ; ; ) { // __first1 != __last1 will be checked in find below __first1 = find(__first1, __last1, *__first2); if (__first1 == __last1) return __last1; _ForwardIter2 __p = __p1; _ForwardIter1 __current = __first1; if (++__current == __last1) return __last1; while (*__current == *__p) { if (++__p == __last2) return __first1; if (++__current == __last1) return __last1; } ++__first1; } return __first1; } _STLP_MOVE_TO_PRIV_NAMESPACE template <class _RandomAccessIter, class _Integer, class _Tp, class _BinaryPred, class _Distance> _RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last, _Integer __count, const _Tp& __val, _BinaryPred __pred, _Distance*, const random_access_iterator_tag &) { _Distance __tailSize = __last - __first; const _Distance __pattSize = __count; const _Distance __skipOffset = __pattSize - 1; _RandomAccessIter __backTrack; _Distance __remainder, __prevRemainder; for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) { // the main loop... //__lookAhead here is always pointing to the last element of next possible match. __tailSize -= __pattSize; while ( !__pred(*__lookAhead, __val) ) { // the skip loop... if (__tailSize < __pattSize) return __last; __lookAhead += __pattSize; __tailSize -= __pattSize; } if ( __skipOffset == 0 ) { return (__lookAhead - __skipOffset); //Success } __remainder = __skipOffset; for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) { if (--__remainder == 0) return (__lookAhead - __skipOffset); //Success } if (__remainder > __tailSize) return __last; //failure __lookAhead += __remainder; __tailSize -= __remainder; while ( __pred(*__lookAhead, __val) ) { __prevRemainder = __remainder; __backTrack = __lookAhead; do { if (--__remainder == 0) return (__lookAhead - __skipOffset); //Success } while (__pred(*--__backTrack, __val)); //adjust remainder for next comparison __remainder += __pattSize - __prevRemainder; if (__remainder > __tailSize) return __last; //failure __lookAhead += __remainder; __tailSize -= __remainder; } //__lookAhead here is always pointing to the element of the last mismatch. } return __last; //failure } template <class _ForwardIter, class _Integer, class _Tp, class _Distance, class _BinaryPred> _ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp& __val, _BinaryPred __pred, _Distance*, const forward_iterator_tag &) { for (; (__first != __last) && !__pred(*__first, __val); ++__first) {} while (__first != __last) { _Integer __n = __count - 1; _ForwardIter __i = __first; ++__i; while (__i != __last && __n != 0 && __pred(*__i, __val)) { ++__i; --__n; } if (__n == 0) return __first; else if (__i != __last) for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {} else break; } return __last; } _STLP_MOVE_TO_STD_NAMESPACE // search_n. Search for __count consecutive copies of __val. template <class _ForwardIter, class _Integer, class _Tp> _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, _Integer __count, const _Tp& __val) { _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) if (__count <= 0) return __first; if (__count == 1) //We use find when __count == 1 to use potential find overload. return find(__first, __last, __val); return _STLP_PRIV __search_n(__first, __last, __count, __val, equal_to<_Tp>(), _STLP_DISTANCE_TYPE(__first, _ForwardIter),