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