_algo.c revision e46c9386c4f79aa40185f79a19fc5b2a7ef528b3
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 269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_ALGO_C 279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_ALGO_C 289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_INTERNAL_ALGO_H) 309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_algo.h> 319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_TEMPBUF_H 349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_tempbuf.h> 359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE 389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Distance, class _Compare> 429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __merge_without_buffer(_BidirectionalIter __first, 439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __middle, 449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __last, 459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len1, _Distance __len2, 469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp); 479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter1, class _BidirectionalIter2, 509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _BidirectionalIter3, class _Compare> 519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, 529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter1 __last1, 539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter2 __first2, 549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter2 __last2, 559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter3 __result, 569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp); 579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Tp> 599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 )) 609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline 619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockconst _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { 639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__a < __b) 649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__b < __c) 659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __b; 669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__a < __c) 679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __c; 689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __a; 709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__a < __c) 719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __a; 729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__b < __c) 739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __c; 749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __b; 769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Tp, class _Compare> 799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 )) 809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline 819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockconst _Tp& 839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { 849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(__a, __b)) { 859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(__b, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(__b, __c)) { 879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __b; 899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__comp(__a, __c)) { 919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __c; 939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __a; 969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__comp(__a, __c)) { 989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __a; 1009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__comp(__b, __c)) { 1029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 1039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __c; 1049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 1069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __b; 1079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 1109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter1, class _ForwardIter2> 1129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, 1139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter2 __first2, _ForwardIter2 __last2) { 1149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 1159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 1169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Test for empty ranges 1179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first1 == __last1 || __first2 == __last2) 1189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first1; 1199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Test for a pattern of length 1. 1219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter2 __p1(__first2); 1229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if ( ++__p1 == __last2 ) 1249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return find(__first1, __last1, *__first2); 1259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // General case. 1279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; ; ) { // __first1 != __last1 will be checked in find below 1299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first1 = find(__first1, __last1, *__first2); 1309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first1 == __last1) 1319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last1; 1329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter2 __p = __p1; 1349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter1 __current = __first1; 1359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (++__current == __last1) 1369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last1; 1379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (*__current == *__p) { 1399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (++__p == __last2) 1409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first1; 1419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (++__current == __last1) 1429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last1; 1439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 1469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first1; 1489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 1519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Integer, class _Tp, 1539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _BinaryPred, class _Distance> 1549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last, 1559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Integer __count, const _Tp& __val, _BinaryPred __pred, 1569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance*, const random_access_iterator_tag &) 1579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 1589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __tailSize = __last - __first; 1599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Distance __pattSize = __count; 1609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Distance __skipOffset = __pattSize - 1; 1619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __backTrack; 1629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __remainder, __prevRemainder; 1639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) { // the main loop... 1659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //__lookAhead here is always pointing to the last element of next possible match. 1669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __tailSize -= __pattSize; 1679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while ( !__pred(*__lookAhead, __val) ) { // the skip loop... 1699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__tailSize < __pattSize) 1709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; 1719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __lookAhead += __pattSize; 1739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __tailSize -= __pattSize; 1749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if ( __skipOffset == 0 ) { 1779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return (__lookAhead - __skipOffset); //Success 1789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __remainder = __skipOffset; 1819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) { 1839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (--__remainder == 0) 1849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return (__lookAhead - __skipOffset); //Success 1859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__remainder > __tailSize) 1889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; //failure 1899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __lookAhead += __remainder; 1919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __tailSize -= __remainder; 1929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while ( __pred(*__lookAhead, __val) ) { 1949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __prevRemainder = __remainder; 1959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __backTrack = __lookAhead; 1969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block do { 1989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (--__remainder == 0) 1999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return (__lookAhead - __skipOffset); //Success 2009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } while (__pred(*--__backTrack, __val)); 2019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //adjust remainder for next comparison 2039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __remainder += __pattSize - __prevRemainder; 2049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__remainder > __tailSize) 2069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; //failure 2079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __lookAhead += __remainder; 2099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __tailSize -= __remainder; 2109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //__lookAhead here is always pointing to the element of the last mismatch. 2139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; //failure 2169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Integer, class _Tp, 2199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Distance, class _BinaryPred> 2209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last, 2219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Integer __count, const _Tp& __val, _BinaryPred __pred, 2229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance*, const forward_iterator_tag &) { 2239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; (__first != __last) && !__pred(*__first, __val); ++__first) {} 2249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first != __last) { 2259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Integer __n = __count - 1; 2269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __i = __first; 2279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__i; 2289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__i != __last && __n != 0 && __pred(*__i, __val)) { 2299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__i; 2309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__n; 2319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__n == 0) 2339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 2349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__i != __last) 2359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {} 2369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 2379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 2389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; 2409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 2439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// search_n. Search for __count consecutive copies of __val. 2459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Integer, class _Tp> 2469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, 2479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Integer __count, const _Tp& __val) { 2489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 2499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__count <= 0) 2509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 2519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__count == 1) 2529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //We use find when __count == 1 to use potential find overload. 2539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return find(__first, __last, __val); 2549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __search_n(__first, __last, __count, __val, equal_to<_Tp>(), 2559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _ForwardIter), 2569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); 2579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred> 2609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, 2619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Integer __count, const _Tp& __val, 2629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPred __binary_pred) { 2639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 2649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__count <= 0) 2659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 2669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __search_n(__first, __last, __count, __val, __binary_pred, 2679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _ForwardIter), 2689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); 2699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter1, class _ForwardIter2> 2729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter1 2739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockfind_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 2749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter2 __first2, _ForwardIter2 __last2) { 2759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 2769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 2779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2, 2789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 2799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1), 2809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2), 2819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 2829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block forward_iterator_tag(), 2839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block forward_iterator_tag(), 2849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 2859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1)) 2869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ); 2879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// unique and unique_copy 2909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 2919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIterator, class _OutputIterator, class _BinaryPredicate, 2939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Tp> 2949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _OutputIterator 2959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__unique_copy(_InputIterator __first, _InputIterator __last, 2969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIterator __result, 2979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPredicate __binary_pred, _Tp*) { 2989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Tp __val = *__first; 2999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = __val; 3009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (++__first != __last) 3019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (!__binary_pred(__val, *__first)) { 3029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __val = *__first; 3039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *++__result = __val; 3049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return ++__result; 3069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _OutputIter, class _BinaryPredicate> 3099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _OutputIter 3109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result, 3119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPredicate __binary_pred, const output_iterator_tag &) { 312e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, 313e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_VALUE_TYPE(__first, _InputIter)); 3149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _ForwardIter, class _BinaryPredicate> 3179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _ForwardIter 3189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, 3199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPredicate __binary_pred, const forward_iterator_tag &) { 3209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first; 3219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (++__first != __last) 3229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (!__binary_pred(*__result, *__first)) *++__result = *__first; 3239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return ++__result; 3249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) 3279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate> 3289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _BidirectionalIterator 3299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__unique_copy(_InputIterator __first, _InputIterator __last, 3309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIterator __result, _BinaryPredicate __binary_pred, 3319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const bidirectional_iterator_tag &) { 332e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag()); 3339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate> 3369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _RandomAccessIterator 3379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__unique_copy(_InputIterator __first, _InputIterator __last, 3389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIterator __result, _BinaryPredicate __binary_pred, 3399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const random_access_iterator_tag &) { 340e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag()); 3419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */ 3439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 3459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _OutputIter> 3479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter 3489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockunique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) { 3499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 3509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) return __result; 3519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __unique_copy(__first, __last, __result, 3529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)), 3539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ITERATOR_CATEGORY(__result, _OutputIter)); 3549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _OutputIter, class _BinaryPredicate> 3579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter 3589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockunique_copy(_InputIter __first, _InputIter __last,_OutputIter __result, 3599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BinaryPredicate __binary_pred) { 3609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 3619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) return __result; 3629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, 3639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ITERATOR_CATEGORY(__result, _OutputIter)); 3649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// rotate and rotate_copy, and their auxiliary functions 3679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 3689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Distance> 3709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter __rotate_aux(_ForwardIter __first, 3719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __middle, 3729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __last, 3739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance*, 3749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const forward_iterator_tag &) { 3759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __middle) 3769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; 3779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__last == __middle) 3789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 3799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __first2 = __middle; 3819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block do { 382e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::swap(*__first++, *__first2++); 3839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __middle) 3849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __middle = __first2; 3859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } while (__first2 != __last); 3869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __new_middle = __first; 3889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first2 = __middle; 3909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first2 != __last) { 392e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::swap (*__first++, *__first2++); 3939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __middle) 3949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __middle = __first2; 3959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__first2 == __last) 3969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first2 = __middle; 3979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __new_middle; 4009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Distance> 4039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_BidirectionalIter __rotate_aux(_BidirectionalIter __first, 4049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __middle, 4059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __last, 4069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance*, 4079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const bidirectional_iterator_tag &) { 4089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __middle) 4099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; 4109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__last == __middle) 4119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 4129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 413e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_PRIV __reverse(__first, __middle, bidirectional_iterator_tag()); 414e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_PRIV __reverse(__middle, __last, bidirectional_iterator_tag()); 4159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first != __middle && __middle != __last) 417e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::swap(*__first++, *--__last); 4189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __middle) { 420e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_PRIV __reverse(__middle, __last, bidirectional_iterator_tag()); 4219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; 4229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 424e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_PRIV __reverse(__first, __middle, bidirectional_iterator_tag()); 4259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 4269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 429e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott// rotate and rotate_copy, and their auxiliary functions 430e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scotttemplate <class _EuclideanRingElement> 431e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_STLP_INLINE_LOOP 432e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott_EuclideanRingElement __gcd(_EuclideanRingElement __m, 433e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _EuclideanRingElement __n) { 434e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott while (__n != 0) { 435e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _EuclideanRingElement __t = __m % __n; 436e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __m = __n; 437e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __n = __t; 438e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 439e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return __m; 440e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott} 441e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 4429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Distance, class _Tp> 4439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter __rotate_aux(_RandomAccessIter __first, 4449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __middle, 4459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, 4469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance *, _Tp *) { 4479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __n = __last - __first; 4499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __k = __middle - __first; 4509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __l = __n - __k; 4519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __result = __first + (__last - __middle); 4529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__k == 0) /* __first == middle */ 4549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __last; 4559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__k == __l) { 457e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::swap_ranges(__first, __middle, __middle); 4589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 4599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 461e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Distance __d = _STLP_PRIV __gcd(__n, __k); 4629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (_Distance __i = 0; __i < __d; __i++) { 4649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Tp __tmp = *__first; 4659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __p = __first; 4669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__k < __l) { 4689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (_Distance __j = 0; __j < __l/__d; __j++) { 4699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__p > __first + __l) { 4709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__p = *(__p - __l); 4719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __p -= __l; 4729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__p = *(__p + __k); 4759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __p += __k; 4769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 4809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (_Distance __j = 0; __j < __k/__d - 1; __j ++) { 4819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__p < __last - __k) { 4829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__p = *(__p + __k); 4839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __p += __k; 4849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__p = * (__p - __l); 4879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __p -= __l; 4889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__p = __tmp; 4929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 4939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 4969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Distance> 4999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _RandomAccessIter 5009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__rotate_aux(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, 5019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance * __dis, const random_access_iterator_tag &) { 502e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_PRIV __rotate_aux(__first, __middle, __last, 503e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter)); 5049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter> 5079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter 5089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) { 5099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(__check_range(__first, __middle)) 5109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(__check_range(__middle, __last)) 5119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __rotate_aux(__first, __middle, __last, 5129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _ForwardIter), 5139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); 5149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 5179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter> 5199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) { 5209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __rotate(__first, __middle, __last); 5219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Return a random number in the range [0, __n). This function encapsulates 5249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// whether we're using rand (part of the standard C library) or lrand48 5259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// (not standard, but a much better choice whenever it's available). 5269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 5279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Distance> 5299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _Distance __random_number(_Distance __n) { 5309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifdef _STLP_NO_DRAND48 5319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return rand() % __n; 5329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 5339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return lrand48() % __n; 5349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 5359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 5389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 5409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid random_shuffle(_RandomAccessIter __first, 5419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last) { 5429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 5439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) return; 5449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 5459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iter_swap(__i, __first + _STLP_PRIV __random_number((__i - __first) + 1)); 5469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _RandomNumberGenerator> 5499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, 5509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomNumberGenerator &__rand) { 5519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 5529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) return; 5539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 5549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iter_swap(__i, __first + __rand((__i - __first) + 1)); 5559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_NO_EXTENSIONS) 5589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// random_sample and random_sample_n (extensions, not part of the standard). 5599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _OutputIter, class _Distance> 5609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, 5619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __out_ite, const _Distance __n) { 5629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 563e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Distance __remaining = _STLP_STD::distance(__first, __last); 5649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __m = (min) (__n, __remaining); 5659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__m > 0) { 5679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_STLP_PRIV __random_number(__remaining) < __m) { 5689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__out_ite = *__first; 5699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__out_ite; 5709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__m; 5719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__remaining; 5749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 5759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __out_ite; 5779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _OutputIter, class _Distance, 5819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _RandomNumberGenerator> 5829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, 5839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __out_ite, const _Distance __n, 5849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomNumberGenerator& __rand) { 5859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 586e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Distance __remaining = _STLP_STD::distance(__first, __last); 5879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __m = (min) (__n, __remaining); 5889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__m > 0) { 5909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__rand(__remaining) < __m) { 5919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__out_ite = *__first; 5929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__out_ite; 5939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__m; 5949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__remaining; 5979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 5989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __out_ite; 6009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 6019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 6039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _RandomAccessIter, class _Distance> 6059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, 6069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __out_ite, 6079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Distance __n) { 6089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __m = 0; 6099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __t = __n; 6109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last && __m < __n; ++__m, ++__first) 6119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __out_ite[__m] = *__first; 6129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first != __last) { 6149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__t; 6159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __M = __random_number(__t); 6169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__M < __n) 6179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __out_ite[__M] = *__first; 6189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 6199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __out_ite + __m; 6229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 6239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _RandomAccessIter, 6259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _RandomNumberGenerator, class _Distance> 6269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, 6279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __out_ite, 6289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomNumberGenerator& __rand, 6299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _Distance __n) { 6309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __m = 0; 6319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __t = __n; 6329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __first != __last && __m < __n; ++__m, ++__first) 6339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __out_ite[__m] = *__first; 6349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first != __last) { 6369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__t; 6379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __M = __rand(__t); 6389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__M < __n) 6399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __out_ite[__M] = *__first; 6409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 6419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __out_ite + __m; 6449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 6459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 6479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _RandomAccessIter> 6499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter 6509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrandom_sample(_InputIter __first, _InputIter __last, 6519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __out_first, _RandomAccessIter __out_last) { 6529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 6539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last)) 6549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __random_sample(__first, __last, 6559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __out_first, __out_last - __out_first); 6569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 6579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator> 6599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter 6609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrandom_sample(_InputIter __first, _InputIter __last, 6619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __out_first, _RandomAccessIter __out_last, 6629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomNumberGenerator& __rand) { 6639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 6649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last)) 6659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __random_sample(__first, __last, 6669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __out_first, __rand, 6679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __out_last - __out_first); 6689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 6699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_NO_EXTENSIONS */ 6719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// partition, stable_partition, and their auxiliary functions 6739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 6749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Predicate> 6769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first, 6779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __last, 6789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Predicate __pred, 6799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const forward_iterator_tag &) { 6809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) return __first; 6819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__pred(*__first)) 6839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (++__first == __last) return __first; 6849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __next = __first; 6869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (++__next != __last) { 6889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pred(*__next)) { 689e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::swap(*__first, *__next); 6909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 6919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 6949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 6959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Predicate> 6979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first, 6989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __last, 6999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Predicate __pred, 7009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const bidirectional_iterator_tag &) { 7019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (;;) { 7029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (;;) { 7039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) 7049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 7059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__pred(*__first)) 7069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 7079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 7089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 7099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__last; 7119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (;;) { 7129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) 7139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 7149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (!__pred(*__last)) 7159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__last; 7169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 7179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 7189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iter_swap(__first, __last); 7209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 7219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 7239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) 7259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Predicate> 7269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline 7279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_BidirectionalIter __partition(_BidirectionalIter __first, 7289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __last, 7299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Predicate __pred, 7309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const random_access_iterator_tag &) { 7319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __partition(__first, __last, __pred, bidirectional_iterator_tag()); 7329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 7339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 7349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 7369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Predicate> 7389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { 7399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 7409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); 7419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 7429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* __pred_of_first: false if we know that __pred(*__first) is false, 7459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * true when we don't know the result of __pred(*__first). 7469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * __not_pred_of_before_last: true if we know that __pred(*--__last) is true, 7479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * false when we don't know the result of __pred(*--__last). 7489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 7499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 7509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Predicate, class _Distance> 7529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter __inplace_stable_partition(_ForwardIter __first, 7539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __last, 7549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Predicate __pred, _Distance __len, 7559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool __pred_of_first, bool __pred_of_before_last) { 7569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__len == 1) 7579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first; 7589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __middle = __first; 7599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __half_len = __len / 2; 760e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::advance(__middle, __half_len); 761e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_PRIV __rotate(_STLP_PRIV __inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false), 762e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __middle, 763e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_PRIV __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last)); 7649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 7659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Pointer, class _Predicate, 7679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Distance> 7689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter __stable_partition_adaptive(_ForwardIter __first, 7699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __last, 7709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Predicate __pred, _Distance __len, 7719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Pointer __buffer, _Distance __buffer_size, 7729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool __pred_of_first, bool __pred_of_before_last) { 7739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__len <= __buffer_size) { 7749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __result1 = __first; 7759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Pointer __result2 = __buffer; 7769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if ((__first != __last) && (!__pred_of_first || __pred(*__first))) { 7779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result2 = *__first; 7789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result2; ++__first; --__len; 7799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; __first != __last ; ++__first, --__len) { 7819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (((__len == 1) && (__pred_of_before_last || __pred(*__first))) || 7829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ((__len != 1) && __pred(*__first))){ 7839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result1 = *__first; 7849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result1; 7859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 7879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result2 = *__first; 7889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result2; 7899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 791e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::copy(__buffer, __result2, __result1); 7929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result1; 7939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 7959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __middle = __first; 7969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __half_len = __len / 2; 797e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::advance(__middle, __half_len); 798e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_PRIV __rotate(_STLP_PRIV __stable_partition_adaptive(__first, __middle, __pred, 799e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __half_len, __buffer, __buffer_size, 800e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __pred_of_first, false), 801e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __middle, 802e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_PRIV __stable_partition_adaptive(__middle, __last, __pred, 803e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __len - __half_len, __buffer, __buffer_size, 804e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott true, __pred_of_before_last)); 8059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 8079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Predicate, class _Tp, class _Distance> 8099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _ForwardIter 8109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last, 811e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last) { 8129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last); 8139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_MPWFIX_TRY //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present 8149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return (__buf.size() > 0) ? 8159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __stable_partition_adaptive(__first, __last, __pred, 8169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance(__buf.requested_size()), 8179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __buf.begin(), __buf.size(), 8189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block false, __pred_of_before_last) : 8199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __inplace_stable_partition(__first, __last, __pred, 8209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance(__buf.requested_size()), 8219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block false, __pred_of_before_last); 8229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_MPWFIX_CATCH //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present 8239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 8249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Predicate> 8269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter 8279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, 8289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const forward_iterator_tag &) { 8299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __stable_partition_aux_aux(__first, __last, __pred, 8309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first, _ForwardIter), 831e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DISTANCE_TYPE(__first, _ForwardIter), false); 8329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 8339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectIter, class _Predicate> 8359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_BidirectIter 8369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred, 8379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const bidirectional_iterator_tag &) { 8389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (--__last;;) { 8399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) 8409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 8419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (!__pred(*__last)) 8429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__last; 8439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 8449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 8459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__last; 8479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //Here we know that __pred(*--__last) is true 8489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __stable_partition_aux_aux(__first, __last, __pred, 8499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first, _BidirectIter), 8509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _BidirectIter), true); 8519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 8529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) 8549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectIter, class _Predicate> 8559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_BidirectIter 8569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred, 8579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const random_access_iterator_tag &) { 8589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __stable_partition_aux(__first, __last, __pred, bidirectional_iterator_tag()); 8599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 8609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 8619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 8639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Predicate> 8659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter 8669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { 8679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 8689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (;;) { 8699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) 8709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 8719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__pred(*__first)) 8729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 8739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 8749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 8759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __stable_partition_aux(__first, __last, __pred, 8779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); 8789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 8799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 8819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Tp, class _Compare> 8839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 8849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, 8859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Tp __pivot, _Compare __comp) { 8869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (;;) { 8879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__comp(*__first, __pivot)) { 8889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(__pivot, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 8899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 8909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__last; 8929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__comp(__pivot, *__last)) { 8939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__last, __pivot), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 8949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__last; 8959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (!(__first < __last)) 8979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 8989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iter_swap(__first, __last); 8999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 9009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 9029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// sort() and its auxiliary functions. 9049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define __stl_threshold 16 9059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Tp, class _Compare> 9079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, 9089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 9099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __next = __last; 9109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__next; 9119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__comp(__val, *__next)) { 9129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__next, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 9139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__last = *__next; 9149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __last = __next; 9159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__next; 9169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__last = __val; 9189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 9199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Tp, class _Compare> 9219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void __linear_insert(_RandomAccessIter __first, 9229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Tp __val, _Compare __comp) { 9239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //*TY 12/26/1998 - added __val as a paramter 9249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _Tp __val = *__last; //*TY 12/26/1998 - __val supplied by caller 9259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(__val, *__first)) { 9269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__first, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 9279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block copy_backward(__first, __last, __last + 1); 9289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__first = __val; 9299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 9319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __unguarded_linear_insert(__last, __val, __comp); 9329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 9339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Tp, class _Compare> 9359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __insertion_sort(_RandomAccessIter __first, 9369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, 9379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Tp *, _Compare __comp) { 9389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) return; 9399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 9409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __linear_insert<_RandomAccessIter, _Tp, _Compare>(__first, __i, *__i, __comp); //*TY 12/26/1998 - supply *__i as __val 9419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 9429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Tp, class _Compare> 9449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __unguarded_insertion_sort_aux(_RandomAccessIter __first, 9459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, 9469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Tp*, _Compare __comp) { 9479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (_RandomAccessIter __i = __first; __i != __last; ++__i) 9489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __unguarded_linear_insert<_RandomAccessIter, _Tp, _Compare>(__i, *__i, __comp); 9499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 9509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Compare> 9529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void __unguarded_insertion_sort(_RandomAccessIter __first, 9539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, 9549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 9559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp); 9569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 9579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Compare> 9599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __final_insertion_sort(_RandomAccessIter __first, 9609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Compare __comp) { 9619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__last - __first > __stl_threshold) { 9629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __insertion_sort(__first, __first + __stl_threshold, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); 9639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp); 9649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 9669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); 9679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 9689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Tp, class _Size, class _Compare> 9709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __introsort_loop(_RandomAccessIter __first, 9719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Tp*, 9729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Size __depth_limit, _Compare __comp) { 9739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__last - __first > __stl_threshold) { 9749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__depth_limit == 0) { 9759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block partial_sort(__first, __last, __last, __comp); 9769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 9779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__depth_limit; 9799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __cut = 9809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __unguarded_partition(__first, __last, 9819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Tp(__median(*__first, 9829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *(__first + (__last - __first)/2), 9839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *(__last - 1), __comp)), 9849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 9859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp); 9869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __last = __cut; 9879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 9899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 9919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 9939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid sort(_RandomAccessIter __first, _RandomAccessIter __last) { 9949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 9959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first != __last) { 9969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __introsort_loop(__first, __last, 9979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first, _RandomAccessIter), 9989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __lg(__last - __first) * 2, 9999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); 10009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __final_insertion_sort(__first, __last, 10019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); 10029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 10049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Compare> 10069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { 10079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 10089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first != __last) { 10099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __introsort_loop(__first, __last, 10109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first, _RandomAccessIter), 10119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __lg(__last - __first) * 2, __comp); 10129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __final_insertion_sort(__first, __last, __comp); 10139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 10159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// stable_sort() and its auxiliary functions. 10179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 10189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Compare> 10209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __inplace_stable_sort(_RandomAccessIter __first, 10219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Compare __comp) { 10229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__last - __first < 15) { 10239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); 10249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 10259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __middle = __first + (__last - __first) / 2; 10279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __inplace_stable_sort(__first, __middle, __comp); 10289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __inplace_stable_sort(__middle, __last, __comp); 10299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __merge_without_buffer(__first, __middle, __last, 10309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __middle - __first, 10319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __last - __middle, 10329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 10339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 10349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter1, class _RandomAccessIter2, 10369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Distance, class _Compare> 10379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __merge_sort_loop(_RandomAccessIter1 __first, 10389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter1 __last, 10399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter2 __result, _Distance __step_size, 10409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 10419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __two_step = 2 * __step_size; 10429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__last - __first >= __two_step) { 10449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = merge(__first, __first + __step_size, 10459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first + __step_size, __first + __two_step, 10469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result, 10479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 10489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first += __two_step; 10499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __step_size = (min) (_Distance(__last - __first), __step_size); 10519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block merge(__first, __first + __step_size, 10539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first + __step_size, __last, 10549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result, 10559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 10569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 10579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockconst int __stl_chunk_size = 7; 10599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Distance, class _Compare> 10619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __chunk_insertion_sort(_RandomAccessIter __first, 10629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, 10639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __chunk_size, _Compare __comp) { 10649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__last - __first >= __chunk_size) { 10659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __insertion_sort(__first, __first + __chunk_size, 10669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); 10679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first += __chunk_size; 10689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); 10709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 10719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Pointer, class _Distance, 10739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 10749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __merge_sort_with_buffer(_RandomAccessIter __first, 10759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Pointer __buffer, 10769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance*, _Compare __comp) { 10779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len = __last - __first; 10789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Pointer __buffer_last = __buffer + __len; 10799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __step_size = __stl_chunk_size; 10819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __chunk_insertion_sort(__first, __last, __step_size, __comp); 10829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__step_size < __len) { 10849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __merge_sort_loop(__first, __last, __buffer, __step_size, __comp); 10859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __step_size *= 2; 10869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp); 10879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __step_size *= 2; 10889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 10909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter1, class _BidirectionalIter2, 10929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Distance> 10939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first, 10949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter1 __middle, 10959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter1 __last, 10969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len1, _Distance __len2, 10979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter2 __buffer, 10989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __buffer_size) { 10999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__len1 > __len2 && __len2 <= __buffer_size) { 1100e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _BidirectionalIter2 __buffer_end = _STLP_STD::copy(__middle, __last, __buffer); 1101e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::copy_backward(__first, __middle, __last); 1102e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_STD::copy(__buffer, __buffer_end, __first); 11039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__len1 <= __buffer_size) { 1105e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _BidirectionalIter2 __buffer_end = _STLP_STD::copy(__first, __middle, __buffer); 1106e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::copy(__middle, __last, __first); 1107e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_STD::copy_backward(__buffer, __buffer_end, __last); 11089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 1110e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_PRIV __rotate(__first, __middle, __last); 11119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 11129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 11139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Distance, class _Pointer, 11149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 11159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __merge_adaptive(_BidirectionalIter __first, 11169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __middle, 11179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __last, 11189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len1, _Distance __len2, 11199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Pointer __buffer, _Distance __buffer_size, 11209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 11219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__len1 <= __len2 && __len1 <= __buffer_size) { 1122e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Pointer __buffer_end = _STLP_STD::copy(__first, __middle, __buffer); 1123e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::merge(__buffer, __buffer_end, __middle, __last, __first, __comp); 11249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__len2 <= __buffer_size) { 1126e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Pointer __buffer_end = _STLP_STD::copy(__middle, __last, __buffer); 1127e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_PRIV __merge_backward(__first, __middle, __buffer, __buffer_end, __last, 1128e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __comp); 11299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 11319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __first_cut = __first; 11329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __second_cut = __middle; 11339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len11 = 0; 11349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len22 = 0; 11359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__len1 > __len2) { 11369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len11 = __len1 / 2; 1137e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::advance(__first_cut, __len11); 1138e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __second_cut = _STLP_STD::lower_bound(__middle, __last, *__first_cut, __comp); 1139e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __len22 += _STLP_STD::distance(__middle, __second_cut); 11409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 11429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len22 = __len2 / 2; 1143e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::advance(__second_cut, __len22); 1144e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __first_cut = _STLP_STD::upper_bound(__first, __middle, *__second_cut, __comp); 1145e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __len11 += _STLP_STD::distance(__first, __first_cut); 11469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __new_middle = 11489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11, 11499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len22, __buffer, __buffer_size); 11509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __merge_adaptive(__first, __first_cut, __new_middle, __len11, 11519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len22, __buffer, __buffer_size, __comp); 11529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, 11539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len2 - __len22, __buffer, __buffer_size, __comp); 11549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 11569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 11579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Pointer, class _Distance, 11589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 11599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __stable_sort_adaptive(_RandomAccessIter __first, 11609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Pointer __buffer, 11619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __buffer_size, _Compare __comp) { 11629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len = (__last - __first + 1) / 2; 11639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __middle = __first + __len; 11649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__len > __buffer_size) { 11659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, 11669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 11679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, 11689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 11699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 11719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0, 11729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 11739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0, 11749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 11759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 11779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance(__last - __middle), __buffer, __buffer_size, 11789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 11799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 11809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 11819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Tp, class _Distance, class _Compare> 11829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __stable_sort_aux(_RandomAccessIter __first, 11839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Tp*, _Distance*, 11849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 11859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last); 11869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (buf.begin() == 0) 11879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __inplace_stable_sort(__first, __last, __comp); 11889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 11899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __stable_sort_adaptive(__first, __last, buf.begin(), 11909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance(buf.size()), 11919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 11929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 11939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 11949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 11959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 11969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 11979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid stable_sort(_RandomAccessIter __first, 11989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last) { 11999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 12009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __stable_sort_aux(__first, __last, 12019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first, _RandomAccessIter), 12029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _RandomAccessIter), 12039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); 12049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 12059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Compare> 12079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid stable_sort(_RandomAccessIter __first, 12089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Compare __comp) { 12099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 12109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __stable_sort_aux(__first, __last, 12119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first, _RandomAccessIter), 12129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _RandomAccessIter), 12139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 12149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 12159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// partial_sort, partial_sort_copy, and auxiliary functions. 12179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 12189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Tp, class _Compare> 12209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, 12219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Tp*, _Compare __comp) { 12229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block make_heap(__first, __middle, __comp); 12239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (_RandomAccessIter __i = __middle; __i < __last; ++__i) { 12249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__i, *__first)) { 12259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__first, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 12269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __pop_heap(__first, __middle, __i, _Tp(*__i), __comp, 12279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__first, _RandomAccessIter)); 12289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block sort_heap(__first, __middle, __comp); 12319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 12329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 12349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 12369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, 12379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last) { 12389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle)) 12399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last)) 12409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), 12419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); 12429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 12439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Compare> 12459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, 12469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Compare __comp) { 12479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle)) 12489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last)) 12499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp); 12509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 12519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 12539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _RandomAccessIter, class _Compare, 12559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Distance, class _Tp> 12569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter __partial_sort_copy(_InputIter __first, 12579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter __last, 12589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __result_first, 12599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __result_last, 12609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp, _Distance*, _Tp*) { 12619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__result_first == __result_last) return __result_last; 12629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __result_real_last = __result_first; 12639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while(__first != __last && __result_real_last != __result_last) { 12649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result_real_last = *__first; 12659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result_real_last; 12669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 12679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block make_heap(__result_first, __result_real_last, __comp); 12699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first != __last) { 12709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__first, *__result_first)) { 12719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__result_first, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 12729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __adjust_heap(__result_first, _Distance(0), 12739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance(__result_real_last - __result_first), 12749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Tp(*__first), 12759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 12769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 12789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block sort_heap(__result_first, __result_real_last, __comp); 12809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result_real_last; 12819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 12829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 12849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _RandomAccessIter> 12869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter 12879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpartial_sort_copy(_InputIter __first, _InputIter __last, 12889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __result_first, _RandomAccessIter __result_last) { 12899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 12909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last)) 12919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last, 12929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _InputIter)), 12939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter), 12949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first, _InputIter)); 12959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 12969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter, class _RandomAccessIter, class _Compare> 12989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_RandomAccessIter 12999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpartial_sort_copy(_InputIter __first, _InputIter __last, 13009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __result_first, 13019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __result_last, _Compare __comp) { 13029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 13039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last)) 13049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last, 13059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp, 13069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter), 13079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first, _InputIter)); 13089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 13099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// nth_element() and its auxiliary functions. 13119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 13129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Tp, class _Compare> 13149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 13159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Tp*, _Compare __comp) { 13169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__last - __first > 3) { 13179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __cut = 13189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __unguarded_partition(__first, __last, 13199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Tp(__median(*__first, 13209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *(__first + (__last - __first)/2), 13219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *(__last - 1), 13229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp)), 13239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 13249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__cut <= __nth) 13259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first = __cut; 13269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 13279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __last = __cut; 13289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 13299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); 13309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 13319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 13339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 13359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 13369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last) { 13379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth)) 13389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last)) 13399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), 13409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); 13419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 13429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Compare> 13449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 13459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RandomAccessIter __last, _Compare __comp) { 13469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth)) 13479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last)) 13489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp); 13499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 13509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Binary search (lower_bound, upper_bound, equal_range, binary_search). 13529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 13539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp, 13559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare1, class _Compare2, class _Distance> 13569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 13579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare1 __comp1, _Compare2 __comp2, _Distance*) { 1358e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Distance __len = _STLP_STD::distance(__first, __last); 13599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __half; 13609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__len > 0) { 13629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __half = __len >> 1; 13639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __middle = __first; 1364e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::advance(__middle, __half); 13659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp2(__val, *__middle)) { 13669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 13679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len = __half; 13689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 13699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 13709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first = __middle; 13719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 13729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len = __len - __half - 1; 13739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 13749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 13759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 13769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 13779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Tp, 13799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare1, class _Compare2, class _Distance> 13809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpair<_ForwardIter, _ForwardIter> 13819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 13829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare1 __comp1, _Compare2 __comp2, _Distance* __dist) { 1383e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Distance __len = _STLP_STD::distance(__first, __last); 13849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __half; 13859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__len > 0) { 13879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __half = __len >> 1; 13889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __middle = __first; 1389e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::advance(__middle, __half); 13909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp1(*__middle, __val)) { 13919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 13929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first = __middle; 13939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first; 13949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len = __len - __half - 1; 13959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 13969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__comp2(__val, *__middle)) { 13979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 13989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len = __half; 13999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 14009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 1401e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _ForwardIter __left = _STLP_PRIV __lower_bound(__first, __middle, __val, __comp1, __comp2, __dist); 14029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //Small optim: If lower_bound haven't found an equivalent value 14039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //there is no need to call upper_bound. 14049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp1(*__left, __val)) { 14059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp2(__val, *__left), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 14069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return pair<_ForwardIter, _ForwardIter>(__left, __left); 14079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1408e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::advance(__first, __len); 1409e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _ForwardIter __right = _STLP_PRIV __upper_bound(++__middle, __first, __val, __comp1, __comp2, __dist); 14109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return pair<_ForwardIter, _ForwardIter>(__left, __right); 14119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 14129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 14139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return pair<_ForwardIter, _ForwardIter>(__first, __first); 14149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 14159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 14169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 14179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 14189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter> 14199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, 14209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 14219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result) { 14229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 14239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 14249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first1 != __last1 && __first2 != __last2) { 14259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (*__first2 < *__first1) { 14269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first2; 14279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first2; 14289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 14299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 14309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first1; 14319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 14329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 14339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result; 14349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1435e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result)); 14369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 14379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 14389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, 14399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 14409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, 14419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 14429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, _Compare __comp) { 14439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 14449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 14459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first1 != __last1 && __first2 != __last2) { 14469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__first2, *__first1)) { 14479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 14489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first2; 14499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first2; 14509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 14519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 14529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first1; 14539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 14549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 14559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result; 14569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1457e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result)); 14589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 14599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 14609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 14619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 14629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Distance, class _Compare> 14639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid __merge_without_buffer(_BidirectionalIter __first, 14649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __middle, 14659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __last, 14669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len1, _Distance __len2, 14679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 14689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__len1 == 0 || __len2 == 0) 14699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 14709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__len1 + __len2 == 2) { 14719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__middle, *__first)) { 14729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__first, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 14739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iter_swap(__first, __middle); 14749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 14759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 14769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 14779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __first_cut = __first; 14789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __second_cut = __middle; 14799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len11 = 0; 14809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __len22 = 0; 14819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__len1 > __len2) { 14829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len11 = __len1 / 2; 1483e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::advance(__first_cut, __len11); 1484e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __second_cut = _STLP_STD::lower_bound(__middle, __last, *__first_cut, __comp); 1485e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __len22 += _STLP_STD::distance(__middle, __second_cut); 14869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 14879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 14889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len22 = __len2 / 2; 1489e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_STD::advance(__second_cut, __len22); 1490e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __first_cut = _STLP_STD::upper_bound(__first, __middle, *__second_cut, __comp); 1491e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott __len11 += _STLP_STD::distance(__first, __first_cut); 14929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 14939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __new_middle 1494e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott = _STLP_PRIV __rotate(__first_cut, __middle, __second_cut); 14959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22, 14969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 14979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11, 14989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len2 - __len22, __comp); 14999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 15009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 15019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter1, class _BidirectionalIter2, 15029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _BidirectionalIter3, class _Compare> 15039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, 15049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter1 __last1, 15059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter2 __first2, 15069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter2 __last2, 15079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter3 __result, 15089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 15099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first1 == __last1) 15109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return copy_backward(__first2, __last2, __result); 15119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first2 == __last2) 15129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return copy_backward(__first1, __last1, __result); 15139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__last1; 15149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__last2; 15159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (;;) { 15169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__last2, *__last1)) { 15179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__last1, *__last2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 15189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *--__result = *__last1; 15199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first1 == __last1) 15209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return copy_backward(__first2, ++__last2, __result); 15219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__last1; 15229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 15239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 15249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *--__result = *__last2; 15259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first2 == __last2) 15269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return copy_backward(__first1, ++__last1, __result); 15279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__last2; 15289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 15299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 15309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 15319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 15329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Tp, 15339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Distance, class _Compare> 15349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void __inplace_merge_aux(_BidirectionalIter __first, 15359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __middle, 15369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __last, _Tp*, _Distance*, 15379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 1538e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Distance __len1 = _STLP_STD::distance(__first, __middle); 1539e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Distance __len2 = _STLP_STD::distance(__middle, __last); 15409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 15419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last); 15429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__buf.begin() == 0) 15439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp); 15449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 15459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __merge_adaptive(__first, __middle, __last, __len1, __len2, 15469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __buf.begin(), _Distance(__buf.size()), 15479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 15489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 15499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 15509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 15519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 15529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter> 15539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid inplace_merge(_BidirectionalIter __first, 15549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __middle, 15559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __last) { 15569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle)) 15579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last)) 15589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __middle || __middle == __last) 15599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 15609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __inplace_merge_aux(__first, __middle, __last, 15619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter), 15629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter))); 15639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 15649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 15659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Compare> 15669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid inplace_merge(_BidirectionalIter __first, 15679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __middle, 15689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __last, _Compare __comp) { 15699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle)) 15709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last)) 15719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __middle || __middle == __last) 15729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 15739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __inplace_merge_aux(__first, __middle, __last, 15749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter), 15759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __comp); 15769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 15779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 15789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 15799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 15809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _Compare> 15819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool __includes(_InputIter1 __first1, _InputIter1 __last1, 15829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) { 1583e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 1584e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 15859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first1 != __last1 && __first2 != __last2) 15869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__first2, *__first1)) { 15879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 15889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 15899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 15909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__comp(*__first1, *__first2)) 15919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 15929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 15939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1, ++__first2; 15949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 15959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first2 == __last2; 15969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 15979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 15989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 15999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 16009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _Compare> 16019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool includes(_InputIter1 __first1, _InputIter1 __last1, 16029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) { 16039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, __comp); 16049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 16059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 16069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2> 16079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool includes(_InputIter1 __first1, _InputIter1 __last1, 16089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2) { 16099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, 16109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); 16119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 16129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 16139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 16149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 16159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, 16169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 16179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1, 16189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 16199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, _Compare __comp) { 1620e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 1621e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 16229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first1 != __last1 && __first2 != __last2) { 16239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__first1, *__first2)) { 16249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 16259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first1; 16269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 16279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 16289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__comp(*__first2, *__first1)) { 16299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 16309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first2; 16319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first2; 16329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 16339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 16349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first1; 16359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 16369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first2; 16379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 16389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result; 16399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1640e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result)); 16419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 16429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 16439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 16449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 16459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter> 16469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, 16479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 16489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result) { 16499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, 16509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); 16519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 16529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 16539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, 16549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 16559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, 16569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 16579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, _Compare __comp) { 16589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, __comp); 16599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 16609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 16619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 16629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 16639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, 16649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 16659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1, 16669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 16679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, _Compare __comp) { 1668e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 1669e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 16709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first1 != __last1 && __first2 != __last2) 16719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__first1, *__first2)) { 16729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 16739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 16749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 16759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__comp(*__first2, *__first1)) 16769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first2; 16779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 16789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first1; 16799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 16809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first2; 16819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result; 16829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 16839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 16849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 16859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 16869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 16879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 16889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter> 16899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, 16909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 16919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result) { 16929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, 16939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); 16949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 16959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 16969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, 16979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 16989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, 16999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 17009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, _Compare __comp) { 17019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, __comp); 17029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 17039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 17049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 17059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 17069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, 17079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 17089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1, 17099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 17109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, _Compare __comp) { 1711e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 1712e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 17139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first1 != __last1 && __first2 != __last2) 17149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__first1, *__first2)) { 17159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 17169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first1; 17179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 17189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result; 17199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 17209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__comp(*__first2, *__first1)) 17219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first2; 17229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 17239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 17249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first2; 17259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1726e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_STD::copy(__first1, __last1, __result); 17279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 17289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 17299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 17309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 17319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter> 17329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, 17339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 17349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result) { 17359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, 17369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); 17379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 17389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 17399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, 17409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Compare> 17419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, 17429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 17439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, _Compare __comp) { 17449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, __comp); 17459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 17469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 17479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 17489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 17499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> 17509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter 17519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 17529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 17539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, _Compare __comp) { 1754e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 1755e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 17569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__first1 != __last1 && __first2 != __last2) { 17579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__first1, *__first2)) { 17589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 17599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first1; 17609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 17619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result; 17629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 17639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else if (__comp(*__first2, *__first1)) { 17649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__result = *__first2; 17659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first2; 17669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result; 17679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 17689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 17699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first1; 17709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__first2; 17719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 17729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1773e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result)); 17749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 17759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 17769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 17779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 17789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter> 17799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter 17809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockset_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 17819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 17829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result) { 17839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, 17849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); 17859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 17869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 17879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> 17889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_OutputIter 17899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockset_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 17909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _InputIter2 __first2, _InputIter2 __last2, 17919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _OutputIter __result, 17929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 17939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp); 17949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 17959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 17969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// min_element and max_element, with and without an explicitly supplied 17979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// comparison function. 17989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 17999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter> 18009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) { 18019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 18029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) return __first; 18039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __result = __first; 18049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (++__first != __last) 1805e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (*__result < *__first) { 1806e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_VERBOSE_ASSERT(!(*__first < *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 18079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = __first; 1808e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 18099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 18109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 18119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 18129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Compare> 18139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last, 18149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 18159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 18169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) return __first; 18179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __result = __first; 18189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (++__first != __last) { 18199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__result, *__first)) { 18209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__first, *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 18219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = __first; 18229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 18239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 18249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 18259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 18269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 18279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter> 18289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) { 18299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 18309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) return __first; 18319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __result = __first; 18329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (++__first != __last) 1833e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott if (*__first < *__result) { 1834e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_VERBOSE_ASSERT(!(*__result < *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 18359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = __first; 1836e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott } 18379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 18389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 18399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 18409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _Compare> 18419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last, 18429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 18439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 18449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) return __first; 18459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __result = __first; 18469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (++__first != __last) { 18479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__first, *__result)) { 18489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__result, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 18499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = __first; 18509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 18519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 18529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 18539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 18549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 18559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// next_permutation and prev_permutation, with and without an explicitly 18569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// supplied comparison function. 18579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 18589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 18599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Compare> 18609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 18619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 1862e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 18639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) 18649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 18659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __i = __first; 18669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__i; 18679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__i == __last) 18689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 18699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __i = __last; 18709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__i; 18719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 18729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for(;;) { 18739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __ii = __i; 18749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__i; 18759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__i, *__ii)) { 18769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__ii, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 18779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __j = __last; 18789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (!__comp(*__i, *--__j)) {} 18799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iter_swap(__i, __j); 18809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block reverse(__ii, __last); 18819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return true; 18829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 18839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__i == __first) { 18849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block reverse(__first, __last); 18859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 18869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 18879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 18889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_NEED_UNREACHABLE_RETURN) 18899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 18909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 18919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 18929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 18939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 18949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 18959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter> 18969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { 18979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 18989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __next_permutation(__first, __last, 18999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter))); 19009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 19019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Compare> 19039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 19049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 19059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 19069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __next_permutation(__first, __last, __comp); 19079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 19089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 19109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Compare> 19129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 19139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 19149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) 19159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 19169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __i = __first; 19179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__i; 19189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__i == __last) 19199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 19209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __i = __last; 19219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__i; 19229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for(;;) { 19249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __ii = __i; 19259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__i; 19269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__ii, *__i)) { 19279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__i, *__ii), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 19289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BidirectionalIter __j = __last; 19299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (!__comp(*--__j, *__i)) {} 19309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iter_swap(__i, __j); 19319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block reverse(__ii, __last); 19329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return true; 19339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 19349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__i == __first) { 19359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block reverse(__first, __last); 19369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 19379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 19389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 19399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_NEED_UNREACHABLE_RETURN) 19409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 19419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 19429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 19439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 19459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter> 19479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { 19489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 19499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __prev_permutation(__first, __last, 19509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter))); 19519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 19529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BidirectionalIter, class _Compare> 19549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 19559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Compare __comp) { 19569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 19579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __prev_permutation(__first, __last, __comp); 19589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 19599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_NO_EXTENSIONS) 19619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// is_heap, a predicate testing whether or not a range is 19639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// a heap. This function is an extension, not part of the C++ 19649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// standard. 19659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 19669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering> 19689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp, 19699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __n) { 19709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Distance __parent = 0; 19719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (_Distance __child = 1; __child < __n; ++__child) { 19729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(__first[__parent], __first[__child])) { 19739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(__first[__child], __first[__parent]), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 19749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 19759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 19769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if ((__child & 1) == 0) 19779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__parent; 19789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 19799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return true; 19809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 19819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 19839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter> 19859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) { 19869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 19879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __is_heap(__first, _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first); 19889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 19899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _RandomAccessIter, class _StrictWeakOrdering> 19919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool is_heap(_RandomAccessIter __first, _RandomAccessIter __last, 19929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _StrictWeakOrdering __comp) { 19939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 19949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __is_heap(__first, __comp, __last - __first); 19959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 19969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 19989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 19999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 20009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _ForwardIter, class _StrictWeakOrdering> 20019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool __is_sorted(_ForwardIter __first, _ForwardIter __last, 20029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _StrictWeakOrdering __comp) { 2003e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 20049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first == __last) 20059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return true; 20069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 20079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ForwardIter __next = __first; 20089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (++__next; __next != __last; __first = __next, ++__next) { 20099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__comp(*__next, *__first)) { 20109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(!__comp(*__first, *__next), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 20119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 20129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 20139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 20149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 20159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return true; 20169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 20179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 20189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 20199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_NO_EXTENSIONS */ 20209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 20219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE 20229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 20239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef __stl_threshold 20249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 20259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_ALGO_C */ 20269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Local Variables: 20279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// mode:C++ 20289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// End: 2029