1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/tools/stlport/stl/_algo.c Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -0,0 +1,2016 @@
1.4 +/*
1.5 + *
1.6 + * Copyright (c) 1994
1.7 + * Hewlett-Packard Company
1.8 + *
1.9 + * Copyright (c) 1996,1997
1.10 + * Silicon Graphics Computer Systems, Inc.
1.11 + *
1.12 + * Copyright (c) 1997
1.13 + * Moscow Center for SPARC Technology
1.14 + *
1.15 + * Copyright (c) 1999
1.16 + * Boris Fomitchev
1.17 + *
1.18 + * This material is provided "as is", with absolutely no warranty expressed
1.19 + * or implied. Any use is at your own risk.
1.20 + *
1.21 + * Permission to use or copy this software for any purpose is hereby granted
1.22 + * without fee, provided the above notices are retained on all copies.
1.23 + * Permission to modify the code and to distribute modified code is granted,
1.24 + * provided the above notices are retained, and a notice that the code was
1.25 + * modified is included with the above copyright notice.
1.26 + *
1.27 + */
1.28 +
1.29 +#ifndef _STLP_ALGO_C
1.30 +#define _STLP_ALGO_C
1.31 +
1.32 +#if !defined (_STLP_INTERNAL_ALGO_H)
1.33 +# include <stl/_algo.h>
1.34 +#endif
1.35 +
1.36 +#ifndef _STLP_INTERNAL_TEMPBUF_H
1.37 +# include <stl/_tempbuf.h>
1.38 +#endif
1.39 +
1.40 +_STLP_BEGIN_NAMESPACE
1.41 +
1.42 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.43 +
1.44 +template <class _BidirectionalIter, class _Distance, class _Compare>
1.45 +void __merge_without_buffer(_BidirectionalIter __first,
1.46 + _BidirectionalIter __middle,
1.47 + _BidirectionalIter __last,
1.48 + _Distance __len1, _Distance __len2,
1.49 + _Compare __comp);
1.50 +
1.51 +
1.52 +template <class _BidirectionalIter1, class _BidirectionalIter2,
1.53 + class _BidirectionalIter3, class _Compare>
1.54 +_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
1.55 + _BidirectionalIter1 __last1,
1.56 + _BidirectionalIter2 __first2,
1.57 + _BidirectionalIter2 __last2,
1.58 + _BidirectionalIter3 __result,
1.59 + _Compare __comp);
1.60 +
1.61 +template <class _Tp>
1.62 +#if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
1.63 +inline
1.64 +#endif
1.65 +const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
1.66 + if (__a < __b)
1.67 + if (__b < __c)
1.68 + return __b;
1.69 + else if (__a < __c)
1.70 + return __c;
1.71 + else
1.72 + return __a;
1.73 + else if (__a < __c)
1.74 + return __a;
1.75 + else if (__b < __c)
1.76 + return __c;
1.77 + else
1.78 + return __b;
1.79 +}
1.80 +
1.81 +template <class _Tp, class _Compare>
1.82 +#if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
1.83 +inline
1.84 +#endif
1.85 +const _Tp&
1.86 +__median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
1.87 + if (__comp(__a, __b)) {
1.88 + _STLP_VERBOSE_ASSERT(!__comp(__b, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.89 + if (__comp(__b, __c)) {
1.90 + _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.91 + return __b;
1.92 + }
1.93 + else if (__comp(__a, __c)) {
1.94 + _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.95 + return __c;
1.96 + }
1.97 + else
1.98 + return __a;
1.99 + }
1.100 + else if (__comp(__a, __c)) {
1.101 + _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.102 + return __a;
1.103 + }
1.104 + else if (__comp(__b, __c)) {
1.105 + _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.106 + return __c;
1.107 + }
1.108 + else
1.109 + return __b;
1.110 +}
1.111 +
1.112 +_STLP_MOVE_TO_STD_NAMESPACE
1.113 +
1.114 +template <class _ForwardIter1, class _ForwardIter2>
1.115 +_ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
1.116 + _ForwardIter2 __first2, _ForwardIter2 __last2) {
1.117 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1.118 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1.119 + // Test for empty ranges
1.120 + if (__first1 == __last1 || __first2 == __last2)
1.121 + return __first1;
1.122 +
1.123 + // Test for a pattern of length 1.
1.124 + _ForwardIter2 __tmp(__first2);
1.125 + ++__tmp;
1.126 + if (__tmp == __last2)
1.127 + return find(__first1, __last1, *__first2);
1.128 +
1.129 + // General case.
1.130 + _ForwardIter2 __p1 = __first2;
1.131 + ++__p1;
1.132 +
1.133 + _ForwardIter1 __current;// = __first1;
1.134 +
1.135 + while (__first1 != __last1) {
1.136 + __first1 = find(__first1, __last1, *__first2);
1.137 + if (__first1 == __last1)
1.138 + return __last1;
1.139 +
1.140 + _ForwardIter2 __p = __p1;
1.141 + __current = __first1;
1.142 + if (++__current == __last1)
1.143 + return __last1;
1.144 +
1.145 + while (*__current == *__p) {
1.146 + if (++__p == __last2)
1.147 + return __first1;
1.148 + if (++__current == __last1)
1.149 + return __last1;
1.150 + }
1.151 +
1.152 + ++__first1;
1.153 + }
1.154 + return __first1;
1.155 +}
1.156 +
1.157 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.158 +
1.159 +template <class _RandomAccessIter, class _Integer, class _Tp,
1.160 + class _BinaryPred, class _Distance>
1.161 +_RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
1.162 + _Integer __count, const _Tp& __val, _BinaryPred __pred,
1.163 + _Distance*, const random_access_iterator_tag &)
1.164 +{
1.165 + _Distance __tailSize = __last - __first;
1.166 + const _Distance __pattSize = __count;
1.167 + const _Distance __skipOffset = __pattSize - 1;
1.168 + _RandomAccessIter __backTrack;
1.169 + _Distance __remainder, __prevRemainder;
1.170 +
1.171 + for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) { // the main loop...
1.172 + //__lookAhead here is always pointing to the last element of next possible match.
1.173 + __tailSize -= __pattSize;
1.174 +
1.175 + while ( !__pred(*__lookAhead, __val) ) { // the skip loop...
1.176 + if (__tailSize < __pattSize)
1.177 + return __last;
1.178 +
1.179 + __lookAhead += __pattSize;
1.180 + __tailSize -= __pattSize;
1.181 + }
1.182 +
1.183 + if ( __skipOffset == 0 ) {
1.184 + return (__lookAhead - __skipOffset); //Success
1.185 + }
1.186 +
1.187 + __remainder = __skipOffset;
1.188 +
1.189 + for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) {
1.190 + if (--__remainder == 0)
1.191 + return (__lookAhead - __skipOffset); //Success
1.192 + }
1.193 +
1.194 + if (__remainder > __tailSize)
1.195 + return __last; //failure
1.196 +
1.197 + __lookAhead += __remainder;
1.198 + __tailSize -= __remainder;
1.199 +
1.200 + while ( __pred(*__lookAhead, __val) ) {
1.201 + __prevRemainder = __remainder;
1.202 + __backTrack = __lookAhead;
1.203 +
1.204 + do {
1.205 + if (--__remainder == 0)
1.206 + return (__lookAhead - __skipOffset); //Success
1.207 + } while (__pred(*--__backTrack, __val));
1.208 +
1.209 + //adjust remainder for next comparison
1.210 + __remainder += __pattSize - __prevRemainder;
1.211 +
1.212 + if (__remainder > __tailSize)
1.213 + return __last; //failure
1.214 +
1.215 + __lookAhead += __remainder;
1.216 + __tailSize -= __remainder;
1.217 + }
1.218 +
1.219 + //__lookAhead here is always pointing to the element of the last mismatch.
1.220 + }
1.221 +
1.222 + return __last; //failure
1.223 +}
1.224 +
1.225 +template <class _ForwardIter, class _Integer, class _Tp,
1.226 + class _Distance, class _BinaryPred>
1.227 +_ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last,
1.228 + _Integer __count, const _Tp& __val, _BinaryPred __pred,
1.229 + _Distance*, const forward_iterator_tag &) {
1.230 + for (; (__first != __last) && !__pred(*__first, __val); ++__first) {}
1.231 + while (__first != __last) {
1.232 + _Integer __n = __count - 1;
1.233 + _ForwardIter __i = __first;
1.234 + ++__i;
1.235 + while (__i != __last && __n != 0 && __pred(*__i, __val)) {
1.236 + ++__i;
1.237 + --__n;
1.238 + }
1.239 + if (__n == 0)
1.240 + return __first;
1.241 + else if (__i != __last)
1.242 + for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {}
1.243 + else
1.244 + break;
1.245 + }
1.246 + return __last;
1.247 +}
1.248 +
1.249 +_STLP_MOVE_TO_STD_NAMESPACE
1.250 +
1.251 +// search_n. Search for __count consecutive copies of __val.
1.252 +template <class _ForwardIter, class _Integer, class _Tp>
1.253 +_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
1.254 + _Integer __count, const _Tp& __val) {
1.255 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.256 + if (__count <= 0)
1.257 + return __first;
1.258 + if (__count == 1)
1.259 + //We use find when __count == 1 to use potential find overload.
1.260 + return find(__first, __last, __val);
1.261 + return _STLP_PRIV __search_n(__first, __last, __count, __val, equal_to<_Tp>(),
1.262 + _STLP_DISTANCE_TYPE(__first, _ForwardIter),
1.263 + _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.264 +}
1.265 +
1.266 +template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
1.267 +_ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
1.268 + _Integer __count, const _Tp& __val,
1.269 + _BinaryPred __binary_pred) {
1.270 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.271 + if (__count <= 0)
1.272 + return __first;
1.273 + return _STLP_PRIV __search_n(__first, __last, __count, __val, __binary_pred,
1.274 + _STLP_DISTANCE_TYPE(__first, _ForwardIter),
1.275 + _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.276 +}
1.277 +
1.278 +template <class _ForwardIter1, class _ForwardIter2>
1.279 +_ForwardIter1
1.280 +find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
1.281 + _ForwardIter2 __first2, _ForwardIter2 __last2) {
1.282 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1.283 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1.284 + return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
1.285 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.286 + _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
1.287 + _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
1.288 +#else
1.289 + forward_iterator_tag(),
1.290 + forward_iterator_tag(),
1.291 +#endif
1.292 + _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))
1.293 + );
1.294 +}
1.295 +
1.296 +// unique and unique_copy
1.297 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.298 +
1.299 +template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,
1.300 + class _Tp>
1.301 +_STLP_INLINE_LOOP _OutputIterator
1.302 +__unique_copy(_InputIterator __first, _InputIterator __last,
1.303 + _OutputIterator __result,
1.304 + _BinaryPredicate __binary_pred, _Tp*) {
1.305 + _Tp __val = *__first;
1.306 + *__result = __val;
1.307 + while (++__first != __last)
1.308 + if (!__binary_pred(__val, *__first)) {
1.309 + __val = *__first;
1.310 + *++__result = __val;
1.311 + }
1.312 + return ++__result;
1.313 +}
1.314 +
1.315 +template <class _InputIter, class _OutputIter, class _BinaryPredicate>
1.316 +inline _OutputIter
1.317 +__unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
1.318 + _BinaryPredicate __binary_pred, const output_iterator_tag &) {
1.319 + return __unique_copy(__first, __last, __result, __binary_pred, _STLP_VALUE_TYPE(__first, _InputIter));
1.320 +}
1.321 +
1.322 +template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
1.323 +_STLP_INLINE_LOOP _ForwardIter
1.324 +__unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result,
1.325 + _BinaryPredicate __binary_pred, const forward_iterator_tag &) {
1.326 + *__result = *__first;
1.327 + while (++__first != __last)
1.328 + if (!__binary_pred(*__result, *__first)) *++__result = *__first;
1.329 + return ++__result;
1.330 +}
1.331 +
1.332 +#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
1.333 +template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate>
1.334 +inline _BidirectionalIterator
1.335 +__unique_copy(_InputIterator __first, _InputIterator __last,
1.336 + _BidirectionalIterator __result, _BinaryPredicate __binary_pred,
1.337 + const bidirectional_iterator_tag &) {
1.338 + return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
1.339 +}
1.340 +
1.341 +template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate>
1.342 +inline _RandomAccessIterator
1.343 +__unique_copy(_InputIterator __first, _InputIterator __last,
1.344 + _RandomAccessIterator __result, _BinaryPredicate __binary_pred,
1.345 + const random_access_iterator_tag &) {
1.346 + return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
1.347 +}
1.348 +#endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */
1.349 +
1.350 +_STLP_MOVE_TO_STD_NAMESPACE
1.351 +
1.352 +template <class _InputIter, class _OutputIter>
1.353 +_OutputIter
1.354 +unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
1.355 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.356 + if (__first == __last) return __result;
1.357 + return _STLP_PRIV __unique_copy(__first, __last, __result,
1.358 + _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),
1.359 + _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
1.360 +}
1.361 +
1.362 +template <class _InputIter, class _OutputIter, class _BinaryPredicate>
1.363 +_OutputIter
1.364 +unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
1.365 + _BinaryPredicate __binary_pred) {
1.366 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.367 + if (__first == __last) return __result;
1.368 + return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred,
1.369 + _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
1.370 +}
1.371 +
1.372 +// rotate and rotate_copy, and their auxiliary functions
1.373 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.374 +
1.375 +template <class _ForwardIter, class _Distance>
1.376 +_ForwardIter __rotate_aux(_ForwardIter __first,
1.377 + _ForwardIter __middle,
1.378 + _ForwardIter __last,
1.379 + _Distance*,
1.380 + const forward_iterator_tag &) {
1.381 + if (__first == __middle)
1.382 + return __last;
1.383 + if (__last == __middle)
1.384 + return __first;
1.385 +
1.386 + _ForwardIter __first2 = __middle;
1.387 + do {
1.388 + swap(*__first++, *__first2++);
1.389 + if (__first == __middle)
1.390 + __middle = __first2;
1.391 + } while (__first2 != __last);
1.392 +
1.393 + _ForwardIter __new_middle = __first;
1.394 +
1.395 + __first2 = __middle;
1.396 +
1.397 + while (__first2 != __last) {
1.398 + swap (*__first++, *__first2++);
1.399 + if (__first == __middle)
1.400 + __middle = __first2;
1.401 + else if (__first2 == __last)
1.402 + __first2 = __middle;
1.403 + }
1.404 +
1.405 + return __new_middle;
1.406 +}
1.407 +
1.408 +template <class _BidirectionalIter, class _Distance>
1.409 +_BidirectionalIter __rotate_aux(_BidirectionalIter __first,
1.410 + _BidirectionalIter __middle,
1.411 + _BidirectionalIter __last,
1.412 + _Distance*,
1.413 + const bidirectional_iterator_tag &) {
1.414 + if (__first == __middle)
1.415 + return __last;
1.416 + if (__last == __middle)
1.417 + return __first;
1.418 +
1.419 + __reverse(__first, __middle, bidirectional_iterator_tag());
1.420 + __reverse(__middle, __last, bidirectional_iterator_tag());
1.421 +
1.422 + while (__first != __middle && __middle != __last)
1.423 + swap (*__first++, *--__last);
1.424 +
1.425 + if (__first == __middle) {
1.426 + __reverse(__middle, __last, bidirectional_iterator_tag());
1.427 + return __last;
1.428 + }
1.429 + else {
1.430 + __reverse(__first, __middle, bidirectional_iterator_tag());
1.431 + return __first;
1.432 + }
1.433 +}
1.434 +
1.435 +template <class _RandomAccessIter, class _Distance, class _Tp>
1.436 +_RandomAccessIter __rotate_aux(_RandomAccessIter __first,
1.437 + _RandomAccessIter __middle,
1.438 + _RandomAccessIter __last,
1.439 + _Distance *, _Tp *) {
1.440 +
1.441 + _Distance __n = __last - __first;
1.442 + _Distance __k = __middle - __first;
1.443 + _Distance __l = __n - __k;
1.444 + _RandomAccessIter __result = __first + (__last - __middle);
1.445 +
1.446 + if (__k == 0) /* __first == middle */
1.447 + return __last;
1.448 +
1.449 + if (__k == __l) {
1.450 + swap_ranges(__first, __middle, __middle);
1.451 + return __result;
1.452 + }
1.453 +
1.454 + _Distance __d = __gcd(__n, __k);
1.455 +
1.456 + for (_Distance __i = 0; __i < __d; __i++) {
1.457 + _Tp __tmp = *__first;
1.458 + _RandomAccessIter __p = __first;
1.459 +
1.460 + if (__k < __l) {
1.461 + for (_Distance __j = 0; __j < __l/__d; __j++) {
1.462 + if (__p > __first + __l) {
1.463 + *__p = *(__p - __l);
1.464 + __p -= __l;
1.465 + }
1.466 +
1.467 + *__p = *(__p + __k);
1.468 + __p += __k;
1.469 + }
1.470 + }
1.471 +
1.472 + else {
1.473 + for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
1.474 + if (__p < __last - __k) {
1.475 + *__p = *(__p + __k);
1.476 + __p += __k;
1.477 + }
1.478 +
1.479 + *__p = * (__p - __l);
1.480 + __p -= __l;
1.481 + }
1.482 + }
1.483 +
1.484 + *__p = __tmp;
1.485 + ++__first;
1.486 + }
1.487 +
1.488 + return __result;
1.489 +}
1.490 +
1.491 +template <class _RandomAccessIter, class _Distance>
1.492 +inline _RandomAccessIter
1.493 +__rotate_aux(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,
1.494 + _Distance * __dis, const random_access_iterator_tag &) {
1.495 + return __rotate_aux(__first, __middle, __last,
1.496 + __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));
1.497 +}
1.498 +
1.499 +template <class _ForwardIter>
1.500 +_ForwardIter
1.501 +__rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
1.502 + _STLP_DEBUG_CHECK(__check_range(__first, __middle))
1.503 + _STLP_DEBUG_CHECK(__check_range(__middle, __last))
1.504 + return __rotate_aux(__first, __middle, __last,
1.505 + _STLP_DISTANCE_TYPE(__first, _ForwardIter),
1.506 + _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.507 +}
1.508 +
1.509 +_STLP_MOVE_TO_STD_NAMESPACE
1.510 +
1.511 +template <class _ForwardIter>
1.512 +void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
1.513 + _STLP_PRIV __rotate(__first, __middle, __last);
1.514 +}
1.515 +
1.516 +// Return a random number in the range [0, __n). This function encapsulates
1.517 +// whether we're using rand (part of the standard C library) or lrand48
1.518 +// (not standard, but a much better choice whenever it's available).
1.519 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.520 +
1.521 +template <class _Distance>
1.522 +inline _Distance __random_number(_Distance __n) {
1.523 +#ifdef _STLP_NO_DRAND48
1.524 + return rand() % __n;
1.525 +#else
1.526 + return lrand48() % __n;
1.527 +#endif
1.528 +}
1.529 +
1.530 +_STLP_MOVE_TO_STD_NAMESPACE
1.531 +
1.532 +template <class _RandomAccessIter>
1.533 +void random_shuffle(_RandomAccessIter __first,
1.534 + _RandomAccessIter __last) {
1.535 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.536 + if (__first == __last) return;
1.537 + for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1.538 + iter_swap(__i, __first + _STLP_PRIV __random_number((__i - __first) + 1));
1.539 +}
1.540 +
1.541 +template <class _RandomAccessIter, class _RandomNumberGenerator>
1.542 +void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
1.543 + _RandomNumberGenerator &__rand) {
1.544 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.545 + if (__first == __last) return;
1.546 + for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1.547 + iter_swap(__i, __first + __rand((__i - __first) + 1));
1.548 +}
1.549 +
1.550 +#if !defined (_STLP_NO_EXTENSIONS)
1.551 +// random_sample and random_sample_n (extensions, not part of the standard).
1.552 +template <class _ForwardIter, class _OutputIter, class _Distance>
1.553 +_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
1.554 + _OutputIter __out_ite, const _Distance __n) {
1.555 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.556 + _Distance __remaining = distance(__first, __last);
1.557 + _Distance __m = (min) (__n, __remaining);
1.558 +
1.559 + while (__m > 0) {
1.560 + if (_STLP_PRIV __random_number(__remaining) < __m) {
1.561 + *__out_ite = *__first;
1.562 + ++__out_ite;
1.563 + --__m;
1.564 + }
1.565 +
1.566 + --__remaining;
1.567 + ++__first;
1.568 + }
1.569 + return __out_ite;
1.570 +}
1.571 +
1.572 +
1.573 +template <class _ForwardIter, class _OutputIter, class _Distance,
1.574 + class _RandomNumberGenerator>
1.575 +_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
1.576 + _OutputIter __out_ite, const _Distance __n,
1.577 + _RandomNumberGenerator& __rand) {
1.578 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.579 + _Distance __remaining = distance(__first, __last);
1.580 + _Distance __m = (min) (__n, __remaining);
1.581 +
1.582 + while (__m > 0) {
1.583 + if (__rand(__remaining) < __m) {
1.584 + *__out_ite = *__first;
1.585 + ++__out_ite;
1.586 + --__m;
1.587 + }
1.588 +
1.589 + --__remaining;
1.590 + ++__first;
1.591 + }
1.592 + return __out_ite;
1.593 +}
1.594 +
1.595 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.596 +
1.597 +template <class _InputIter, class _RandomAccessIter, class _Distance>
1.598 +_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
1.599 + _RandomAccessIter __out_ite,
1.600 + const _Distance __n) {
1.601 + _Distance __m = 0;
1.602 + _Distance __t = __n;
1.603 + for ( ; __first != __last && __m < __n; ++__m, ++__first)
1.604 + __out_ite[__m] = *__first;
1.605 +
1.606 + while (__first != __last) {
1.607 + ++__t;
1.608 + _Distance __M = __random_number(__t);
1.609 + if (__M < __n)
1.610 + __out_ite[__M] = *__first;
1.611 + ++__first;
1.612 + }
1.613 +
1.614 + return __out_ite + __m;
1.615 +}
1.616 +
1.617 +template <class _InputIter, class _RandomAccessIter,
1.618 + class _RandomNumberGenerator, class _Distance>
1.619 +_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
1.620 + _RandomAccessIter __out_ite,
1.621 + _RandomNumberGenerator& __rand,
1.622 + const _Distance __n) {
1.623 + _Distance __m = 0;
1.624 + _Distance __t = __n;
1.625 + for ( ; __first != __last && __m < __n; ++__m, ++__first)
1.626 + __out_ite[__m] = *__first;
1.627 +
1.628 + while (__first != __last) {
1.629 + ++__t;
1.630 + _Distance __M = __rand(__t);
1.631 + if (__M < __n)
1.632 + __out_ite[__M] = *__first;
1.633 + ++__first;
1.634 + }
1.635 +
1.636 + return __out_ite + __m;
1.637 +}
1.638 +
1.639 +_STLP_MOVE_TO_STD_NAMESPACE
1.640 +
1.641 +template <class _InputIter, class _RandomAccessIter>
1.642 +_RandomAccessIter
1.643 +random_sample(_InputIter __first, _InputIter __last,
1.644 + _RandomAccessIter __out_first, _RandomAccessIter __out_last) {
1.645 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.646 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
1.647 + return _STLP_PRIV __random_sample(__first, __last,
1.648 + __out_first, __out_last - __out_first);
1.649 +}
1.650 +
1.651 +template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>
1.652 +_RandomAccessIter
1.653 +random_sample(_InputIter __first, _InputIter __last,
1.654 + _RandomAccessIter __out_first, _RandomAccessIter __out_last,
1.655 + _RandomNumberGenerator& __rand) {
1.656 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.657 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
1.658 + return _STLP_PRIV __random_sample(__first, __last,
1.659 + __out_first, __rand,
1.660 + __out_last - __out_first);
1.661 +}
1.662 +
1.663 +#endif /* _STLP_NO_EXTENSIONS */
1.664 +
1.665 +// partition, stable_partition, and their auxiliary functions
1.666 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.667 +
1.668 +template <class _ForwardIter, class _Predicate>
1.669 +_STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,
1.670 + _ForwardIter __last,
1.671 + _Predicate __pred,
1.672 + const forward_iterator_tag &) {
1.673 + if (__first == __last) return __first;
1.674 +
1.675 + while (__pred(*__first))
1.676 + if (++__first == __last) return __first;
1.677 +
1.678 + _ForwardIter __next = __first;
1.679 +
1.680 + while (++__next != __last) {
1.681 + if (__pred(*__next)) {
1.682 + swap(*__first, *__next);
1.683 + ++__first;
1.684 + }
1.685 + }
1.686 + return __first;
1.687 +}
1.688 +
1.689 +template <class _BidirectionalIter, class _Predicate>
1.690 +_STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,
1.691 + _BidirectionalIter __last,
1.692 + _Predicate __pred,
1.693 + const bidirectional_iterator_tag &) {
1.694 + for (;;) {
1.695 + for (;;) {
1.696 + if (__first == __last)
1.697 + return __first;
1.698 + else if (__pred(*__first))
1.699 + ++__first;
1.700 + else
1.701 + break;
1.702 + }
1.703 + --__last;
1.704 + for (;;) {
1.705 + if (__first == __last)
1.706 + return __first;
1.707 + else if (!__pred(*__last))
1.708 + --__last;
1.709 + else
1.710 + break;
1.711 + }
1.712 + iter_swap(__first, __last);
1.713 + ++__first;
1.714 + }
1.715 +}
1.716 +
1.717 +#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
1.718 +template <class _BidirectionalIter, class _Predicate>
1.719 +inline
1.720 +_BidirectionalIter __partition(_BidirectionalIter __first,
1.721 + _BidirectionalIter __last,
1.722 + _Predicate __pred,
1.723 + const random_access_iterator_tag &) {
1.724 + return __partition(__first, __last, __pred, bidirectional_iterator_tag());
1.725 +}
1.726 +#endif
1.727 +
1.728 +_STLP_MOVE_TO_STD_NAMESPACE
1.729 +
1.730 +template <class _ForwardIter, class _Predicate>
1.731 +_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
1.732 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.733 + return _STLP_PRIV __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.734 +}
1.735 +
1.736 +
1.737 +/* __pred_of_first: false if we know that __pred(*__first) is false,
1.738 + * true when we don't know the result of __pred(*__first).
1.739 + * __not_pred_of_before_last: true if we know that __pred(*--__last) is true,
1.740 + * false when we don't know the result of __pred(*--__last).
1.741 + */
1.742 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.743 +
1.744 +template <class _ForwardIter, class _Predicate, class _Distance>
1.745 +_ForwardIter __inplace_stable_partition(_ForwardIter __first,
1.746 + _ForwardIter __last,
1.747 + _Predicate __pred, _Distance __len,
1.748 + bool __pred_of_first, bool __pred_of_before_last) {
1.749 + if (__len == 1)
1.750 + return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first;
1.751 + _ForwardIter __middle = __first;
1.752 + _Distance __half_len = __len / 2;
1.753 + advance(__middle, __half_len);
1.754 + return __rotate(__inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false),
1.755 + __middle,
1.756 + __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last));
1.757 +}
1.758 +
1.759 +template <class _ForwardIter, class _Pointer, class _Predicate,
1.760 + class _Distance>
1.761 +_ForwardIter __stable_partition_adaptive(_ForwardIter __first,
1.762 + _ForwardIter __last,
1.763 + _Predicate __pred, _Distance __len,
1.764 + _Pointer __buffer, _Distance __buffer_size,
1.765 + bool __pred_of_first, bool __pred_of_before_last) {
1.766 + if (__len <= __buffer_size) {
1.767 + _ForwardIter __result1 = __first;
1.768 + _Pointer __result2 = __buffer;
1.769 + if ((__first != __last) && (!__pred_of_first || __pred(*__first))) {
1.770 + *__result2 = *__first;
1.771 + ++__result2; ++__first; --__len;
1.772 + }
1.773 + for (; __first != __last ; ++__first, --__len) {
1.774 + if (((__len == 1) && (__pred_of_before_last || __pred(*__first))) ||
1.775 + ((__len != 1) && __pred(*__first))){
1.776 + *__result1 = *__first;
1.777 + ++__result1;
1.778 + }
1.779 + else {
1.780 + *__result2 = *__first;
1.781 + ++__result2;
1.782 + }
1.783 + }
1.784 + copy(__buffer, __result2, __result1);
1.785 + return __result1;
1.786 + }
1.787 + else {
1.788 + _ForwardIter __middle = __first;
1.789 + _Distance __half_len = __len / 2;
1.790 + advance(__middle, __half_len);
1.791 + return __rotate(__stable_partition_adaptive(
1.792 + __first, __middle, __pred,
1.793 + __half_len, __buffer, __buffer_size,
1.794 + __pred_of_first, false),
1.795 + __middle,
1.796 + __stable_partition_adaptive(
1.797 + __middle, __last, __pred,
1.798 + __len - __half_len, __buffer, __buffer_size,
1.799 + true, __pred_of_before_last));
1.800 + }
1.801 +}
1.802 +
1.803 +template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
1.804 +inline _ForwardIter
1.805 +__stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,
1.806 + _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last = false) {
1.807 + _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
1.808 + _STLP_MPWFIX_TRY //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
1.809 + return (__buf.size() > 0) ?
1.810 + __stable_partition_adaptive(__first, __last, __pred,
1.811 + _Distance(__buf.requested_size()),
1.812 + __buf.begin(), __buf.size(),
1.813 + false, __pred_of_before_last) :
1.814 + __inplace_stable_partition(__first, __last, __pred,
1.815 + _Distance(__buf.requested_size()),
1.816 + false, __pred_of_before_last);
1.817 + _STLP_MPWFIX_CATCH //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
1.818 +}
1.819 +
1.820 +template <class _ForwardIter, class _Predicate>
1.821 +_ForwardIter
1.822 +__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred,
1.823 + const forward_iterator_tag &) {
1.824 + return __stable_partition_aux_aux(__first, __last, __pred,
1.825 + _STLP_VALUE_TYPE(__first, _ForwardIter),
1.826 + _STLP_DISTANCE_TYPE(__first, _ForwardIter));
1.827 +}
1.828 +
1.829 +template <class _BidirectIter, class _Predicate>
1.830 +_BidirectIter
1.831 +__stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
1.832 + const bidirectional_iterator_tag &) {
1.833 + for (--__last;;) {
1.834 + if (__first == __last)
1.835 + return __first;
1.836 + else if (!__pred(*__last))
1.837 + --__last;
1.838 + else
1.839 + break;
1.840 + }
1.841 + ++__last;
1.842 + //Here we know that __pred(*--__last) is true
1.843 + return __stable_partition_aux_aux(__first, __last, __pred,
1.844 + _STLP_VALUE_TYPE(__first, _BidirectIter),
1.845 + _STLP_DISTANCE_TYPE(__first, _BidirectIter), true);
1.846 +}
1.847 +
1.848 +#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
1.849 +template <class _BidirectIter, class _Predicate>
1.850 +_BidirectIter
1.851 +__stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
1.852 + const random_access_iterator_tag &) {
1.853 + return __stable_partition_aux(__first, __last, __pred, bidirectional_iterator_tag());
1.854 +}
1.855 +#endif
1.856 +
1.857 +_STLP_MOVE_TO_STD_NAMESPACE
1.858 +
1.859 +template <class _ForwardIter, class _Predicate>
1.860 +_ForwardIter
1.861 +stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
1.862 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.863 + for (;;) {
1.864 + if (__first == __last)
1.865 + return __first;
1.866 + else if (__pred(*__first))
1.867 + ++__first;
1.868 + else
1.869 + break;
1.870 + }
1.871 + return _STLP_PRIV __stable_partition_aux(__first, __last, __pred,
1.872 + _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.873 +}
1.874 +
1.875 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.876 +
1.877 +template <class _RandomAccessIter, class _Tp, class _Compare>
1.878 +_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
1.879 + _RandomAccessIter __last,
1.880 + _Tp __pivot, _Compare __comp) {
1.881 + for (;;) {
1.882 + while (__comp(*__first, __pivot)) {
1.883 + _STLP_VERBOSE_ASSERT(!__comp(__pivot, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.884 + ++__first;
1.885 + }
1.886 + --__last;
1.887 + while (__comp(__pivot, *__last)) {
1.888 + _STLP_VERBOSE_ASSERT(!__comp(*__last, __pivot), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.889 + --__last;
1.890 + }
1.891 + if (!(__first < __last))
1.892 + return __first;
1.893 + iter_swap(__first, __last);
1.894 + ++__first;
1.895 + }
1.896 +}
1.897 +
1.898 +// sort() and its auxiliary functions.
1.899 +#define __stl_threshold 16
1.900 +
1.901 +template <class _RandomAccessIter, class _Tp, class _Compare>
1.902 +void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
1.903 + _Compare __comp) {
1.904 + _RandomAccessIter __next = __last;
1.905 + --__next;
1.906 + while (__comp(__val, *__next)) {
1.907 + _STLP_VERBOSE_ASSERT(!__comp(*__next, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.908 + *__last = *__next;
1.909 + __last = __next;
1.910 + --__next;
1.911 + }
1.912 + *__last = __val;
1.913 +}
1.914 +
1.915 +template <class _RandomAccessIter, class _Tp, class _Compare>
1.916 +inline void __linear_insert(_RandomAccessIter __first,
1.917 + _RandomAccessIter __last, _Tp __val, _Compare __comp) {
1.918 + //*TY 12/26/1998 - added __val as a paramter
1.919 + // _Tp __val = *__last; //*TY 12/26/1998 - __val supplied by caller
1.920 + if (__comp(__val, *__first)) {
1.921 + _STLP_VERBOSE_ASSERT(!__comp(*__first, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.922 + copy_backward(__first, __last, __last + 1);
1.923 + *__first = __val;
1.924 + }
1.925 + else
1.926 + __unguarded_linear_insert(__last, __val, __comp);
1.927 +}
1.928 +
1.929 +template <class _RandomAccessIter, class _Tp, class _Compare>
1.930 +void __insertion_sort(_RandomAccessIter __first,
1.931 + _RandomAccessIter __last,
1.932 + _Tp *, _Compare __comp) {
1.933 + if (__first == __last) return;
1.934 + for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1.935 + __linear_insert<_RandomAccessIter, _Tp, _Compare>(__first, __i, *__i, __comp); //*TY 12/26/1998 - supply *__i as __val
1.936 +}
1.937 +
1.938 +template <class _RandomAccessIter, class _Tp, class _Compare>
1.939 +void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
1.940 + _RandomAccessIter __last,
1.941 + _Tp*, _Compare __comp) {
1.942 + for (_RandomAccessIter __i = __first; __i != __last; ++__i)
1.943 + __unguarded_linear_insert<_RandomAccessIter, _Tp, _Compare>(__i, *__i, __comp);
1.944 +}
1.945 +
1.946 +template <class _RandomAccessIter, class _Compare>
1.947 +inline void __unguarded_insertion_sort(_RandomAccessIter __first,
1.948 + _RandomAccessIter __last,
1.949 + _Compare __comp) {
1.950 + __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
1.951 +}
1.952 +
1.953 +template <class _RandomAccessIter, class _Compare>
1.954 +void __final_insertion_sort(_RandomAccessIter __first,
1.955 + _RandomAccessIter __last, _Compare __comp) {
1.956 + if (__last - __first > __stl_threshold) {
1.957 + __insertion_sort(__first, __first + __stl_threshold, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1.958 + __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
1.959 + }
1.960 + else
1.961 + __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1.962 +}
1.963 +
1.964 +template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
1.965 +void __introsort_loop(_RandomAccessIter __first,
1.966 + _RandomAccessIter __last, _Tp*,
1.967 + _Size __depth_limit, _Compare __comp) {
1.968 + while (__last - __first > __stl_threshold) {
1.969 + if (__depth_limit == 0) {
1.970 + partial_sort(__first, __last, __last, __comp);
1.971 + return;
1.972 + }
1.973 + --__depth_limit;
1.974 + _RandomAccessIter __cut =
1.975 + __unguarded_partition(__first, __last,
1.976 + _Tp(__median(*__first,
1.977 + *(__first + (__last - __first)/2),
1.978 + *(__last - 1), __comp)),
1.979 + __comp);
1.980 + __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
1.981 + __last = __cut;
1.982 + }
1.983 +}
1.984 +
1.985 +_STLP_MOVE_TO_STD_NAMESPACE
1.986 +
1.987 +template <class _RandomAccessIter>
1.988 +void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
1.989 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.990 + if (__first != __last) {
1.991 + _STLP_PRIV __introsort_loop(__first, __last,
1.992 + _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.993 + _STLP_PRIV __lg(__last - __first) * 2,
1.994 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.995 + _STLP_PRIV __final_insertion_sort(__first, __last,
1.996 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.997 + }
1.998 +}
1.999 +
1.1000 +template <class _RandomAccessIter, class _Compare>
1.1001 +void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) {
1.1002 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1003 + if (__first != __last) {
1.1004 + _STLP_PRIV __introsort_loop(__first, __last,
1.1005 + _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1006 + _STLP_PRIV __lg(__last - __first) * 2, __comp);
1.1007 + _STLP_PRIV __final_insertion_sort(__first, __last, __comp);
1.1008 + }
1.1009 +}
1.1010 +
1.1011 +// stable_sort() and its auxiliary functions.
1.1012 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1013 +
1.1014 +template <class _RandomAccessIter, class _Compare>
1.1015 +void __inplace_stable_sort(_RandomAccessIter __first,
1.1016 + _RandomAccessIter __last, _Compare __comp) {
1.1017 + if (__last - __first < 15) {
1.1018 + __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1.1019 + return;
1.1020 + }
1.1021 + _RandomAccessIter __middle = __first + (__last - __first) / 2;
1.1022 + __inplace_stable_sort(__first, __middle, __comp);
1.1023 + __inplace_stable_sort(__middle, __last, __comp);
1.1024 + __merge_without_buffer(__first, __middle, __last,
1.1025 + __middle - __first,
1.1026 + __last - __middle,
1.1027 + __comp);
1.1028 +}
1.1029 +
1.1030 +template <class _RandomAccessIter1, class _RandomAccessIter2,
1.1031 + class _Distance, class _Compare>
1.1032 +void __merge_sort_loop(_RandomAccessIter1 __first,
1.1033 + _RandomAccessIter1 __last,
1.1034 + _RandomAccessIter2 __result, _Distance __step_size,
1.1035 + _Compare __comp) {
1.1036 + _Distance __two_step = 2 * __step_size;
1.1037 +
1.1038 + while (__last - __first >= __two_step) {
1.1039 + __result = merge(__first, __first + __step_size,
1.1040 + __first + __step_size, __first + __two_step,
1.1041 + __result,
1.1042 + __comp);
1.1043 + __first += __two_step;
1.1044 + }
1.1045 + __step_size = (min) (_Distance(__last - __first), __step_size);
1.1046 +
1.1047 + merge(__first, __first + __step_size,
1.1048 + __first + __step_size, __last,
1.1049 + __result,
1.1050 + __comp);
1.1051 +}
1.1052 +
1.1053 +const int __stl_chunk_size = 7;
1.1054 +
1.1055 +template <class _RandomAccessIter, class _Distance, class _Compare>
1.1056 +void __chunk_insertion_sort(_RandomAccessIter __first,
1.1057 + _RandomAccessIter __last,
1.1058 + _Distance __chunk_size, _Compare __comp) {
1.1059 + while (__last - __first >= __chunk_size) {
1.1060 + __insertion_sort(__first, __first + __chunk_size,
1.1061 + _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1.1062 + __first += __chunk_size;
1.1063 + }
1.1064 + __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1.1065 +}
1.1066 +
1.1067 +template <class _RandomAccessIter, class _Pointer, class _Distance,
1.1068 + class _Compare>
1.1069 +void __merge_sort_with_buffer(_RandomAccessIter __first,
1.1070 + _RandomAccessIter __last, _Pointer __buffer,
1.1071 + _Distance*, _Compare __comp) {
1.1072 + _Distance __len = __last - __first;
1.1073 + _Pointer __buffer_last = __buffer + __len;
1.1074 +
1.1075 + _Distance __step_size = __stl_chunk_size;
1.1076 + __chunk_insertion_sort(__first, __last, __step_size, __comp);
1.1077 +
1.1078 + while (__step_size < __len) {
1.1079 + __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
1.1080 + __step_size *= 2;
1.1081 + __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
1.1082 + __step_size *= 2;
1.1083 + }
1.1084 +}
1.1085 +
1.1086 +template <class _BidirectionalIter1, class _BidirectionalIter2,
1.1087 + class _Distance>
1.1088 +_BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
1.1089 + _BidirectionalIter1 __middle,
1.1090 + _BidirectionalIter1 __last,
1.1091 + _Distance __len1, _Distance __len2,
1.1092 + _BidirectionalIter2 __buffer,
1.1093 + _Distance __buffer_size) {
1.1094 + if (__len1 > __len2 && __len2 <= __buffer_size) {
1.1095 + _BidirectionalIter2 __buffer_end = copy(__middle, __last, __buffer);
1.1096 + copy_backward(__first, __middle, __last);
1.1097 + return copy(__buffer, __buffer_end, __first);
1.1098 + }
1.1099 + else if (__len1 <= __buffer_size) {
1.1100 + _BidirectionalIter2 __buffer_end = copy(__first, __middle, __buffer);
1.1101 + copy(__middle, __last, __first);
1.1102 + return copy_backward(__buffer, __buffer_end, __last);
1.1103 + }
1.1104 + else
1.1105 + return __rotate(__first, __middle, __last);
1.1106 +}
1.1107 +
1.1108 +template <class _BidirectionalIter, class _Distance, class _Pointer,
1.1109 + class _Compare>
1.1110 +void __merge_adaptive(_BidirectionalIter __first,
1.1111 + _BidirectionalIter __middle,
1.1112 + _BidirectionalIter __last,
1.1113 + _Distance __len1, _Distance __len2,
1.1114 + _Pointer __buffer, _Distance __buffer_size,
1.1115 + _Compare __comp) {
1.1116 + if (__len1 <= __len2 && __len1 <= __buffer_size) {
1.1117 + _Pointer __buffer_end = copy(__first, __middle, __buffer);
1.1118 + merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
1.1119 + }
1.1120 + else if (__len2 <= __buffer_size) {
1.1121 + _Pointer __buffer_end = copy(__middle, __last, __buffer);
1.1122 + __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
1.1123 + __comp);
1.1124 + }
1.1125 + else {
1.1126 + _BidirectionalIter __first_cut = __first;
1.1127 + _BidirectionalIter __second_cut = __middle;
1.1128 + _Distance __len11 = 0;
1.1129 + _Distance __len22 = 0;
1.1130 + if (__len1 > __len2) {
1.1131 + __len11 = __len1 / 2;
1.1132 + advance(__first_cut, __len11);
1.1133 + __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
1.1134 + __len22 += distance(__middle, __second_cut);
1.1135 + }
1.1136 + else {
1.1137 + __len22 = __len2 / 2;
1.1138 + advance(__second_cut, __len22);
1.1139 + __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
1.1140 + __len11 += distance(__first, __first_cut);
1.1141 + }
1.1142 + _BidirectionalIter __new_middle =
1.1143 + __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
1.1144 + __len22, __buffer, __buffer_size);
1.1145 + __merge_adaptive(__first, __first_cut, __new_middle, __len11,
1.1146 + __len22, __buffer, __buffer_size, __comp);
1.1147 + __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
1.1148 + __len2 - __len22, __buffer, __buffer_size, __comp);
1.1149 + }
1.1150 +}
1.1151 +
1.1152 +template <class _RandomAccessIter, class _Pointer, class _Distance,
1.1153 + class _Compare>
1.1154 +void __stable_sort_adaptive(_RandomAccessIter __first,
1.1155 + _RandomAccessIter __last, _Pointer __buffer,
1.1156 + _Distance __buffer_size, _Compare __comp) {
1.1157 + _Distance __len = (__last - __first + 1) / 2;
1.1158 + _RandomAccessIter __middle = __first + __len;
1.1159 + if (__len > __buffer_size) {
1.1160 + __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
1.1161 + __comp);
1.1162 + __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
1.1163 + __comp);
1.1164 + }
1.1165 + else {
1.1166 + __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
1.1167 + __comp);
1.1168 + __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
1.1169 + __comp);
1.1170 + }
1.1171 + __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
1.1172 + _Distance(__last - __middle), __buffer, __buffer_size,
1.1173 + __comp);
1.1174 +}
1.1175 +
1.1176 +template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
1.1177 +void __stable_sort_aux(_RandomAccessIter __first,
1.1178 + _RandomAccessIter __last, _Tp*, _Distance*,
1.1179 + _Compare __comp) {
1.1180 + _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
1.1181 + if (buf.begin() == 0)
1.1182 + __inplace_stable_sort(__first, __last, __comp);
1.1183 + else
1.1184 + __stable_sort_adaptive(__first, __last, buf.begin(),
1.1185 + _Distance(buf.size()),
1.1186 + __comp);
1.1187 +}
1.1188 +
1.1189 +_STLP_MOVE_TO_STD_NAMESPACE
1.1190 +
1.1191 +template <class _RandomAccessIter>
1.1192 +void stable_sort(_RandomAccessIter __first,
1.1193 + _RandomAccessIter __last) {
1.1194 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1195 + _STLP_PRIV __stable_sort_aux(__first, __last,
1.1196 + _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1197 + _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
1.1198 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.1199 +}
1.1200 +
1.1201 +template <class _RandomAccessIter, class _Compare>
1.1202 +void stable_sort(_RandomAccessIter __first,
1.1203 + _RandomAccessIter __last, _Compare __comp) {
1.1204 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1205 + _STLP_PRIV __stable_sort_aux(__first, __last,
1.1206 + _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1207 + _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
1.1208 + __comp);
1.1209 +}
1.1210 +
1.1211 +// partial_sort, partial_sort_copy, and auxiliary functions.
1.1212 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1213 +
1.1214 +template <class _RandomAccessIter, class _Tp, class _Compare>
1.1215 +void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
1.1216 + _RandomAccessIter __last, _Tp*, _Compare __comp) {
1.1217 + make_heap(__first, __middle, __comp);
1.1218 + for (_RandomAccessIter __i = __middle; __i < __last; ++__i) {
1.1219 + if (__comp(*__i, *__first)) {
1.1220 + _STLP_VERBOSE_ASSERT(!__comp(*__first, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1221 + __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
1.1222 + _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));
1.1223 + }
1.1224 + }
1.1225 + sort_heap(__first, __middle, __comp);
1.1226 +}
1.1227 +
1.1228 +_STLP_MOVE_TO_STD_NAMESPACE
1.1229 +
1.1230 +template <class _RandomAccessIter>
1.1231 +void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
1.1232 + _RandomAccessIter __last) {
1.1233 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
1.1234 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
1.1235 + _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1236 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.1237 +}
1.1238 +
1.1239 +template <class _RandomAccessIter, class _Compare>
1.1240 +void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
1.1241 + _RandomAccessIter __last, _Compare __comp) {
1.1242 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
1.1243 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
1.1244 + _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
1.1245 +}
1.1246 +
1.1247 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1248 +
1.1249 +template <class _InputIter, class _RandomAccessIter, class _Compare,
1.1250 + class _Distance, class _Tp>
1.1251 +_RandomAccessIter __partial_sort_copy(_InputIter __first,
1.1252 + _InputIter __last,
1.1253 + _RandomAccessIter __result_first,
1.1254 + _RandomAccessIter __result_last,
1.1255 + _Compare __comp, _Distance*, _Tp*) {
1.1256 + if (__result_first == __result_last) return __result_last;
1.1257 + _RandomAccessIter __result_real_last = __result_first;
1.1258 + while(__first != __last && __result_real_last != __result_last) {
1.1259 + *__result_real_last = *__first;
1.1260 + ++__result_real_last;
1.1261 + ++__first;
1.1262 + }
1.1263 + make_heap(__result_first, __result_real_last, __comp);
1.1264 + while (__first != __last) {
1.1265 + if (__comp(*__first, *__result_first)) {
1.1266 + _STLP_VERBOSE_ASSERT(!__comp(*__result_first, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1267 + __adjust_heap(__result_first, _Distance(0),
1.1268 + _Distance(__result_real_last - __result_first),
1.1269 + _Tp(*__first),
1.1270 + __comp);
1.1271 + }
1.1272 + ++__first;
1.1273 + }
1.1274 + sort_heap(__result_first, __result_real_last, __comp);
1.1275 + return __result_real_last;
1.1276 +}
1.1277 +
1.1278 +_STLP_MOVE_TO_STD_NAMESPACE
1.1279 +
1.1280 +template <class _InputIter, class _RandomAccessIter>
1.1281 +_RandomAccessIter
1.1282 +partial_sort_copy(_InputIter __first, _InputIter __last,
1.1283 + _RandomAccessIter __result_first, _RandomAccessIter __result_last) {
1.1284 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1285 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
1.1286 + return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
1.1287 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _InputIter)),
1.1288 + _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
1.1289 + _STLP_VALUE_TYPE(__first, _InputIter));
1.1290 +}
1.1291 +
1.1292 +template <class _InputIter, class _RandomAccessIter, class _Compare>
1.1293 +_RandomAccessIter
1.1294 +partial_sort_copy(_InputIter __first, _InputIter __last,
1.1295 + _RandomAccessIter __result_first,
1.1296 + _RandomAccessIter __result_last, _Compare __comp) {
1.1297 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1298 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
1.1299 + return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
1.1300 + __comp,
1.1301 + _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
1.1302 + _STLP_VALUE_TYPE(__first, _InputIter));
1.1303 +}
1.1304 +
1.1305 +// nth_element() and its auxiliary functions.
1.1306 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1307 +
1.1308 +template <class _RandomAccessIter, class _Tp, class _Compare>
1.1309 +void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1.1310 + _RandomAccessIter __last, _Tp*, _Compare __comp) {
1.1311 + while (__last - __first > 3) {
1.1312 + _RandomAccessIter __cut =
1.1313 + __unguarded_partition(__first, __last,
1.1314 + _Tp(__median(*__first,
1.1315 + *(__first + (__last - __first)/2),
1.1316 + *(__last - 1),
1.1317 + __comp)),
1.1318 + __comp);
1.1319 + if (__cut <= __nth)
1.1320 + __first = __cut;
1.1321 + else
1.1322 + __last = __cut;
1.1323 + }
1.1324 + __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1.1325 +}
1.1326 +
1.1327 +_STLP_MOVE_TO_STD_NAMESPACE
1.1328 +
1.1329 +template <class _RandomAccessIter>
1.1330 +void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1.1331 + _RandomAccessIter __last) {
1.1332 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
1.1333 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
1.1334 + _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1335 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.1336 +}
1.1337 +
1.1338 +template <class _RandomAccessIter, class _Compare>
1.1339 +void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1.1340 + _RandomAccessIter __last, _Compare __comp) {
1.1341 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
1.1342 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
1.1343 + _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
1.1344 +}
1.1345 +
1.1346 +// Binary search (lower_bound, upper_bound, equal_range, binary_search).
1.1347 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1348 +
1.1349 +template <class _ForwardIter, class _Tp,
1.1350 + class _Compare1, class _Compare2, class _Distance>
1.1351 +_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1.1352 + _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
1.1353 + _Distance __len = distance(__first, __last);
1.1354 + _Distance __half;
1.1355 +
1.1356 + while (__len > 0) {
1.1357 + __half = __len >> 1;
1.1358 + _ForwardIter __middle = __first;
1.1359 + advance(__middle, __half);
1.1360 + if (__comp2(__val, *__middle)) {
1.1361 + _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1362 + __len = __half;
1.1363 + }
1.1364 + else {
1.1365 + __first = __middle;
1.1366 + ++__first;
1.1367 + __len = __len - __half - 1;
1.1368 + }
1.1369 + }
1.1370 + return __first;
1.1371 +}
1.1372 +
1.1373 +template <class _ForwardIter, class _Tp,
1.1374 + class _Compare1, class _Compare2, class _Distance>
1.1375 +pair<_ForwardIter, _ForwardIter>
1.1376 +__equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1.1377 + _Compare1 __comp1, _Compare2 __comp2, _Distance* __dist) {
1.1378 + _Distance __len = distance(__first, __last);
1.1379 + _Distance __half;
1.1380 +
1.1381 + while (__len > 0) {
1.1382 + __half = __len >> 1;
1.1383 + _ForwardIter __middle = __first;
1.1384 + advance(__middle, __half);
1.1385 + if (__comp1(*__middle, __val)) {
1.1386 + _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1387 + __first = __middle;
1.1388 + ++__first;
1.1389 + __len = __len - __half - 1;
1.1390 + }
1.1391 + else if (__comp2(__val, *__middle)) {
1.1392 + _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1393 + __len = __half;
1.1394 + }
1.1395 + else {
1.1396 + _ForwardIter __left = __lower_bound(__first, __middle, __val, __comp1, __comp2, __dist);
1.1397 + //Small optim: If lower_bound haven't found an equivalent value
1.1398 + //there is no need to call upper_bound.
1.1399 + if (__comp1(*__left, __val)) {
1.1400 + _STLP_VERBOSE_ASSERT(!__comp2(__val, *__left), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1401 + return pair<_ForwardIter, _ForwardIter>(__left, __left);
1.1402 + }
1.1403 + advance(__first, __len);
1.1404 + _ForwardIter __right = __upper_bound(++__middle, __first, __val, __comp1, __comp2, __dist);
1.1405 + return pair<_ForwardIter, _ForwardIter>(__left, __right);
1.1406 + }
1.1407 + }
1.1408 + return pair<_ForwardIter, _ForwardIter>(__first, __first);
1.1409 +}
1.1410 +
1.1411 +_STLP_MOVE_TO_STD_NAMESPACE
1.1412 +
1.1413 +template <class _InputIter1, class _InputIter2, class _OutputIter>
1.1414 +_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
1.1415 + _InputIter2 __first2, _InputIter2 __last2,
1.1416 + _OutputIter __result) {
1.1417 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1.1418 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1.1419 + while (__first1 != __last1 && __first2 != __last2) {
1.1420 + if (*__first2 < *__first1) {
1.1421 + *__result = *__first2;
1.1422 + ++__first2;
1.1423 + }
1.1424 + else {
1.1425 + *__result = *__first1;
1.1426 + ++__first1;
1.1427 + }
1.1428 + ++__result;
1.1429 + }
1.1430 + return copy(__first2, __last2, copy(__first1, __last1, __result));
1.1431 +}
1.1432 +
1.1433 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.1434 + class _Compare>
1.1435 +_OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
1.1436 + _InputIter2 __first2, _InputIter2 __last2,
1.1437 + _OutputIter __result, _Compare __comp) {
1.1438 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1.1439 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1.1440 + while (__first1 != __last1 && __first2 != __last2) {
1.1441 + if (__comp(*__first2, *__first1)) {
1.1442 + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1443 + *__result = *__first2;
1.1444 + ++__first2;
1.1445 + }
1.1446 + else {
1.1447 + *__result = *__first1;
1.1448 + ++__first1;
1.1449 + }
1.1450 + ++__result;
1.1451 + }
1.1452 + return copy(__first2, __last2, copy(__first1, __last1, __result));
1.1453 +}
1.1454 +
1.1455 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1456 +
1.1457 +template <class _BidirectionalIter, class _Distance, class _Compare>
1.1458 +void __merge_without_buffer(_BidirectionalIter __first,
1.1459 + _BidirectionalIter __middle,
1.1460 + _BidirectionalIter __last,
1.1461 + _Distance __len1, _Distance __len2,
1.1462 + _Compare __comp) {
1.1463 + if (__len1 == 0 || __len2 == 0)
1.1464 + return;
1.1465 + if (__len1 + __len2 == 2) {
1.1466 + if (__comp(*__middle, *__first)) {
1.1467 + _STLP_VERBOSE_ASSERT(!__comp(*__first, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1468 + iter_swap(__first, __middle);
1.1469 + }
1.1470 + return;
1.1471 + }
1.1472 + _BidirectionalIter __first_cut = __first;
1.1473 + _BidirectionalIter __second_cut = __middle;
1.1474 + _Distance __len11 = 0;
1.1475 + _Distance __len22 = 0;
1.1476 + if (__len1 > __len2) {
1.1477 + __len11 = __len1 / 2;
1.1478 + advance(__first_cut, __len11);
1.1479 + __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
1.1480 + __len22 += distance(__middle, __second_cut);
1.1481 + }
1.1482 + else {
1.1483 + __len22 = __len2 / 2;
1.1484 + advance(__second_cut, __len22);
1.1485 + __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
1.1486 + __len11 +=distance(__first, __first_cut);
1.1487 + }
1.1488 + _BidirectionalIter __new_middle
1.1489 + = __rotate(__first_cut, __middle, __second_cut);
1.1490 + __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
1.1491 + __comp);
1.1492 + __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
1.1493 + __len2 - __len22, __comp);
1.1494 +}
1.1495 +
1.1496 +template <class _BidirectionalIter1, class _BidirectionalIter2,
1.1497 + class _BidirectionalIter3, class _Compare>
1.1498 +_BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
1.1499 + _BidirectionalIter1 __last1,
1.1500 + _BidirectionalIter2 __first2,
1.1501 + _BidirectionalIter2 __last2,
1.1502 + _BidirectionalIter3 __result,
1.1503 + _Compare __comp) {
1.1504 + if (__first1 == __last1)
1.1505 + return copy_backward(__first2, __last2, __result);
1.1506 + if (__first2 == __last2)
1.1507 + return copy_backward(__first1, __last1, __result);
1.1508 + --__last1;
1.1509 + --__last2;
1.1510 + for (;;) {
1.1511 + if (__comp(*__last2, *__last1)) {
1.1512 + _STLP_VERBOSE_ASSERT(!__comp(*__last1, *__last2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1513 + *--__result = *__last1;
1.1514 + if (__first1 == __last1)
1.1515 + return copy_backward(__first2, ++__last2, __result);
1.1516 + --__last1;
1.1517 + }
1.1518 + else {
1.1519 + *--__result = *__last2;
1.1520 + if (__first2 == __last2)
1.1521 + return copy_backward(__first1, ++__last1, __result);
1.1522 + --__last2;
1.1523 + }
1.1524 + }
1.1525 +}
1.1526 +
1.1527 +template <class _BidirectionalIter, class _Tp,
1.1528 + class _Distance, class _Compare>
1.1529 +inline void __inplace_merge_aux(_BidirectionalIter __first,
1.1530 + _BidirectionalIter __middle,
1.1531 + _BidirectionalIter __last, _Tp*, _Distance*,
1.1532 + _Compare __comp) {
1.1533 + _Distance __len1 = distance(__first, __middle);
1.1534 + _Distance __len2 = distance(__middle, __last);
1.1535 +
1.1536 + _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
1.1537 + if (__buf.begin() == 0)
1.1538 + __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
1.1539 + else
1.1540 + __merge_adaptive(__first, __middle, __last, __len1, __len2,
1.1541 + __buf.begin(), _Distance(__buf.size()),
1.1542 + __comp);
1.1543 +}
1.1544 +
1.1545 +_STLP_MOVE_TO_STD_NAMESPACE
1.1546 +
1.1547 +template <class _BidirectionalIter>
1.1548 +void inplace_merge(_BidirectionalIter __first,
1.1549 + _BidirectionalIter __middle,
1.1550 + _BidirectionalIter __last) {
1.1551 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
1.1552 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
1.1553 + if (__first == __middle || __middle == __last)
1.1554 + return;
1.1555 + _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
1.1556 + _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
1.1557 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
1.1558 +}
1.1559 +
1.1560 +template <class _BidirectionalIter, class _Compare>
1.1561 +void inplace_merge(_BidirectionalIter __first,
1.1562 + _BidirectionalIter __middle,
1.1563 + _BidirectionalIter __last, _Compare __comp) {
1.1564 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
1.1565 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
1.1566 + if (__first == __middle || __middle == __last)
1.1567 + return;
1.1568 + _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
1.1569 + _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
1.1570 + __comp);
1.1571 +}
1.1572 +
1.1573 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1574 +
1.1575 +template <class _InputIter1, class _InputIter2, class _Compare>
1.1576 +bool __includes(_InputIter1 __first1, _InputIter1 __last1,
1.1577 + _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
1.1578 + _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.1579 + _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.1580 + while (__first1 != __last1 && __first2 != __last2)
1.1581 + if (__comp(*__first2, *__first1)) {
1.1582 + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1583 + return false;
1.1584 + }
1.1585 + else if (__comp(*__first1, *__first2))
1.1586 + ++__first1;
1.1587 + else
1.1588 + ++__first1, ++__first2;
1.1589 +
1.1590 + return __first2 == __last2;
1.1591 +}
1.1592 +
1.1593 +_STLP_MOVE_TO_STD_NAMESPACE
1.1594 +
1.1595 +template <class _InputIter1, class _InputIter2, class _Compare>
1.1596 +bool includes(_InputIter1 __first1, _InputIter1 __last1,
1.1597 + _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
1.1598 + return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, __comp);
1.1599 +}
1.1600 +
1.1601 +template <class _InputIter1, class _InputIter2>
1.1602 +bool includes(_InputIter1 __first1, _InputIter1 __last1,
1.1603 + _InputIter2 __first2, _InputIter2 __last2) {
1.1604 + return _STLP_PRIV __includes(__first1, __last1, __first2, __last2,
1.1605 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.1606 +}
1.1607 +
1.1608 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1609 +
1.1610 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.1611 + class _Compare>
1.1612 +_OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,
1.1613 + _InputIter2 __first2, _InputIter2 __last2,
1.1614 + _OutputIter __result, _Compare __comp) {
1.1615 + _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.1616 + _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.1617 + while (__first1 != __last1 && __first2 != __last2) {
1.1618 + if (__comp(*__first1, *__first2)) {
1.1619 + _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1620 + *__result = *__first1;
1.1621 + ++__first1;
1.1622 + }
1.1623 + else if (__comp(*__first2, *__first1)) {
1.1624 + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1625 + *__result = *__first2;
1.1626 + ++__first2;
1.1627 + }
1.1628 + else {
1.1629 + *__result = *__first1;
1.1630 + ++__first1;
1.1631 + ++__first2;
1.1632 + }
1.1633 + ++__result;
1.1634 + }
1.1635 + return copy(__first2, __last2, copy(__first1, __last1, __result));
1.1636 +}
1.1637 +
1.1638 +_STLP_MOVE_TO_STD_NAMESPACE
1.1639 +
1.1640 +template <class _InputIter1, class _InputIter2, class _OutputIter>
1.1641 +_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
1.1642 + _InputIter2 __first2, _InputIter2 __last2,
1.1643 + _OutputIter __result) {
1.1644 + return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result,
1.1645 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.1646 +}
1.1647 +
1.1648 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.1649 + class _Compare>
1.1650 +_OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
1.1651 + _InputIter2 __first2, _InputIter2 __last2,
1.1652 + _OutputIter __result, _Compare __comp) {
1.1653 + return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, __comp);
1.1654 +}
1.1655 +
1.1656 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1657 +
1.1658 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.1659 + class _Compare>
1.1660 +_OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,
1.1661 + _InputIter2 __first2, _InputIter2 __last2,
1.1662 + _OutputIter __result, _Compare __comp) {
1.1663 + _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.1664 + _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.1665 + while (__first1 != __last1 && __first2 != __last2)
1.1666 + if (__comp(*__first1, *__first2)) {
1.1667 + _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1668 + ++__first1;
1.1669 + }
1.1670 + else if (__comp(*__first2, *__first1))
1.1671 + ++__first2;
1.1672 + else {
1.1673 + *__result = *__first1;
1.1674 + ++__first1;
1.1675 + ++__first2;
1.1676 + ++__result;
1.1677 + }
1.1678 + return __result;
1.1679 +}
1.1680 +
1.1681 +_STLP_MOVE_TO_STD_NAMESPACE
1.1682 +
1.1683 +template <class _InputIter1, class _InputIter2, class _OutputIter>
1.1684 +_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
1.1685 + _InputIter2 __first2, _InputIter2 __last2,
1.1686 + _OutputIter __result) {
1.1687 + return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result,
1.1688 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.1689 +}
1.1690 +
1.1691 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.1692 + class _Compare>
1.1693 +_OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
1.1694 + _InputIter2 __first2, _InputIter2 __last2,
1.1695 + _OutputIter __result, _Compare __comp) {
1.1696 + return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
1.1697 +}
1.1698 +
1.1699 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1700 +
1.1701 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.1702 + class _Compare>
1.1703 +_OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,
1.1704 + _InputIter2 __first2, _InputIter2 __last2,
1.1705 + _OutputIter __result, _Compare __comp) {
1.1706 + _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.1707 + _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.1708 + while (__first1 != __last1 && __first2 != __last2)
1.1709 + if (__comp(*__first1, *__first2)) {
1.1710 + _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1711 + *__result = *__first1;
1.1712 + ++__first1;
1.1713 + ++__result;
1.1714 + }
1.1715 + else if (__comp(*__first2, *__first1))
1.1716 + ++__first2;
1.1717 + else {
1.1718 + ++__first1;
1.1719 + ++__first2;
1.1720 + }
1.1721 + return copy(__first1, __last1, __result);
1.1722 +}
1.1723 +
1.1724 +_STLP_MOVE_TO_STD_NAMESPACE
1.1725 +
1.1726 +template <class _InputIter1, class _InputIter2, class _OutputIter>
1.1727 +_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
1.1728 + _InputIter2 __first2, _InputIter2 __last2,
1.1729 + _OutputIter __result) {
1.1730 + return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result,
1.1731 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.1732 +}
1.1733 +
1.1734 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.1735 + class _Compare>
1.1736 +_OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
1.1737 + _InputIter2 __first2, _InputIter2 __last2,
1.1738 + _OutputIter __result, _Compare __comp) {
1.1739 + return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, __comp);
1.1740 +}
1.1741 +
1.1742 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1743 +
1.1744 +template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
1.1745 +_OutputIter
1.1746 +__set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
1.1747 + _InputIter2 __first2, _InputIter2 __last2,
1.1748 + _OutputIter __result, _Compare __comp) {
1.1749 + _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.1750 + _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.1751 + while (__first1 != __last1 && __first2 != __last2) {
1.1752 + if (__comp(*__first1, *__first2)) {
1.1753 + _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1754 + *__result = *__first1;
1.1755 + ++__first1;
1.1756 + ++__result;
1.1757 + }
1.1758 + else if (__comp(*__first2, *__first1)) {
1.1759 + *__result = *__first2;
1.1760 + ++__first2;
1.1761 + ++__result;
1.1762 + }
1.1763 + else {
1.1764 + ++__first1;
1.1765 + ++__first2;
1.1766 + }
1.1767 + }
1.1768 + return copy(__first2, __last2, copy(__first1, __last1, __result));
1.1769 +}
1.1770 +
1.1771 +_STLP_MOVE_TO_STD_NAMESPACE
1.1772 +
1.1773 +template <class _InputIter1, class _InputIter2, class _OutputIter>
1.1774 +_OutputIter
1.1775 +set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
1.1776 + _InputIter2 __first2, _InputIter2 __last2,
1.1777 + _OutputIter __result) {
1.1778 + return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
1.1779 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.1780 +}
1.1781 +
1.1782 +template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
1.1783 +_OutputIter
1.1784 +set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
1.1785 + _InputIter2 __first2, _InputIter2 __last2,
1.1786 + _OutputIter __result,
1.1787 + _Compare __comp) {
1.1788 + return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
1.1789 +}
1.1790 +
1.1791 +// min_element and max_element, with and without an explicitly supplied
1.1792 +// comparison function.
1.1793 +
1.1794 +template <class _ForwardIter>
1.1795 +_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
1.1796 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1797 + if (__first == __last) return __first;
1.1798 + _ForwardIter __result = __first;
1.1799 + while (++__first != __last)
1.1800 + if (*__result < *__first)
1.1801 + __result = __first;
1.1802 + return __result;
1.1803 +}
1.1804 +
1.1805 +template <class _ForwardIter, class _Compare>
1.1806 +_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
1.1807 + _Compare __comp) {
1.1808 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1809 + if (__first == __last) return __first;
1.1810 + _ForwardIter __result = __first;
1.1811 + while (++__first != __last) {
1.1812 + if (__comp(*__result, *__first)) {
1.1813 + _STLP_VERBOSE_ASSERT(!__comp(*__first, *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1814 + __result = __first;
1.1815 + }
1.1816 + }
1.1817 + return __result;
1.1818 +}
1.1819 +
1.1820 +template <class _ForwardIter>
1.1821 +_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
1.1822 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1823 + if (__first == __last) return __first;
1.1824 + _ForwardIter __result = __first;
1.1825 + while (++__first != __last)
1.1826 + if (*__first < *__result)
1.1827 + __result = __first;
1.1828 + return __result;
1.1829 +}
1.1830 +
1.1831 +template <class _ForwardIter, class _Compare>
1.1832 +_ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
1.1833 + _Compare __comp) {
1.1834 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1835 + if (__first == __last) return __first;
1.1836 + _ForwardIter __result = __first;
1.1837 + while (++__first != __last) {
1.1838 + if (__comp(*__first, *__result)) {
1.1839 + _STLP_VERBOSE_ASSERT(!__comp(*__result, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1840 + __result = __first;
1.1841 + }
1.1842 + }
1.1843 + return __result;
1.1844 +}
1.1845 +
1.1846 +// next_permutation and prev_permutation, with and without an explicitly
1.1847 +// supplied comparison function.
1.1848 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1849 +
1.1850 +template <class _BidirectionalIter, class _Compare>
1.1851 +bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1.1852 + _Compare __comp) {
1.1853 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.1854 + if (__first == __last)
1.1855 + return false;
1.1856 + _BidirectionalIter __i = __first;
1.1857 + ++__i;
1.1858 + if (__i == __last)
1.1859 + return false;
1.1860 + __i = __last;
1.1861 + --__i;
1.1862 +
1.1863 + for(;;) {
1.1864 + _BidirectionalIter __ii = __i;
1.1865 + --__i;
1.1866 + if (__comp(*__i, *__ii)) {
1.1867 + _STLP_VERBOSE_ASSERT(!__comp(*__ii, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1868 + _BidirectionalIter __j = __last;
1.1869 + while (!__comp(*__i, *--__j)) {}
1.1870 + iter_swap(__i, __j);
1.1871 + reverse(__ii, __last);
1.1872 + return true;
1.1873 + }
1.1874 + if (__i == __first) {
1.1875 + reverse(__first, __last);
1.1876 + return false;
1.1877 + }
1.1878 + }
1.1879 +#if defined (_STLP_NEED_UNREACHABLE_RETURN)
1.1880 + return false;
1.1881 +#endif
1.1882 +}
1.1883 +
1.1884 +_STLP_MOVE_TO_STD_NAMESPACE
1.1885 +
1.1886 +template <class _BidirectionalIter>
1.1887 +bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
1.1888 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1889 + return _STLP_PRIV __next_permutation(__first, __last,
1.1890 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
1.1891 +}
1.1892 +
1.1893 +template <class _BidirectionalIter, class _Compare>
1.1894 +bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1.1895 + _Compare __comp) {
1.1896 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1897 + return _STLP_PRIV __next_permutation(__first, __last, __comp);
1.1898 +}
1.1899 +
1.1900 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1901 +
1.1902 +template <class _BidirectionalIter, class _Compare>
1.1903 +bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1.1904 + _Compare __comp) {
1.1905 + if (__first == __last)
1.1906 + return false;
1.1907 + _BidirectionalIter __i = __first;
1.1908 + ++__i;
1.1909 + if (__i == __last)
1.1910 + return false;
1.1911 + __i = __last;
1.1912 + --__i;
1.1913 +
1.1914 + for(;;) {
1.1915 + _BidirectionalIter __ii = __i;
1.1916 + --__i;
1.1917 + if (__comp(*__ii, *__i)) {
1.1918 + _STLP_VERBOSE_ASSERT(!__comp(*__i, *__ii), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1919 + _BidirectionalIter __j = __last;
1.1920 + while (!__comp(*--__j, *__i)) {}
1.1921 + iter_swap(__i, __j);
1.1922 + reverse(__ii, __last);
1.1923 + return true;
1.1924 + }
1.1925 + if (__i == __first) {
1.1926 + reverse(__first, __last);
1.1927 + return false;
1.1928 + }
1.1929 + }
1.1930 +#if defined (_STLP_NEED_UNREACHABLE_RETURN)
1.1931 + return false;
1.1932 +#endif
1.1933 +}
1.1934 +
1.1935 +_STLP_MOVE_TO_STD_NAMESPACE
1.1936 +
1.1937 +template <class _BidirectionalIter>
1.1938 +bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
1.1939 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1940 + return _STLP_PRIV __prev_permutation(__first, __last,
1.1941 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
1.1942 +}
1.1943 +
1.1944 +template <class _BidirectionalIter, class _Compare>
1.1945 +bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1.1946 + _Compare __comp) {
1.1947 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1948 + return _STLP_PRIV __prev_permutation(__first, __last, __comp);
1.1949 +}
1.1950 +
1.1951 +#if !defined (_STLP_NO_EXTENSIONS)
1.1952 +
1.1953 +// is_heap, a predicate testing whether or not a range is
1.1954 +// a heap. This function is an extension, not part of the C++
1.1955 +// standard.
1.1956 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1957 +
1.1958 +template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
1.1959 +bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
1.1960 + _Distance __n) {
1.1961 + _Distance __parent = 0;
1.1962 + for (_Distance __child = 1; __child < __n; ++__child) {
1.1963 + if (__comp(__first[__parent], __first[__child])) {
1.1964 + _STLP_VERBOSE_ASSERT(!__comp(__first[__child], __first[__parent]), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1965 + return false;
1.1966 + }
1.1967 + if ((__child & 1) == 0)
1.1968 + ++__parent;
1.1969 + }
1.1970 + return true;
1.1971 +}
1.1972 +
1.1973 +_STLP_MOVE_TO_STD_NAMESPACE
1.1974 +
1.1975 +template <class _RandomAccessIter>
1.1976 +bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) {
1.1977 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1978 + return _STLP_PRIV __is_heap(__first, _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first);
1.1979 +}
1.1980 +
1.1981 +template <class _RandomAccessIter, class _StrictWeakOrdering>
1.1982 +bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
1.1983 + _StrictWeakOrdering __comp) {
1.1984 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1985 + return _STLP_PRIV __is_heap(__first, __comp, __last - __first);
1.1986 +}
1.1987 +
1.1988 +
1.1989 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1990 +
1.1991 +template <class _ForwardIter, class _StrictWeakOrdering>
1.1992 +bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
1.1993 + _StrictWeakOrdering __comp) {
1.1994 + _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.1995 + if (__first == __last)
1.1996 + return true;
1.1997 +
1.1998 + _ForwardIter __next = __first;
1.1999 + for (++__next; __next != __last; __first = __next, ++__next) {
1.2000 + if (__comp(*__next, *__first)) {
1.2001 + _STLP_VERBOSE_ASSERT(!__comp(*__first, *__next), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2002 + return false;
1.2003 + }
1.2004 + }
1.2005 +
1.2006 + return true;
1.2007 +}
1.2008 +
1.2009 +_STLP_MOVE_TO_STD_NAMESPACE
1.2010 +#endif /* _STLP_NO_EXTENSIONS */
1.2011 +
1.2012 +_STLP_END_NAMESPACE
1.2013 +
1.2014 +#undef __stl_threshold
1.2015 +
1.2016 +#endif /* _STLP_ALGO_C */
1.2017 +// Local Variables:
1.2018 +// mode:C++
1.2019 +// End: