1.1 --- a/epoc32/include/stdapis/stlportv5/stl/_algo.c Wed Mar 31 12:27:01 2010 +0100
1.2 +++ b/epoc32/include/stdapis/stlportv5/stl/_algo.c Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -9,13 +9,13 @@
1.4 * Copyright (c) 1997
1.5 * Moscow Center for SPARC Technology
1.6 *
1.7 - * Copyright (c) 1999
1.8 + * Copyright (c) 1999
1.9 * Boris Fomitchev
1.10 *
1.11 * This material is provided "as is", with absolutely no warranty expressed
1.12 * or implied. Any use is at your own risk.
1.13 *
1.14 - * Permission to use or copy this software for any purpose is hereby granted
1.15 + * Permission to use or copy this software for any purpose is hereby granted
1.16 * without fee, provided the above notices are retained on all copies.
1.17 * Permission to modify the code and to distribute modified code is granted,
1.18 * provided the above notices are retained, and a notice that the code was
1.19 @@ -24,14 +24,20 @@
1.20 */
1.21
1.22 #ifndef _STLP_ALGO_C
1.23 -# define _STLP_ALGO_C
1.24 +#define _STLP_ALGO_C
1.25
1.26 -# if !defined (_STLP_INTERNAL_ALGO_H)
1.27 +#if !defined (_STLP_INTERNAL_ALGO_H)
1.28 # include <stl/_algo.h>
1.29 -# endif
1.30 +#endif
1.31 +
1.32 +#ifndef _STLP_INTERNAL_TEMPBUF_H
1.33 +# include <stl/_tempbuf.h>
1.34 +#endif
1.35
1.36 _STLP_BEGIN_NAMESPACE
1.37
1.38 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.39 +
1.40 template <class _BidirectionalIter, class _Distance, class _Compare>
1.41 void __merge_without_buffer(_BidirectionalIter __first,
1.42 _BidirectionalIter __middle,
1.43 @@ -50,9 +56,9 @@
1.44 _Compare __comp);
1.45
1.46 template <class _Tp>
1.47 -# if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
1.48 -inline
1.49 -# endif
1.50 +#if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
1.51 +inline
1.52 +#endif
1.53 const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
1.54 if (__a < __b)
1.55 if (__b < __c)
1.56 @@ -70,55 +76,62 @@
1.57 }
1.58
1.59 template <class _Tp, class _Compare>
1.60 -# if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
1.61 -inline
1.62 -# endif
1.63 +#if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
1.64 +inline
1.65 +#endif
1.66 const _Tp&
1.67 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
1.68 - if (__comp(__a, __b))
1.69 - if (__comp(__b, __c))
1.70 + if (__comp(__a, __b)) {
1.71 + _STLP_VERBOSE_ASSERT(!__comp(__b, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.72 + if (__comp(__b, __c)) {
1.73 + _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.74 return __b;
1.75 - else if (__comp(__a, __c))
1.76 + }
1.77 + else if (__comp(__a, __c)) {
1.78 + _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.79 return __c;
1.80 + }
1.81 else
1.82 return __a;
1.83 - else if (__comp(__a, __c))
1.84 + }
1.85 + else if (__comp(__a, __c)) {
1.86 + _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.87 return __a;
1.88 - else if (__comp(__b, __c))
1.89 + }
1.90 + else if (__comp(__b, __c)) {
1.91 + _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.92 return __c;
1.93 + }
1.94 else
1.95 return __b;
1.96 }
1.97
1.98 +_STLP_MOVE_TO_STD_NAMESPACE
1.99 +
1.100 template <class _ForwardIter1, class _ForwardIter2>
1.101 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
1.102 - _ForwardIter2 __first2, _ForwardIter2 __last2)
1.103 -{
1.104 - _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.105 - _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.106 + _ForwardIter2 __first2, _ForwardIter2 __last2) {
1.107 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1.108 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1.109 // Test for empty ranges
1.110 if (__first1 == __last1 || __first2 == __last2)
1.111 return __first1;
1.112
1.113 // Test for a pattern of length 1.
1.114 - _ForwardIter2 __tmp(__first2);
1.115 - ++__tmp;
1.116 - if (__tmp == __last2)
1.117 + _ForwardIter2 __p1(__first2);
1.118 +
1.119 + if ( ++__p1 == __last2 )
1.120 return find(__first1, __last1, *__first2);
1.121
1.122 // General case.
1.123 - _ForwardIter2 __p1 = __first2;
1.124 - ++__p1;
1.125
1.126 - _ForwardIter1 __current = __first1;
1.127 -
1.128 - while (__first1 != __last1) {
1.129 + for ( ; ; ) { // __first1 != __last1 will be checked in find below
1.130 __first1 = find(__first1, __last1, *__first2);
1.131 if (__first1 == __last1)
1.132 return __last1;
1.133
1.134 _ForwardIter2 __p = __p1;
1.135 - __current = __first1;
1.136 + _ForwardIter1 __current = __first1;
1.137 if (++__current == __last1)
1.138 return __last1;
1.139
1.140 @@ -134,97 +147,155 @@
1.141 return __first1;
1.142 }
1.143
1.144 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.145 +
1.146 +template <class _RandomAccessIter, class _Integer, class _Tp,
1.147 + class _BinaryPred, class _Distance>
1.148 +_RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
1.149 + _Integer __count, const _Tp& __val, _BinaryPred __pred,
1.150 + _Distance*, const random_access_iterator_tag &)
1.151 +{
1.152 + _Distance __tailSize = __last - __first;
1.153 + const _Distance __pattSize = __count;
1.154 + const _Distance __skipOffset = __pattSize - 1;
1.155 + _RandomAccessIter __backTrack;
1.156 + _Distance __remainder, __prevRemainder;
1.157 +
1.158 + for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) { // the main loop...
1.159 + //__lookAhead here is always pointing to the last element of next possible match.
1.160 + __tailSize -= __pattSize;
1.161 +
1.162 + while ( !__pred(*__lookAhead, __val) ) { // the skip loop...
1.163 + if (__tailSize < __pattSize)
1.164 + return __last;
1.165 +
1.166 + __lookAhead += __pattSize;
1.167 + __tailSize -= __pattSize;
1.168 + }
1.169 +
1.170 + if ( __skipOffset == 0 ) {
1.171 + return (__lookAhead - __skipOffset); //Success
1.172 + }
1.173 +
1.174 + __remainder = __skipOffset;
1.175 +
1.176 + for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) {
1.177 + if (--__remainder == 0)
1.178 + return (__lookAhead - __skipOffset); //Success
1.179 + }
1.180 +
1.181 + if (__remainder > __tailSize)
1.182 + return __last; //failure
1.183 +
1.184 + __lookAhead += __remainder;
1.185 + __tailSize -= __remainder;
1.186 +
1.187 + while ( __pred(*__lookAhead, __val) ) {
1.188 + __prevRemainder = __remainder;
1.189 + __backTrack = __lookAhead;
1.190 +
1.191 + do {
1.192 + if (--__remainder == 0)
1.193 + return (__lookAhead - __skipOffset); //Success
1.194 + } while (__pred(*--__backTrack, __val));
1.195 +
1.196 + //adjust remainder for next comparison
1.197 + __remainder += __pattSize - __prevRemainder;
1.198 +
1.199 + if (__remainder > __tailSize)
1.200 + return __last; //failure
1.201 +
1.202 + __lookAhead += __remainder;
1.203 + __tailSize -= __remainder;
1.204 + }
1.205 +
1.206 + //__lookAhead here is always pointing to the element of the last mismatch.
1.207 + }
1.208 +
1.209 + return __last; //failure
1.210 +}
1.211 +
1.212 +template <class _ForwardIter, class _Integer, class _Tp,
1.213 + class _Distance, class _BinaryPred>
1.214 +_ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last,
1.215 + _Integer __count, const _Tp& __val, _BinaryPred __pred,
1.216 + _Distance*, const forward_iterator_tag &) {
1.217 + for (; (__first != __last) && !__pred(*__first, __val); ++__first) {}
1.218 + while (__first != __last) {
1.219 + _Integer __n = __count - 1;
1.220 + _ForwardIter __i = __first;
1.221 + ++__i;
1.222 + while (__i != __last && __n != 0 && __pred(*__i, __val)) {
1.223 + ++__i;
1.224 + --__n;
1.225 + }
1.226 + if (__n == 0)
1.227 + return __first;
1.228 + else if (__i != __last)
1.229 + for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {}
1.230 + else
1.231 + break;
1.232 + }
1.233 + return __last;
1.234 +}
1.235 +
1.236 +_STLP_MOVE_TO_STD_NAMESPACE
1.237 +
1.238 // search_n. Search for __count consecutive copies of __val.
1.239 -
1.240 template <class _ForwardIter, class _Integer, class _Tp>
1.241 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
1.242 _Integer __count, const _Tp& __val) {
1.243 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.244 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.245 if (__count <= 0)
1.246 return __first;
1.247 - else {
1.248 - __first = find(__first, __last, __val);
1.249 - while (__first != __last) {
1.250 - _Integer __n = __count - 1;
1.251 - _ForwardIter __i = __first;
1.252 - ++__i;
1.253 - while (__i != __last && __n != 0 && *__i == __val) {
1.254 - ++__i;
1.255 - --__n;
1.256 - }
1.257 - if (__n == 0)
1.258 - return __first;
1.259 - else
1.260 - __first = find(__i, __last, __val);
1.261 - }
1.262 - return __last;
1.263 - }
1.264 + if (__count == 1)
1.265 + //We use find when __count == 1 to use potential find overload.
1.266 + return find(__first, __last, __val);
1.267 + return _STLP_PRIV __search_n(__first, __last, __count, __val, equal_to<_Tp>(),
1.268 + _STLP_DISTANCE_TYPE(__first, _ForwardIter),
1.269 + _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.270 }
1.271
1.272 template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
1.273 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
1.274 _Integer __count, const _Tp& __val,
1.275 _BinaryPred __binary_pred) {
1.276 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.277 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.278 if (__count <= 0)
1.279 return __first;
1.280 - else {
1.281 - while (__first != __last) {
1.282 - if (__binary_pred(*__first, __val))
1.283 - break;
1.284 - ++__first;
1.285 - }
1.286 - while (__first != __last) {
1.287 - _Integer __n = __count - 1;
1.288 - _ForwardIter __i = __first;
1.289 - ++__i;
1.290 - while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
1.291 - ++__i;
1.292 - --__n;
1.293 - }
1.294 - if (__n == 0)
1.295 - return __first;
1.296 - else {
1.297 - while (__i != __last) {
1.298 - if (__binary_pred(*__i, __val))
1.299 - break;
1.300 - ++__i;
1.301 - }
1.302 - __first = __i;
1.303 - }
1.304 - }
1.305 - return __last;
1.306 - }
1.307 -}
1.308 + return _STLP_PRIV __search_n(__first, __last, __count, __val, __binary_pred,
1.309 + _STLP_DISTANCE_TYPE(__first, _ForwardIter),
1.310 + _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.311 +}
1.312
1.313 template <class _ForwardIter1, class _ForwardIter2>
1.314 -_ForwardIter1
1.315 -find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
1.316 - _ForwardIter2 __first2, _ForwardIter2 __last2)
1.317 -{
1.318 - _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.319 - _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.320 - return __find_end(__first1, __last1, __first2, __last2,
1.321 -# if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.322 - _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
1.323 - _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
1.324 -# else
1.325 - forward_iterator_tag(),
1.326 - forward_iterator_tag(),
1.327 -# endif
1.328 - __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))
1.329 +_ForwardIter1
1.330 +find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
1.331 + _ForwardIter2 __first2, _ForwardIter2 __last2) {
1.332 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1.333 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1.334 + return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
1.335 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.336 + _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
1.337 + _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
1.338 +#else
1.339 + forward_iterator_tag(),
1.340 + forward_iterator_tag(),
1.341 +#endif
1.342 + _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))
1.343 );
1.344 }
1.345
1.346 // unique and unique_copy
1.347 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.348 +
1.349 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,
1.350 - class _Tp>
1.351 -_STLP_INLINE_LOOP _OutputIterator
1.352 + class _Tp>
1.353 +_STLP_INLINE_LOOP _OutputIterator
1.354 __unique_copy(_InputIterator __first, _InputIterator __last,
1.355 _OutputIterator __result,
1.356 _BinaryPredicate __binary_pred, _Tp*) {
1.357 _Tp __val = *__first;
1.358 - _STLP_PUSH_STACK_ITEM(_Tp, &__val)
1.359 *__result = __val;
1.360 while (++__first != __last)
1.361 if (!__binary_pred(__val, *__first)) {
1.362 @@ -235,15 +306,15 @@
1.363 }
1.364
1.365 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
1.366 -inline _OutputIter
1.367 +inline _OutputIter
1.368 __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
1.369 _BinaryPredicate __binary_pred, const output_iterator_tag &) {
1.370 return __unique_copy(__first, __last, __result, __binary_pred, _STLP_VALUE_TYPE(__first, _InputIter));
1.371 }
1.372
1.373 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
1.374 -_STLP_INLINE_LOOP _ForwardIter
1.375 -__unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result,
1.376 +_STLP_INLINE_LOOP _ForwardIter
1.377 +__unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result,
1.378 _BinaryPredicate __binary_pred, const forward_iterator_tag &) {
1.379 *__result = *__first;
1.380 while (++__first != __last)
1.381 @@ -251,9 +322,9 @@
1.382 return ++__result;
1.383 }
1.384
1.385 -# if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
1.386 +#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
1.387 template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate>
1.388 -inline _BidirectionalIterator
1.389 +inline _BidirectionalIterator
1.390 __unique_copy(_InputIterator __first, _InputIterator __last,
1.391 _BidirectionalIterator __result, _BinaryPredicate __binary_pred,
1.392 const bidirectional_iterator_tag &) {
1.393 @@ -261,354 +332,38 @@
1.394 }
1.395
1.396 template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate>
1.397 -inline _RandomAccessIterator
1.398 +inline _RandomAccessIterator
1.399 __unique_copy(_InputIterator __first, _InputIterator __last,
1.400 _RandomAccessIterator __result, _BinaryPredicate __binary_pred,
1.401 const random_access_iterator_tag &) {
1.402 return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
1.403 }
1.404 -# endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */
1.405 +#endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */
1.406
1.407 +_STLP_MOVE_TO_STD_NAMESPACE
1.408
1.409 template <class _InputIter, class _OutputIter>
1.410 -_OutputIter
1.411 +_OutputIter
1.412 unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
1.413 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.414 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.415 if (__first == __last) return __result;
1.416 - return __unique_copy(__first, __last, __result, __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),
1.417 - _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
1.418 + return _STLP_PRIV __unique_copy(__first, __last, __result,
1.419 + _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),
1.420 + _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
1.421 }
1.422
1.423 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
1.424 -_OutputIter
1.425 +_OutputIter
1.426 unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
1.427 _BinaryPredicate __binary_pred) {
1.428 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.429 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.430 if (__first == __last) return __result;
1.431 - return __unique_copy(__first, __last, __result, __binary_pred,
1.432 - _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
1.433 + return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred,
1.434 + _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
1.435 }
1.436
1.437 // rotate and rotate_copy, and their auxiliary functions
1.438 -
1.439 -template <class _ForwardIter, class _Distance>
1.440 -_ForwardIter __rotate(_ForwardIter __first,
1.441 - _ForwardIter __middle,
1.442 - _ForwardIter __last,
1.443 - _Distance*,
1.444 - const forward_iterator_tag &) {
1.445 - if (__first == __middle)
1.446 - return __last;
1.447 - if (__last == __middle)
1.448 - return __first;
1.449 -
1.450 - _ForwardIter __first2 = __middle;
1.451 - do {
1.452 - swap(*__first++, *__first2++);
1.453 - if (__first == __middle)
1.454 - __middle = __first2;
1.455 - } while (__first2 != __last);
1.456 -
1.457 - _ForwardIter __new_middle = __first;
1.458 -
1.459 - __first2 = __middle;
1.460 -
1.461 - while (__first2 != __last) {
1.462 - swap (*__first++, *__first2++);
1.463 - if (__first == __middle)
1.464 - __middle = __first2;
1.465 - else if (__first2 == __last)
1.466 - __first2 = __middle;
1.467 - }
1.468 -
1.469 - return __new_middle;
1.470 -}
1.471 -
1.472 -template <class _BidirectionalIter, class _Distance>
1.473 -_BidirectionalIter __rotate(_BidirectionalIter __first,
1.474 - _BidirectionalIter __middle,
1.475 - _BidirectionalIter __last,
1.476 - _Distance*,
1.477 - const bidirectional_iterator_tag &) {
1.478 - if (__first == __middle)
1.479 - return __last;
1.480 - if (__last == __middle)
1.481 - return __first;
1.482 -
1.483 - __reverse(__first, __middle, bidirectional_iterator_tag());
1.484 - __reverse(__middle, __last, bidirectional_iterator_tag());
1.485 -
1.486 - while (__first != __middle && __middle != __last)
1.487 - swap (*__first++, *--__last);
1.488 -
1.489 - if (__first == __middle) {
1.490 - __reverse(__middle, __last, bidirectional_iterator_tag());
1.491 - return __last;
1.492 - }
1.493 - else {
1.494 - __reverse(__first, __middle, bidirectional_iterator_tag());
1.495 - return __first;
1.496 - }
1.497 -}
1.498 -
1.499 -template <class _RandomAccessIter, class _Distance, class _Tp>
1.500 -_RandomAccessIter __rotate(_RandomAccessIter __first,
1.501 - _RandomAccessIter __middle,
1.502 - _RandomAccessIter __last,
1.503 - _Distance *, _Tp *) {
1.504 -
1.505 - _Distance __n = __last - __first;
1.506 - _Distance __k = __middle - __first;
1.507 - _Distance __l = __n - __k;
1.508 - _RandomAccessIter __result = __first + (__last - __middle);
1.509 -
1.510 - if (__k==0) /* __first == middle */
1.511 - return __last;
1.512 -
1.513 - if (__k == __l) {
1.514 - swap_ranges(__first, __middle, __middle);
1.515 - return __result;
1.516 - }
1.517 -
1.518 - _Distance __d = __gcd(__n, __k);
1.519 -
1.520 - for (_Distance __i = 0; __i < __d; __i++) {
1.521 - _Tp __tmp = *__first;
1.522 - _STLP_PUSH_STACK_ITEM(_Tp, &__tmp)
1.523 - _RandomAccessIter __p = __first;
1.524 -
1.525 - if (__k < __l) {
1.526 - for (_Distance __j = 0; __j < __l/__d; __j++) {
1.527 - if (__p > __first + __l) {
1.528 - *__p = *(__p - __l);
1.529 - __p -= __l;
1.530 - }
1.531 -
1.532 - *__p = *(__p + __k);
1.533 - __p += __k;
1.534 - }
1.535 - }
1.536 -
1.537 - else {
1.538 - for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
1.539 - if (__p < __last - __k) {
1.540 - *__p = *(__p + __k);
1.541 - __p += __k;
1.542 - }
1.543 -
1.544 - *__p = * (__p - __l);
1.545 - __p -= __l;
1.546 - }
1.547 - }
1.548 -
1.549 - *__p = __tmp;
1.550 - ++__first;
1.551 - }
1.552 -
1.553 - return __result;
1.554 -}
1.555 -
1.556 -template <class _RandomAccessIter, class _Distance>
1.557 -inline _RandomAccessIter
1.558 -__rotate(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,
1.559 - _Distance * __dis, const random_access_iterator_tag &) {
1.560 - return __rotate(__first, __middle, __last,
1.561 - __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));
1.562 -}
1.563 -
1.564 -template <class _ForwardIter>
1.565 -_ForwardIter
1.566 -rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
1.567 - _STLP_DEBUG_CHECK(__check_range(__first, __middle))
1.568 - _STLP_DEBUG_CHECK(__check_range(__middle, __last))
1.569 - return __rotate(__first, __middle, __last,
1.570 - _STLP_DISTANCE_TYPE(__first, _ForwardIter),
1.571 - _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.572 -}
1.573 -
1.574 -// Return a random number in the range [0, __n). This function encapsulates
1.575 -// whether we're using rand (part of the standard C library) or lrand48
1.576 -// (not standard, but a much better choice whenever it's available).
1.577 -
1.578 -template <class _Distance>
1.579 -inline _Distance __random_number(_Distance __n) {
1.580 -#ifdef _STLP_NO_DRAND48
1.581 - return rand() % __n;
1.582 -#else
1.583 - return lrand48() % __n;
1.584 -#endif
1.585 -}
1.586 -
1.587 -template <class _RandomAccessIter>
1.588 -void random_shuffle(_RandomAccessIter __first,
1.589 - _RandomAccessIter __last) {
1.590 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.591 - if (__first == __last) return;
1.592 - for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1.593 - iter_swap(__i, __first + __random_number((__i - __first) + 1));
1.594 -}
1.595 -
1.596 -template <class _RandomAccessIter, class _RandomNumberGenerator>
1.597 -void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
1.598 - _RandomNumberGenerator& __rand) {
1.599 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.600 - if (__first == __last) return;
1.601 - for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1.602 - iter_swap(__i, __first + __rand((__i - __first) + 1));
1.603 -}
1.604 -
1.605 -# ifndef _STLP_NO_EXTENSIONS
1.606 -
1.607 -// random_sample and random_sample_n (extensions, not part of the standard).
1.608 -
1.609 -template <class _ForwardIter, class _OutputIter, class _Distance>
1.610 -_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
1.611 - _OutputIter __stl_out, const _Distance __n)
1.612 -{
1.613 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.614 - _Distance __remaining = distance(__first, __last);
1.615 - _Distance __m = (min) (__n, __remaining);
1.616 -
1.617 - while (__m > 0) {
1.618 - if (__random_number(__remaining) < __m) {
1.619 - *__stl_out = *__first;
1.620 - ++__stl_out;
1.621 - --__m;
1.622 - }
1.623 -
1.624 - --__remaining;
1.625 - ++__first;
1.626 - }
1.627 - return __stl_out;
1.628 -}
1.629 -
1.630 -
1.631 -template <class _ForwardIter, class _OutputIter, class _Distance,
1.632 - class _RandomNumberGenerator>
1.633 -_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
1.634 - _OutputIter __stl_out, const _Distance __n,
1.635 - _RandomNumberGenerator& __rand)
1.636 -{
1.637 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.638 - _Distance __remaining = distance(__first, __last);
1.639 - _Distance __m = (min) (__n, __remaining);
1.640 -
1.641 - while (__m > 0) {
1.642 - if (__rand(__remaining) < __m) {
1.643 - *__stl_out = *__first;
1.644 - ++__stl_out;
1.645 - --__m;
1.646 - }
1.647 -
1.648 - --__remaining;
1.649 - ++__first;
1.650 - }
1.651 - return __stl_out;
1.652 -}
1.653 -
1.654 -template <class _InputIter, class _RandomAccessIter, class _Distance>
1.655 -_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
1.656 - _RandomAccessIter __stl_out,
1.657 - const _Distance __n)
1.658 -{
1.659 - _Distance __m = 0;
1.660 - _Distance __t = __n;
1.661 - for ( ; __first != __last && __m < __n; ++__m, ++__first)
1.662 - __stl_out[__m] = *__first;
1.663 -
1.664 - while (__first != __last) {
1.665 - ++__t;
1.666 - _Distance __M = __random_number(__t);
1.667 - if (__M < __n)
1.668 - __stl_out[__M] = *__first;
1.669 - ++__first;
1.670 - }
1.671 -
1.672 - return __stl_out + __m;
1.673 -}
1.674 -
1.675 -template <class _InputIter, class _RandomAccessIter,
1.676 - class _RandomNumberGenerator, class _Distance>
1.677 -_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
1.678 - _RandomAccessIter __stl_out,
1.679 - _RandomNumberGenerator& __rand,
1.680 - const _Distance __n)
1.681 -{
1.682 - _Distance __m = 0;
1.683 - _Distance __t = __n;
1.684 - for ( ; __first != __last && __m < __n; ++__m, ++__first)
1.685 - __stl_out[__m] = *__first;
1.686 -
1.687 - while (__first != __last) {
1.688 - ++__t;
1.689 - _Distance __M = __rand(__t);
1.690 - if (__M < __n)
1.691 - __stl_out[__M] = *__first;
1.692 - ++__first;
1.693 - }
1.694 -
1.695 - return __stl_out + __m;
1.696 -}
1.697 -
1.698 -template <class _InputIter, class _RandomAccessIter>
1.699 -_RandomAccessIter
1.700 -random_sample(_InputIter __first, _InputIter __last,
1.701 - _RandomAccessIter __out_first, _RandomAccessIter __out_last)
1.702 -{
1.703 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.704 - _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last))
1.705 - return __random_sample(__first, __last,
1.706 - __out_first, __out_last - __out_first);
1.707 -}
1.708 -
1.709 -template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>
1.710 -_RandomAccessIter
1.711 -random_sample(_InputIter __first, _InputIter __last,
1.712 - _RandomAccessIter __out_first, _RandomAccessIter __out_last,
1.713 - _RandomNumberGenerator& __rand)
1.714 -{
1.715 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.716 - _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last))
1.717 - return __random_sample(__first, __last,
1.718 - __out_first, __rand,
1.719 - __out_last - __out_first);
1.720 -}
1.721 -
1.722 -# endif /* _STLP_NO_EXTENSIONS */
1.723 -
1.724 -// partition, stable_partition, and their auxiliary functions
1.725 -
1.726 -template <class _ForwardIter, class _Predicate>
1.727 -_STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,
1.728 - _ForwardIter __last,
1.729 - _Predicate __pred,
1.730 - const forward_iterator_tag &) {
1.731 - if (__first == __last) return __first;
1.732 -
1.733 - while (__pred(*__first))
1.734 - if (++__first == __last) return __first;
1.735 -
1.736 - _ForwardIter __next = __first;
1.737 -
1.738 - while (++__next != __last)
1.739 - if (__pred(*__next)) {
1.740 - swap(*__first, *__next);
1.741 - ++__first;
1.742 - }
1.743 - return __first;
1.744 -}
1.745 -
1.746 -/* bug fix- start*/
1.747 -
1.748 -template <class _ForwardIter>
1.749 -_ForwardIter
1.750 -__rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
1.751 - _STLP_DEBUG_CHECK(__check_range(__first, __middle))
1.752 - _STLP_DEBUG_CHECK(__check_range(__middle, __last))
1.753 - return __rotate_aux(__first, __middle, __last,
1.754 - _STLP_DISTANCE_TYPE(__first, _ForwardIter),
1.755 - _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.756 -}
1.757 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.758
1.759 template <class _ForwardIter, class _Distance>
1.760 _ForwardIter __rotate_aux(_ForwardIter __first,
1.761 @@ -643,6 +398,356 @@
1.762 return __new_middle;
1.763 }
1.764
1.765 +template <class _BidirectionalIter, class _Distance>
1.766 +_BidirectionalIter __rotate_aux(_BidirectionalIter __first,
1.767 + _BidirectionalIter __middle,
1.768 + _BidirectionalIter __last,
1.769 + _Distance*,
1.770 + const bidirectional_iterator_tag &) {
1.771 + if (__first == __middle)
1.772 + return __last;
1.773 + if (__last == __middle)
1.774 + return __first;
1.775 +
1.776 + __reverse(__first, __middle, bidirectional_iterator_tag());
1.777 + __reverse(__middle, __last, bidirectional_iterator_tag());
1.778 +
1.779 + while (__first != __middle && __middle != __last)
1.780 + swap (*__first++, *--__last);
1.781 +
1.782 + if (__first == __middle) {
1.783 + __reverse(__middle, __last, bidirectional_iterator_tag());
1.784 + return __last;
1.785 + }
1.786 + else {
1.787 + __reverse(__first, __middle, bidirectional_iterator_tag());
1.788 + return __first;
1.789 + }
1.790 +}
1.791 +
1.792 +template <class _RandomAccessIter, class _Distance, class _Tp>
1.793 +_RandomAccessIter __rotate_aux(_RandomAccessIter __first,
1.794 + _RandomAccessIter __middle,
1.795 + _RandomAccessIter __last,
1.796 + _Distance *, _Tp *) {
1.797 +
1.798 + _Distance __n = __last - __first;
1.799 + _Distance __k = __middle - __first;
1.800 + _Distance __l = __n - __k;
1.801 + _RandomAccessIter __result = __first + (__last - __middle);
1.802 +
1.803 + if (__k == 0) /* __first == middle */
1.804 + return __last;
1.805 +
1.806 + if (__k == __l) {
1.807 + swap_ranges(__first, __middle, __middle);
1.808 + return __result;
1.809 + }
1.810 +
1.811 + _Distance __d = __gcd(__n, __k);
1.812 +
1.813 + for (_Distance __i = 0; __i < __d; __i++) {
1.814 + _Tp __tmp = *__first;
1.815 + _RandomAccessIter __p = __first;
1.816 +
1.817 + if (__k < __l) {
1.818 + for (_Distance __j = 0; __j < __l/__d; __j++) {
1.819 + if (__p > __first + __l) {
1.820 + *__p = *(__p - __l);
1.821 + __p -= __l;
1.822 + }
1.823 +
1.824 + *__p = *(__p + __k);
1.825 + __p += __k;
1.826 + }
1.827 + }
1.828 +
1.829 + else {
1.830 + for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
1.831 + if (__p < __last - __k) {
1.832 + *__p = *(__p + __k);
1.833 + __p += __k;
1.834 + }
1.835 +
1.836 + *__p = * (__p - __l);
1.837 + __p -= __l;
1.838 + }
1.839 + }
1.840 +
1.841 + *__p = __tmp;
1.842 + ++__first;
1.843 + }
1.844 +
1.845 + return __result;
1.846 +}
1.847 +
1.848 +template <class _RandomAccessIter, class _Distance>
1.849 +inline _RandomAccessIter
1.850 +__rotate_aux(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,
1.851 + _Distance * __dis, const random_access_iterator_tag &) {
1.852 + return __rotate_aux(__first, __middle, __last,
1.853 + __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));
1.854 +}
1.855 +
1.856 +template <class _ForwardIter>
1.857 +_ForwardIter
1.858 +__rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
1.859 + _STLP_DEBUG_CHECK(__check_range(__first, __middle))
1.860 + _STLP_DEBUG_CHECK(__check_range(__middle, __last))
1.861 + return __rotate_aux(__first, __middle, __last,
1.862 + _STLP_DISTANCE_TYPE(__first, _ForwardIter),
1.863 + _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.864 +}
1.865 +
1.866 +_STLP_MOVE_TO_STD_NAMESPACE
1.867 +
1.868 +template <class _ForwardIter>
1.869 +void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
1.870 + _STLP_PRIV __rotate(__first, __middle, __last);
1.871 +}
1.872 +
1.873 +// Return a random number in the range [0, __n). This function encapsulates
1.874 +// whether we're using rand (part of the standard C library) or lrand48
1.875 +// (not standard, but a much better choice whenever it's available).
1.876 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.877 +
1.878 +template <class _Distance>
1.879 +inline _Distance __random_number(_Distance __n) {
1.880 +#ifdef _STLP_NO_DRAND48
1.881 + return rand() % __n;
1.882 +#else
1.883 + return lrand48() % __n;
1.884 +#endif
1.885 +}
1.886 +
1.887 +_STLP_MOVE_TO_STD_NAMESPACE
1.888 +
1.889 +template <class _RandomAccessIter>
1.890 +void random_shuffle(_RandomAccessIter __first,
1.891 + _RandomAccessIter __last) {
1.892 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.893 + if (__first == __last) return;
1.894 + for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1.895 + iter_swap(__i, __first + _STLP_PRIV __random_number((__i - __first) + 1));
1.896 +}
1.897 +
1.898 +template <class _RandomAccessIter, class _RandomNumberGenerator>
1.899 +void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
1.900 + _RandomNumberGenerator &__rand) {
1.901 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.902 + if (__first == __last) return;
1.903 + for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1.904 + iter_swap(__i, __first + __rand((__i - __first) + 1));
1.905 +}
1.906 +
1.907 +#if !defined (_STLP_NO_EXTENSIONS)
1.908 +// random_sample and random_sample_n (extensions, not part of the standard).
1.909 +template <class _ForwardIter, class _OutputIter, class _Distance>
1.910 +_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
1.911 + _OutputIter __out_ite, const _Distance __n) {
1.912 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.913 + _Distance __remaining = distance(__first, __last);
1.914 + _Distance __m = (min) (__n, __remaining);
1.915 +
1.916 + while (__m > 0) {
1.917 + if (_STLP_PRIV __random_number(__remaining) < __m) {
1.918 + *__out_ite = *__first;
1.919 + ++__out_ite;
1.920 + --__m;
1.921 + }
1.922 +
1.923 + --__remaining;
1.924 + ++__first;
1.925 + }
1.926 + return __out_ite;
1.927 +}
1.928 +
1.929 +
1.930 +template <class _ForwardIter, class _OutputIter, class _Distance,
1.931 + class _RandomNumberGenerator>
1.932 +_OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
1.933 + _OutputIter __out_ite, const _Distance __n,
1.934 + _RandomNumberGenerator& __rand) {
1.935 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.936 + _Distance __remaining = distance(__first, __last);
1.937 + _Distance __m = (min) (__n, __remaining);
1.938 +
1.939 + while (__m > 0) {
1.940 + if (__rand(__remaining) < __m) {
1.941 + *__out_ite = *__first;
1.942 + ++__out_ite;
1.943 + --__m;
1.944 + }
1.945 +
1.946 + --__remaining;
1.947 + ++__first;
1.948 + }
1.949 + return __out_ite;
1.950 +}
1.951 +
1.952 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.953 +
1.954 +template <class _InputIter, class _RandomAccessIter, class _Distance>
1.955 +_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
1.956 + _RandomAccessIter __out_ite,
1.957 + const _Distance __n) {
1.958 + _Distance __m = 0;
1.959 + _Distance __t = __n;
1.960 + for ( ; __first != __last && __m < __n; ++__m, ++__first)
1.961 + __out_ite[__m] = *__first;
1.962 +
1.963 + while (__first != __last) {
1.964 + ++__t;
1.965 + _Distance __M = __random_number(__t);
1.966 + if (__M < __n)
1.967 + __out_ite[__M] = *__first;
1.968 + ++__first;
1.969 + }
1.970 +
1.971 + return __out_ite + __m;
1.972 +}
1.973 +
1.974 +template <class _InputIter, class _RandomAccessIter,
1.975 + class _RandomNumberGenerator, class _Distance>
1.976 +_RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
1.977 + _RandomAccessIter __out_ite,
1.978 + _RandomNumberGenerator& __rand,
1.979 + const _Distance __n) {
1.980 + _Distance __m = 0;
1.981 + _Distance __t = __n;
1.982 + for ( ; __first != __last && __m < __n; ++__m, ++__first)
1.983 + __out_ite[__m] = *__first;
1.984 +
1.985 + while (__first != __last) {
1.986 + ++__t;
1.987 + _Distance __M = __rand(__t);
1.988 + if (__M < __n)
1.989 + __out_ite[__M] = *__first;
1.990 + ++__first;
1.991 + }
1.992 +
1.993 + return __out_ite + __m;
1.994 +}
1.995 +
1.996 +_STLP_MOVE_TO_STD_NAMESPACE
1.997 +
1.998 +template <class _InputIter, class _RandomAccessIter>
1.999 +_RandomAccessIter
1.1000 +random_sample(_InputIter __first, _InputIter __last,
1.1001 + _RandomAccessIter __out_first, _RandomAccessIter __out_last) {
1.1002 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1003 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
1.1004 + return _STLP_PRIV __random_sample(__first, __last,
1.1005 + __out_first, __out_last - __out_first);
1.1006 +}
1.1007 +
1.1008 +template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>
1.1009 +_RandomAccessIter
1.1010 +random_sample(_InputIter __first, _InputIter __last,
1.1011 + _RandomAccessIter __out_first, _RandomAccessIter __out_last,
1.1012 + _RandomNumberGenerator& __rand) {
1.1013 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1014 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
1.1015 + return _STLP_PRIV __random_sample(__first, __last,
1.1016 + __out_first, __rand,
1.1017 + __out_last - __out_first);
1.1018 +}
1.1019 +
1.1020 +#endif /* _STLP_NO_EXTENSIONS */
1.1021 +
1.1022 +// partition, stable_partition, and their auxiliary functions
1.1023 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1024 +
1.1025 +template <class _ForwardIter, class _Predicate>
1.1026 +_STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,
1.1027 + _ForwardIter __last,
1.1028 + _Predicate __pred,
1.1029 + const forward_iterator_tag &) {
1.1030 + if (__first == __last) return __first;
1.1031 +
1.1032 + while (__pred(*__first))
1.1033 + if (++__first == __last) return __first;
1.1034 +
1.1035 + _ForwardIter __next = __first;
1.1036 +
1.1037 + while (++__next != __last) {
1.1038 + if (__pred(*__next)) {
1.1039 + swap(*__first, *__next);
1.1040 + ++__first;
1.1041 + }
1.1042 + }
1.1043 + return __first;
1.1044 +}
1.1045 +
1.1046 +template <class _BidirectionalIter, class _Predicate>
1.1047 +_STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,
1.1048 + _BidirectionalIter __last,
1.1049 + _Predicate __pred,
1.1050 + const bidirectional_iterator_tag &) {
1.1051 + for (;;) {
1.1052 + for (;;) {
1.1053 + if (__first == __last)
1.1054 + return __first;
1.1055 + else if (__pred(*__first))
1.1056 + ++__first;
1.1057 + else
1.1058 + break;
1.1059 + }
1.1060 + --__last;
1.1061 + for (;;) {
1.1062 + if (__first == __last)
1.1063 + return __first;
1.1064 + else if (!__pred(*__last))
1.1065 + --__last;
1.1066 + else
1.1067 + break;
1.1068 + }
1.1069 + iter_swap(__first, __last);
1.1070 + ++__first;
1.1071 + }
1.1072 +}
1.1073 +
1.1074 +#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
1.1075 +template <class _BidirectionalIter, class _Predicate>
1.1076 +inline
1.1077 +_BidirectionalIter __partition(_BidirectionalIter __first,
1.1078 + _BidirectionalIter __last,
1.1079 + _Predicate __pred,
1.1080 + const random_access_iterator_tag &) {
1.1081 + return __partition(__first, __last, __pred, bidirectional_iterator_tag());
1.1082 +}
1.1083 +#endif
1.1084 +
1.1085 +_STLP_MOVE_TO_STD_NAMESPACE
1.1086 +
1.1087 +template <class _ForwardIter, class _Predicate>
1.1088 +_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
1.1089 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1090 + return _STLP_PRIV __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.1091 +}
1.1092 +
1.1093 +
1.1094 +/* __pred_of_first: false if we know that __pred(*__first) is false,
1.1095 + * true when we don't know the result of __pred(*__first).
1.1096 + * __not_pred_of_before_last: true if we know that __pred(*--__last) is true,
1.1097 + * false when we don't know the result of __pred(*--__last).
1.1098 + */
1.1099 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1100 +
1.1101 +template <class _ForwardIter, class _Predicate, class _Distance>
1.1102 +_ForwardIter __inplace_stable_partition(_ForwardIter __first,
1.1103 + _ForwardIter __last,
1.1104 + _Predicate __pred, _Distance __len,
1.1105 + bool __pred_of_first, bool __pred_of_before_last) {
1.1106 + if (__len == 1)
1.1107 + return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first;
1.1108 + _ForwardIter __middle = __first;
1.1109 + _Distance __half_len = __len / 2;
1.1110 + advance(__middle, __half_len);
1.1111 + return __rotate(__inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false),
1.1112 + __middle,
1.1113 + __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last));
1.1114 +}
1.1115
1.1116 template <class _ForwardIter, class _Pointer, class _Predicate,
1.1117 class _Distance>
1.1118 @@ -688,23 +793,61 @@
1.1119 }
1.1120 }
1.1121
1.1122 -
1.1123 -template <class _ForwardIter, class _Predicate, class _Distance>
1.1124 -_ForwardIter __inplace_stable_partition(_ForwardIter __first,
1.1125 - _ForwardIter __last,
1.1126 - _Predicate __pred, _Distance __len,
1.1127 - bool __pred_of_first, bool __pred_of_before_last) {
1.1128 - if (__len == 1)
1.1129 - return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first;
1.1130 - _ForwardIter __middle = __first;
1.1131 - _Distance __half_len = __len / 2;
1.1132 - advance(__middle, __half_len);
1.1133 - return __rotate(__inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false),
1.1134 - __middle,
1.1135 - __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last));
1.1136 +template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
1.1137 +inline _ForwardIter
1.1138 +__stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,
1.1139 + _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last = false) {
1.1140 + _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
1.1141 + _STLP_MPWFIX_TRY //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
1.1142 + return (__buf.size() > 0) ?
1.1143 + __stable_partition_adaptive(__first, __last, __pred,
1.1144 + _Distance(__buf.requested_size()),
1.1145 + __buf.begin(), __buf.size(),
1.1146 + false, __pred_of_before_last) :
1.1147 + __inplace_stable_partition(__first, __last, __pred,
1.1148 + _Distance(__buf.requested_size()),
1.1149 + false, __pred_of_before_last);
1.1150 + _STLP_MPWFIX_CATCH //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
1.1151 }
1.1152
1.1153 +template <class _ForwardIter, class _Predicate>
1.1154 +_ForwardIter
1.1155 +__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred,
1.1156 + const forward_iterator_tag &) {
1.1157 + return __stable_partition_aux_aux(__first, __last, __pred,
1.1158 + _STLP_VALUE_TYPE(__first, _ForwardIter),
1.1159 + _STLP_DISTANCE_TYPE(__first, _ForwardIter));
1.1160 +}
1.1161
1.1162 +template <class _BidirectIter, class _Predicate>
1.1163 +_BidirectIter
1.1164 +__stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
1.1165 + const bidirectional_iterator_tag &) {
1.1166 + for (--__last;;) {
1.1167 + if (__first == __last)
1.1168 + return __first;
1.1169 + else if (!__pred(*__last))
1.1170 + --__last;
1.1171 + else
1.1172 + break;
1.1173 + }
1.1174 + ++__last;
1.1175 + //Here we know that __pred(*--__last) is true
1.1176 + return __stable_partition_aux_aux(__first, __last, __pred,
1.1177 + _STLP_VALUE_TYPE(__first, _BidirectIter),
1.1178 + _STLP_DISTANCE_TYPE(__first, _BidirectIter), true);
1.1179 +}
1.1180 +
1.1181 +#if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
1.1182 +template <class _BidirectIter, class _Predicate>
1.1183 +_BidirectIter
1.1184 +__stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
1.1185 + const random_access_iterator_tag &) {
1.1186 + return __stable_partition_aux(__first, __last, __pred, bidirectional_iterator_tag());
1.1187 +}
1.1188 +#endif
1.1189 +
1.1190 +_STLP_MOVE_TO_STD_NAMESPACE
1.1191
1.1192 template <class _ForwardIter, class _Predicate>
1.1193 _ForwardIter
1.1194 @@ -718,180 +861,26 @@
1.1195 else
1.1196 break;
1.1197 }
1.1198 - return __stable_partition_aux(__first, __last, __pred,
1.1199 + return _STLP_PRIV __stable_partition_aux(__first, __last, __pred,
1.1200 _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.1201 }
1.1202
1.1203 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1204
1.1205 -template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
1.1206 -inline _ForwardIter
1.1207 -__stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,
1.1208 - _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last = false) {
1.1209 - _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
1.1210 - return (__buf.size() > 0) ?
1.1211 - __stable_partition_adaptive(__first, __last, __pred,
1.1212 - _Distance(__buf.requested_size()),
1.1213 - __buf.begin(), __buf.size(),
1.1214 - false, __pred_of_before_last) :
1.1215 - __inplace_stable_partition(__first, __last, __pred,
1.1216 - _Distance(__buf.requested_size()),
1.1217 - false, __pred_of_before_last);
1.1218 -
1.1219 -}
1.1220 -
1.1221 -template <class _ForwardIter, class _Predicate>
1.1222 -_ForwardIter
1.1223 -__stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred,
1.1224 - const forward_iterator_tag &) {
1.1225 - return __stable_partition_aux_aux(__first, __last, __pred,
1.1226 - _STLP_VALUE_TYPE(__first, _ForwardIter),
1.1227 - _STLP_DISTANCE_TYPE(__first, _ForwardIter));
1.1228 -}
1.1229 -
1.1230 -
1.1231 -/* bug fix- end*/
1.1232 -
1.1233 -
1.1234 -
1.1235 -template <class _BidirectionalIter, class _Predicate>
1.1236 -_STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,
1.1237 - _BidirectionalIter __last,
1.1238 - _Predicate __pred,
1.1239 - const bidirectional_iterator_tag &) {
1.1240 - while (true) {
1.1241 - while (true)
1.1242 - if (__first == __last)
1.1243 - return __first;
1.1244 - else if (__pred(*__first))
1.1245 - ++__first;
1.1246 - else
1.1247 - break;
1.1248 +template <class _RandomAccessIter, class _Tp, class _Compare>
1.1249 +_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
1.1250 + _RandomAccessIter __last,
1.1251 + _Tp __pivot, _Compare __comp) {
1.1252 + for (;;) {
1.1253 + while (__comp(*__first, __pivot)) {
1.1254 + _STLP_VERBOSE_ASSERT(!__comp(__pivot, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1255 + ++__first;
1.1256 + }
1.1257 --__last;
1.1258 - while (true)
1.1259 - if (__first == __last)
1.1260 - return __first;
1.1261 - else if (!__pred(*__last))
1.1262 - --__last;
1.1263 - else
1.1264 - break;
1.1265 - iter_swap(__first, __last);
1.1266 - ++__first;
1.1267 - }
1.1268 -}
1.1269 -
1.1270 -# if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
1.1271 -template <class _BidirectionalIter, class _Predicate>
1.1272 -inline
1.1273 -_BidirectionalIter __partition(_BidirectionalIter __first,
1.1274 - _BidirectionalIter __last,
1.1275 - _Predicate __pred,
1.1276 - const random_access_iterator_tag &) {
1.1277 - return __partition(__first, __last, __pred, bidirectional_iterator_tag());
1.1278 -}
1.1279 -# endif
1.1280 -
1.1281 -template <class _ForwardIter, class _Predicate>
1.1282 -_ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
1.1283 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.1284 - return __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
1.1285 -}
1.1286 -
1.1287 -/*
1.1288 -template <class _ForwardIter, class _Predicate, class _Distance>
1.1289 -_ForwardIter __inplace_stable_partition(_ForwardIter __first,
1.1290 - _ForwardIter __last,
1.1291 - _Predicate __pred, _Distance __len) {
1.1292 - if (__len == 1)
1.1293 - return __pred(*__first) ? __last : __first;
1.1294 - _ForwardIter __middle = __first;
1.1295 - advance(__middle, __len / 2);
1.1296 - return rotate(__inplace_stable_partition(__first, __middle, __pred,
1.1297 - __len / 2),
1.1298 - __middle,
1.1299 - __inplace_stable_partition(__middle, __last, __pred,
1.1300 - __len - __len / 2));
1.1301 -}
1.1302 -
1.1303 -
1.1304 -template <class _ForwardIter, class _Pointer, class _Predicate,
1.1305 - class _Distance>
1.1306 -_ForwardIter __stable_partition_adaptive(_ForwardIter __first,
1.1307 - _ForwardIter __last,
1.1308 - _Predicate __pred, _Distance __len,
1.1309 - _Pointer __buffer,
1.1310 - _Distance __buffer_size)
1.1311 -{
1.1312 - if (__len <= __buffer_size) {
1.1313 - _ForwardIter __result1 = __first;
1.1314 - _Pointer __result2 = __buffer;
1.1315 - for ( ; __first != __last ; ++__first)
1.1316 - if (__pred(*__first)) {
1.1317 - *__result1 = *__first;
1.1318 - ++__result1;
1.1319 - }
1.1320 - else {
1.1321 - *__result2 = *__first;
1.1322 - ++__result2;
1.1323 - }
1.1324 - copy(__buffer, __result2, __result1);
1.1325 - return __result1;
1.1326 - }
1.1327 - else {
1.1328 - _ForwardIter __middle = __first;
1.1329 - advance(__middle, __len / 2);
1.1330 - return rotate(__stable_partition_adaptive(
1.1331 - __first, __middle, __pred,
1.1332 - _Distance(__len / 2), __buffer, __buffer_size),
1.1333 - __middle,
1.1334 - __stable_partition_adaptive(
1.1335 - __middle, __last, __pred,
1.1336 - _Distance(__len - __len / 2), __buffer, __buffer_size));
1.1337 - }
1.1338 -}
1.1339 -*/ //bug fix
1.1340 -template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
1.1341 -inline _ForwardIter
1.1342 -__stable_partition_aux(_ForwardIter __first, _ForwardIter __last,
1.1343 - _Predicate __pred, _Tp*, _Distance*)
1.1344 -{
1.1345 - typedef _Temporary_buffer<_ForwardIter, _Tp> _TmpBuf;
1.1346 - _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
1.1347 - _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);
1.1348 -
1.1349 - _STLP_MPWFIX_TRY //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
1.1350 - return (__buf.size() > 0) ?
1.1351 - __stable_partition_adaptive(__first, __last, __pred,
1.1352 - _Distance(__buf.requested_size()),
1.1353 - __buf.begin(), _Distance(__buf.size())) :
1.1354 - __inplace_stable_partition(__first, __last, __pred,
1.1355 - _Distance(__buf.requested_size()));
1.1356 - _STLP_MPWFIX_CATCH //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
1.1357 -}
1.1358 -/*
1.1359 -template <class _ForwardIter, class _Predicate>
1.1360 -_ForwardIter
1.1361 -stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
1.1362 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.1363 - if (__first == __last)
1.1364 - return __first;
1.1365 - else
1.1366 - return __stable_partition_aux(__first, __last, __pred,
1.1367 - _STLP_VALUE_TYPE(__first, _ForwardIter),
1.1368 - _STLP_DISTANCE_TYPE(__first, _ForwardIter));
1.1369 -}
1.1370 -*/ //bug fix
1.1371 -template <class _RandomAccessIter, class _Tp, class _Compare>
1.1372 -_RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
1.1373 - _RandomAccessIter __last,
1.1374 - _Tp __pivot, _Compare __comp)
1.1375 -{
1.1376 - _STLP_PUSH_STACK_ITEM(_Tp, &__pivot)
1.1377 - while (true) {
1.1378 - while (__comp(*__first, __pivot))
1.1379 - ++__first;
1.1380 - --__last;
1.1381 - while (__comp(__pivot, *__last))
1.1382 + while (__comp(__pivot, *__last)) {
1.1383 + _STLP_VERBOSE_ASSERT(!__comp(*__last, __pivot), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1384 --__last;
1.1385 + }
1.1386 if (!(__first < __last))
1.1387 return __first;
1.1388 iter_swap(__first, __last);
1.1389 @@ -899,17 +888,16 @@
1.1390 }
1.1391 }
1.1392
1.1393 -// sort() and its auxiliary functions.
1.1394 -
1.1395 -# define __stl_threshold 16
1.1396 +// sort() and its auxiliary functions.
1.1397 +#define __stl_threshold 16
1.1398
1.1399 template <class _RandomAccessIter, class _Tp, class _Compare>
1.1400 -void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
1.1401 +void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
1.1402 _Compare __comp) {
1.1403 - _STLP_PUSH_STACK_ITEM(_Tp, &__val)
1.1404 _RandomAccessIter __next = __last;
1.1405 - --__next;
1.1406 + --__next;
1.1407 while (__comp(__val, *__next)) {
1.1408 + _STLP_VERBOSE_ASSERT(!__comp(*__next, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1409 *__last = *__next;
1.1410 __last = __next;
1.1411 --__next;
1.1412 @@ -918,10 +906,12 @@
1.1413 }
1.1414
1.1415 template <class _RandomAccessIter, class _Tp, class _Compare>
1.1416 -inline void __linear_insert(_RandomAccessIter __first,
1.1417 +inline void __linear_insert(_RandomAccessIter __first,
1.1418 _RandomAccessIter __last, _Tp __val, _Compare __comp) {
1.1419 - _STLP_PUSH_STACK_ITEM(_Tp, &__val)
1.1420 + //*TY 12/26/1998 - added __val as a paramter
1.1421 + // _Tp __val = *__last; //*TY 12/26/1998 - __val supplied by caller
1.1422 if (__comp(__val, *__first)) {
1.1423 + _STLP_VERBOSE_ASSERT(!__comp(*__first, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1424 copy_backward(__first, __last, __last + 1);
1.1425 *__first = __val;
1.1426 }
1.1427 @@ -929,45 +919,45 @@
1.1428 __unguarded_linear_insert(__last, __val, __comp);
1.1429 }
1.1430
1.1431 -template <class _RandomAccessIter, class _Compare>
1.1432 +template <class _RandomAccessIter, class _Tp, class _Compare>
1.1433 void __insertion_sort(_RandomAccessIter __first,
1.1434 - _RandomAccessIter __last, _Compare __comp) {
1.1435 + _RandomAccessIter __last,
1.1436 + _Tp *, _Compare __comp) {
1.1437 if (__first == __last) return;
1.1438 for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1.1439 - __linear_insert(__first, __i, *__i, __comp); //*TY 12/26/1998 - supply *__i as __val
1.1440 + __linear_insert<_RandomAccessIter, _Tp, _Compare>(__first, __i, *__i, __comp); //*TY 12/26/1998 - supply *__i as __val
1.1441 }
1.1442
1.1443 template <class _RandomAccessIter, class _Tp, class _Compare>
1.1444 -void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
1.1445 +void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
1.1446 _RandomAccessIter __last,
1.1447 _Tp*, _Compare __comp) {
1.1448 for (_RandomAccessIter __i = __first; __i != __last; ++__i)
1.1449 - __unguarded_linear_insert(__i, _Tp(*__i), __comp);
1.1450 + __unguarded_linear_insert<_RandomAccessIter, _Tp, _Compare>(__i, *__i, __comp);
1.1451 }
1.1452
1.1453 template <class _RandomAccessIter, class _Compare>
1.1454 -inline void __unguarded_insertion_sort(_RandomAccessIter __first,
1.1455 +inline void __unguarded_insertion_sort(_RandomAccessIter __first,
1.1456 _RandomAccessIter __last,
1.1457 _Compare __comp) {
1.1458 __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
1.1459 }
1.1460
1.1461 template <class _RandomAccessIter, class _Compare>
1.1462 -void __final_insertion_sort(_RandomAccessIter __first,
1.1463 +void __final_insertion_sort(_RandomAccessIter __first,
1.1464 _RandomAccessIter __last, _Compare __comp) {
1.1465 if (__last - __first > __stl_threshold) {
1.1466 - __insertion_sort(__first, __first + __stl_threshold, __comp);
1.1467 + __insertion_sort(__first, __first + __stl_threshold, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1.1468 __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
1.1469 }
1.1470 else
1.1471 - __insertion_sort(__first, __last, __comp);
1.1472 + __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1.1473 }
1.1474
1.1475 template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
1.1476 void __introsort_loop(_RandomAccessIter __first,
1.1477 _RandomAccessIter __last, _Tp*,
1.1478 - _Size __depth_limit, _Compare __comp)
1.1479 -{
1.1480 + _Size __depth_limit, _Compare __comp) {
1.1481 while (__last - __first > __stl_threshold) {
1.1482 if (__depth_limit == 0) {
1.1483 partial_sort(__first, __last, __last, __comp);
1.1484 @@ -985,36 +975,40 @@
1.1485 }
1.1486 }
1.1487
1.1488 +_STLP_MOVE_TO_STD_NAMESPACE
1.1489 +
1.1490 template <class _RandomAccessIter>
1.1491 void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
1.1492 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.1493 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1494 if (__first != __last) {
1.1495 - __introsort_loop(__first, __last,
1.1496 - _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1497 - __lg(__last - __first) * 2, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)) );
1.1498 - __final_insertion_sort(__first, __last, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.1499 + _STLP_PRIV __introsort_loop(__first, __last,
1.1500 + _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1501 + _STLP_PRIV __lg(__last - __first) * 2,
1.1502 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.1503 + _STLP_PRIV __final_insertion_sort(__first, __last,
1.1504 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.1505 }
1.1506 }
1.1507
1.1508 template <class _RandomAccessIter, class _Compare>
1.1509 void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) {
1.1510 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.1511 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1512 if (__first != __last) {
1.1513 - __introsort_loop(__first, __last,
1.1514 - _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1515 - __lg(__last - __first) * 2,
1.1516 - __comp);
1.1517 - __final_insertion_sort(__first, __last, __comp);
1.1518 + _STLP_PRIV __introsort_loop(__first, __last,
1.1519 + _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1520 + _STLP_PRIV __lg(__last - __first) * 2, __comp);
1.1521 + _STLP_PRIV __final_insertion_sort(__first, __last, __comp);
1.1522 }
1.1523 }
1.1524
1.1525 // stable_sort() and its auxiliary functions.
1.1526 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1527
1.1528 template <class _RandomAccessIter, class _Compare>
1.1529 void __inplace_stable_sort(_RandomAccessIter __first,
1.1530 _RandomAccessIter __last, _Compare __comp) {
1.1531 if (__last - __first < 15) {
1.1532 - __insertion_sort(__first, __last, __comp);
1.1533 + __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1.1534 return;
1.1535 }
1.1536 _RandomAccessIter __middle = __first + (__last - __first) / 2;
1.1537 @@ -1029,7 +1023,7 @@
1.1538 template <class _RandomAccessIter1, class _RandomAccessIter2,
1.1539 class _Distance, class _Compare>
1.1540 void __merge_sort_loop(_RandomAccessIter1 __first,
1.1541 - _RandomAccessIter1 __last,
1.1542 + _RandomAccessIter1 __last,
1.1543 _RandomAccessIter2 __result, _Distance __step_size,
1.1544 _Compare __comp) {
1.1545 _Distance __two_step = 2 * __step_size;
1.1546 @@ -1050,22 +1044,22 @@
1.1547 }
1.1548
1.1549 const int __stl_chunk_size = 7;
1.1550 -
1.1551 +
1.1552 template <class _RandomAccessIter, class _Distance, class _Compare>
1.1553 -void __chunk_insertion_sort(_RandomAccessIter __first,
1.1554 +void __chunk_insertion_sort(_RandomAccessIter __first,
1.1555 _RandomAccessIter __last,
1.1556 - _Distance __chunk_size, _Compare __comp)
1.1557 -{
1.1558 + _Distance __chunk_size, _Compare __comp) {
1.1559 while (__last - __first >= __chunk_size) {
1.1560 - __insertion_sort(__first, __first + __chunk_size, __comp);
1.1561 + __insertion_sort(__first, __first + __chunk_size,
1.1562 + _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1.1563 __first += __chunk_size;
1.1564 }
1.1565 - __insertion_sort(__first, __last, __comp);
1.1566 + __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1.1567 }
1.1568
1.1569 template <class _RandomAccessIter, class _Pointer, class _Distance,
1.1570 class _Compare>
1.1571 -void __merge_sort_with_buffer(_RandomAccessIter __first,
1.1572 +void __merge_sort_with_buffer(_RandomAccessIter __first,
1.1573 _RandomAccessIter __last, _Pointer __buffer,
1.1574 _Distance*, _Compare __comp) {
1.1575 _Distance __len = __last - __first;
1.1576 @@ -1101,13 +1095,13 @@
1.1577 return copy_backward(__buffer, __buffer_end, __last);
1.1578 }
1.1579 else
1.1580 - return rotate(__first, __middle, __last);
1.1581 + return __rotate(__first, __middle, __last);
1.1582 }
1.1583
1.1584 template <class _BidirectionalIter, class _Distance, class _Pointer,
1.1585 class _Compare>
1.1586 -void __merge_adaptive(_BidirectionalIter __first,
1.1587 - _BidirectionalIter __middle,
1.1588 +void __merge_adaptive(_BidirectionalIter __first,
1.1589 + _BidirectionalIter __middle,
1.1590 _BidirectionalIter __last,
1.1591 _Distance __len1, _Distance __len2,
1.1592 _Pointer __buffer, _Distance __buffer_size,
1.1593 @@ -1130,7 +1124,7 @@
1.1594 __len11 = __len1 / 2;
1.1595 advance(__first_cut, __len11);
1.1596 __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
1.1597 - __len22 += distance(__middle, __second_cut);
1.1598 + __len22 += distance(__middle, __second_cut);
1.1599 }
1.1600 else {
1.1601 __len22 = __len2 / 2;
1.1602 @@ -1148,17 +1142,17 @@
1.1603 }
1.1604 }
1.1605
1.1606 -template <class _RandomAccessIter, class _Pointer, class _Distance,
1.1607 +template <class _RandomAccessIter, class _Pointer, class _Distance,
1.1608 class _Compare>
1.1609 -void __stable_sort_adaptive(_RandomAccessIter __first,
1.1610 +void __stable_sort_adaptive(_RandomAccessIter __first,
1.1611 _RandomAccessIter __last, _Pointer __buffer,
1.1612 _Distance __buffer_size, _Compare __comp) {
1.1613 _Distance __len = (__last - __first + 1) / 2;
1.1614 _RandomAccessIter __middle = __first + __len;
1.1615 if (__len > __buffer_size) {
1.1616 - __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
1.1617 + __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
1.1618 __comp);
1.1619 - __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
1.1620 + __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
1.1621 __comp);
1.1622 }
1.1623 else {
1.1624 @@ -1167,86 +1161,91 @@
1.1625 __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
1.1626 __comp);
1.1627 }
1.1628 - __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
1.1629 + __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
1.1630 _Distance(__last - __middle), __buffer, __buffer_size,
1.1631 __comp);
1.1632 }
1.1633
1.1634 template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
1.1635 void __stable_sort_aux(_RandomAccessIter __first,
1.1636 - _RandomAccessIter __last, _Tp*, _Distance*,
1.1637 - _Compare __comp) {
1.1638 -
1.1639 - typedef _Temporary_buffer<_RandomAccessIter, _Tp> _TmpBuf;
1.1640 - _TmpBuf __buf(__first, __last);
1.1641 - _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);
1.1642 -
1.1643 - if (__buf.begin() == 0)
1.1644 + _RandomAccessIter __last, _Tp*, _Distance*,
1.1645 + _Compare __comp) {
1.1646 + _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
1.1647 + if (buf.begin() == 0)
1.1648 __inplace_stable_sort(__first, __last, __comp);
1.1649 - else
1.1650 - __stable_sort_adaptive(__first, __last, __buf.begin(),
1.1651 - _Distance(__buf.size()),
1.1652 + else
1.1653 + __stable_sort_adaptive(__first, __last, buf.begin(),
1.1654 + _Distance(buf.size()),
1.1655 __comp);
1.1656 }
1.1657
1.1658 +_STLP_MOVE_TO_STD_NAMESPACE
1.1659 +
1.1660 template <class _RandomAccessIter>
1.1661 void stable_sort(_RandomAccessIter __first,
1.1662 - _RandomAccessIter __last) {
1.1663 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.1664 - __stable_sort_aux(__first, __last,
1.1665 - _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1666 - _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
1.1667 - __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.1668 + _RandomAccessIter __last) {
1.1669 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1670 + _STLP_PRIV __stable_sort_aux(__first, __last,
1.1671 + _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1672 + _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
1.1673 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.1674 }
1.1675
1.1676 template <class _RandomAccessIter, class _Compare>
1.1677 void stable_sort(_RandomAccessIter __first,
1.1678 - _RandomAccessIter __last, _Compare __comp) {
1.1679 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.1680 - __stable_sort_aux(__first, __last,
1.1681 - _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1682 - _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
1.1683 - __comp);
1.1684 + _RandomAccessIter __last, _Compare __comp) {
1.1685 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1686 + _STLP_PRIV __stable_sort_aux(__first, __last,
1.1687 + _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1688 + _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
1.1689 + __comp);
1.1690 }
1.1691
1.1692 // partial_sort, partial_sort_copy, and auxiliary functions.
1.1693 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1694
1.1695 template <class _RandomAccessIter, class _Tp, class _Compare>
1.1696 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
1.1697 _RandomAccessIter __last, _Tp*, _Compare __comp) {
1.1698 make_heap(__first, __middle, __comp);
1.1699 - for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
1.1700 - if (__comp(*__i, *__first))
1.1701 + for (_RandomAccessIter __i = __middle; __i < __last; ++__i) {
1.1702 + if (__comp(*__i, *__first)) {
1.1703 + _STLP_VERBOSE_ASSERT(!__comp(*__first, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1704 __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
1.1705 _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));
1.1706 + }
1.1707 + }
1.1708 sort_heap(__first, __middle, __comp);
1.1709 }
1.1710
1.1711 +_STLP_MOVE_TO_STD_NAMESPACE
1.1712
1.1713 template <class _RandomAccessIter>
1.1714 -void
1.1715 -partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, _RandomAccessIter __last) {
1.1716 - _STLP_DEBUG_CHECK(__check_range(__first, __middle))
1.1717 - _STLP_DEBUG_CHECK(__check_range(__middle, __last))
1.1718 - __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1719 - __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.1720 +void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
1.1721 + _RandomAccessIter __last) {
1.1722 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
1.1723 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
1.1724 + _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1725 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.1726 }
1.1727
1.1728 template <class _RandomAccessIter, class _Compare>
1.1729 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
1.1730 _RandomAccessIter __last, _Compare __comp) {
1.1731 - _STLP_DEBUG_CHECK(__check_range(__first, __middle))
1.1732 - _STLP_DEBUG_CHECK(__check_range(__middle, __last))
1.1733 - __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
1.1734 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
1.1735 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
1.1736 + _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
1.1737 }
1.1738
1.1739 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1740 +
1.1741 template <class _InputIter, class _RandomAccessIter, class _Compare,
1.1742 class _Distance, class _Tp>
1.1743 _RandomAccessIter __partial_sort_copy(_InputIter __first,
1.1744 - _InputIter __last,
1.1745 - _RandomAccessIter __result_first,
1.1746 - _RandomAccessIter __result_last,
1.1747 - _Compare __comp, _Distance*, _Tp*) {
1.1748 + _InputIter __last,
1.1749 + _RandomAccessIter __result_first,
1.1750 + _RandomAccessIter __result_last,
1.1751 + _Compare __comp, _Distance*, _Tp*) {
1.1752 if (__result_first == __result_last) return __result_last;
1.1753 _RandomAccessIter __result_real_last = __result_first;
1.1754 while(__first != __last && __result_real_last != __result_last) {
1.1755 @@ -1256,27 +1255,31 @@
1.1756 }
1.1757 make_heap(__result_first, __result_real_last, __comp);
1.1758 while (__first != __last) {
1.1759 - if (__comp(*__first, *__result_first))
1.1760 + if (__comp(*__first, *__result_first)) {
1.1761 + _STLP_VERBOSE_ASSERT(!__comp(*__result_first, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1762 __adjust_heap(__result_first, _Distance(0),
1.1763 _Distance(__result_real_last - __result_first),
1.1764 _Tp(*__first),
1.1765 __comp);
1.1766 + }
1.1767 ++__first;
1.1768 }
1.1769 sort_heap(__result_first, __result_real_last, __comp);
1.1770 return __result_real_last;
1.1771 }
1.1772
1.1773 +_STLP_MOVE_TO_STD_NAMESPACE
1.1774 +
1.1775 template <class _InputIter, class _RandomAccessIter>
1.1776 _RandomAccessIter
1.1777 partial_sort_copy(_InputIter __first, _InputIter __last,
1.1778 _RandomAccessIter __result_first, _RandomAccessIter __result_last) {
1.1779 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.1780 - _STLP_DEBUG_CHECK(__check_range(__result_first, __result_last))
1.1781 - return __partial_sort_copy(__first, __last, __result_first, __result_last,
1.1782 - __less(_STLP_VALUE_TYPE(__first, _InputIter)),
1.1783 - _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
1.1784 - _STLP_VALUE_TYPE(__first, _InputIter));
1.1785 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1786 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
1.1787 + return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
1.1788 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _InputIter)),
1.1789 + _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
1.1790 + _STLP_VALUE_TYPE(__first, _InputIter));
1.1791 }
1.1792
1.1793 template <class _InputIter, class _RandomAccessIter, class _Compare>
1.1794 @@ -1284,15 +1287,16 @@
1.1795 partial_sort_copy(_InputIter __first, _InputIter __last,
1.1796 _RandomAccessIter __result_first,
1.1797 _RandomAccessIter __result_last, _Compare __comp) {
1.1798 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.1799 - _STLP_DEBUG_CHECK(__check_range(__result_first, __result_last))
1.1800 - return __partial_sort_copy(__first, __last, __result_first, __result_last,
1.1801 - __comp,
1.1802 - _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
1.1803 - _STLP_VALUE_TYPE(__first, _InputIter));
1.1804 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.1805 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
1.1806 + return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
1.1807 + __comp,
1.1808 + _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
1.1809 + _STLP_VALUE_TYPE(__first, _InputIter));
1.1810 }
1.1811
1.1812 -// nth_element() and its auxiliary functions.
1.1813 +// nth_element() and its auxiliary functions.
1.1814 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1815
1.1816 template <class _RandomAccessIter, class _Tp, class _Compare>
1.1817 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1.1818 @@ -1301,42 +1305,44 @@
1.1819 _RandomAccessIter __cut =
1.1820 __unguarded_partition(__first, __last,
1.1821 _Tp(__median(*__first,
1.1822 - *(__first + (__last - __first)/2),
1.1823 + *(__first + (__last - __first)/2),
1.1824 *(__last - 1),
1.1825 __comp)),
1.1826 __comp);
1.1827 if (__cut <= __nth)
1.1828 __first = __cut;
1.1829 - else
1.1830 + else
1.1831 __last = __cut;
1.1832 }
1.1833 - __insertion_sort(__first, __last, __comp);
1.1834 + __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1.1835 }
1.1836
1.1837 +_STLP_MOVE_TO_STD_NAMESPACE
1.1838
1.1839 template <class _RandomAccessIter>
1.1840 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1.1841 _RandomAccessIter __last) {
1.1842 - _STLP_DEBUG_CHECK(__check_range(__first, __nth))
1.1843 - _STLP_DEBUG_CHECK(__check_range(__nth, __last))
1.1844 - __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1845 - __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.1846 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
1.1847 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
1.1848 + _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1.1849 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1.1850 }
1.1851
1.1852 template <class _RandomAccessIter, class _Compare>
1.1853 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1.1854 _RandomAccessIter __last, _Compare __comp) {
1.1855 - _STLP_DEBUG_CHECK(__check_range(__first, __nth))
1.1856 - _STLP_DEBUG_CHECK(__check_range(__nth, __last))
1.1857 - __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
1.1858 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
1.1859 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
1.1860 + _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
1.1861 }
1.1862
1.1863 // Binary search (lower_bound, upper_bound, equal_range, binary_search).
1.1864 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1865
1.1866 -template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
1.1867 -_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
1.1868 - const _Tp& __val, _Compare __comp, _Distance*)
1.1869 -{
1.1870 +template <class _ForwardIter, class _Tp,
1.1871 + class _Compare1, class _Compare2, class _Distance>
1.1872 +_ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1.1873 + _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
1.1874 _Distance __len = distance(__first, __last);
1.1875 _Distance __half;
1.1876
1.1877 @@ -1344,8 +1350,10 @@
1.1878 __half = __len >> 1;
1.1879 _ForwardIter __middle = __first;
1.1880 advance(__middle, __half);
1.1881 - if (__comp(__val, *__middle))
1.1882 + if (__comp2(__val, *__middle)) {
1.1883 + _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1884 __len = __half;
1.1885 + }
1.1886 else {
1.1887 __first = __middle;
1.1888 ++__first;
1.1889 @@ -1355,11 +1363,11 @@
1.1890 return __first;
1.1891 }
1.1892
1.1893 -template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
1.1894 +template <class _ForwardIter, class _Tp,
1.1895 + class _Compare1, class _Compare2, class _Distance>
1.1896 pair<_ForwardIter, _ForwardIter>
1.1897 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1.1898 - _Compare __comp, _Distance*)
1.1899 -{
1.1900 + _Compare1 __comp1, _Compare2 __comp2, _Distance* __dist) {
1.1901 _Distance __len = distance(__first, __last);
1.1902 _Distance __half;
1.1903
1.1904 @@ -1367,29 +1375,40 @@
1.1905 __half = __len >> 1;
1.1906 _ForwardIter __middle = __first;
1.1907 advance(__middle, __half);
1.1908 - if (__comp(*__middle, __val)) {
1.1909 + if (__comp1(*__middle, __val)) {
1.1910 + _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1911 __first = __middle;
1.1912 ++__first;
1.1913 __len = __len - __half - 1;
1.1914 }
1.1915 - else if (__comp(__val, *__middle))
1.1916 + else if (__comp2(__val, *__middle)) {
1.1917 + _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1918 __len = __half;
1.1919 + }
1.1920 else {
1.1921 - _ForwardIter __left = lower_bound(__first, __middle, __val, __comp);
1.1922 + _ForwardIter __left = __lower_bound(__first, __middle, __val, __comp1, __comp2, __dist);
1.1923 + //Small optim: If lower_bound haven't found an equivalent value
1.1924 + //there is no need to call upper_bound.
1.1925 + if (__comp1(*__left, __val)) {
1.1926 + _STLP_VERBOSE_ASSERT(!__comp2(__val, *__left), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1927 + return pair<_ForwardIter, _ForwardIter>(__left, __left);
1.1928 + }
1.1929 advance(__first, __len);
1.1930 - _ForwardIter __right = upper_bound(++__middle, __first, __val, __comp);
1.1931 + _ForwardIter __right = __upper_bound(++__middle, __first, __val, __comp1, __comp2, __dist);
1.1932 return pair<_ForwardIter, _ForwardIter>(__left, __right);
1.1933 }
1.1934 }
1.1935 return pair<_ForwardIter, _ForwardIter>(__first, __first);
1.1936 -}
1.1937 +}
1.1938 +
1.1939 +_STLP_MOVE_TO_STD_NAMESPACE
1.1940
1.1941 template <class _InputIter1, class _InputIter2, class _OutputIter>
1.1942 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
1.1943 _InputIter2 __first2, _InputIter2 __last2,
1.1944 _OutputIter __result) {
1.1945 - _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.1946 - _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.1947 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1.1948 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1.1949 while (__first1 != __last1 && __first2 != __last2) {
1.1950 if (*__first2 < *__first1) {
1.1951 *__result = *__first2;
1.1952 @@ -1409,10 +1428,11 @@
1.1953 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
1.1954 _InputIter2 __first2, _InputIter2 __last2,
1.1955 _OutputIter __result, _Compare __comp) {
1.1956 - _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.1957 - _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.1958 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1.1959 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1.1960 while (__first1 != __last1 && __first2 != __last2) {
1.1961 if (__comp(*__first2, *__first1)) {
1.1962 + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1963 *__result = *__first2;
1.1964 ++__first2;
1.1965 }
1.1966 @@ -1425,6 +1445,8 @@
1.1967 return copy(__first2, __last2, copy(__first1, __last1, __result));
1.1968 }
1.1969
1.1970 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.1971 +
1.1972 template <class _BidirectionalIter, class _Distance, class _Compare>
1.1973 void __merge_without_buffer(_BidirectionalIter __first,
1.1974 _BidirectionalIter __middle,
1.1975 @@ -1434,8 +1456,10 @@
1.1976 if (__len1 == 0 || __len2 == 0)
1.1977 return;
1.1978 if (__len1 + __len2 == 2) {
1.1979 - if (__comp(*__middle, *__first))
1.1980 + if (__comp(*__middle, *__first)) {
1.1981 + _STLP_VERBOSE_ASSERT(!__comp(*__first, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.1982 iter_swap(__first, __middle);
1.1983 + }
1.1984 return;
1.1985 }
1.1986 _BidirectionalIter __first_cut = __first;
1.1987 @@ -1455,7 +1479,7 @@
1.1988 __len11 +=distance(__first, __first_cut);
1.1989 }
1.1990 _BidirectionalIter __new_middle
1.1991 - = rotate(__first_cut, __middle, __second_cut);
1.1992 + = __rotate(__first_cut, __middle, __second_cut);
1.1993 __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
1.1994 __comp);
1.1995 __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
1.1996 @@ -1476,8 +1500,9 @@
1.1997 return copy_backward(__first1, __last1, __result);
1.1998 --__last1;
1.1999 --__last2;
1.2000 - while (true) {
1.2001 + for (;;) {
1.2002 if (__comp(*__last2, *__last1)) {
1.2003 + _STLP_VERBOSE_ASSERT(!__comp(*__last1, *__last2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2004 *--__result = *__last1;
1.2005 if (__first1 == __last1)
1.2006 return copy_backward(__first2, ++__last2, __result);
1.2007 @@ -1492,7 +1517,7 @@
1.2008 }
1.2009 }
1.2010
1.2011 -template <class _BidirectionalIter, class _Tp,
1.2012 +template <class _BidirectionalIter, class _Tp,
1.2013 class _Distance, class _Compare>
1.2014 inline void __inplace_merge_aux(_BidirectionalIter __first,
1.2015 _BidirectionalIter __middle,
1.2016 @@ -1501,10 +1526,7 @@
1.2017 _Distance __len1 = distance(__first, __middle);
1.2018 _Distance __len2 = distance(__middle, __last);
1.2019
1.2020 - typedef _Temporary_buffer<_BidirectionalIter, _Tp> _TmpBuf;
1.2021 - _TmpBuf __buf(__first, __last);
1.2022 - _STLP_PUSH_STACK_ITEM(_TmpBuf, &__buf);
1.2023 -
1.2024 + _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
1.2025 if (__buf.begin() == 0)
1.2026 __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
1.2027 else
1.2028 @@ -1513,32 +1535,35 @@
1.2029 __comp);
1.2030 }
1.2031
1.2032 +_STLP_MOVE_TO_STD_NAMESPACE
1.2033 +
1.2034 template <class _BidirectionalIter>
1.2035 void inplace_merge(_BidirectionalIter __first,
1.2036 - _BidirectionalIter __middle,
1.2037 - _BidirectionalIter __last) {
1.2038 - _STLP_DEBUG_CHECK(__check_range(__first, __middle))
1.2039 - _STLP_DEBUG_CHECK(__check_range(__middle, __last))
1.2040 + _BidirectionalIter __middle,
1.2041 + _BidirectionalIter __last) {
1.2042 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
1.2043 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
1.2044 if (__first == __middle || __middle == __last)
1.2045 return;
1.2046 - __inplace_merge_aux(__first, __middle, __last,
1.2047 - _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
1.2048 - __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
1.2049 + _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
1.2050 + _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
1.2051 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
1.2052 }
1.2053
1.2054 template <class _BidirectionalIter, class _Compare>
1.2055 void inplace_merge(_BidirectionalIter __first,
1.2056 - _BidirectionalIter __middle,
1.2057 - _BidirectionalIter __last, _Compare __comp) {
1.2058 - _STLP_DEBUG_CHECK(__check_range(__first, __middle))
1.2059 - _STLP_DEBUG_CHECK(__check_range(__middle, __last))
1.2060 + _BidirectionalIter __middle,
1.2061 + _BidirectionalIter __last, _Compare __comp) {
1.2062 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
1.2063 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
1.2064 if (__first == __middle || __middle == __last)
1.2065 return;
1.2066 - __inplace_merge_aux(__first, __middle, __last,
1.2067 - _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
1.2068 - __comp);
1.2069 + _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
1.2070 + _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
1.2071 + __comp);
1.2072 }
1.2073
1.2074 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.2075
1.2076 template <class _InputIter1, class _InputIter2, class _Compare>
1.2077 bool __includes(_InputIter1 __first1, _InputIter1 __last1,
1.2078 @@ -1546,9 +1571,11 @@
1.2079 _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.2080 _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.2081 while (__first1 != __last1 && __first2 != __last2)
1.2082 - if (__comp(*__first2, *__first1))
1.2083 + if (__comp(*__first2, *__first1)) {
1.2084 + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2085 return false;
1.2086 - else if(__comp(*__first1, *__first2))
1.2087 + }
1.2088 + else if (__comp(*__first1, *__first2))
1.2089 ++__first1;
1.2090 else
1.2091 ++__first1, ++__first2;
1.2092 @@ -1556,18 +1583,23 @@
1.2093 return __first2 == __last2;
1.2094 }
1.2095
1.2096 +_STLP_MOVE_TO_STD_NAMESPACE
1.2097 +
1.2098 template <class _InputIter1, class _InputIter2, class _Compare>
1.2099 bool includes(_InputIter1 __first1, _InputIter1 __last1,
1.2100 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
1.2101 - return __includes(__first1, __last1, __first2, __last2, __comp);
1.2102 + return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, __comp);
1.2103 }
1.2104
1.2105 template <class _InputIter1, class _InputIter2>
1.2106 bool includes(_InputIter1 __first1, _InputIter1 __last1,
1.2107 _InputIter2 __first2, _InputIter2 __last2) {
1.2108 - return __includes(__first1, __last1, __first2, __last2, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.2109 + return _STLP_PRIV __includes(__first1, __last1, __first2, __last2,
1.2110 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.2111 }
1.2112
1.2113 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.2114 +
1.2115 template <class _InputIter1, class _InputIter2, class _OutputIter,
1.2116 class _Compare>
1.2117 _OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,
1.2118 @@ -1577,10 +1609,12 @@
1.2119 _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.2120 while (__first1 != __last1 && __first2 != __last2) {
1.2121 if (__comp(*__first1, *__first2)) {
1.2122 + _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2123 *__result = *__first1;
1.2124 ++__first1;
1.2125 }
1.2126 else if (__comp(*__first2, *__first1)) {
1.2127 + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2128 *__result = *__first2;
1.2129 ++__first2;
1.2130 }
1.2131 @@ -1594,11 +1628,14 @@
1.2132 return copy(__first2, __last2, copy(__first1, __last1, __result));
1.2133 }
1.2134
1.2135 +_STLP_MOVE_TO_STD_NAMESPACE
1.2136 +
1.2137 template <class _InputIter1, class _InputIter2, class _OutputIter>
1.2138 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
1.2139 _InputIter2 __first2, _InputIter2 __last2,
1.2140 _OutputIter __result) {
1.2141 - return __set_union(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.2142 + return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result,
1.2143 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.2144 }
1.2145
1.2146 template <class _InputIter1, class _InputIter2, class _OutputIter,
1.2147 @@ -1606,9 +1643,11 @@
1.2148 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
1.2149 _InputIter2 __first2, _InputIter2 __last2,
1.2150 _OutputIter __result, _Compare __comp) {
1.2151 - return __set_union(__first1, __last1, __first2, __last2, __result, __comp);
1.2152 + return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, __comp);
1.2153 }
1.2154
1.2155 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.2156 +
1.2157 template <class _InputIter1, class _InputIter2, class _OutputIter,
1.2158 class _Compare>
1.2159 _OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,
1.2160 @@ -1617,8 +1656,10 @@
1.2161 _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.2162 _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.2163 while (__first1 != __last1 && __first2 != __last2)
1.2164 - if (__comp(*__first1, *__first2))
1.2165 + if (__comp(*__first1, *__first2)) {
1.2166 + _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2167 ++__first1;
1.2168 + }
1.2169 else if (__comp(*__first2, *__first1))
1.2170 ++__first2;
1.2171 else {
1.2172 @@ -1630,11 +1671,14 @@
1.2173 return __result;
1.2174 }
1.2175
1.2176 +_STLP_MOVE_TO_STD_NAMESPACE
1.2177 +
1.2178 template <class _InputIter1, class _InputIter2, class _OutputIter>
1.2179 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
1.2180 _InputIter2 __first2, _InputIter2 __last2,
1.2181 _OutputIter __result) {
1.2182 - return __set_intersection(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.2183 + return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result,
1.2184 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.2185 }
1.2186
1.2187 template <class _InputIter1, class _InputIter2, class _OutputIter,
1.2188 @@ -1642,18 +1686,21 @@
1.2189 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
1.2190 _InputIter2 __first2, _InputIter2 __last2,
1.2191 _OutputIter __result, _Compare __comp) {
1.2192 - return __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
1.2193 + return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
1.2194 }
1.2195
1.2196 -template <class _InputIter1, class _InputIter2, class _OutputIter,
1.2197 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.2198 +
1.2199 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.2200 class _Compare>
1.2201 _OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,
1.2202 - _InputIter2 __first2, _InputIter2 __last2,
1.2203 + _InputIter2 __first2, _InputIter2 __last2,
1.2204 _OutputIter __result, _Compare __comp) {
1.2205 _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.2206 _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.2207 while (__first1 != __last1 && __first2 != __last2)
1.2208 if (__comp(*__first1, *__first2)) {
1.2209 + _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2210 *__result = *__first1;
1.2211 ++__first1;
1.2212 ++__result;
1.2213 @@ -1667,31 +1714,36 @@
1.2214 return copy(__first1, __last1, __result);
1.2215 }
1.2216
1.2217 +_STLP_MOVE_TO_STD_NAMESPACE
1.2218 +
1.2219 template <class _InputIter1, class _InputIter2, class _OutputIter>
1.2220 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
1.2221 _InputIter2 __first2, _InputIter2 __last2,
1.2222 _OutputIter __result) {
1.2223 - return __set_difference(__first1, __last1, __first2, __last2, __result,
1.2224 - __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.2225 + return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result,
1.2226 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.2227 }
1.2228
1.2229 -template <class _InputIter1, class _InputIter2, class _OutputIter,
1.2230 +template <class _InputIter1, class _InputIter2, class _OutputIter,
1.2231 class _Compare>
1.2232 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
1.2233 - _InputIter2 __first2, _InputIter2 __last2,
1.2234 + _InputIter2 __first2, _InputIter2 __last2,
1.2235 _OutputIter __result, _Compare __comp) {
1.2236 - return __set_difference(__first1, __last1, __first2, __last2, __result, __comp);
1.2237 + return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, __comp);
1.2238 }
1.2239
1.2240 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.2241 +
1.2242 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
1.2243 -_OutputIter
1.2244 +_OutputIter
1.2245 __set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
1.2246 _InputIter2 __first2, _InputIter2 __last2,
1.2247 _OutputIter __result, _Compare __comp) {
1.2248 _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
1.2249 _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
1.2250 - while (__first1 != __last1 && __first2 != __last2)
1.2251 + while (__first1 != __last1 && __first2 != __last2) {
1.2252 if (__comp(*__first1, *__first2)) {
1.2253 + _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2254 *__result = *__first1;
1.2255 ++__first1;
1.2256 ++__result;
1.2257 @@ -1705,58 +1757,65 @@
1.2258 ++__first1;
1.2259 ++__first2;
1.2260 }
1.2261 + }
1.2262 return copy(__first2, __last2, copy(__first1, __last1, __result));
1.2263 }
1.2264
1.2265 +_STLP_MOVE_TO_STD_NAMESPACE
1.2266 +
1.2267 template <class _InputIter1, class _InputIter2, class _OutputIter>
1.2268 -_OutputIter
1.2269 +_OutputIter
1.2270 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
1.2271 _InputIter2 __first2, _InputIter2 __last2,
1.2272 _OutputIter __result) {
1.2273 - return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
1.2274 - __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.2275 + return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
1.2276 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1.2277 }
1.2278
1.2279 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
1.2280 -_OutputIter
1.2281 +_OutputIter
1.2282 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
1.2283 _InputIter2 __first2, _InputIter2 __last2,
1.2284 _OutputIter __result,
1.2285 _Compare __comp) {
1.2286 - return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
1.2287 + return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
1.2288 }
1.2289
1.2290 // min_element and max_element, with and without an explicitly supplied
1.2291 // comparison function.
1.2292
1.2293 -template <class _ForwardIter, class _Compare>
1.2294 -_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
1.2295 - _Compare __comp) {
1.2296 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.2297 +template <class _ForwardIter>
1.2298 +_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
1.2299 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.2300 if (__first == __last) return __first;
1.2301 _ForwardIter __result = __first;
1.2302 - while (++__first != __last)
1.2303 - if (__comp(*__result, *__first)) __result = __first;
1.2304 - return __result;
1.2305 -}
1.2306 -
1.2307 -template <class _ForwardIter>
1.2308 -_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
1.2309 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.2310 - if (__first == __last) return __first;
1.2311 - _ForwardIter __result = __first;
1.2312 - while (++__first != __last)
1.2313 + while (++__first != __last)
1.2314 if (*__result < *__first)
1.2315 __result = __first;
1.2316 return __result;
1.2317 }
1.2318
1.2319 +template <class _ForwardIter, class _Compare>
1.2320 +_ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
1.2321 + _Compare __comp) {
1.2322 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.2323 + if (__first == __last) return __first;
1.2324 + _ForwardIter __result = __first;
1.2325 + while (++__first != __last) {
1.2326 + if (__comp(*__result, *__first)) {
1.2327 + _STLP_VERBOSE_ASSERT(!__comp(*__first, *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2328 + __result = __first;
1.2329 + }
1.2330 + }
1.2331 + return __result;
1.2332 +}
1.2333 +
1.2334 template <class _ForwardIter>
1.2335 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
1.2336 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.2337 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.2338 if (__first == __last) return __first;
1.2339 _ForwardIter __result = __first;
1.2340 - while (++__first != __last)
1.2341 + while (++__first != __last)
1.2342 if (*__first < *__result)
1.2343 __result = __first;
1.2344 return __result;
1.2345 @@ -1764,17 +1823,23 @@
1.2346
1.2347 template <class _ForwardIter, class _Compare>
1.2348 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
1.2349 - _Compare __comp) {
1.2350 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.2351 + _Compare __comp) {
1.2352 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.2353 if (__first == __last) return __first;
1.2354 _ForwardIter __result = __first;
1.2355 - while (++__first != __last)
1.2356 - if (__comp(*__first, *__result)) __result = __first;
1.2357 + while (++__first != __last) {
1.2358 + if (__comp(*__first, *__result)) {
1.2359 + _STLP_VERBOSE_ASSERT(!__comp(*__result, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2360 + __result = __first;
1.2361 + }
1.2362 + }
1.2363 return __result;
1.2364 }
1.2365
1.2366 -// next_permutation and prev_permutation, with and without an explicitly
1.2367 +// next_permutation and prev_permutation, with and without an explicitly
1.2368 // supplied comparison function.
1.2369 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.2370 +
1.2371 template <class _BidirectionalIter, class _Compare>
1.2372 bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1.2373 _Compare __comp) {
1.2374 @@ -1792,9 +1857,9 @@
1.2375 _BidirectionalIter __ii = __i;
1.2376 --__i;
1.2377 if (__comp(*__i, *__ii)) {
1.2378 + _STLP_VERBOSE_ASSERT(!__comp(*__ii, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2379 _BidirectionalIter __j = __last;
1.2380 - while (!__comp(*__i, *--__j))
1.2381 - {}
1.2382 + while (!__comp(*__i, *--__j)) {}
1.2383 iter_swap(__i, __j);
1.2384 reverse(__ii, __last);
1.2385 return true;
1.2386 @@ -1804,27 +1869,32 @@
1.2387 return false;
1.2388 }
1.2389 }
1.2390 -#if defined(_STLP_NEED_UNREACHABLE_RETURN)
1.2391 - return 0;
1.2392 +#if defined (_STLP_NEED_UNREACHABLE_RETURN)
1.2393 + return false;
1.2394 #endif
1.2395 }
1.2396
1.2397 +_STLP_MOVE_TO_STD_NAMESPACE
1.2398 +
1.2399 template <class _BidirectionalIter>
1.2400 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
1.2401 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.2402 - return __next_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
1.2403 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.2404 + return _STLP_PRIV __next_permutation(__first, __last,
1.2405 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
1.2406 }
1.2407
1.2408 template <class _BidirectionalIter, class _Compare>
1.2409 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1.2410 _Compare __comp) {
1.2411 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.2412 - return __next_permutation(__first, __last, __comp);
1.2413 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.2414 + return _STLP_PRIV __next_permutation(__first, __last, __comp);
1.2415 }
1.2416
1.2417 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.2418 +
1.2419 template <class _BidirectionalIter, class _Compare>
1.2420 bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1.2421 - _Compare __comp) {
1.2422 + _Compare __comp) {
1.2423 if (__first == __last)
1.2424 return false;
1.2425 _BidirectionalIter __i = __first;
1.2426 @@ -1838,9 +1908,9 @@
1.2427 _BidirectionalIter __ii = __i;
1.2428 --__i;
1.2429 if (__comp(*__ii, *__i)) {
1.2430 + _STLP_VERBOSE_ASSERT(!__comp(*__i, *__ii), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2431 _BidirectionalIter __j = __last;
1.2432 - while (!__comp(*--__j, *__i))
1.2433 - {}
1.2434 + while (!__comp(*--__j, *__i)) {}
1.2435 iter_swap(__i, __j);
1.2436 reverse(__ii, __last);
1.2437 return true;
1.2438 @@ -1850,83 +1920,91 @@
1.2439 return false;
1.2440 }
1.2441 }
1.2442 -#if defined(_STLP_NEED_UNREACHABLE_RETURN)
1.2443 - return 0;
1.2444 +#if defined (_STLP_NEED_UNREACHABLE_RETURN)
1.2445 + return false;
1.2446 #endif
1.2447 }
1.2448
1.2449 +_STLP_MOVE_TO_STD_NAMESPACE
1.2450 +
1.2451 template <class _BidirectionalIter>
1.2452 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
1.2453 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.2454 - return __prev_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
1.2455 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.2456 + return _STLP_PRIV __prev_permutation(__first, __last,
1.2457 + _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
1.2458 }
1.2459
1.2460 template <class _BidirectionalIter, class _Compare>
1.2461 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1.2462 _Compare __comp) {
1.2463 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.2464 - return __prev_permutation(__first, __last, __comp);
1.2465 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.2466 + return _STLP_PRIV __prev_permutation(__first, __last, __comp);
1.2467 }
1.2468
1.2469 -# ifndef _STLP_NO_EXTENSIONS
1.2470 +#if !defined (_STLP_NO_EXTENSIONS)
1.2471
1.2472 // is_heap, a predicate testing whether or not a range is
1.2473 // a heap. This function is an extension, not part of the C++
1.2474 // standard.
1.2475 -
1.2476 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.2477
1.2478 template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
1.2479 bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
1.2480 - _Distance __n)
1.2481 -{
1.2482 + _Distance __n) {
1.2483 _Distance __parent = 0;
1.2484 for (_Distance __child = 1; __child < __n; ++__child) {
1.2485 - if (__comp(__first[__parent], __first[__child]))
1.2486 + if (__comp(__first[__parent], __first[__child])) {
1.2487 + _STLP_VERBOSE_ASSERT(!__comp(__first[__child], __first[__parent]), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2488 return false;
1.2489 + }
1.2490 if ((__child & 1) == 0)
1.2491 ++__parent;
1.2492 }
1.2493 return true;
1.2494 }
1.2495
1.2496 +_STLP_MOVE_TO_STD_NAMESPACE
1.2497 +
1.2498 template <class _RandomAccessIter>
1.2499 -bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
1.2500 -{
1.2501 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.2502 - return __is_heap(__first, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first);
1.2503 +bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) {
1.2504 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.2505 + return _STLP_PRIV __is_heap(__first, _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first);
1.2506 }
1.2507
1.2508 template <class _RandomAccessIter, class _StrictWeakOrdering>
1.2509 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
1.2510 - _StrictWeakOrdering __comp)
1.2511 -{
1.2512 - _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.2513 - return __is_heap(__first, __comp, __last - __first);
1.2514 + _StrictWeakOrdering __comp) {
1.2515 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1.2516 + return _STLP_PRIV __is_heap(__first, __comp, __last - __first);
1.2517 }
1.2518
1.2519
1.2520 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.2521 +
1.2522 template <class _ForwardIter, class _StrictWeakOrdering>
1.2523 bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
1.2524 - _StrictWeakOrdering __comp)
1.2525 -{
1.2526 + _StrictWeakOrdering __comp) {
1.2527 _STLP_DEBUG_CHECK(__check_range(__first, __last))
1.2528 if (__first == __last)
1.2529 return true;
1.2530
1.2531 _ForwardIter __next = __first;
1.2532 for (++__next; __next != __last; __first = __next, ++__next) {
1.2533 - if (__comp(*__next, *__first))
1.2534 + if (__comp(*__next, *__first)) {
1.2535 + _STLP_VERBOSE_ASSERT(!__comp(*__first, *__next), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.2536 return false;
1.2537 + }
1.2538 }
1.2539
1.2540 return true;
1.2541 }
1.2542
1.2543 -# endif /* _STLP_NO_EXTENSIONS */
1.2544 +_STLP_MOVE_TO_STD_NAMESPACE
1.2545 +#endif /* _STLP_NO_EXTENSIONS */
1.2546
1.2547 _STLP_END_NAMESPACE
1.2548
1.2549 -# undef __stl_threshold
1.2550 +#undef __stl_threshold
1.2551
1.2552 #endif /* _STLP_ALGO_C */
1.2553 // Local Variables: