ReactOS Development > Doxygen
_algo.c
Go to the documentation of this file.
00001 /* 00002 * 00003 * Copyright (c) 1994 00004 * Hewlett-Packard Company 00005 * 00006 * Copyright (c) 1996,1997 00007 * Silicon Graphics Computer Systems, Inc. 00008 * 00009 * Copyright (c) 1997 00010 * Moscow Center for SPARC Technology 00011 * 00012 * Copyright (c) 1999 00013 * Boris Fomitchev 00014 * 00015 * This material is provided "as is", with absolutely no warranty expressed 00016 * or implied. Any use is at your own risk. 00017 * 00018 * Permission to use or copy this software for any purpose is hereby granted 00019 * without fee, provided the above notices are retained on all copies. 00020 * Permission to modify the code and to distribute modified code is granted, 00021 * provided the above notices are retained, and a notice that the code was 00022 * modified is included with the above copyright notice. 00023 * 00024 */ 00025 00026 #ifndef _STLP_ALGO_C 00027 #define _STLP_ALGO_C 00028 00029 #if !defined (_STLP_INTERNAL_ALGO_H) 00030 # include <stl/_algo.h> 00031 #endif 00032 00033 #ifndef _STLP_INTERNAL_TEMPBUF_H 00034 # include <stl/_tempbuf.h> 00035 #endif 00036 00037 _STLP_BEGIN_NAMESPACE 00038 00039 _STLP_MOVE_TO_PRIV_NAMESPACE 00040 00041 template <class _BidirectionalIter, class _Distance, class _Compare> 00042 void __merge_without_buffer(_BidirectionalIter __first, 00043 _BidirectionalIter __middle, 00044 _BidirectionalIter __last, 00045 _Distance __len1, _Distance __len2, 00046 _Compare __comp); 00047 00048 00049 template <class _BidirectionalIter1, class _BidirectionalIter2, 00050 class _BidirectionalIter3, class _Compare> 00051 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, 00052 _BidirectionalIter1 __last1, 00053 _BidirectionalIter2 __first2, 00054 _BidirectionalIter2 __last2, 00055 _BidirectionalIter3 __result, 00056 _Compare __comp); 00057 00058 template <class _Tp> 00059 #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 )) 00060 inline 00061 #endif 00062 const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) { 00063 if (__a < __b) 00064 if (__b < __c) 00065 return __b; 00066 else if (__a < __c) 00067 return __c; 00068 else 00069 return __a; 00070 else if (__a < __c) 00071 return __a; 00072 else if (__b < __c) 00073 return __c; 00074 else 00075 return __b; 00076 } 00077 00078 template <class _Tp, class _Compare> 00079 #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 )) 00080 inline 00081 #endif 00082 const _Tp& 00083 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) { 00084 if (__comp(__a, __b)) { 00085 _STLP_VERBOSE_ASSERT(!__comp(__b, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 00086 if (__comp(__b, __c)) { 00087 _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 00088 return __b; 00089 } 00090 else if (__comp(__a, __c)) { 00091 _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 00092 return __c; 00093 } 00094 else 00095 return __a; 00096 } 00097 else if (__comp(__a, __c)) { 00098 _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 00099 return __a; 00100 } 00101 else if (__comp(__b, __c)) { 00102 _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 00103 return __c; 00104 } 00105 else 00106 return __b; 00107 } 00108 00109 _STLP_MOVE_TO_STD_NAMESPACE 00110 00111 template <class _ForwardIter1, class _ForwardIter2> 00112 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1, 00113 _ForwardIter2 __first2, _ForwardIter2 __last2) { 00114 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 00115 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 00116 // Test for empty ranges 00117 if (__first1 == __last1 || __first2 == __last2) 00118 return __first1; 00119 00120 // Test for a pattern of length 1. 00121 _ForwardIter2 __p1(__first2); 00122 00123 if ( ++__p1 == __last2 ) 00124 return find(__first1, __last1, *__first2); 00125 00126 // General case. 00127 00128 for ( ; ; ) { // __first1 != __last1 will be checked in find below 00129 __first1 = find(__first1, __last1, *__first2); 00130 if (__first1 == __last1) 00131 return __last1; 00132 00133 _ForwardIter2 __p = __p1; 00134 _ForwardIter1 __current = __first1; 00135 if (++__current == __last1) 00136 return __last1; 00137 00138 while (*__current == *__p) { 00139 if (++__p == __last2) 00140 return __first1; 00141 if (++__current == __last1) 00142 return __last1; 00143 } 00144 00145 ++__first1; 00146 } 00147 return __first1; 00148 } 00149 00150 _STLP_MOVE_TO_PRIV_NAMESPACE 00151 00152 template <class _RandomAccessIter, class _Integer, class _Tp, 00153 class _BinaryPred, class _Distance> 00154 _RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last, 00155 _Integer __count, const _Tp& __val, _BinaryPred __pred, 00156 _Distance*, const random_access_iterator_tag &) 00157 { 00158 _Distance __tailSize = __last - __first; 00159 const _Distance __pattSize = __count; 00160 const _Distance __skipOffset = __pattSize - 1; 00161 _RandomAccessIter __backTrack; 00162 _Distance __remainder, __prevRemainder; 00163 00164 for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) { // the main loop... 00165 //__lookAhead here is always pointing to the last element of next possible match. 00166 __tailSize -= __pattSize; 00167 00168 while ( !__pred(*__lookAhead, __val) ) { // the skip loop... 00169 if (__tailSize < __pattSize) 00170 return __last; 00171 00172 __lookAhead += __pattSize; 00173 __tailSize -= __pattSize; 00174 } 00175 00176 if ( __skipOffset == 0 ) { 00177 return (__lookAhead - __skipOffset); //Success 00178 } 00179 00180 __remainder = __skipOffset; 00181 00182 for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) { 00183 if (--__remainder == 0) 00184 return (__lookAhead - __skipOffset); //Success 00185 } 00186 00187 if (__remainder > __tailSize) 00188 return __last; //failure 00189 00190 __lookAhead += __remainder; 00191 __tailSize -= __remainder; 00192 00193 while ( __pred(*__lookAhead, __val) ) { 00194 __prevRemainder = __remainder; 00195 __backTrack = __lookAhead; 00196 00197 do { 00198 if (--__remainder == 0) 00199 return (__lookAhead - __skipOffset); //Success 00200 } while (__pred(*--__backTrack, __val)); 00201 00202 //adjust remainder for next comparison 00203 __remainder += __pattSize - __prevRemainder; 00204 00205 if (__remainder > __tailSize) 00206 return __last; //failure 00207 00208 __lookAhead += __remainder; 00209 __tailSize -= __remainder; 00210 } 00211 00212 //__lookAhead here is always pointing to the element of the last mismatch. 00213 } 00214 00215 return __last; //failure 00216 } 00217 00218 template <class _ForwardIter, class _Integer, class _Tp, 00219 class _Distance, class _BinaryPred> 00220 _ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last, 00221 _Integer __count, const _Tp& __val, _BinaryPred __pred, 00222 _Distance*, const forward_iterator_tag &) { 00223 for (; (__first != __last) && !__pred(*__first, __val); ++__first) {} 00224 while (__first != __last) { 00225 _Integer __n = __count - 1; 00226 _ForwardIter __i = __first; 00227 ++__i; 00228 while (__i != __last && __n != 0 && __pred(*__i, __val)) { 00229 ++__i; 00230 --__n; 00231 } 00232 if (__n == 0) 00233 return __first; 00234 else if (__i != __last) 00235 for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {} 00236 else 00237 break; 00238 } 00239 return __last; 00240 } 00241 00242 _STLP_MOVE_TO_STD_NAMESPACE 00243 00244 // search_n. Search for __count consecutive copies of __val. 00245 template <class _ForwardIter, class _Integer, class _Tp> 00246 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, 00247 _Integer __count, const _Tp& __val) { 00248 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00249 if (__count <= 0) 00250 return __first; 00251 if (__count == 1) 00252 //We use find when __count == 1 to use potential find overload. 00253 return find(__first, __last, __val); 00254 return _STLP_PRIV __search_n(__first, __last, __count, __val, equal_to<_Tp>(), 00255 _STLP_DISTANCE_TYPE(__first, _ForwardIter), 00256 _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); 00257 } 00258 00259 template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred> 00260 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last, 00261 _Integer __count, const _Tp& __val, 00262 _BinaryPred __binary_pred) { 00263 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00264 if (__count <= 0) 00265 return __first; 00266 return _STLP_PRIV __search_n(__first, __last, __count, __val, __binary_pred, 00267 _STLP_DISTANCE_TYPE(__first, _ForwardIter), 00268 _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); 00269 } 00270 00271 template <class _ForwardIter1, class _ForwardIter2> 00272 _ForwardIter1 00273 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 00274 _ForwardIter2 __first2, _ForwardIter2 __last2) { 00275 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 00276 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 00277 return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2, 00278 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 00279 _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1), 00280 _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2), 00281 #else 00282 forward_iterator_tag(), 00283 forward_iterator_tag(), 00284 #endif 00285 _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1)) 00286 ); 00287 } 00288 00289 // unique and unique_copy 00290 _STLP_MOVE_TO_PRIV_NAMESPACE 00291 00292 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate, 00293 class _Tp> 00294 _STLP_INLINE_LOOP _OutputIterator 00295 __unique_copy(_InputIterator __first, _InputIterator __last, 00296 _OutputIterator __result, 00297 _BinaryPredicate __binary_pred, _Tp*) { 00298 _Tp __val = *__first; 00299 *__result = __val; 00300 while (++__first != __last) 00301 if (!__binary_pred(__val, *__first)) { 00302 __val = *__first; 00303 *++__result = __val; 00304 } 00305 return ++__result; 00306 } 00307 00308 template <class _InputIter, class _OutputIter, class _BinaryPredicate> 00309 inline _OutputIter 00310 __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result, 00311 _BinaryPredicate __binary_pred, const output_iterator_tag &) { 00312 return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, 00313 _STLP_VALUE_TYPE(__first, _InputIter)); 00314 } 00315 00316 template <class _InputIter, class _ForwardIter, class _BinaryPredicate> 00317 _STLP_INLINE_LOOP _ForwardIter 00318 __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, 00319 _BinaryPredicate __binary_pred, const forward_iterator_tag &) { 00320 *__result = *__first; 00321 while (++__first != __last) 00322 if (!__binary_pred(*__result, *__first)) *++__result = *__first; 00323 return ++__result; 00324 } 00325 00326 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) 00327 template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate> 00328 inline _BidirectionalIterator 00329 __unique_copy(_InputIterator __first, _InputIterator __last, 00330 _BidirectionalIterator __result, _BinaryPredicate __binary_pred, 00331 const bidirectional_iterator_tag &) { 00332 return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag()); 00333 } 00334 00335 template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate> 00336 inline _RandomAccessIterator 00337 __unique_copy(_InputIterator __first, _InputIterator __last, 00338 _RandomAccessIterator __result, _BinaryPredicate __binary_pred, 00339 const random_access_iterator_tag &) { 00340 return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag()); 00341 } 00342 #endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */ 00343 00344 _STLP_MOVE_TO_STD_NAMESPACE 00345 00346 template <class _InputIter, class _OutputIter> 00347 _OutputIter 00348 unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) { 00349 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00350 if (__first == __last) return __result; 00351 return _STLP_PRIV __unique_copy(__first, __last, __result, 00352 _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)), 00353 _STLP_ITERATOR_CATEGORY(__result, _OutputIter)); 00354 } 00355 00356 template <class _InputIter, class _OutputIter, class _BinaryPredicate> 00357 _OutputIter 00358 unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result, 00359 _BinaryPredicate __binary_pred) { 00360 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00361 if (__first == __last) return __result; 00362 return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, 00363 _STLP_ITERATOR_CATEGORY(__result, _OutputIter)); 00364 } 00365 00366 // rotate and rotate_copy, and their auxiliary functions 00367 _STLP_MOVE_TO_PRIV_NAMESPACE 00368 00369 template <class _ForwardIter, class _Distance> 00370 _ForwardIter __rotate_aux(_ForwardIter __first, 00371 _ForwardIter __middle, 00372 _ForwardIter __last, 00373 _Distance*, 00374 const forward_iterator_tag &) { 00375 if (__first == __middle) 00376 return __last; 00377 if (__last == __middle) 00378 return __first; 00379 00380 _ForwardIter __first2 = __middle; 00381 do { 00382 _STLP_STD::swap(*__first++, *__first2++); 00383 if (__first == __middle) 00384 __middle = __first2; 00385 } while (__first2 != __last); 00386 00387 _ForwardIter __new_middle = __first; 00388 00389 __first2 = __middle; 00390 00391 while (__first2 != __last) { 00392 _STLP_STD::swap (*__first++, *__first2++); 00393 if (__first == __middle) 00394 __middle = __first2; 00395 else if (__first2 == __last) 00396 __first2 = __middle; 00397 } 00398 00399 return __new_middle; 00400 } 00401 00402 template <class _BidirectionalIter, class _Distance> 00403 _BidirectionalIter __rotate_aux(_BidirectionalIter __first, 00404 _BidirectionalIter __middle, 00405 _BidirectionalIter __last, 00406 _Distance*, 00407 const bidirectional_iterator_tag &) { 00408 if (__first == __middle) 00409 return __last; 00410 if (__last == __middle) 00411 return __first; 00412 00413 _STLP_PRIV __reverse(__first, __middle, bidirectional_iterator_tag()); 00414 _STLP_PRIV __reverse(__middle, __last, bidirectional_iterator_tag()); 00415 00416 while (__first != __middle && __middle != __last) 00417 _STLP_STD::swap(*__first++, *--__last); 00418 00419 if (__first == __middle) { 00420 _STLP_PRIV __reverse(__middle, __last, bidirectional_iterator_tag()); 00421 return __last; 00422 } 00423 else { 00424 _STLP_PRIV __reverse(__first, __middle, bidirectional_iterator_tag()); 00425 return __first; 00426 } 00427 } 00428 00429 // rotate and rotate_copy, and their auxiliary functions 00430 template <class _EuclideanRingElement> 00431 _STLP_INLINE_LOOP 00432 _EuclideanRingElement __gcd(_EuclideanRingElement __m, 00433 _EuclideanRingElement __n) { 00434 while (__n != 0) { 00435 _EuclideanRingElement __t = __m % __n; 00436 __m = __n; 00437 __n = __t; 00438 } 00439 return __m; 00440 } 00441 00442 template <class _RandomAccessIter, class _Distance, class _Tp> 00443 _RandomAccessIter __rotate_aux(_RandomAccessIter __first, 00444 _RandomAccessIter __middle, 00445 _RandomAccessIter __last, 00446 _Distance *, _Tp *) { 00447 00448 _Distance __n = __last - __first; 00449 _Distance __k = __middle - __first; 00450 _Distance __l = __n - __k; 00451 _RandomAccessIter __result = __first + (__last - __middle); 00452 00453 if (__k == 0) /* __first == middle */ 00454 return __last; 00455 00456 if (__k == __l) { 00457 _STLP_STD::swap_ranges(__first, __middle, __middle); 00458 return __result; 00459 } 00460 00461 _Distance __d = _STLP_PRIV __gcd(__n, __k); 00462 00463 for (_Distance __i = 0; __i < __d; __i++) { 00464 _Tp __tmp = *__first; 00465 _RandomAccessIter __p = __first; 00466 00467 if (__k < __l) { 00468 for (_Distance __j = 0; __j < __l/__d; __j++) { 00469 if (__p > __first + __l) { 00470 *__p = *(__p - __l); 00471 __p -= __l; 00472 } 00473 00474 *__p = *(__p + __k); 00475 __p += __k; 00476 } 00477 } 00478 00479 else { 00480 for (_Distance __j = 0; __j < __k/__d - 1; __j ++) { 00481 if (__p < __last - __k) { 00482 *__p = *(__p + __k); 00483 __p += __k; 00484 } 00485 00486 *__p = * (__p - __l); 00487 __p -= __l; 00488 } 00489 } 00490 00491 *__p = __tmp; 00492 ++__first; 00493 } 00494 00495 return __result; 00496 } 00497 00498 template <class _RandomAccessIter, class _Distance> 00499 inline _RandomAccessIter 00500 __rotate_aux(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last, 00501 _Distance * __dis, const random_access_iterator_tag &) { 00502 return _STLP_PRIV __rotate_aux(__first, __middle, __last, 00503 __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter)); 00504 } 00505 00506 template <class _ForwardIter> 00507 _ForwardIter 00508 __rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) { 00509 _STLP_DEBUG_CHECK(__check_range(__first, __middle)) 00510 _STLP_DEBUG_CHECK(__check_range(__middle, __last)) 00511 return __rotate_aux(__first, __middle, __last, 00512 _STLP_DISTANCE_TYPE(__first, _ForwardIter), 00513 _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); 00514 } 00515 00516 _STLP_MOVE_TO_STD_NAMESPACE 00517 00518 template <class _ForwardIter> 00519 void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) { 00520 _STLP_PRIV __rotate(__first, __middle, __last); 00521 } 00522 00523 // Return a random number in the range [0, __n). This function encapsulates 00524 // whether we're using rand (part of the standard C library) or lrand48 00525 // (not standard, but a much better choice whenever it's available). 00526 _STLP_MOVE_TO_PRIV_NAMESPACE 00527 00528 template <class _Distance> 00529 inline _Distance __random_number(_Distance __n) { 00530 #ifdef _STLP_NO_DRAND48 00531 return rand() % __n; 00532 #else 00533 return lrand48() % __n; 00534 #endif 00535 } 00536 00537 _STLP_MOVE_TO_STD_NAMESPACE 00538 00539 template <class _RandomAccessIter> 00540 void random_shuffle(_RandomAccessIter __first, 00541 _RandomAccessIter __last) { 00542 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00543 if (__first == __last) return; 00544 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 00545 iter_swap(__i, __first + _STLP_PRIV __random_number((__i - __first) + 1)); 00546 } 00547 00548 template <class _RandomAccessIter, class _RandomNumberGenerator> 00549 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last, 00550 _RandomNumberGenerator &__rand) { 00551 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00552 if (__first == __last) return; 00553 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 00554 iter_swap(__i, __first + __rand((__i - __first) + 1)); 00555 } 00556 00557 #if !defined (_STLP_NO_EXTENSIONS) 00558 // random_sample and random_sample_n (extensions, not part of the standard). 00559 template <class _ForwardIter, class _OutputIter, class _Distance> 00560 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, 00561 _OutputIter __out_ite, const _Distance __n) { 00562 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00563 _Distance __remaining = _STLP_STD::distance(__first, __last); 00564 _Distance __m = (min) (__n, __remaining); 00565 00566 while (__m > 0) { 00567 if (_STLP_PRIV __random_number(__remaining) < __m) { 00568 *__out_ite = *__first; 00569 ++__out_ite; 00570 --__m; 00571 } 00572 00573 --__remaining; 00574 ++__first; 00575 } 00576 return __out_ite; 00577 } 00578 00579 00580 template <class _ForwardIter, class _OutputIter, class _Distance, 00581 class _RandomNumberGenerator> 00582 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last, 00583 _OutputIter __out_ite, const _Distance __n, 00584 _RandomNumberGenerator& __rand) { 00585 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00586 _Distance __remaining = _STLP_STD::distance(__first, __last); 00587 _Distance __m = (min) (__n, __remaining); 00588 00589 while (__m > 0) { 00590 if (__rand(__remaining) < __m) { 00591 *__out_ite = *__first; 00592 ++__out_ite; 00593 --__m; 00594 } 00595 00596 --__remaining; 00597 ++__first; 00598 } 00599 return __out_ite; 00600 } 00601 00602 _STLP_MOVE_TO_PRIV_NAMESPACE 00603 00604 template <class _InputIter, class _RandomAccessIter, class _Distance> 00605 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, 00606 _RandomAccessIter __out_ite, 00607 const _Distance __n) { 00608 _Distance __m = 0; 00609 _Distance __t = __n; 00610 for ( ; __first != __last && __m < __n; ++__m, ++__first) 00611 __out_ite[__m] = *__first; 00612 00613 while (__first != __last) { 00614 ++__t; 00615 _Distance __M = __random_number(__t); 00616 if (__M < __n) 00617 __out_ite[__M] = *__first; 00618 ++__first; 00619 } 00620 00621 return __out_ite + __m; 00622 } 00623 00624 template <class _InputIter, class _RandomAccessIter, 00625 class _RandomNumberGenerator, class _Distance> 00626 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last, 00627 _RandomAccessIter __out_ite, 00628 _RandomNumberGenerator& __rand, 00629 const _Distance __n) { 00630 _Distance __m = 0; 00631 _Distance __t = __n; 00632 for ( ; __first != __last && __m < __n; ++__m, ++__first) 00633 __out_ite[__m] = *__first; 00634 00635 while (__first != __last) { 00636 ++__t; 00637 _Distance __M = __rand(__t); 00638 if (__M < __n) 00639 __out_ite[__M] = *__first; 00640 ++__first; 00641 } 00642 00643 return __out_ite + __m; 00644 } 00645 00646 _STLP_MOVE_TO_STD_NAMESPACE 00647 00648 template <class _InputIter, class _RandomAccessIter> 00649 _RandomAccessIter 00650 random_sample(_InputIter __first, _InputIter __last, 00651 _RandomAccessIter __out_first, _RandomAccessIter __out_last) { 00652 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00653 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last)) 00654 return _STLP_PRIV __random_sample(__first, __last, 00655 __out_first, __out_last - __out_first); 00656 } 00657 00658 template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator> 00659 _RandomAccessIter 00660 random_sample(_InputIter __first, _InputIter __last, 00661 _RandomAccessIter __out_first, _RandomAccessIter __out_last, 00662 _RandomNumberGenerator& __rand) { 00663 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00664 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last)) 00665 return _STLP_PRIV __random_sample(__first, __last, 00666 __out_first, __rand, 00667 __out_last - __out_first); 00668 } 00669 00670 #endif /* _STLP_NO_EXTENSIONS */ 00671 00672 // partition, stable_partition, and their auxiliary functions 00673 _STLP_MOVE_TO_PRIV_NAMESPACE 00674 00675 template <class _ForwardIter, class _Predicate> 00676 _STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first, 00677 _ForwardIter __last, 00678 _Predicate __pred, 00679 const forward_iterator_tag &) { 00680 if (__first == __last) return __first; 00681 00682 while (__pred(*__first)) 00683 if (++__first == __last) return __first; 00684 00685 _ForwardIter __next = __first; 00686 00687 while (++__next != __last) { 00688 if (__pred(*__next)) { 00689 _STLP_STD::swap(*__first, *__next); 00690 ++__first; 00691 } 00692 } 00693 return __first; 00694 } 00695 00696 template <class _BidirectionalIter, class _Predicate> 00697 _STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first, 00698 _BidirectionalIter __last, 00699 _Predicate __pred, 00700 const bidirectional_iterator_tag &) { 00701 for (;;) { 00702 for (;;) { 00703 if (__first == __last) 00704 return __first; 00705 else if (__pred(*__first)) 00706 ++__first; 00707 else 00708 break; 00709 } 00710 --__last; 00711 for (;;) { 00712 if (__first == __last) 00713 return __first; 00714 else if (!__pred(*__last)) 00715 --__last; 00716 else 00717 break; 00718 } 00719 iter_swap(__first, __last); 00720 ++__first; 00721 } 00722 } 00723 00724 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) 00725 template <class _BidirectionalIter, class _Predicate> 00726 inline 00727 _BidirectionalIter __partition(_BidirectionalIter __first, 00728 _BidirectionalIter __last, 00729 _Predicate __pred, 00730 const random_access_iterator_tag &) { 00731 return __partition(__first, __last, __pred, bidirectional_iterator_tag()); 00732 } 00733 #endif 00734 00735 _STLP_MOVE_TO_STD_NAMESPACE 00736 00737 template <class _ForwardIter, class _Predicate> 00738 _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { 00739 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00740 return _STLP_PRIV __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); 00741 } 00742 00743 00744 /* __pred_of_first: false if we know that __pred(*__first) is false, 00745 * true when we don't know the result of __pred(*__first). 00746 * __not_pred_of_before_last: true if we know that __pred(*--__last) is true, 00747 * false when we don't know the result of __pred(*--__last). 00748 */ 00749 _STLP_MOVE_TO_PRIV_NAMESPACE 00750 00751 template <class _ForwardIter, class _Predicate, class _Distance> 00752 _ForwardIter __inplace_stable_partition(_ForwardIter __first, 00753 _ForwardIter __last, 00754 _Predicate __pred, _Distance __len, 00755 bool __pred_of_first, bool __pred_of_before_last) { 00756 if (__len == 1) 00757 return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first; 00758 _ForwardIter __middle = __first; 00759 _Distance __half_len = __len / 2; 00760 _STLP_STD::advance(__middle, __half_len); 00761 return _STLP_PRIV __rotate(_STLP_PRIV __inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false), 00762 __middle, 00763 _STLP_PRIV __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last)); 00764 } 00765 00766 template <class _ForwardIter, class _Pointer, class _Predicate, 00767 class _Distance> 00768 _ForwardIter __stable_partition_adaptive(_ForwardIter __first, 00769 _ForwardIter __last, 00770 _Predicate __pred, _Distance __len, 00771 _Pointer __buffer, _Distance __buffer_size, 00772 bool __pred_of_first, bool __pred_of_before_last) { 00773 if (__len <= __buffer_size) { 00774 _ForwardIter __result1 = __first; 00775 _Pointer __result2 = __buffer; 00776 if ((__first != __last) && (!__pred_of_first || __pred(*__first))) { 00777 *__result2 = *__first; 00778 ++__result2; ++__first; --__len; 00779 } 00780 for (; __first != __last ; ++__first, --__len) { 00781 if (((__len == 1) && (__pred_of_before_last || __pred(*__first))) || 00782 ((__len != 1) && __pred(*__first))){ 00783 *__result1 = *__first; 00784 ++__result1; 00785 } 00786 else { 00787 *__result2 = *__first; 00788 ++__result2; 00789 } 00790 } 00791 _STLP_STD::copy(__buffer, __result2, __result1); 00792 return __result1; 00793 } 00794 else { 00795 _ForwardIter __middle = __first; 00796 _Distance __half_len = __len / 2; 00797 _STLP_STD::advance(__middle, __half_len); 00798 return _STLP_PRIV __rotate(_STLP_PRIV __stable_partition_adaptive(__first, __middle, __pred, 00799 __half_len, __buffer, __buffer_size, 00800 __pred_of_first, false), 00801 __middle, 00802 _STLP_PRIV __stable_partition_adaptive(__middle, __last, __pred, 00803 __len - __half_len, __buffer, __buffer_size, 00804 true, __pred_of_before_last)); 00805 } 00806 } 00807 00808 template <class _ForwardIter, class _Predicate, class _Tp, class _Distance> 00809 inline _ForwardIter 00810 __stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last, 00811 _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last) { 00812 _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last); 00813 _STLP_MPWFIX_TRY //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present 00814 return (__buf.size() > 0) ? 00815 __stable_partition_adaptive(__first, __last, __pred, 00816 _Distance(__buf.requested_size()), 00817 __buf.begin(), __buf.size(), 00818 false, __pred_of_before_last) : 00819 __inplace_stable_partition(__first, __last, __pred, 00820 _Distance(__buf.requested_size()), 00821 false, __pred_of_before_last); 00822 _STLP_MPWFIX_CATCH //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present 00823 } 00824 00825 template <class _ForwardIter, class _Predicate> 00826 _ForwardIter 00827 __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred, 00828 const forward_iterator_tag &) { 00829 return __stable_partition_aux_aux(__first, __last, __pred, 00830 _STLP_VALUE_TYPE(__first, _ForwardIter), 00831 _STLP_DISTANCE_TYPE(__first, _ForwardIter), false); 00832 } 00833 00834 template <class _BidirectIter, class _Predicate> 00835 _BidirectIter 00836 __stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred, 00837 const bidirectional_iterator_tag &) { 00838 for (--__last;;) { 00839 if (__first == __last) 00840 return __first; 00841 else if (!__pred(*__last)) 00842 --__last; 00843 else 00844 break; 00845 } 00846 ++__last; 00847 //Here we know that __pred(*--__last) is true 00848 return __stable_partition_aux_aux(__first, __last, __pred, 00849 _STLP_VALUE_TYPE(__first, _BidirectIter), 00850 _STLP_DISTANCE_TYPE(__first, _BidirectIter), true); 00851 } 00852 00853 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG) 00854 template <class _BidirectIter, class _Predicate> 00855 _BidirectIter 00856 __stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred, 00857 const random_access_iterator_tag &) { 00858 return __stable_partition_aux(__first, __last, __pred, bidirectional_iterator_tag()); 00859 } 00860 #endif 00861 00862 _STLP_MOVE_TO_STD_NAMESPACE 00863 00864 template <class _ForwardIter, class _Predicate> 00865 _ForwardIter 00866 stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) { 00867 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00868 for (;;) { 00869 if (__first == __last) 00870 return __first; 00871 else if (__pred(*__first)) 00872 ++__first; 00873 else 00874 break; 00875 } 00876 return _STLP_PRIV __stable_partition_aux(__first, __last, __pred, 00877 _STLP_ITERATOR_CATEGORY(__first, _ForwardIter)); 00878 } 00879 00880 _STLP_MOVE_TO_PRIV_NAMESPACE 00881 00882 template <class _RandomAccessIter, class _Tp, class _Compare> 00883 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 00884 _RandomAccessIter __last, 00885 _Tp __pivot, _Compare __comp) { 00886 for (;;) { 00887 while (__comp(*__first, __pivot)) { 00888 _STLP_VERBOSE_ASSERT(!__comp(__pivot, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 00889 ++__first; 00890 } 00891 --__last; 00892 while (__comp(__pivot, *__last)) { 00893 _STLP_VERBOSE_ASSERT(!__comp(*__last, __pivot), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 00894 --__last; 00895 } 00896 if (!(__first < __last)) 00897 return __first; 00898 iter_swap(__first, __last); 00899 ++__first; 00900 } 00901 } 00902 00903 // sort() and its auxiliary functions. 00904 #define __stl_threshold 16 00905 00906 template <class _RandomAccessIter, class _Tp, class _Compare> 00907 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, 00908 _Compare __comp) { 00909 _RandomAccessIter __next = __last; 00910 --__next; 00911 while (__comp(__val, *__next)) { 00912 _STLP_VERBOSE_ASSERT(!__comp(*__next, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 00913 *__last = *__next; 00914 __last = __next; 00915 --__next; 00916 } 00917 *__last = __val; 00918 } 00919 00920 template <class _RandomAccessIter, class _Tp, class _Compare> 00921 inline void __linear_insert(_RandomAccessIter __first, 00922 _RandomAccessIter __last, _Tp __val, _Compare __comp) { 00923 //*TY 12/26/1998 - added __val as a paramter 00924 // _Tp __val = *__last; //*TY 12/26/1998 - __val supplied by caller 00925 if (__comp(__val, *__first)) { 00926 _STLP_VERBOSE_ASSERT(!__comp(*__first, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 00927 copy_backward(__first, __last, __last + 1); 00928 *__first = __val; 00929 } 00930 else 00931 __unguarded_linear_insert(__last, __val, __comp); 00932 } 00933 00934 template <class _RandomAccessIter, class _Tp, class _Compare> 00935 void __insertion_sort(_RandomAccessIter __first, 00936 _RandomAccessIter __last, 00937 _Tp *, _Compare __comp) { 00938 if (__first == __last) return; 00939 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i) 00940 __linear_insert<_RandomAccessIter, _Tp, _Compare>(__first, __i, *__i, __comp); //*TY 12/26/1998 - supply *__i as __val 00941 } 00942 00943 template <class _RandomAccessIter, class _Tp, class _Compare> 00944 void __unguarded_insertion_sort_aux(_RandomAccessIter __first, 00945 _RandomAccessIter __last, 00946 _Tp*, _Compare __comp) { 00947 for (_RandomAccessIter __i = __first; __i != __last; ++__i) 00948 __unguarded_linear_insert<_RandomAccessIter, _Tp, _Compare>(__i, *__i, __comp); 00949 } 00950 00951 template <class _RandomAccessIter, class _Compare> 00952 inline void __unguarded_insertion_sort(_RandomAccessIter __first, 00953 _RandomAccessIter __last, 00954 _Compare __comp) { 00955 __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp); 00956 } 00957 00958 template <class _RandomAccessIter, class _Compare> 00959 void __final_insertion_sort(_RandomAccessIter __first, 00960 _RandomAccessIter __last, _Compare __comp) { 00961 if (__last - __first > __stl_threshold) { 00962 __insertion_sort(__first, __first + __stl_threshold, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); 00963 __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp); 00964 } 00965 else 00966 __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); 00967 } 00968 00969 template <class _RandomAccessIter, class _Tp, class _Size, class _Compare> 00970 void __introsort_loop(_RandomAccessIter __first, 00971 _RandomAccessIter __last, _Tp*, 00972 _Size __depth_limit, _Compare __comp) { 00973 while (__last - __first > __stl_threshold) { 00974 if (__depth_limit == 0) { 00975 partial_sort(__first, __last, __last, __comp); 00976 return; 00977 } 00978 --__depth_limit; 00979 _RandomAccessIter __cut = 00980 __unguarded_partition(__first, __last, 00981 _Tp(__median(*__first, 00982 *(__first + (__last - __first)/2), 00983 *(__last - 1), __comp)), 00984 __comp); 00985 __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp); 00986 __last = __cut; 00987 } 00988 } 00989 00990 _STLP_MOVE_TO_STD_NAMESPACE 00991 00992 template <class _RandomAccessIter> 00993 void sort(_RandomAccessIter __first, _RandomAccessIter __last) { 00994 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 00995 if (__first != __last) { 00996 _STLP_PRIV __introsort_loop(__first, __last, 00997 _STLP_VALUE_TYPE(__first, _RandomAccessIter), 00998 _STLP_PRIV __lg(__last - __first) * 2, 00999 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); 01000 _STLP_PRIV __final_insertion_sort(__first, __last, 01001 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); 01002 } 01003 } 01004 01005 template <class _RandomAccessIter, class _Compare> 01006 void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) { 01007 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01008 if (__first != __last) { 01009 _STLP_PRIV __introsort_loop(__first, __last, 01010 _STLP_VALUE_TYPE(__first, _RandomAccessIter), 01011 _STLP_PRIV __lg(__last - __first) * 2, __comp); 01012 _STLP_PRIV __final_insertion_sort(__first, __last, __comp); 01013 } 01014 } 01015 01016 // stable_sort() and its auxiliary functions. 01017 _STLP_MOVE_TO_PRIV_NAMESPACE 01018 01019 template <class _RandomAccessIter, class _Compare> 01020 void __inplace_stable_sort(_RandomAccessIter __first, 01021 _RandomAccessIter __last, _Compare __comp) { 01022 if (__last - __first < 15) { 01023 __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); 01024 return; 01025 } 01026 _RandomAccessIter __middle = __first + (__last - __first) / 2; 01027 __inplace_stable_sort(__first, __middle, __comp); 01028 __inplace_stable_sort(__middle, __last, __comp); 01029 __merge_without_buffer(__first, __middle, __last, 01030 __middle - __first, 01031 __last - __middle, 01032 __comp); 01033 } 01034 01035 template <class _RandomAccessIter1, class _RandomAccessIter2, 01036 class _Distance, class _Compare> 01037 void __merge_sort_loop(_RandomAccessIter1 __first, 01038 _RandomAccessIter1 __last, 01039 _RandomAccessIter2 __result, _Distance __step_size, 01040 _Compare __comp) { 01041 _Distance __two_step = 2 * __step_size; 01042 01043 while (__last - __first >= __two_step) { 01044 __result = merge(__first, __first + __step_size, 01045 __first + __step_size, __first + __two_step, 01046 __result, 01047 __comp); 01048 __first += __two_step; 01049 } 01050 __step_size = (min) (_Distance(__last - __first), __step_size); 01051 01052 merge(__first, __first + __step_size, 01053 __first + __step_size, __last, 01054 __result, 01055 __comp); 01056 } 01057 01058 const int __stl_chunk_size = 7; 01059 01060 template <class _RandomAccessIter, class _Distance, class _Compare> 01061 void __chunk_insertion_sort(_RandomAccessIter __first, 01062 _RandomAccessIter __last, 01063 _Distance __chunk_size, _Compare __comp) { 01064 while (__last - __first >= __chunk_size) { 01065 __insertion_sort(__first, __first + __chunk_size, 01066 _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); 01067 __first += __chunk_size; 01068 } 01069 __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); 01070 } 01071 01072 template <class _RandomAccessIter, class _Pointer, class _Distance, 01073 class _Compare> 01074 void __merge_sort_with_buffer(_RandomAccessIter __first, 01075 _RandomAccessIter __last, _Pointer __buffer, 01076 _Distance*, _Compare __comp) { 01077 _Distance __len = __last - __first; 01078 _Pointer __buffer_last = __buffer + __len; 01079 01080 _Distance __step_size = __stl_chunk_size; 01081 __chunk_insertion_sort(__first, __last, __step_size, __comp); 01082 01083 while (__step_size < __len) { 01084 __merge_sort_loop(__first, __last, __buffer, __step_size, __comp); 01085 __step_size *= 2; 01086 __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp); 01087 __step_size *= 2; 01088 } 01089 } 01090 01091 template <class _BidirectionalIter1, class _BidirectionalIter2, 01092 class _Distance> 01093 _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first, 01094 _BidirectionalIter1 __middle, 01095 _BidirectionalIter1 __last, 01096 _Distance __len1, _Distance __len2, 01097 _BidirectionalIter2 __buffer, 01098 _Distance __buffer_size) { 01099 if (__len1 > __len2 && __len2 <= __buffer_size) { 01100 _BidirectionalIter2 __buffer_end = _STLP_STD::copy(__middle, __last, __buffer); 01101 _STLP_STD::copy_backward(__first, __middle, __last); 01102 return _STLP_STD::copy(__buffer, __buffer_end, __first); 01103 } 01104 else if (__len1 <= __buffer_size) { 01105 _BidirectionalIter2 __buffer_end = _STLP_STD::copy(__first, __middle, __buffer); 01106 _STLP_STD::copy(__middle, __last, __first); 01107 return _STLP_STD::copy_backward(__buffer, __buffer_end, __last); 01108 } 01109 else 01110 return _STLP_PRIV __rotate(__first, __middle, __last); 01111 } 01112 01113 template <class _BidirectionalIter, class _Distance, class _Pointer, 01114 class _Compare> 01115 void __merge_adaptive(_BidirectionalIter __first, 01116 _BidirectionalIter __middle, 01117 _BidirectionalIter __last, 01118 _Distance __len1, _Distance __len2, 01119 _Pointer __buffer, _Distance __buffer_size, 01120 _Compare __comp) { 01121 if (__len1 <= __len2 && __len1 <= __buffer_size) { 01122 _Pointer __buffer_end = _STLP_STD::copy(__first, __middle, __buffer); 01123 _STLP_STD::merge(__buffer, __buffer_end, __middle, __last, __first, __comp); 01124 } 01125 else if (__len2 <= __buffer_size) { 01126 _Pointer __buffer_end = _STLP_STD::copy(__middle, __last, __buffer); 01127 _STLP_PRIV __merge_backward(__first, __middle, __buffer, __buffer_end, __last, 01128 __comp); 01129 } 01130 else { 01131 _BidirectionalIter __first_cut = __first; 01132 _BidirectionalIter __second_cut = __middle; 01133 _Distance __len11 = 0; 01134 _Distance __len22 = 0; 01135 if (__len1 > __len2) { 01136 __len11 = __len1 / 2; 01137 _STLP_STD::advance(__first_cut, __len11); 01138 __second_cut = _STLP_STD::lower_bound(__middle, __last, *__first_cut, __comp); 01139 __len22 += _STLP_STD::distance(__middle, __second_cut); 01140 } 01141 else { 01142 __len22 = __len2 / 2; 01143 _STLP_STD::advance(__second_cut, __len22); 01144 __first_cut = _STLP_STD::upper_bound(__first, __middle, *__second_cut, __comp); 01145 __len11 += _STLP_STD::distance(__first, __first_cut); 01146 } 01147 _BidirectionalIter __new_middle = 01148 __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11, 01149 __len22, __buffer, __buffer_size); 01150 __merge_adaptive(__first, __first_cut, __new_middle, __len11, 01151 __len22, __buffer, __buffer_size, __comp); 01152 __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11, 01153 __len2 - __len22, __buffer, __buffer_size, __comp); 01154 } 01155 } 01156 01157 template <class _RandomAccessIter, class _Pointer, class _Distance, 01158 class _Compare> 01159 void __stable_sort_adaptive(_RandomAccessIter __first, 01160 _RandomAccessIter __last, _Pointer __buffer, 01161 _Distance __buffer_size, _Compare __comp) { 01162 _Distance __len = (__last - __first + 1) / 2; 01163 _RandomAccessIter __middle = __first + __len; 01164 if (__len > __buffer_size) { 01165 __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, 01166 __comp); 01167 __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, 01168 __comp); 01169 } 01170 else { 01171 __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0, 01172 __comp); 01173 __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0, 01174 __comp); 01175 } 01176 __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 01177 _Distance(__last - __middle), __buffer, __buffer_size, 01178 __comp); 01179 } 01180 01181 template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare> 01182 void __stable_sort_aux(_RandomAccessIter __first, 01183 _RandomAccessIter __last, _Tp*, _Distance*, 01184 _Compare __comp) { 01185 _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last); 01186 if (buf.begin() == 0) 01187 __inplace_stable_sort(__first, __last, __comp); 01188 else 01189 __stable_sort_adaptive(__first, __last, buf.begin(), 01190 _Distance(buf.size()), 01191 __comp); 01192 } 01193 01194 _STLP_MOVE_TO_STD_NAMESPACE 01195 01196 template <class _RandomAccessIter> 01197 void stable_sort(_RandomAccessIter __first, 01198 _RandomAccessIter __last) { 01199 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01200 _STLP_PRIV __stable_sort_aux(__first, __last, 01201 _STLP_VALUE_TYPE(__first, _RandomAccessIter), 01202 _STLP_DISTANCE_TYPE(__first, _RandomAccessIter), 01203 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); 01204 } 01205 01206 template <class _RandomAccessIter, class _Compare> 01207 void stable_sort(_RandomAccessIter __first, 01208 _RandomAccessIter __last, _Compare __comp) { 01209 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01210 _STLP_PRIV __stable_sort_aux(__first, __last, 01211 _STLP_VALUE_TYPE(__first, _RandomAccessIter), 01212 _STLP_DISTANCE_TYPE(__first, _RandomAccessIter), 01213 __comp); 01214 } 01215 01216 // partial_sort, partial_sort_copy, and auxiliary functions. 01217 _STLP_MOVE_TO_PRIV_NAMESPACE 01218 01219 template <class _RandomAccessIter, class _Tp, class _Compare> 01220 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle, 01221 _RandomAccessIter __last, _Tp*, _Compare __comp) { 01222 make_heap(__first, __middle, __comp); 01223 for (_RandomAccessIter __i = __middle; __i < __last; ++__i) { 01224 if (__comp(*__i, *__first)) { 01225 _STLP_VERBOSE_ASSERT(!__comp(*__first, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01226 __pop_heap(__first, __middle, __i, _Tp(*__i), __comp, 01227 _STLP_DISTANCE_TYPE(__first, _RandomAccessIter)); 01228 } 01229 } 01230 sort_heap(__first, __middle, __comp); 01231 } 01232 01233 _STLP_MOVE_TO_STD_NAMESPACE 01234 01235 template <class _RandomAccessIter> 01236 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, 01237 _RandomAccessIter __last) { 01238 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle)) 01239 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last)) 01240 _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), 01241 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); 01242 } 01243 01244 template <class _RandomAccessIter, class _Compare> 01245 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, 01246 _RandomAccessIter __last, _Compare __comp) { 01247 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle)) 01248 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last)) 01249 _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp); 01250 } 01251 01252 _STLP_MOVE_TO_PRIV_NAMESPACE 01253 01254 template <class _InputIter, class _RandomAccessIter, class _Compare, 01255 class _Distance, class _Tp> 01256 _RandomAccessIter __partial_sort_copy(_InputIter __first, 01257 _InputIter __last, 01258 _RandomAccessIter __result_first, 01259 _RandomAccessIter __result_last, 01260 _Compare __comp, _Distance*, _Tp*) { 01261 if (__result_first == __result_last) return __result_last; 01262 _RandomAccessIter __result_real_last = __result_first; 01263 while(__first != __last && __result_real_last != __result_last) { 01264 *__result_real_last = *__first; 01265 ++__result_real_last; 01266 ++__first; 01267 } 01268 make_heap(__result_first, __result_real_last, __comp); 01269 while (__first != __last) { 01270 if (__comp(*__first, *__result_first)) { 01271 _STLP_VERBOSE_ASSERT(!__comp(*__result_first, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01272 __adjust_heap(__result_first, _Distance(0), 01273 _Distance(__result_real_last - __result_first), 01274 _Tp(*__first), 01275 __comp); 01276 } 01277 ++__first; 01278 } 01279 sort_heap(__result_first, __result_real_last, __comp); 01280 return __result_real_last; 01281 } 01282 01283 _STLP_MOVE_TO_STD_NAMESPACE 01284 01285 template <class _InputIter, class _RandomAccessIter> 01286 _RandomAccessIter 01287 partial_sort_copy(_InputIter __first, _InputIter __last, 01288 _RandomAccessIter __result_first, _RandomAccessIter __result_last) { 01289 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01290 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last)) 01291 return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last, 01292 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _InputIter)), 01293 _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter), 01294 _STLP_VALUE_TYPE(__first, _InputIter)); 01295 } 01296 01297 template <class _InputIter, class _RandomAccessIter, class _Compare> 01298 _RandomAccessIter 01299 partial_sort_copy(_InputIter __first, _InputIter __last, 01300 _RandomAccessIter __result_first, 01301 _RandomAccessIter __result_last, _Compare __comp) { 01302 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01303 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last)) 01304 return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last, 01305 __comp, 01306 _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter), 01307 _STLP_VALUE_TYPE(__first, _InputIter)); 01308 } 01309 01310 // nth_element() and its auxiliary functions. 01311 _STLP_MOVE_TO_PRIV_NAMESPACE 01312 01313 template <class _RandomAccessIter, class _Tp, class _Compare> 01314 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 01315 _RandomAccessIter __last, _Tp*, _Compare __comp) { 01316 while (__last - __first > 3) { 01317 _RandomAccessIter __cut = 01318 __unguarded_partition(__first, __last, 01319 _Tp(__median(*__first, 01320 *(__first + (__last - __first)/2), 01321 *(__last - 1), 01322 __comp)), 01323 __comp); 01324 if (__cut <= __nth) 01325 __first = __cut; 01326 else 01327 __last = __cut; 01328 } 01329 __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp); 01330 } 01331 01332 _STLP_MOVE_TO_STD_NAMESPACE 01333 01334 template <class _RandomAccessIter> 01335 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 01336 _RandomAccessIter __last) { 01337 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth)) 01338 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last)) 01339 _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), 01340 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter))); 01341 } 01342 01343 template <class _RandomAccessIter, class _Compare> 01344 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth, 01345 _RandomAccessIter __last, _Compare __comp) { 01346 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth)) 01347 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last)) 01348 _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp); 01349 } 01350 01351 // Binary search (lower_bound, upper_bound, equal_range, binary_search). 01352 _STLP_MOVE_TO_PRIV_NAMESPACE 01353 01354 template <class _ForwardIter, class _Tp, 01355 class _Compare1, class _Compare2, class _Distance> 01356 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 01357 _Compare1 __comp1, _Compare2 __comp2, _Distance*) { 01358 _Distance __len = _STLP_STD::distance(__first, __last); 01359 _Distance __half; 01360 01361 while (__len > 0) { 01362 __half = __len >> 1; 01363 _ForwardIter __middle = __first; 01364 _STLP_STD::advance(__middle, __half); 01365 if (__comp2(__val, *__middle)) { 01366 _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01367 __len = __half; 01368 } 01369 else { 01370 __first = __middle; 01371 ++__first; 01372 __len = __len - __half - 1; 01373 } 01374 } 01375 return __first; 01376 } 01377 01378 template <class _ForwardIter, class _Tp, 01379 class _Compare1, class _Compare2, class _Distance> 01380 pair<_ForwardIter, _ForwardIter> 01381 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val, 01382 _Compare1 __comp1, _Compare2 __comp2, _Distance* __dist) { 01383 _Distance __len = _STLP_STD::distance(__first, __last); 01384 _Distance __half; 01385 01386 while (__len > 0) { 01387 __half = __len >> 1; 01388 _ForwardIter __middle = __first; 01389 _STLP_STD::advance(__middle, __half); 01390 if (__comp1(*__middle, __val)) { 01391 _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01392 __first = __middle; 01393 ++__first; 01394 __len = __len - __half - 1; 01395 } 01396 else if (__comp2(__val, *__middle)) { 01397 _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01398 __len = __half; 01399 } 01400 else { 01401 _ForwardIter __left = _STLP_PRIV __lower_bound(__first, __middle, __val, __comp1, __comp2, __dist); 01402 //Small optim: If lower_bound haven't found an equivalent value 01403 //there is no need to call upper_bound. 01404 if (__comp1(*__left, __val)) { 01405 _STLP_VERBOSE_ASSERT(!__comp2(__val, *__left), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01406 return pair<_ForwardIter, _ForwardIter>(__left, __left); 01407 } 01408 _STLP_STD::advance(__first, __len); 01409 _ForwardIter __right = _STLP_PRIV __upper_bound(++__middle, __first, __val, __comp1, __comp2, __dist); 01410 return pair<_ForwardIter, _ForwardIter>(__left, __right); 01411 } 01412 } 01413 return pair<_ForwardIter, _ForwardIter>(__first, __first); 01414 } 01415 01416 _STLP_MOVE_TO_STD_NAMESPACE 01417 01418 template <class _InputIter1, class _InputIter2, class _OutputIter> 01419 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, 01420 _InputIter2 __first2, _InputIter2 __last2, 01421 _OutputIter __result) { 01422 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 01423 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 01424 while (__first1 != __last1 && __first2 != __last2) { 01425 if (*__first2 < *__first1) { 01426 *__result = *__first2; 01427 ++__first2; 01428 } 01429 else { 01430 *__result = *__first1; 01431 ++__first1; 01432 } 01433 ++__result; 01434 } 01435 return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result)); 01436 } 01437 01438 template <class _InputIter1, class _InputIter2, class _OutputIter, 01439 class _Compare> 01440 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1, 01441 _InputIter2 __first2, _InputIter2 __last2, 01442 _OutputIter __result, _Compare __comp) { 01443 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 01444 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 01445 while (__first1 != __last1 && __first2 != __last2) { 01446 if (__comp(*__first2, *__first1)) { 01447 _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01448 *__result = *__first2; 01449 ++__first2; 01450 } 01451 else { 01452 *__result = *__first1; 01453 ++__first1; 01454 } 01455 ++__result; 01456 } 01457 return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result)); 01458 } 01459 01460 _STLP_MOVE_TO_PRIV_NAMESPACE 01461 01462 template <class _BidirectionalIter, class _Distance, class _Compare> 01463 void __merge_without_buffer(_BidirectionalIter __first, 01464 _BidirectionalIter __middle, 01465 _BidirectionalIter __last, 01466 _Distance __len1, _Distance __len2, 01467 _Compare __comp) { 01468 if (__len1 == 0 || __len2 == 0) 01469 return; 01470 if (__len1 + __len2 == 2) { 01471 if (__comp(*__middle, *__first)) { 01472 _STLP_VERBOSE_ASSERT(!__comp(*__first, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01473 iter_swap(__first, __middle); 01474 } 01475 return; 01476 } 01477 _BidirectionalIter __first_cut = __first; 01478 _BidirectionalIter __second_cut = __middle; 01479 _Distance __len11 = 0; 01480 _Distance __len22 = 0; 01481 if (__len1 > __len2) { 01482 __len11 = __len1 / 2; 01483 _STLP_STD::advance(__first_cut, __len11); 01484 __second_cut = _STLP_STD::lower_bound(__middle, __last, *__first_cut, __comp); 01485 __len22 += _STLP_STD::distance(__middle, __second_cut); 01486 } 01487 else { 01488 __len22 = __len2 / 2; 01489 _STLP_STD::advance(__second_cut, __len22); 01490 __first_cut = _STLP_STD::upper_bound(__first, __middle, *__second_cut, __comp); 01491 __len11 += _STLP_STD::distance(__first, __first_cut); 01492 } 01493 _BidirectionalIter __new_middle 01494 = _STLP_PRIV __rotate(__first_cut, __middle, __second_cut); 01495 __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22, 01496 __comp); 01497 __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11, 01498 __len2 - __len22, __comp); 01499 } 01500 01501 template <class _BidirectionalIter1, class _BidirectionalIter2, 01502 class _BidirectionalIter3, class _Compare> 01503 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1, 01504 _BidirectionalIter1 __last1, 01505 _BidirectionalIter2 __first2, 01506 _BidirectionalIter2 __last2, 01507 _BidirectionalIter3 __result, 01508 _Compare __comp) { 01509 if (__first1 == __last1) 01510 return copy_backward(__first2, __last2, __result); 01511 if (__first2 == __last2) 01512 return copy_backward(__first1, __last1, __result); 01513 --__last1; 01514 --__last2; 01515 for (;;) { 01516 if (__comp(*__last2, *__last1)) { 01517 _STLP_VERBOSE_ASSERT(!__comp(*__last1, *__last2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01518 *--__result = *__last1; 01519 if (__first1 == __last1) 01520 return copy_backward(__first2, ++__last2, __result); 01521 --__last1; 01522 } 01523 else { 01524 *--__result = *__last2; 01525 if (__first2 == __last2) 01526 return copy_backward(__first1, ++__last1, __result); 01527 --__last2; 01528 } 01529 } 01530 } 01531 01532 template <class _BidirectionalIter, class _Tp, 01533 class _Distance, class _Compare> 01534 inline void __inplace_merge_aux(_BidirectionalIter __first, 01535 _BidirectionalIter __middle, 01536 _BidirectionalIter __last, _Tp*, _Distance*, 01537 _Compare __comp) { 01538 _Distance __len1 = _STLP_STD::distance(__first, __middle); 01539 _Distance __len2 = _STLP_STD::distance(__middle, __last); 01540 01541 _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last); 01542 if (__buf.begin() == 0) 01543 __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp); 01544 else 01545 __merge_adaptive(__first, __middle, __last, __len1, __len2, 01546 __buf.begin(), _Distance(__buf.size()), 01547 __comp); 01548 } 01549 01550 _STLP_MOVE_TO_STD_NAMESPACE 01551 01552 template <class _BidirectionalIter> 01553 void inplace_merge(_BidirectionalIter __first, 01554 _BidirectionalIter __middle, 01555 _BidirectionalIter __last) { 01556 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle)) 01557 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last)) 01558 if (__first == __middle || __middle == __last) 01559 return; 01560 _STLP_PRIV __inplace_merge_aux(__first, __middle, __last, 01561 _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter), 01562 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter))); 01563 } 01564 01565 template <class _BidirectionalIter, class _Compare> 01566 void inplace_merge(_BidirectionalIter __first, 01567 _BidirectionalIter __middle, 01568 _BidirectionalIter __last, _Compare __comp) { 01569 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle)) 01570 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last)) 01571 if (__first == __middle || __middle == __last) 01572 return; 01573 _STLP_PRIV __inplace_merge_aux(__first, __middle, __last, 01574 _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter), 01575 __comp); 01576 } 01577 01578 _STLP_MOVE_TO_PRIV_NAMESPACE 01579 01580 template <class _InputIter1, class _InputIter2, class _Compare> 01581 bool __includes(_InputIter1 __first1, _InputIter1 __last1, 01582 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) { 01583 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 01584 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 01585 while (__first1 != __last1 && __first2 != __last2) 01586 if (__comp(*__first2, *__first1)) { 01587 _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01588 return false; 01589 } 01590 else if (__comp(*__first1, *__first2)) 01591 ++__first1; 01592 else 01593 ++__first1, ++__first2; 01594 01595 return __first2 == __last2; 01596 } 01597 01598 _STLP_MOVE_TO_STD_NAMESPACE 01599 01600 template <class _InputIter1, class _InputIter2, class _Compare> 01601 bool includes(_InputIter1 __first1, _InputIter1 __last1, 01602 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) { 01603 return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, __comp); 01604 } 01605 01606 template <class _InputIter1, class _InputIter2> 01607 bool includes(_InputIter1 __first1, _InputIter1 __last1, 01608 _InputIter2 __first2, _InputIter2 __last2) { 01609 return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, 01610 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); 01611 } 01612 01613 _STLP_MOVE_TO_PRIV_NAMESPACE 01614 01615 template <class _InputIter1, class _InputIter2, class _OutputIter, 01616 class _Compare> 01617 _OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1, 01618 _InputIter2 __first2, _InputIter2 __last2, 01619 _OutputIter __result, _Compare __comp) { 01620 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 01621 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 01622 while (__first1 != __last1 && __first2 != __last2) { 01623 if (__comp(*__first1, *__first2)) { 01624 _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01625 *__result = *__first1; 01626 ++__first1; 01627 } 01628 else if (__comp(*__first2, *__first1)) { 01629 _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01630 *__result = *__first2; 01631 ++__first2; 01632 } 01633 else { 01634 *__result = *__first1; 01635 ++__first1; 01636 ++__first2; 01637 } 01638 ++__result; 01639 } 01640 return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result)); 01641 } 01642 01643 _STLP_MOVE_TO_STD_NAMESPACE 01644 01645 template <class _InputIter1, class _InputIter2, class _OutputIter> 01646 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, 01647 _InputIter2 __first2, _InputIter2 __last2, 01648 _OutputIter __result) { 01649 return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, 01650 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); 01651 } 01652 01653 template <class _InputIter1, class _InputIter2, class _OutputIter, 01654 class _Compare> 01655 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1, 01656 _InputIter2 __first2, _InputIter2 __last2, 01657 _OutputIter __result, _Compare __comp) { 01658 return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, __comp); 01659 } 01660 01661 _STLP_MOVE_TO_PRIV_NAMESPACE 01662 01663 template <class _InputIter1, class _InputIter2, class _OutputIter, 01664 class _Compare> 01665 _OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1, 01666 _InputIter2 __first2, _InputIter2 __last2, 01667 _OutputIter __result, _Compare __comp) { 01668 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 01669 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 01670 while (__first1 != __last1 && __first2 != __last2) 01671 if (__comp(*__first1, *__first2)) { 01672 _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01673 ++__first1; 01674 } 01675 else if (__comp(*__first2, *__first1)) 01676 ++__first2; 01677 else { 01678 *__result = *__first1; 01679 ++__first1; 01680 ++__first2; 01681 ++__result; 01682 } 01683 return __result; 01684 } 01685 01686 _STLP_MOVE_TO_STD_NAMESPACE 01687 01688 template <class _InputIter1, class _InputIter2, class _OutputIter> 01689 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, 01690 _InputIter2 __first2, _InputIter2 __last2, 01691 _OutputIter __result) { 01692 return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, 01693 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); 01694 } 01695 01696 template <class _InputIter1, class _InputIter2, class _OutputIter, 01697 class _Compare> 01698 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1, 01699 _InputIter2 __first2, _InputIter2 __last2, 01700 _OutputIter __result, _Compare __comp) { 01701 return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, __comp); 01702 } 01703 01704 _STLP_MOVE_TO_PRIV_NAMESPACE 01705 01706 template <class _InputIter1, class _InputIter2, class _OutputIter, 01707 class _Compare> 01708 _OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1, 01709 _InputIter2 __first2, _InputIter2 __last2, 01710 _OutputIter __result, _Compare __comp) { 01711 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 01712 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 01713 while (__first1 != __last1 && __first2 != __last2) 01714 if (__comp(*__first1, *__first2)) { 01715 _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01716 *__result = *__first1; 01717 ++__first1; 01718 ++__result; 01719 } 01720 else if (__comp(*__first2, *__first1)) 01721 ++__first2; 01722 else { 01723 ++__first1; 01724 ++__first2; 01725 } 01726 return _STLP_STD::copy(__first1, __last1, __result); 01727 } 01728 01729 _STLP_MOVE_TO_STD_NAMESPACE 01730 01731 template <class _InputIter1, class _InputIter2, class _OutputIter> 01732 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, 01733 _InputIter2 __first2, _InputIter2 __last2, 01734 _OutputIter __result) { 01735 return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, 01736 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); 01737 } 01738 01739 template <class _InputIter1, class _InputIter2, class _OutputIter, 01740 class _Compare> 01741 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1, 01742 _InputIter2 __first2, _InputIter2 __last2, 01743 _OutputIter __result, _Compare __comp) { 01744 return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, __comp); 01745 } 01746 01747 _STLP_MOVE_TO_PRIV_NAMESPACE 01748 01749 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> 01750 _OutputIter 01751 __set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 01752 _InputIter2 __first2, _InputIter2 __last2, 01753 _OutputIter __result, _Compare __comp) { 01754 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1)) 01755 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2)) 01756 while (__first1 != __last1 && __first2 != __last2) { 01757 if (__comp(*__first1, *__first2)) { 01758 _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01759 *__result = *__first1; 01760 ++__first1; 01761 ++__result; 01762 } 01763 else if (__comp(*__first2, *__first1)) { 01764 *__result = *__first2; 01765 ++__first2; 01766 ++__result; 01767 } 01768 else { 01769 ++__first1; 01770 ++__first2; 01771 } 01772 } 01773 return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result)); 01774 } 01775 01776 _STLP_MOVE_TO_STD_NAMESPACE 01777 01778 template <class _InputIter1, class _InputIter2, class _OutputIter> 01779 _OutputIter 01780 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 01781 _InputIter2 __first2, _InputIter2 __last2, 01782 _OutputIter __result) { 01783 return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, 01784 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1))); 01785 } 01786 01787 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare> 01788 _OutputIter 01789 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1, 01790 _InputIter2 __first2, _InputIter2 __last2, 01791 _OutputIter __result, 01792 _Compare __comp) { 01793 return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp); 01794 } 01795 01796 // min_element and max_element, with and without an explicitly supplied 01797 // comparison function. 01798 01799 template <class _ForwardIter> 01800 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) { 01801 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01802 if (__first == __last) return __first; 01803 _ForwardIter __result = __first; 01804 while (++__first != __last) 01805 if (*__result < *__first) { 01806 _STLP_VERBOSE_ASSERT(!(*__first < *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01807 __result = __first; 01808 } 01809 return __result; 01810 } 01811 01812 template <class _ForwardIter, class _Compare> 01813 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last, 01814 _Compare __comp) { 01815 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01816 if (__first == __last) return __first; 01817 _ForwardIter __result = __first; 01818 while (++__first != __last) { 01819 if (__comp(*__result, *__first)) { 01820 _STLP_VERBOSE_ASSERT(!__comp(*__first, *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01821 __result = __first; 01822 } 01823 } 01824 return __result; 01825 } 01826 01827 template <class _ForwardIter> 01828 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) { 01829 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01830 if (__first == __last) return __first; 01831 _ForwardIter __result = __first; 01832 while (++__first != __last) 01833 if (*__first < *__result) { 01834 _STLP_VERBOSE_ASSERT(!(*__result < *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01835 __result = __first; 01836 } 01837 return __result; 01838 } 01839 01840 template <class _ForwardIter, class _Compare> 01841 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last, 01842 _Compare __comp) { 01843 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01844 if (__first == __last) return __first; 01845 _ForwardIter __result = __first; 01846 while (++__first != __last) { 01847 if (__comp(*__first, *__result)) { 01848 _STLP_VERBOSE_ASSERT(!__comp(*__result, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01849 __result = __first; 01850 } 01851 } 01852 return __result; 01853 } 01854 01855 // next_permutation and prev_permutation, with and without an explicitly 01856 // supplied comparison function. 01857 _STLP_MOVE_TO_PRIV_NAMESPACE 01858 01859 template <class _BidirectionalIter, class _Compare> 01860 bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 01861 _Compare __comp) { 01862 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01863 if (__first == __last) 01864 return false; 01865 _BidirectionalIter __i = __first; 01866 ++__i; 01867 if (__i == __last) 01868 return false; 01869 __i = __last; 01870 --__i; 01871 01872 for(;;) { 01873 _BidirectionalIter __ii = __i; 01874 --__i; 01875 if (__comp(*__i, *__ii)) { 01876 _STLP_VERBOSE_ASSERT(!__comp(*__ii, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01877 _BidirectionalIter __j = __last; 01878 while (!__comp(*__i, *--__j)) {} 01879 iter_swap(__i, __j); 01880 reverse(__ii, __last); 01881 return true; 01882 } 01883 if (__i == __first) { 01884 reverse(__first, __last); 01885 return false; 01886 } 01887 } 01888 #if defined (_STLP_NEED_UNREACHABLE_RETURN) 01889 return false; 01890 #endif 01891 } 01892 01893 _STLP_MOVE_TO_STD_NAMESPACE 01894 01895 template <class _BidirectionalIter> 01896 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { 01897 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01898 return _STLP_PRIV __next_permutation(__first, __last, 01899 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter))); 01900 } 01901 01902 template <class _BidirectionalIter, class _Compare> 01903 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 01904 _Compare __comp) { 01905 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01906 return _STLP_PRIV __next_permutation(__first, __last, __comp); 01907 } 01908 01909 _STLP_MOVE_TO_PRIV_NAMESPACE 01910 01911 template <class _BidirectionalIter, class _Compare> 01912 bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 01913 _Compare __comp) { 01914 if (__first == __last) 01915 return false; 01916 _BidirectionalIter __i = __first; 01917 ++__i; 01918 if (__i == __last) 01919 return false; 01920 __i = __last; 01921 --__i; 01922 01923 for(;;) { 01924 _BidirectionalIter __ii = __i; 01925 --__i; 01926 if (__comp(*__ii, *__i)) { 01927 _STLP_VERBOSE_ASSERT(!__comp(*__i, *__ii), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01928 _BidirectionalIter __j = __last; 01929 while (!__comp(*--__j, *__i)) {} 01930 iter_swap(__i, __j); 01931 reverse(__ii, __last); 01932 return true; 01933 } 01934 if (__i == __first) { 01935 reverse(__first, __last); 01936 return false; 01937 } 01938 } 01939 #if defined (_STLP_NEED_UNREACHABLE_RETURN) 01940 return false; 01941 #endif 01942 } 01943 01944 _STLP_MOVE_TO_STD_NAMESPACE 01945 01946 template <class _BidirectionalIter> 01947 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) { 01948 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01949 return _STLP_PRIV __prev_permutation(__first, __last, 01950 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter))); 01951 } 01952 01953 template <class _BidirectionalIter, class _Compare> 01954 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last, 01955 _Compare __comp) { 01956 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01957 return _STLP_PRIV __prev_permutation(__first, __last, __comp); 01958 } 01959 01960 #if !defined (_STLP_NO_EXTENSIONS) 01961 01962 // is_heap, a predicate testing whether or not a range is 01963 // a heap. This function is an extension, not part of the C++ 01964 // standard. 01965 _STLP_MOVE_TO_PRIV_NAMESPACE 01966 01967 template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering> 01968 bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp, 01969 _Distance __n) { 01970 _Distance __parent = 0; 01971 for (_Distance __child = 1; __child < __n; ++__child) { 01972 if (__comp(__first[__parent], __first[__child])) { 01973 _STLP_VERBOSE_ASSERT(!__comp(__first[__child], __first[__parent]), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 01974 return false; 01975 } 01976 if ((__child & 1) == 0) 01977 ++__parent; 01978 } 01979 return true; 01980 } 01981 01982 _STLP_MOVE_TO_STD_NAMESPACE 01983 01984 template <class _RandomAccessIter> 01985 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) { 01986 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01987 return _STLP_PRIV __is_heap(__first, _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first); 01988 } 01989 01990 template <class _RandomAccessIter, class _StrictWeakOrdering> 01991 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last, 01992 _StrictWeakOrdering __comp) { 01993 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 01994 return _STLP_PRIV __is_heap(__first, __comp, __last - __first); 01995 } 01996 01997 01998 _STLP_MOVE_TO_PRIV_NAMESPACE 01999 02000 template <class _ForwardIter, class _StrictWeakOrdering> 02001 bool __is_sorted(_ForwardIter __first, _ForwardIter __last, 02002 _StrictWeakOrdering __comp) { 02003 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 02004 if (__first == __last) 02005 return true; 02006 02007 _ForwardIter __next = __first; 02008 for (++__next; __next != __last; __first = __next, ++__next) { 02009 if (__comp(*__next, *__first)) { 02010 _STLP_VERBOSE_ASSERT(!__comp(*__first, *__next), _StlMsg_INVALID_STRICT_WEAK_PREDICATE) 02011 return false; 02012 } 02013 } 02014 02015 return true; 02016 } 02017 02018 _STLP_MOVE_TO_STD_NAMESPACE 02019 #endif /* _STLP_NO_EXTENSIONS */ 02020 02021 _STLP_END_NAMESPACE 02022 02023 #undef __stl_threshold 02024 02025 #endif /* _STLP_ALGO_C */ 02026 // Local Variables: 02027 // mode:C++ 02028 // End:
Generated on Sun May 27 2012 04:28:48 for ReactOS by
1.7.6.1
