19720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 29720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 39720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1994 49720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Hewlett-Packard Company 59720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 69720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1996,1997 79720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Silicon Graphics Computer Systems, Inc. 89720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 99720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1997 109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Moscow Center for SPARC Technology 119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1999 139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Boris Fomitchev 149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * This material is provided "as is", with absolutely no warranty expressed 169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * or implied. Any use is at your own risk. 179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to use or copy this software for any purpose is hereby granted 199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * without fee, provided the above notices are retained on all copies. 209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to modify the code and to distribute modified code is granted, 219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * provided the above notices are retained, and a notice that the code was 229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * modified is included with the above copyright notice. 239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_ALGOBASE_C 269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_ALGOBASE_C 279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ALGOBASE_H 299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_algobase.h> 309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 32e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#ifndef _STLP_INTERNAL_FUNCTION_BASE_H 33e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# include <stl/_function_base.h> 34e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif 35e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE 379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2> 399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1, 409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2) { 419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first1 != __last1 && __first2 != __last2 449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ; ++__first1, ++__first2) { 459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first1 < *__first2) { 46e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return true; 489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first2 < *__first1) 509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first1 == __last1 && __first2 != __last2; 539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _Compare> 569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1, 579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first1 != __last1 && __first2 != __last2 629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ; ++__first1, ++__first2) { 639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__first1, *__first2)) { 64e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), 65e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return true; 679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__first2, *__first1)) 699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first1 == __last1 && __first2 != __last2; 729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_NO_EXTENSIONS) 759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2> 789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockint __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, 799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2) { 809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first1 != __last1 && __first2 != __last2) { 819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first1 < *__first2) { 829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!(*__first2 < *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return -1; 849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first2 < *__first1) 869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return 1; 879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first2; 899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first2 == __last2) { 919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return !(__first1 == __last1); 929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return -1; 959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2> 1019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockint lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, 1029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2) { 1039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 1049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 1059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __lexicographical_compare_3way(__first1, __last1, __first2, __last2); 1069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 1089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 1109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Tp> 1129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _RandomAccessIter __find(_RandomAccessIter __first, _RandomAccessIter __last, 1139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Tp& __val, 1149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const random_access_iterator_tag &) { 1159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2; 1169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __trip_count > 0 ; --__trip_count) { 1189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first == __val) return __first; 1199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 1209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first == __val) return __first; 1229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 1239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first == __val) return __first; 1259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 1269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first == __val) return __first; 1289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 1299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block switch (__last - __first) { 1329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case 3: 1339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first == __val) return __first; 1349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 1359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case 2: 1369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first == __val) return __first; 1379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 1389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case 1: 1399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first == __val) return __first; 1409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //++__first; 1419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case 0: 1429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block default: 1439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; 1449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline char* 1489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__find(char* __first, char* __last, char __val, const random_access_iterator_tag &) { 1499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void *res = memchr(__first, __val, __last - __first); 1509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return res != 0 ? __STATIC_CAST(char*, res) : __last; 1519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline const char* 1539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__find(const char* __first, const char* __last, char __val, const random_access_iterator_tag &) { 1549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const void *res = memchr(__first, __val, __last - __first); 1559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return res != 0 ? __STATIC_CAST(const char*, res) : __last; 1569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Predicate> 1599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _RandomAccessIter __find_if(_RandomAccessIter __first, _RandomAccessIter __last, 1609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Predicate __pred, 1619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const random_access_iterator_tag &) { 1629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DIFFERENCE_TYPE(_RandomAccessIter) __trip_count = (__last - __first) >> 2; 1639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __trip_count > 0 ; --__trip_count) { 1659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pred(*__first)) return __first; 1669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 1679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pred(*__first)) return __first; 1699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 1709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pred(*__first)) return __first; 1729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 1739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pred(*__first)) return __first; 1759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 1769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block switch(__last - __first) { 1799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case 3: 1809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pred(*__first)) return __first; 1819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 1829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case 2: 1839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pred(*__first)) return __first; 1849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 1859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case 1: 1869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pred(*__first)) return __first; 1879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //++__first; 1889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case 0: 1899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block default: 1909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; 1919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _Tp> 1959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _InputIter __find(_InputIter __first, _InputIter __last, 1969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Tp& __val, 1979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const input_iterator_tag &) { 1989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first != __last && !(*__first == __val)) ++__first; 1999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 2009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _Predicate> 203e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_STLP_INLINE_LOOP _InputIter __find_if(_InputIter __first, _InputIter __last, 2049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Predicate __pred, 2059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const input_iterator_tag &) { 2069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first != __last && !__pred(*__first)) 2079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 2089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 2099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 2129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _Predicate> 2149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_InputIter find_if(_InputIter __first, _InputIter __last, 2159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Predicate __pred) { 2169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 2179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __find_if(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _InputIter)); 2189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _Tp> 2219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_InputIter find(_InputIter __first, _InputIter __last, const _Tp& __val) { 2229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 2239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __find(__first, __last, __val, _STLP_ITERATOR_CATEGORY(__first, _InputIter)); 2249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter1, class _ForwardIter2, class _BinaryPred> 2279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, 2289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter2 __first2, _ForwardIter2 __last2, 2299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPred __pred) { 2309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 2319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 2329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Test for empty ranges 2339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first1 == __last1 || __first2 == __last2) 2349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first1; 2359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Test for a pattern of length 1. 2379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter2 __p1(__first2); 2389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if ( ++__p1 == __last2 ) { 2409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first1 != __last1 && !__pred(*__first1, *__first2)) { 2419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 2429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first1; 2449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // General case. 2479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; ; ) { // __first1 != __last1 will be checked below 2499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first1 != __last1 && !__pred(*__first1, *__first2)) { 2509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 2519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first1 == __last1) { 2539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last1; 2549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter2 __p = __p1; 2569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter1 __current = __first1; 2579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (++__current == __last1) return __last1; 2589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__pred(*__current, *__p)) { 2609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (++__p == __last2) 2619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first1; 2629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (++__current == __last1) 2639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last1; 2649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 2669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first1; 2689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 271e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _Tp> 272e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottstruct _IsCharLikeType 273e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ typedef __false_type _Ret; }; 274e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 275e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_STLP_TEMPLATE_NULL struct _IsCharLikeType<char> 276e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ typedef __true_type _Ret; }; 277e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 278e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_STLP_TEMPLATE_NULL struct _IsCharLikeType<unsigned char> 279e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ typedef __true_type _Ret; }; 280e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 281e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# ifndef _STLP_NO_SIGNED_BUILTINS 282e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_STLP_TEMPLATE_NULL struct _IsCharLikeType<signed char> 283e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ typedef __true_type _Ret; }; 284e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 285e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 286e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _Tp1, class _Tp2> 287e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottinline bool __stlp_eq(_Tp1 __val1, _Tp2 __val2) 288e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ return __val1 == __val2; } 289e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 290e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 291e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _Tp> 292e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottinline bool __stlp_eq(_Tp, _Tp) 293e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott{ return true; } 294e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif 295e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 296e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _InputIter, class _ForwardIter, class _Tp2, class _Predicate> 297e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottinline _InputIter __find_first_of_aux2(_InputIter __first1, _InputIter __last1, 298e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _ForwardIter __first2, _ForwardIter __last2, 299e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Tp2*, _Predicate __pred, 300e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const __true_type& /* _UseStrcspnLikeAlgo */) { 301e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott unsigned char __hints[(UCHAR_MAX + 1) / CHAR_BIT]; 302e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott memset(__hints, 0, sizeof(__hints) / sizeof(unsigned char)); 303e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott for (; __first2 != __last2; ++__first2) { 304e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott unsigned char __tmp = (unsigned char)*__first2; 305e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __hints[__tmp / CHAR_BIT] |= (1 << (__tmp % CHAR_BIT)); 306e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 307e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 308e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott for (; __first1 != __last1; ++__first1) { 309e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Tp2 __tmp = (_Tp2)*__first1; 310e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (__stlp_eq(*__first1, __tmp) && 311e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __pred((__hints[(unsigned char)__tmp / CHAR_BIT] & (1 << ((unsigned char)__tmp % CHAR_BIT))) != 0)) 312e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott break; 313e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 314e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return __first1; 315e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 316e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 317e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _InputIter, class _ForwardIter, class _Tp2, class _Predicate> 318e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottinline _InputIter __find_first_of_aux2(_InputIter __first1, _InputIter __last1, 319e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _ForwardIter __first2, _ForwardIter __last2, 320e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Tp2* /* __dummy */, _Predicate /* __pred */, 321e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott const __false_type& /* _UseStrcspnLikeAlgo */) { 322e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_PRIV __find_first_of(__first1, __last1, __first2, __last2, 323e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _InputIter))); 324e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 325e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 326e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _InputIter, class _ForwardIter, class _Tp1, class _Tp2> 327e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottinline _InputIter __find_first_of_aux1(_InputIter __first1, _InputIter __last1, 328e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _ForwardIter __first2, _ForwardIter __last2, 329628e14d37c5b239839a466e81c74bf66255b770bTareq A. Siraj _Tp1* _STLP_UNUSED(__pt1), _Tp2* __pt2) { 330e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott typedef _STLP_TYPENAME _STLP_STD::_IsIntegral<_Tp1>::_Ret _IsIntegral; 331e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott typedef _STLP_TYPENAME _STLP_PRIV _IsCharLikeType<_Tp2>::_Ret _IsCharLike; 332e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott typedef _STLP_TYPENAME _STLP_STD::_Land2<_IsIntegral, _IsCharLike>::_Ret _UseStrcspnLikeAlgo; 333e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_PRIV __find_first_of_aux2(__first1, __last1, 334e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __first2, __last2, 335e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __pt2, _Identity<bool>(), _UseStrcspnLikeAlgo()); 336e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 337e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 338e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _InputIter, class _ForwardIter> 339e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scottinline _InputIter __find_first_of(_InputIter __first1, _InputIter __last1, 340e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _ForwardIter __first2, _ForwardIter __last2) { 341e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_PRIV __find_first_of_aux1(__first1, __last1, __first2, __last2, 342e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_VALUE_TYPE(__first1, _InputIter), 343e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_VALUE_TYPE(__first2, _ForwardIter)); 344e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 3459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// find_first_of, with and without an explicitly supplied comparison function. 3479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _ForwardIter, class _BinaryPredicate> 3489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_InputIter __find_first_of(_InputIter __first1, _InputIter __last1, 3499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __first2, _ForwardIter __last2, 3509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPredicate __comp) { 3519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first1 != __last1; ++__first1) { 3529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter) { 3539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__first1, *__iter)) { 3549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first1; 3559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last1; 3599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// find_end, with and without an explicitly supplied comparison function. 3629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Search [first2, last2) as a subsequence in [first1, last1), and return 3639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// the *last* possible match. Note that find_end for bidirectional iterators 3649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// is much faster than for forward iterators. 3659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// find_end for forward iterators. 3679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter1, class _ForwardIter2, 3689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _BinaryPredicate> 3699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 3709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter2 __first2, _ForwardIter2 __last2, 3719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const forward_iterator_tag &, const forward_iterator_tag &, 3729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPredicate __comp) { 3739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first2 == __last2) 3749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last1; 3759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 3769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter1 __result = __last1; 3779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (;;) { 378e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _ForwardIter1 __new_result = _STLP_STD::search(__first1, __last1, __first2, __last2, __comp); 3799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__new_result == __last1) 3809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 3819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 3829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = __new_result; 3839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first1 = __new_result; 3849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 3859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 3919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// find_end for bidirectional iterators. Requires partial specialization. 3939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 3949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifndef _STLP_INTERNAL_ITERATOR_H 3969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE 3979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_iterator.h> 3989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE 3999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif /*_STLP_INTERNAL_ITERATOR_H*/ 4009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 4029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter1, class _BidirectionalIter2, 4049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _BinaryPredicate> 4059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_BidirectionalIter1 4069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1, 4079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter2 __first2, _BidirectionalIter2 __last2, 4089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const bidirectional_iterator_tag &, const bidirectional_iterator_tag &, 4099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPredicate __comp) { 410e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott typedef _STLP_STD::reverse_iterator<_BidirectionalIter1> _RevIter1; 411e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott typedef _STLP_STD::reverse_iterator<_BidirectionalIter2> _RevIter2; 4129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RevIter1 __rlast1(__first1); 4149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RevIter2 __rlast2(__first2); 415e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _RevIter1 __rresult = _STLP_STD::search(_RevIter1(__last1), __rlast1, 416e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _RevIter2(__last2), __rlast2, 417e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __comp); 4189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__rresult == __rlast1) 4209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last1; 4219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 4229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter1 __result = __rresult.base(); 423e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::advance(__result, -_STLP_STD::distance(__first2, __last2)); 4249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 4259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 4299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 4309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter1, class _ForwardIter2, 4329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _BinaryPredicate> 4339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter1 4349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockfind_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 4359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter2 __first2, _ForwardIter2 __last2, 4369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPredicate __comp) { 4379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 4389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 4399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2, 4409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 4419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1), 4429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2), 4439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 4449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block forward_iterator_tag(), 4459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block forward_iterator_tag(), 4469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 4479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 4489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 4519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp, class _Compare1, class _Compare2, class _Distance> 4539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 454628e14d37c5b239839a466e81c74bf66255b770bTareq A. Siraj _Compare1 __comp1, _Compare2 _STLP_UNUSED(__comp2), _Distance*) { 455e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Distance __len = _STLP_STD::distance(__first, __last); 4569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __half; 4579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __middle; 4589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__len > 0) { 4609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __half = __len >> 1; 4619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __middle = __first; 462e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::advance(__middle, __half); 4639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp1(*__middle, __val)) { 4649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 4659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first = __middle; 4669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 4679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len = __len - __half - 1; 4689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 4709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len = __half; 4719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 4739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 4769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE 4789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_ALGOBASE_C */ 4809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Local Variables: 4829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// mode:C++ 4839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// End: 484