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