include/c++/stlport/stl/_algo.c

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Copyright (c) 1996,1997
   7  * Silicon Graphics Computer Systems, Inc.
   8  *
   9  * Copyright (c) 1997
  10  * Moscow Center for SPARC Technology
  11  *
  12  * Copyright (c) 1999
  13  * Boris Fomitchev
  14  *
  15  * This material is provided "as is", with absolutely no warranty expressed
  16  * or implied. Any use is at your own risk.
  17  *
  18  * Permission to use or copy this software for any purpose is hereby granted
  19  * without fee, provided the above notices are retained on all copies.
  20  * Permission to modify the code and to distribute modified code is granted,
  21  * provided the above notices are retained, and a notice that the code was
  22  * modified is included with the above copyright notice.
  23  *
  24  */
  25
  26 #ifndef _STLP_ALGO_C
  27 #define _STLP_ALGO_C
  28
  29 #if !defined (_STLP_INTERNAL_ALGO_H)
  30 #  include <stl/_algo.h>
  31 #endif
  32
  33 #ifndef _STLP_INTERNAL_TEMPBUF_H
  34 #  include <stl/_tempbuf.h>
  35 #endif
  36
  37 _STLP_BEGIN_NAMESPACE
  38
  39 _STLP_MOVE_TO_PRIV_NAMESPACE
  40
  41 template <class _BidirectionalIter, class _Distance, class _Compare>
  42 void __merge_without_buffer(_BidirectionalIter __first,
  43                             _BidirectionalIter __middle,
  44                             _BidirectionalIter __last,
  45                             _Distance __len1, _Distance __len2,
  46                             _Compare __comp);
  47
  48
  49 template <class _BidirectionalIter1, class _BidirectionalIter2,
  50           class _BidirectionalIter3, class _Compare>
  51 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
  52                                      _BidirectionalIter1 __last1,
  53                                      _BidirectionalIter2 __first2,
  54                                      _BidirectionalIter2 __last2,
  55                                      _BidirectionalIter3 __result,
  56                                      _Compare __comp);
  57
  58 template <class _Tp>
  59 #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
  60 inline
  61 #endif
  62 const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
  63   if (__a < __b)
  64     if (__b < __c)
  65       return __b;
  66     else if (__a < __c)
  67       return __c;
  68     else
  69       return __a;
  70   else if (__a < __c)
  71     return __a;
  72   else if (__b < __c)
  73     return __c;
  74   else
  75     return __b;
  76 }
  77
  78 template <class _Tp, class _Compare>
  79 #if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
  80 inline
  81 #endif
  82 const _Tp&
  83 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
  84   if (__comp(__a, __b)) {
  85     _STLP_VERBOSE_ASSERT(!__comp(__b, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  86     if (__comp(__b, __c)) {
  87       _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  88       return __b;
  89     }
  90     else if (__comp(__a, __c)) {
  91       _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  92       return __c;
  93     }
  94     else
  95       return __a;
  96   }
  97   else if (__comp(__a, __c)) {
  98     _STLP_VERBOSE_ASSERT(!__comp(__c, __a), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  99     return __a;
 100   }
 101   else if (__comp(__b, __c)) {
 102     _STLP_VERBOSE_ASSERT(!__comp(__c, __b), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
 103     return __c;
 104   }
 105   else
 106     return __b;
 107 }
 108
 109 _STLP_MOVE_TO_STD_NAMESPACE
 110
 111 template <class _ForwardIter1, class _ForwardIter2>
 112 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
 113                      _ForwardIter2 __first2, _ForwardIter2 __last2) {
 114   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
 115   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
 116   // Test for empty ranges
 117   if (__first1 == __last1 || __first2 == __last2)
 118     return __first1;
 119
 120   // Test for a pattern of length 1.
 121   _ForwardIter2 __p1(__first2);
 122
 123   if ( ++__p1 == __last2 )
 124     return find(__first1, __last1, *__first2);
 125
 126   // General case.
 127
 128   for ( ; ; ) { // __first1 != __last1 will be checked in find below
 129     __first1 = find(__first1, __last1, *__first2);
 130     if (__first1 == __last1)
 131       return __last1;
 132
 133     _ForwardIter2 __p = __p1;
 134     _ForwardIter1 __current = __first1;
 135     if (++__current == __last1)
 136       return __last1;
 137
 138     while (*__current == *__p) {
 139       if (++__p == __last2)
 140         return __first1;
 141       if (++__current == __last1)
 142         return __last1;
 143     }
 144
 145     ++__first1;
 146   }
 147   return __first1;
 148 }
 149
 150 _STLP_MOVE_TO_PRIV_NAMESPACE
 151
 152 template <class _RandomAccessIter, class _Integer, class _Tp,
 153           class _BinaryPred, class _Distance>
 154 _RandomAccessIter __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
 155                              _Integer __count, const _Tp& __val, _BinaryPred __pred,
 156                              _Distance*, const random_access_iterator_tag &)
 157 {
 158   _Distance __tailSize = __last - __first;
 159   const _Distance __pattSize = __count;
 160   const _Distance __skipOffset = __pattSize - 1;
 161   _RandomAccessIter __backTrack;
 162   _Distance __remainder, __prevRemainder;
 163
 164   for ( _RandomAccessIter __lookAhead = __first + __skipOffset; __tailSize >= __pattSize; __lookAhead += __pattSize ) { // the main loop...
 165     //__lookAhead here is always pointing to the last element of next possible match.
 166     __tailSize -= __pattSize;
 167
 168     while ( !__pred(*__lookAhead, __val) ) { // the skip loop...
 169       if (__tailSize < __pattSize)
 170         return __last;
 171
 172       __lookAhead += __pattSize;
 173       __tailSize -= __pattSize;
 174     }
 175
 176     if ( __skipOffset == 0 ) {
 177       return (__lookAhead - __skipOffset); //Success
 178     }
 179
 180     __remainder = __skipOffset;
 181
 182     for (__backTrack = __lookAhead; __pred(*--__backTrack, __val); ) {
 183       if (--__remainder == 0)
 184         return (__lookAhead - __skipOffset); //Success
 185     }
 186
 187     if (__remainder > __tailSize)
 188       return __last; //failure
 189
 190     __lookAhead += __remainder;
 191     __tailSize -= __remainder;
 192
 193     while ( __pred(*__lookAhead, __val) ) {
 194       __prevRemainder = __remainder;
 195       __backTrack = __lookAhead;
 196
 197       do {
 198         if (--__remainder == 0)
 199           return (__lookAhead - __skipOffset); //Success
 200       } while (__pred(*--__backTrack, __val));
 201
 202       //adjust remainder for next comparison
 203       __remainder += __pattSize - __prevRemainder;
 204
 205       if (__remainder > __tailSize)
 206         return __last; //failure
 207
 208       __lookAhead += __remainder;
 209       __tailSize -= __remainder;
 210     }
 211
 212     //__lookAhead here is always pointing to the element of the last mismatch.
 213   }
 214
 215   return __last; //failure
 216 }
 217
 218 template <class _ForwardIter, class _Integer, class _Tp,
 219           class _Distance, class _BinaryPred>
 220 _ForwardIter __search_n(_ForwardIter __first, _ForwardIter __last,
 221                         _Integer __count, const _Tp& __val, _BinaryPred __pred,
 222                         _Distance*, const forward_iterator_tag &) {
 223   for (; (__first != __last) && !__pred(*__first, __val); ++__first) {}
 224   while (__first != __last) {
 225     _Integer __n = __count - 1;
 226     _ForwardIter __i = __first;
 227     ++__i;
 228     while (__i != __last && __n != 0 && __pred(*__i, __val)) {
 229       ++__i;
 230       --__n;
 231     }
 232     if (__n == 0)
 233       return __first;
 234     else if (__i != __last)
 235       for (__first = ++__i; (__first != __last) && !__pred(*__first, __val); ++__first) {}
 236     else
 237       break;
 238   }
 239   return __last;
 240 }
 241
 242 _STLP_MOVE_TO_STD_NAMESPACE
 243
 244 // search_n.  Search for __count consecutive copies of __val.
 245 template <class _ForwardIter, class _Integer, class _Tp>
 246 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
 247                       _Integer __count, const _Tp& __val) {
 248   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 249   if (__count <= 0)
 250     return __first;
 251   if (__count == 1)
 252     //We use find when __count == 1 to use potential find overload.
 253     return find(__first, __last, __val);
 254   return _STLP_PRIV __search_n(__first, __last, __count, __val, equal_to<_Tp>(),
 255                                _STLP_DISTANCE_TYPE(__first, _ForwardIter),
 256                                _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
 257 }
 258
 259 template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
 260 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
 261                       _Integer __count, const _Tp& __val,
 262                       _BinaryPred __binary_pred) {
 263   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 264   if (__count <= 0)
 265     return __first;
 266   return _STLP_PRIV __search_n(__first, __last, __count, __val, __binary_pred,
 267                                _STLP_DISTANCE_TYPE(__first, _ForwardIter),
 268                                _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
 269 }
 270
 271 template <class _ForwardIter1, class _ForwardIter2>
 272 _ForwardIter1
 273 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
 274          _ForwardIter2 __first2, _ForwardIter2 __last2) {
 275   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
 276   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
 277   return _STLP_PRIV __find_end(__first1, __last1, __first2, __last2,
 278 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 279                                _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
 280                                _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
 281 #else
 282                                forward_iterator_tag(),
 283                                forward_iterator_tag(),
 284 #endif
 285                                _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))
 286     );
 287 }
 288
 289 // unique and unique_copy
 290 _STLP_MOVE_TO_PRIV_NAMESPACE
 291
 292 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,
 293           class _Tp>
 294 _STLP_INLINE_LOOP _OutputIterator
 295 __unique_copy(_InputIterator __first, _InputIterator __last,
 296               _OutputIterator __result,
 297               _BinaryPredicate __binary_pred, _Tp*) {
 298   _Tp __val = *__first;
 299   *__result = __val;
 300   while (++__first != __last)
 301     if (!__binary_pred(__val, *__first)) {
 302       __val = *__first;
 303       *++__result = __val;
 304     }
 305   return ++__result;
 306 }
 307
 308 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
 309 inline _OutputIter
 310 __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
 311               _BinaryPredicate __binary_pred, const output_iterator_tag &) {
 312   return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred,
 313                                   _STLP_VALUE_TYPE(__first, _InputIter));
 314 }
 315
 316 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
 317 _STLP_INLINE_LOOP _ForwardIter
 318 __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result,
 319               _BinaryPredicate __binary_pred, const forward_iterator_tag &) {
 320   *__result = *__first;
 321   while (++__first != __last)
 322     if (!__binary_pred(*__result, *__first)) *++__result = *__first;
 323   return ++__result;
 324 }
 325
 326 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
 327 template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate>
 328 inline _BidirectionalIterator
 329 __unique_copy(_InputIterator __first, _InputIterator __last,
 330               _BidirectionalIterator __result, _BinaryPredicate __binary_pred,
 331               const bidirectional_iterator_tag &) {
 332   return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
 333 }
 334
 335 template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate>
 336 inline _RandomAccessIterator
 337 __unique_copy(_InputIterator __first, _InputIterator __last,
 338               _RandomAccessIterator __result, _BinaryPredicate __binary_pred,
 339               const random_access_iterator_tag &) {
 340   return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
 341 }
 342 #endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */
 343
 344 _STLP_MOVE_TO_STD_NAMESPACE
 345
 346 template <class _InputIter, class _OutputIter>
 347 _OutputIter
 348 unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
 349   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 350   if (__first == __last) return __result;
 351   return _STLP_PRIV __unique_copy(__first, __last, __result,
 352                                   _STLP_PRIV __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),
 353                                   _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
 354 }
 355
 356 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
 357 _OutputIter
 358 unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
 359             _BinaryPredicate __binary_pred) {
 360   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 361   if (__first == __last) return __result;
 362   return _STLP_PRIV __unique_copy(__first, __last, __result, __binary_pred,
 363                                   _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
 364 }
 365
 366 // rotate and rotate_copy, and their auxiliary functions
 367 _STLP_MOVE_TO_PRIV_NAMESPACE
 368
 369 template <class _ForwardIter, class _Distance>
 370 _ForwardIter __rotate_aux(_ForwardIter __first,
 371                           _ForwardIter __middle,
 372                           _ForwardIter __last,
 373                           _Distance*,
 374                           const forward_iterator_tag &) {
 375   if (__first == __middle)
 376     return __last;
 377   if (__last  == __middle)
 378     return __first;
 379
 380   _ForwardIter __first2 = __middle;
 381   do {
 382     _STLP_STD::swap(*__first++, *__first2++);
 383     if (__first == __middle)
 384       __middle = __first2;
 385   } while (__first2 != __last);
 386
 387   _ForwardIter __new_middle = __first;
 388
 389   __first2 = __middle;
 390
 391   while (__first2 != __last) {
 392     _STLP_STD::swap (*__first++, *__first2++);
 393     if (__first == __middle)
 394       __middle = __first2;
 395     else if (__first2 == __last)
 396       __first2 = __middle;
 397   }
 398
 399   return __new_middle;
 400 }
 401
 402 template <class _BidirectionalIter, class _Distance>
 403 _BidirectionalIter __rotate_aux(_BidirectionalIter __first,
 404                                 _BidirectionalIter __middle,
 405                                 _BidirectionalIter __last,
 406                                 _Distance*,
 407                                 const bidirectional_iterator_tag &) {
 408   if (__first == __middle)
 409     return __last;
 410   if (__last  == __middle)
 411     return __first;
 412
 413   _STLP_PRIV __reverse(__first,  __middle, bidirectional_iterator_tag());
 414   _STLP_PRIV __reverse(__middle, __last,   bidirectional_iterator_tag());
 415
 416   while (__first != __middle && __middle != __last)
 417     _STLP_STD::swap(*__first++, *--__last);
 418
 419   if (__first == __middle) {
 420     _STLP_PRIV __reverse(__middle, __last,   bidirectional_iterator_tag());
 421     return __last;
 422   }
 423   else {
 424     _STLP_PRIV __reverse(__first,  __middle, bidirectional_iterator_tag());
 425     return __first;
 426   }
 427 }
 428
 429 // rotate and rotate_copy, and their auxiliary functions
 430 template <class _EuclideanRingElement>
 431 _STLP_INLINE_LOOP
 432 _EuclideanRingElement __gcd(_EuclideanRingElement __m,
 433                             _EuclideanRingElement __n) {
 434   while (__n != 0) {
 435     _EuclideanRingElement __t = __m % __n;
 436     __m = __n;
 437     __n = __t;
 438   }
 439   return __m;
 440 }
 441
 442 template <class _RandomAccessIter, class _Distance, class _Tp>
 443 _RandomAccessIter __rotate_aux(_RandomAccessIter __first,
 444                                _RandomAccessIter __middle,
 445                                _RandomAccessIter __last,
 446                                _Distance *, _Tp *) {
 447
 448   _Distance __n = __last   - __first;
 449   _Distance __k = __middle - __first;
 450   _Distance __l = __n - __k;
 451   _RandomAccessIter __result = __first + (__last - __middle);
 452
 453   if (__k == 0)  /* __first == middle */
 454     return __last;
 455
 456   if (__k == __l) {
 457     _STLP_STD::swap_ranges(__first, __middle, __middle);
 458     return __result;
 459   }
 460
 461   _Distance __d = _STLP_PRIV __gcd(__n, __k);
 462
 463   for (_Distance __i = 0; __i < __d; __i++) {
 464     _Tp __tmp = *__first;
 465     _RandomAccessIter __p = __first;
 466
 467     if (__k < __l) {
 468       for (_Distance __j = 0; __j < __l/__d; __j++) {
 469         if (__p > __first + __l) {
 470           *__p = *(__p - __l);
 471           __p -= __l;
 472         }
 473
 474         *__p = *(__p + __k);
 475         __p += __k;
 476       }
 477     }
 478
 479     else {
 480       for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
 481         if (__p < __last - __k) {
 482           *__p = *(__p + __k);
 483           __p += __k;
 484         }
 485
 486         *__p = * (__p - __l);
 487         __p -= __l;
 488       }
 489     }
 490
 491     *__p = __tmp;
 492     ++__first;
 493   }
 494
 495   return __result;
 496 }
 497
 498 template <class _RandomAccessIter, class _Distance>
 499 inline _RandomAccessIter
 500 __rotate_aux(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,
 501              _Distance * __dis, const random_access_iterator_tag &) {
 502   return _STLP_PRIV __rotate_aux(__first, __middle, __last,
 503                                  __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));
 504 }
 505
 506 template <class _ForwardIter>
 507 _ForwardIter
 508 __rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
 509   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
 510   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
 511   return __rotate_aux(__first, __middle, __last,
 512                       _STLP_DISTANCE_TYPE(__first, _ForwardIter),
 513                       _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
 514 }
 515
 516 _STLP_MOVE_TO_STD_NAMESPACE
 517
 518 template <class _ForwardIter>
 519 void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
 520   _STLP_PRIV __rotate(__first, __middle, __last);
 521 }
 522
 523 // Return a random number in the range [0, __n).  This function encapsulates
 524 // whether we're using rand (part of the standard C library) or lrand48
 525 // (not standard, but a much better choice whenever it's available).
 526 _STLP_MOVE_TO_PRIV_NAMESPACE
 527
 528 template <class _Distance>
 529 inline _Distance __random_number(_Distance __n) {
 530 #ifdef _STLP_NO_DRAND48
 531   return rand() % __n;
 532 #else
 533   return lrand48() % __n;
 534 #endif
 535 }
 536
 537 _STLP_MOVE_TO_STD_NAMESPACE
 538
 539 template <class _RandomAccessIter>
 540 void random_shuffle(_RandomAccessIter __first,
 541                     _RandomAccessIter __last) {
 542   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 543   if (__first == __last) return;
 544   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
 545     iter_swap(__i, __first + _STLP_PRIV __random_number((__i - __first) + 1));
 546 }
 547
 548 template <class _RandomAccessIter, class _RandomNumberGenerator>
 549 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
 550                     _RandomNumberGenerator &__rand) {
 551   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 552   if (__first == __last) return;
 553   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
 554     iter_swap(__i, __first + __rand((__i - __first) + 1));
 555 }
 556
 557 #if !defined (_STLP_NO_EXTENSIONS)
 558 // random_sample and random_sample_n (extensions, not part of the standard).
 559 template <class _ForwardIter, class _OutputIter, class _Distance>
 560 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
 561                             _OutputIter __out_ite, const _Distance __n) {
 562   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 563   _Distance __remaining = _STLP_STD::distance(__first, __last);
 564   _Distance __m = (min) (__n, __remaining);
 565
 566   while (__m > 0) {
 567     if (_STLP_PRIV __random_number(__remaining) < __m) {
 568       *__out_ite = *__first;
 569       ++__out_ite;
 570       --__m;
 571     }
 572
 573     --__remaining;
 574     ++__first;
 575   }
 576   return __out_ite;
 577 }
 578
 579
 580 template <class _ForwardIter, class _OutputIter, class _Distance,
 581           class _RandomNumberGenerator>
 582 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
 583                             _OutputIter __out_ite, const _Distance __n,
 584                             _RandomNumberGenerator& __rand) {
 585   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 586   _Distance __remaining = _STLP_STD::distance(__first, __last);
 587   _Distance __m = (min) (__n, __remaining);
 588
 589   while (__m > 0) {
 590     if (__rand(__remaining) < __m) {
 591       *__out_ite = *__first;
 592       ++__out_ite;
 593       --__m;
 594     }
 595
 596     --__remaining;
 597     ++__first;
 598   }
 599   return __out_ite;
 600 }
 601
 602 _STLP_MOVE_TO_PRIV_NAMESPACE
 603
 604 template <class _InputIter, class _RandomAccessIter, class _Distance>
 605 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
 606                                   _RandomAccessIter __out_ite,
 607                                   const _Distance __n) {
 608   _Distance __m = 0;
 609   _Distance __t = __n;
 610   for ( ; __first != __last && __m < __n; ++__m, ++__first)
 611     __out_ite[__m] = *__first;
 612
 613   while (__first != __last) {
 614     ++__t;
 615     _Distance __M = __random_number(__t);
 616     if (__M < __n)
 617       __out_ite[__M] = *__first;
 618     ++__first;
 619   }
 620
 621   return __out_ite + __m;
 622 }
 623
 624 template <class _InputIter, class _RandomAccessIter,
 625           class _RandomNumberGenerator, class _Distance>
 626 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
 627                                   _RandomAccessIter __out_ite,
 628                                   _RandomNumberGenerator& __rand,
 629                                   const _Distance __n) {
 630   _Distance __m = 0;
 631   _Distance __t = __n;
 632   for ( ; __first != __last && __m < __n; ++__m, ++__first)
 633     __out_ite[__m] = *__first;
 634
 635   while (__first != __last) {
 636     ++__t;
 637     _Distance __M = __rand(__t);
 638     if (__M < __n)
 639       __out_ite[__M] = *__first;
 640     ++__first;
 641   }
 642
 643   return __out_ite + __m;
 644 }
 645
 646 _STLP_MOVE_TO_STD_NAMESPACE
 647
 648 template <class _InputIter, class _RandomAccessIter>
 649 _RandomAccessIter
 650 random_sample(_InputIter __first, _InputIter __last,
 651               _RandomAccessIter __out_first, _RandomAccessIter __out_last) {
 652   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 653   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
 654   return _STLP_PRIV __random_sample(__first, __last,
 655                                     __out_first, __out_last - __out_first);
 656 }
 657
 658 template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>
 659 _RandomAccessIter
 660 random_sample(_InputIter __first, _InputIter __last,
 661               _RandomAccessIter __out_first, _RandomAccessIter __out_last,
 662               _RandomNumberGenerator& __rand) {
 663   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 664   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__out_first, __out_last))
 665   return _STLP_PRIV __random_sample(__first, __last,
 666                                     __out_first, __rand,
 667                                     __out_last - __out_first);
 668 }
 669
 670 #endif /* _STLP_NO_EXTENSIONS */
 671
 672 // partition, stable_partition, and their auxiliary functions
 673 _STLP_MOVE_TO_PRIV_NAMESPACE
 674
 675 template <class _ForwardIter, class _Predicate>
 676 _STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,
 677                                            _ForwardIter __last,
 678                                            _Predicate   __pred,
 679                                            const forward_iterator_tag &) {
 680   if (__first == __last) return __first;
 681
 682   while (__pred(*__first))
 683     if (++__first == __last) return __first;
 684
 685   _ForwardIter __next = __first;
 686
 687   while (++__next != __last) {
 688     if (__pred(*__next)) {
 689       _STLP_STD::swap(*__first, *__next);
 690       ++__first;
 691     }
 692   }
 693   return __first;
 694 }
 695
 696 template <class _BidirectionalIter, class _Predicate>
 697 _STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,
 698                                                  _BidirectionalIter __last,
 699                                                  _Predicate __pred,
 700                                                  const bidirectional_iterator_tag &) {
 701   for (;;) {
 702     for (;;) {
 703       if (__first == __last)
 704         return __first;
 705       else if (__pred(*__first))
 706         ++__first;
 707       else
 708         break;
 709     }
 710     --__last;
 711     for (;;) {
 712       if (__first == __last)
 713         return __first;
 714       else if (!__pred(*__last))
 715         --__last;
 716       else
 717         break;
 718     }
 719     iter_swap(__first, __last);
 720     ++__first;
 721   }
 722 }
 723
 724 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
 725 template <class _BidirectionalIter, class _Predicate>
 726 inline
 727 _BidirectionalIter __partition(_BidirectionalIter __first,
 728                                _BidirectionalIter __last,
 729                                _Predicate __pred,
 730                                const random_access_iterator_tag &) {
 731   return __partition(__first, __last, __pred, bidirectional_iterator_tag());
 732 }
 733 #endif
 734
 735 _STLP_MOVE_TO_STD_NAMESPACE
 736
 737 template <class _ForwardIter, class _Predicate>
 738 _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate   __pred) {
 739   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 740   return _STLP_PRIV __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
 741 }
 742
 743
 744 /* __pred_of_first: false if we know that __pred(*__first) is false,
 745  *                  true when we don't know the result of __pred(*__first).
 746  * __not_pred_of_before_last: true if we know that __pred(*--__last) is true,
 747  *                            false when we don't know the result of __pred(*--__last).
 748  */
 749 _STLP_MOVE_TO_PRIV_NAMESPACE
 750
 751 template <class _ForwardIter, class _Predicate, class _Distance>
 752 _ForwardIter __inplace_stable_partition(_ForwardIter __first,
 753                                         _ForwardIter __last,
 754                                         _Predicate __pred, _Distance __len,
 755                                         bool __pred_of_first, bool __pred_of_before_last) {
 756   if (__len == 1)
 757     return (__pred_of_first && (__pred_of_before_last || __pred(*__first))) ? __last : __first;
 758   _ForwardIter __middle = __first;
 759   _Distance __half_len = __len / 2;
 760   _STLP_STD::advance(__middle, __half_len);
 761   return _STLP_PRIV __rotate(_STLP_PRIV __inplace_stable_partition(__first, __middle, __pred, __half_len, __pred_of_first, false),
 762                              __middle,
 763                              _STLP_PRIV __inplace_stable_partition(__middle, __last, __pred, __len - __half_len, true, __pred_of_before_last));
 764 }
 765
 766 template <class _ForwardIter, class _Pointer, class _Predicate,
 767           class _Distance>
 768 _ForwardIter __stable_partition_adaptive(_ForwardIter __first,
 769                                          _ForwardIter __last,
 770                                          _Predicate __pred, _Distance __len,
 771                                          _Pointer __buffer, _Distance __buffer_size,
 772                                          bool __pred_of_first, bool __pred_of_before_last) {
 773   if (__len <= __buffer_size) {
 774     _ForwardIter __result1 = __first;
 775     _Pointer __result2 = __buffer;
 776     if ((__first != __last) && (!__pred_of_first || __pred(*__first))) {
 777       *__result2 = *__first;
 778       ++__result2; ++__first; --__len;
 779     }
 780     for (; __first != __last ; ++__first, --__len) {
 781       if (((__len == 1) && (__pred_of_before_last || __pred(*__first))) ||
 782           ((__len != 1) && __pred(*__first))){
 783         *__result1 = *__first;
 784         ++__result1;
 785       }
 786       else {
 787         *__result2 = *__first;
 788         ++__result2;
 789       }
 790     }
 791     _STLP_STD::copy(__buffer, __result2, __result1);
 792     return __result1;
 793   }
 794   else {
 795     _ForwardIter __middle = __first;
 796     _Distance __half_len = __len / 2;
 797     _STLP_STD::advance(__middle, __half_len);
 798     return _STLP_PRIV __rotate(_STLP_PRIV __stable_partition_adaptive(__first, __middle, __pred,
 799                                                                       __half_len, __buffer, __buffer_size,
 800                                                                       __pred_of_first, false),
 801                                __middle,
 802                                _STLP_PRIV __stable_partition_adaptive(__middle, __last, __pred,
 803                                                                       __len - __half_len, __buffer, __buffer_size,
 804                                                                       true, __pred_of_before_last));
 805   }
 806 }
 807
 808 template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
 809 inline _ForwardIter
 810 __stable_partition_aux_aux(_ForwardIter __first, _ForwardIter __last,
 811                            _Predicate __pred, _Tp*, _Distance*, bool __pred_of_before_last) {
 812   _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
 813   _STLP_MPWFIX_TRY    //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
 814   return (__buf.size() > 0) ?
 815     __stable_partition_adaptive(__first, __last, __pred,
 816                                 _Distance(__buf.requested_size()),
 817                                 __buf.begin(), __buf.size(),
 818                                 false, __pred_of_before_last)  :
 819     __inplace_stable_partition(__first, __last, __pred,
 820                                _Distance(__buf.requested_size()),
 821                                false, __pred_of_before_last);
 822   _STLP_MPWFIX_CATCH  //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
 823 }
 824
 825 template <class _ForwardIter, class _Predicate>
 826 _ForwardIter
 827 __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, _Predicate __pred,
 828                        const forward_iterator_tag &) {
 829   return __stable_partition_aux_aux(__first, __last, __pred,
 830                                     _STLP_VALUE_TYPE(__first, _ForwardIter),
 831                                     _STLP_DISTANCE_TYPE(__first, _ForwardIter), false);
 832 }
 833
 834 template <class _BidirectIter, class _Predicate>
 835 _BidirectIter
 836 __stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
 837                        const bidirectional_iterator_tag &) {
 838   for (--__last;;) {
 839     if (__first == __last)
 840       return __first;
 841     else if (!__pred(*__last))
 842       --__last;
 843     else
 844       break;
 845   }
 846   ++__last;
 847   //Here we know that __pred(*--__last) is true
 848   return __stable_partition_aux_aux(__first, __last, __pred,
 849                                     _STLP_VALUE_TYPE(__first, _BidirectIter),
 850                                     _STLP_DISTANCE_TYPE(__first, _BidirectIter), true);
 851 }
 852
 853 #if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
 854 template <class _BidirectIter, class _Predicate>
 855 _BidirectIter
 856 __stable_partition_aux(_BidirectIter __first, _BidirectIter __last, _Predicate __pred,
 857                        const random_access_iterator_tag &) {
 858   return __stable_partition_aux(__first, __last, __pred, bidirectional_iterator_tag());
 859 }
 860 #endif
 861
 862 _STLP_MOVE_TO_STD_NAMESPACE
 863
 864 template <class _ForwardIter, class _Predicate>
 865 _ForwardIter
 866 stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
 867   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 868   for (;;) {
 869     if (__first == __last)
 870       return __first;
 871     else if (__pred(*__first))
 872       ++__first;
 873     else
 874       break;
 875   }
 876   return _STLP_PRIV __stable_partition_aux(__first, __last, __pred,
 877                                            _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
 878 }
 879
 880 _STLP_MOVE_TO_PRIV_NAMESPACE
 881
 882 template <class _RandomAccessIter, class _Tp, class _Compare>
 883 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
 884                                         _RandomAccessIter __last,
 885                                         _Tp __pivot, _Compare __comp) {
 886   for (;;) {
 887     while (__comp(*__first, __pivot)) {
 888       _STLP_VERBOSE_ASSERT(!__comp(__pivot, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
 889       ++__first;
 890     }
 891     --__last;
 892     while (__comp(__pivot, *__last)) {
 893       _STLP_VERBOSE_ASSERT(!__comp(*__last, __pivot), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
 894       --__last;
 895     }
 896     if (!(__first < __last))
 897       return __first;
 898     iter_swap(__first, __last);
 899     ++__first;
 900   }
 901 }
 902
 903 // sort() and its auxiliary functions.
 904 #define __stl_threshold  16
 905
 906 template <class _RandomAccessIter, class _Tp, class _Compare>
 907 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
 908                                _Compare __comp) {
 909   _RandomAccessIter __next = __last;
 910   --__next;
 911   while (__comp(__val, *__next)) {
 912     _STLP_VERBOSE_ASSERT(!__comp(*__next, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
 913     *__last = *__next;
 914     __last = __next;
 915     --__next;
 916   }
 917   *__last = __val;
 918 }
 919
 920 template <class _RandomAccessIter, class _Tp, class _Compare>
 921 inline void __linear_insert(_RandomAccessIter __first,
 922                             _RandomAccessIter __last, _Tp __val, _Compare __comp) {
 923   //*TY 12/26/1998 - added __val as a paramter
 924   //  _Tp __val = *__last;        //*TY 12/26/1998 - __val supplied by caller
 925   if (__comp(__val, *__first)) {
 926     _STLP_VERBOSE_ASSERT(!__comp(*__first, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
 927     copy_backward(__first, __last, __last + 1);
 928     *__first = __val;
 929   }
 930   else
 931     __unguarded_linear_insert(__last, __val, __comp);
 932 }
 933
 934 template <class _RandomAccessIter, class _Tp, class _Compare>
 935 void __insertion_sort(_RandomAccessIter __first,
 936                       _RandomAccessIter __last,
 937                       _Tp *, _Compare __comp) {
 938   if (__first == __last) return;
 939   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
 940     __linear_insert<_RandomAccessIter, _Tp, _Compare>(__first, __i, *__i, __comp);  //*TY 12/26/1998 - supply *__i as __val
 941 }
 942
 943 template <class _RandomAccessIter, class _Tp, class _Compare>
 944 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
 945                                     _RandomAccessIter __last,
 946                                     _Tp*, _Compare __comp) {
 947   for (_RandomAccessIter __i = __first; __i != __last; ++__i)
 948     __unguarded_linear_insert<_RandomAccessIter, _Tp, _Compare>(__i, *__i, __comp);
 949 }
 950
 951 template <class _RandomAccessIter, class _Compare>
 952 inline void __unguarded_insertion_sort(_RandomAccessIter __first,
 953                                        _RandomAccessIter __last,
 954                                        _Compare __comp) {
 955   __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
 956 }
 957
 958 template <class _RandomAccessIter, class _Compare>
 959 void __final_insertion_sort(_RandomAccessIter __first,
 960                             _RandomAccessIter __last, _Compare __comp) {
 961   if (__last - __first > __stl_threshold) {
 962     __insertion_sort(__first, __first + __stl_threshold, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
 963     __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
 964   }
 965   else
 966     __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
 967 }
 968
 969 template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
 970 void __introsort_loop(_RandomAccessIter __first,
 971                       _RandomAccessIter __last, _Tp*,
 972                       _Size __depth_limit, _Compare __comp) {
 973   while (__last - __first > __stl_threshold) {
 974     if (__depth_limit == 0) {
 975       partial_sort(__first, __last, __last, __comp);
 976       return;
 977     }
 978     --__depth_limit;
 979     _RandomAccessIter __cut =
 980       __unguarded_partition(__first, __last,
 981                             _Tp(__median(*__first,
 982                                          *(__first + (__last - __first)/2),
 983                                          *(__last - 1), __comp)),
 984        __comp);
 985     __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
 986     __last = __cut;
 987   }
 988 }
 989
 990 _STLP_MOVE_TO_STD_NAMESPACE
 991
 992 template <class _RandomAccessIter>
 993 void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
 994   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
 995   if (__first != __last) {
 996     _STLP_PRIV __introsort_loop(__first, __last,
 997                                 _STLP_VALUE_TYPE(__first, _RandomAccessIter),
 998                                 _STLP_PRIV __lg(__last - __first) * 2,
 999                                 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1000     _STLP_PRIV __final_insertion_sort(__first, __last,
1001                                       _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1002   }
1003 }
1004
1005 template <class _RandomAccessIter, class _Compare>
1006 void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) {
1007   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1008   if (__first != __last) {
1009     _STLP_PRIV __introsort_loop(__first, __last,
1010                                 _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1011                                 _STLP_PRIV __lg(__last - __first) * 2, __comp);
1012     _STLP_PRIV __final_insertion_sort(__first, __last, __comp);
1013   }
1014 }
1015
1016 // stable_sort() and its auxiliary functions.
1017 _STLP_MOVE_TO_PRIV_NAMESPACE
1018
1019 template <class _RandomAccessIter, class _Compare>
1020 void __inplace_stable_sort(_RandomAccessIter __first,
1021                            _RandomAccessIter __last, _Compare __comp) {
1022   if (__last - __first < 15) {
1023     __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1024     return;
1025   }
1026   _RandomAccessIter __middle = __first + (__last - __first) / 2;
1027   __inplace_stable_sort(__first, __middle, __comp);
1028   __inplace_stable_sort(__middle, __last, __comp);
1029   __merge_without_buffer(__first, __middle, __last,
1030                          __middle - __first,
1031                          __last - __middle,
1032                          __comp);
1033 }
1034
1035 template <class _RandomAccessIter1, class _RandomAccessIter2,
1036           class _Distance, class _Compare>
1037 void __merge_sort_loop(_RandomAccessIter1 __first,
1038                        _RandomAccessIter1 __last,
1039                        _RandomAccessIter2 __result, _Distance __step_size,
1040                        _Compare __comp) {
1041   _Distance __two_step = 2 * __step_size;
1042
1043   while (__last - __first >= __two_step) {
1044     __result = merge(__first, __first + __step_size,
1045                      __first + __step_size, __first + __two_step,
1046                      __result,
1047                      __comp);
1048     __first += __two_step;
1049   }
1050   __step_size = (min) (_Distance(__last - __first), __step_size);
1051
1052   merge(__first, __first + __step_size,
1053         __first + __step_size, __last,
1054         __result,
1055         __comp);
1056 }
1057
1058 const int __stl_chunk_size = 7;
1059
1060 template <class _RandomAccessIter, class _Distance, class _Compare>
1061 void __chunk_insertion_sort(_RandomAccessIter __first,
1062                             _RandomAccessIter __last,
1063                             _Distance __chunk_size, _Compare __comp) {
1064   while (__last - __first >= __chunk_size) {
1065     __insertion_sort(__first, __first + __chunk_size,
1066                      _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1067     __first += __chunk_size;
1068   }
1069   __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1070 }
1071
1072 template <class _RandomAccessIter, class _Pointer, class _Distance,
1073           class _Compare>
1074 void __merge_sort_with_buffer(_RandomAccessIter __first,
1075                               _RandomAccessIter __last, _Pointer __buffer,
1076                               _Distance*, _Compare __comp) {
1077   _Distance __len = __last - __first;
1078   _Pointer __buffer_last = __buffer + __len;
1079
1080   _Distance __step_size = __stl_chunk_size;
1081   __chunk_insertion_sort(__first, __last, __step_size, __comp);
1082
1083   while (__step_size < __len) {
1084     __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
1085     __step_size *= 2;
1086     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
1087     __step_size *= 2;
1088   }
1089 }
1090
1091 template <class _BidirectionalIter1, class _BidirectionalIter2,
1092           class _Distance>
1093 _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
1094                                       _BidirectionalIter1 __middle,
1095                                       _BidirectionalIter1 __last,
1096                                       _Distance __len1, _Distance __len2,
1097                                       _BidirectionalIter2 __buffer,
1098                                       _Distance __buffer_size) {
1099   if (__len1 > __len2 && __len2 <= __buffer_size) {
1100     _BidirectionalIter2 __buffer_end = _STLP_STD::copy(__middle, __last, __buffer);
1101     _STLP_STD::copy_backward(__first, __middle, __last);
1102     return _STLP_STD::copy(__buffer, __buffer_end, __first);
1103   }
1104   else if (__len1 <= __buffer_size) {
1105     _BidirectionalIter2 __buffer_end = _STLP_STD::copy(__first, __middle, __buffer);
1106     _STLP_STD::copy(__middle, __last, __first);
1107     return _STLP_STD::copy_backward(__buffer, __buffer_end, __last);
1108   }
1109   else
1110     return _STLP_PRIV __rotate(__first, __middle, __last);
1111 }
1112
1113 template <class _BidirectionalIter, class _Distance, class _Pointer,
1114           class _Compare>
1115 void __merge_adaptive(_BidirectionalIter __first,
1116                       _BidirectionalIter __middle,
1117                       _BidirectionalIter __last,
1118                       _Distance __len1, _Distance __len2,
1119                       _Pointer __buffer, _Distance __buffer_size,
1120                       _Compare __comp) {
1121   if (__len1 <= __len2 && __len1 <= __buffer_size) {
1122     _Pointer __buffer_end = _STLP_STD::copy(__first, __middle, __buffer);
1123     _STLP_STD::merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
1124   }
1125   else if (__len2 <= __buffer_size) {
1126     _Pointer __buffer_end = _STLP_STD::copy(__middle, __last, __buffer);
1127     _STLP_PRIV __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
1128                                 __comp);
1129   }
1130   else {
1131     _BidirectionalIter __first_cut = __first;
1132     _BidirectionalIter __second_cut = __middle;
1133     _Distance __len11 = 0;
1134     _Distance __len22 = 0;
1135     if (__len1 > __len2) {
1136       __len11 = __len1 / 2;
1137       _STLP_STD::advance(__first_cut, __len11);
1138       __second_cut = _STLP_STD::lower_bound(__middle, __last, *__first_cut, __comp);
1139       __len22 += _STLP_STD::distance(__middle, __second_cut);
1140     }
1141     else {
1142       __len22 = __len2 / 2;
1143       _STLP_STD::advance(__second_cut, __len22);
1144       __first_cut = _STLP_STD::upper_bound(__first, __middle, *__second_cut, __comp);
1145       __len11 += _STLP_STD::distance(__first, __first_cut);
1146     }
1147     _BidirectionalIter __new_middle =
1148       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
1149                         __len22, __buffer, __buffer_size);
1150     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
1151                      __len22, __buffer, __buffer_size, __comp);
1152     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
1153                      __len2 - __len22, __buffer, __buffer_size, __comp);
1154   }
1155 }
1156
1157 template <class _RandomAccessIter, class _Pointer, class _Distance,
1158           class _Compare>
1159 void __stable_sort_adaptive(_RandomAccessIter __first,
1160                             _RandomAccessIter __last, _Pointer __buffer,
1161                             _Distance __buffer_size, _Compare __comp) {
1162   _Distance __len = (__last - __first + 1) / 2;
1163   _RandomAccessIter __middle = __first + __len;
1164   if (__len > __buffer_size) {
1165     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
1166                            __comp);
1167     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
1168                            __comp);
1169   }
1170   else {
1171     __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
1172                                __comp);
1173     __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
1174                                __comp);
1175   }
1176   __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
1177                    _Distance(__last - __middle), __buffer, __buffer_size,
1178                    __comp);
1179 }
1180
1181 template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
1182 void __stable_sort_aux(_RandomAccessIter __first,
1183                        _RandomAccessIter __last, _Tp*, _Distance*,
1184                        _Compare __comp) {
1185   _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
1186   if (buf.begin() == 0)
1187     __inplace_stable_sort(__first, __last, __comp);
1188   else
1189     __stable_sort_adaptive(__first, __last, buf.begin(),
1190                            _Distance(buf.size()),
1191                            __comp);
1192 }
1193
1194 _STLP_MOVE_TO_STD_NAMESPACE
1195
1196 template <class _RandomAccessIter>
1197 void stable_sort(_RandomAccessIter __first,
1198                  _RandomAccessIter __last) {
1199   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1200   _STLP_PRIV __stable_sort_aux(__first, __last,
1201                                _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1202                                _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
1203                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1204 }
1205
1206 template <class _RandomAccessIter, class _Compare>
1207 void stable_sort(_RandomAccessIter __first,
1208                  _RandomAccessIter __last, _Compare __comp) {
1209   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1210   _STLP_PRIV __stable_sort_aux(__first, __last,
1211                                _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1212                                _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
1213                                __comp);
1214 }
1215
1216 // partial_sort, partial_sort_copy, and auxiliary functions.
1217 _STLP_MOVE_TO_PRIV_NAMESPACE
1218
1219 template <class _RandomAccessIter, class _Tp, class _Compare>
1220 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
1221                     _RandomAccessIter __last, _Tp*, _Compare __comp) {
1222   make_heap(__first, __middle, __comp);
1223   for (_RandomAccessIter __i = __middle; __i < __last; ++__i) {
1224     if (__comp(*__i, *__first)) {
1225       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1226       __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
1227                  _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));
1228     }
1229   }
1230   sort_heap(__first, __middle, __comp);
1231 }
1232
1233 _STLP_MOVE_TO_STD_NAMESPACE
1234
1235 template <class _RandomAccessIter>
1236 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
1237                   _RandomAccessIter __last) {
1238   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
1239   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
1240   _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1241                             _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1242 }
1243
1244 template <class _RandomAccessIter, class _Compare>
1245 void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
1246                   _RandomAccessIter __last, _Compare __comp) {
1247   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
1248   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
1249   _STLP_PRIV __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
1250 }
1251
1252 _STLP_MOVE_TO_PRIV_NAMESPACE
1253
1254 template <class _InputIter, class _RandomAccessIter, class _Compare,
1255           class _Distance, class _Tp>
1256 _RandomAccessIter __partial_sort_copy(_InputIter __first,
1257                                       _InputIter __last,
1258                                       _RandomAccessIter __result_first,
1259                                       _RandomAccessIter __result_last,
1260                                       _Compare __comp, _Distance*, _Tp*) {
1261   if (__result_first == __result_last) return __result_last;
1262   _RandomAccessIter __result_real_last = __result_first;
1263   while(__first != __last && __result_real_last != __result_last) {
1264     *__result_real_last = *__first;
1265     ++__result_real_last;
1266     ++__first;
1267   }
1268   make_heap(__result_first, __result_real_last, __comp);
1269   while (__first != __last) {
1270     if (__comp(*__first, *__result_first)) {
1271       _STLP_VERBOSE_ASSERT(!__comp(*__result_first, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1272       __adjust_heap(__result_first, _Distance(0),
1273                     _Distance(__result_real_last - __result_first),
1274                     _Tp(*__first),
1275                     __comp);
1276     }
1277     ++__first;
1278   }
1279   sort_heap(__result_first, __result_real_last, __comp);
1280   return __result_real_last;
1281 }
1282
1283 _STLP_MOVE_TO_STD_NAMESPACE
1284
1285 template <class _InputIter, class _RandomAccessIter>
1286 _RandomAccessIter
1287 partial_sort_copy(_InputIter __first, _InputIter __last,
1288                   _RandomAccessIter __result_first, _RandomAccessIter __result_last) {
1289   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1290   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
1291   return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
1292                                         _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _InputIter)),
1293                                         _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
1294                                         _STLP_VALUE_TYPE(__first, _InputIter));
1295 }
1296
1297 template <class _InputIter, class _RandomAccessIter, class _Compare>
1298 _RandomAccessIter
1299 partial_sort_copy(_InputIter __first, _InputIter __last,
1300                   _RandomAccessIter __result_first,
1301                   _RandomAccessIter __result_last, _Compare __comp) {
1302   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1303   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__result_first, __result_last))
1304   return _STLP_PRIV __partial_sort_copy(__first, __last, __result_first, __result_last,
1305                                         __comp,
1306                                         _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
1307                                         _STLP_VALUE_TYPE(__first, _InputIter));
1308 }
1309
1310 // nth_element() and its auxiliary functions.
1311 _STLP_MOVE_TO_PRIV_NAMESPACE
1312
1313 template <class _RandomAccessIter, class _Tp, class _Compare>
1314 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1315                    _RandomAccessIter __last, _Tp*, _Compare __comp) {
1316   while (__last - __first > 3) {
1317     _RandomAccessIter __cut =
1318       __unguarded_partition(__first, __last,
1319                             _Tp(__median(*__first,
1320                                          *(__first + (__last - __first)/2),
1321                                          *(__last - 1),
1322                                          __comp)),
1323                             __comp);
1324     if (__cut <= __nth)
1325       __first = __cut;
1326     else
1327       __last = __cut;
1328   }
1329   __insertion_sort(__first, __last, _STLP_VALUE_TYPE(__first,_RandomAccessIter), __comp);
1330 }
1331
1332 _STLP_MOVE_TO_STD_NAMESPACE
1333
1334 template <class _RandomAccessIter>
1335 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1336                  _RandomAccessIter __last) {
1337   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
1338   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
1339   _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter),
1340                            _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
1341 }
1342
1343 template <class _RandomAccessIter, class _Compare>
1344 void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1345                  _RandomAccessIter __last, _Compare __comp) {
1346   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __nth))
1347   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__nth, __last))
1348   _STLP_PRIV __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
1349 }
1350
1351 // Binary search (lower_bound, upper_bound, equal_range, binary_search).
1352 _STLP_MOVE_TO_PRIV_NAMESPACE
1353
1354 template <class _ForwardIter, class _Tp,
1355           class _Compare1, class _Compare2, class _Distance>
1356 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1357                            _Compare1 __comp1, _Compare2 __comp2, _Distance*) {
1358   _Distance __len = _STLP_STD::distance(__first, __last);
1359   _Distance __half;
1360
1361   while (__len > 0) {
1362     __half = __len >> 1;
1363     _ForwardIter __middle = __first;
1364     _STLP_STD::advance(__middle, __half);
1365     if (__comp2(__val, *__middle)) {
1366       _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1367       __len = __half;
1368     }
1369     else {
1370       __first = __middle;
1371       ++__first;
1372       __len = __len - __half - 1;
1373     }
1374   }
1375   return __first;
1376 }
1377
1378 template <class _ForwardIter, class _Tp,
1379           class _Compare1, class _Compare2, class _Distance>
1380 pair<_ForwardIter, _ForwardIter>
1381 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1382               _Compare1 __comp1, _Compare2 __comp2, _Distance* __dist) {
1383   _Distance __len = _STLP_STD::distance(__first, __last);
1384   _Distance __half;
1385
1386   while (__len > 0) {
1387     __half = __len >> 1;
1388     _ForwardIter __middle = __first;
1389     _STLP_STD::advance(__middle, __half);
1390     if (__comp1(*__middle, __val)) {
1391       _STLP_VERBOSE_ASSERT(!__comp2(__val, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1392       __first = __middle;
1393       ++__first;
1394       __len = __len - __half - 1;
1395     }
1396     else if (__comp2(__val, *__middle)) {
1397       _STLP_VERBOSE_ASSERT(!__comp1(*__middle, __val), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1398       __len = __half;
1399     }
1400     else {
1401       _ForwardIter __left = _STLP_PRIV __lower_bound(__first, __middle, __val, __comp1, __comp2, __dist);
1402       //Small optim: If lower_bound haven't found an equivalent value
1403       //there is no need to call upper_bound.
1404       if (__comp1(*__left, __val)) {
1405         _STLP_VERBOSE_ASSERT(!__comp2(__val, *__left), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1406         return pair<_ForwardIter, _ForwardIter>(__left, __left);
1407       }
1408       _STLP_STD::advance(__first, __len);
1409       _ForwardIter __right = _STLP_PRIV __upper_bound(++__middle, __first, __val, __comp1, __comp2, __dist);
1410       return pair<_ForwardIter, _ForwardIter>(__left, __right);
1411     }
1412   }
1413   return pair<_ForwardIter, _ForwardIter>(__first, __first);
1414 }
1415
1416 _STLP_MOVE_TO_STD_NAMESPACE
1417
1418 template <class _InputIter1, class _InputIter2, class _OutputIter>
1419 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
1420                   _InputIter2 __first2, _InputIter2 __last2,
1421                   _OutputIter __result) {
1422   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1423   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1424   while (__first1 != __last1 && __first2 != __last2) {
1425     if (*__first2 < *__first1) {
1426       *__result = *__first2;
1427       ++__first2;
1428     }
1429     else {
1430       *__result = *__first1;
1431       ++__first1;
1432     }
1433     ++__result;
1434   }
1435   return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result));
1436 }
1437
1438 template <class _InputIter1, class _InputIter2, class _OutputIter,
1439           class _Compare>
1440 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
1441                   _InputIter2 __first2, _InputIter2 __last2,
1442                   _OutputIter __result, _Compare __comp) {
1443   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1444   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1445   while (__first1 != __last1 && __first2 != __last2) {
1446     if (__comp(*__first2, *__first1)) {
1447       _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1448       *__result = *__first2;
1449       ++__first2;
1450     }
1451     else {
1452       *__result = *__first1;
1453       ++__first1;
1454     }
1455     ++__result;
1456   }
1457   return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result));
1458 }
1459
1460 _STLP_MOVE_TO_PRIV_NAMESPACE
1461
1462 template <class _BidirectionalIter, class _Distance, class _Compare>
1463 void __merge_without_buffer(_BidirectionalIter __first,
1464                             _BidirectionalIter __middle,
1465                             _BidirectionalIter __last,
1466                             _Distance __len1, _Distance __len2,
1467                             _Compare __comp) {
1468   if (__len1 == 0 || __len2 == 0)
1469     return;
1470   if (__len1 + __len2 == 2) {
1471     if (__comp(*__middle, *__first)) {
1472       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__middle), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1473       iter_swap(__first, __middle);
1474     }
1475     return;
1476   }
1477   _BidirectionalIter __first_cut = __first;
1478   _BidirectionalIter __second_cut = __middle;
1479   _Distance __len11 = 0;
1480   _Distance __len22 = 0;
1481   if (__len1 > __len2) {
1482     __len11 = __len1 / 2;
1483     _STLP_STD::advance(__first_cut, __len11);
1484     __second_cut = _STLP_STD::lower_bound(__middle, __last, *__first_cut, __comp);
1485     __len22 += _STLP_STD::distance(__middle, __second_cut);
1486   }
1487   else {
1488     __len22 = __len2 / 2;
1489     _STLP_STD::advance(__second_cut, __len22);
1490     __first_cut = _STLP_STD::upper_bound(__first, __middle, *__second_cut, __comp);
1491     __len11 += _STLP_STD::distance(__first, __first_cut);
1492   }
1493   _BidirectionalIter __new_middle
1494     = _STLP_PRIV __rotate(__first_cut, __middle, __second_cut);
1495   __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
1496                          __comp);
1497   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
1498                          __len2 - __len22, __comp);
1499 }
1500
1501 template <class _BidirectionalIter1, class _BidirectionalIter2,
1502           class _BidirectionalIter3, class _Compare>
1503 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
1504                                      _BidirectionalIter1 __last1,
1505                                      _BidirectionalIter2 __first2,
1506                                      _BidirectionalIter2 __last2,
1507                                      _BidirectionalIter3 __result,
1508                                      _Compare __comp) {
1509   if (__first1 == __last1)
1510     return copy_backward(__first2, __last2, __result);
1511   if (__first2 == __last2)
1512     return copy_backward(__first1, __last1, __result);
1513   --__last1;
1514   --__last2;
1515   for (;;) {
1516     if (__comp(*__last2, *__last1)) {
1517       _STLP_VERBOSE_ASSERT(!__comp(*__last1, *__last2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1518       *--__result = *__last1;
1519       if (__first1 == __last1)
1520         return copy_backward(__first2, ++__last2, __result);
1521       --__last1;
1522     }
1523     else {
1524       *--__result = *__last2;
1525       if (__first2 == __last2)
1526         return copy_backward(__first1, ++__last1, __result);
1527       --__last2;
1528     }
1529   }
1530 }
1531
1532 template <class _BidirectionalIter, class _Tp,
1533           class _Distance, class _Compare>
1534 inline void __inplace_merge_aux(_BidirectionalIter __first,
1535                                 _BidirectionalIter __middle,
1536                                 _BidirectionalIter __last, _Tp*, _Distance*,
1537                                 _Compare __comp) {
1538   _Distance __len1 = _STLP_STD::distance(__first, __middle);
1539   _Distance __len2 = _STLP_STD::distance(__middle, __last);
1540
1541   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
1542   if (__buf.begin() == 0)
1543     __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
1544   else
1545     __merge_adaptive(__first, __middle, __last, __len1, __len2,
1546                      __buf.begin(), _Distance(__buf.size()),
1547                      __comp);
1548 }
1549
1550 _STLP_MOVE_TO_STD_NAMESPACE
1551
1552 template <class _BidirectionalIter>
1553 void inplace_merge(_BidirectionalIter __first,
1554                    _BidirectionalIter __middle,
1555                    _BidirectionalIter __last) {
1556   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
1557   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
1558   if (__first == __middle || __middle == __last)
1559     return;
1560   _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
1561                                  _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
1562                                  _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
1563 }
1564
1565 template <class _BidirectionalIter, class _Compare>
1566 void inplace_merge(_BidirectionalIter __first,
1567                    _BidirectionalIter __middle,
1568                    _BidirectionalIter __last, _Compare __comp) {
1569   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __middle))
1570   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__middle, __last))
1571   if (__first == __middle || __middle == __last)
1572     return;
1573   _STLP_PRIV __inplace_merge_aux(__first, __middle, __last,
1574                                  _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
1575                                  __comp);
1576 }
1577
1578 _STLP_MOVE_TO_PRIV_NAMESPACE
1579
1580 template <class _InputIter1, class _InputIter2, class _Compare>
1581 bool __includes(_InputIter1 __first1, _InputIter1 __last1,
1582                 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
1583   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1584   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1585   while (__first1 != __last1 && __first2 != __last2)
1586     if (__comp(*__first2, *__first1)) {
1587       _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1588       return false;
1589     }
1590     else if (__comp(*__first1, *__first2))
1591       ++__first1;
1592     else
1593       ++__first1, ++__first2;
1594
1595   return __first2 == __last2;
1596 }
1597
1598 _STLP_MOVE_TO_STD_NAMESPACE
1599
1600 template <class _InputIter1, class _InputIter2, class _Compare>
1601 bool includes(_InputIter1 __first1, _InputIter1 __last1,
1602               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
1603   return _STLP_PRIV __includes(__first1, __last1, __first2, __last2, __comp);
1604 }
1605
1606 template <class _InputIter1, class _InputIter2>
1607 bool includes(_InputIter1 __first1, _InputIter1 __last1,
1608               _InputIter2 __first2, _InputIter2 __last2) {
1609   return _STLP_PRIV __includes(__first1, __last1, __first2, __last2,
1610                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1611 }
1612
1613 _STLP_MOVE_TO_PRIV_NAMESPACE
1614
1615 template <class _InputIter1, class _InputIter2, class _OutputIter,
1616           class _Compare>
1617 _OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,
1618                         _InputIter2 __first2, _InputIter2 __last2,
1619                         _OutputIter __result, _Compare __comp) {
1620   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1621   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1622   while (__first1 != __last1 && __first2 != __last2) {
1623     if (__comp(*__first1, *__first2)) {
1624       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1625       *__result = *__first1;
1626       ++__first1;
1627     }
1628     else if (__comp(*__first2, *__first1)) {
1629       _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1630       *__result = *__first2;
1631       ++__first2;
1632     }
1633     else {
1634       *__result = *__first1;
1635       ++__first1;
1636       ++__first2;
1637     }
1638     ++__result;
1639   }
1640   return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result));
1641 }
1642
1643 _STLP_MOVE_TO_STD_NAMESPACE
1644
1645 template <class _InputIter1, class _InputIter2, class _OutputIter>
1646 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
1647                       _InputIter2 __first2, _InputIter2 __last2,
1648                       _OutputIter __result) {
1649   return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result,
1650                                 _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1651 }
1652
1653 template <class _InputIter1, class _InputIter2, class _OutputIter,
1654           class _Compare>
1655 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
1656                       _InputIter2 __first2, _InputIter2 __last2,
1657                       _OutputIter __result, _Compare __comp) {
1658   return _STLP_PRIV __set_union(__first1, __last1, __first2, __last2, __result, __comp);
1659 }
1660
1661 _STLP_MOVE_TO_PRIV_NAMESPACE
1662
1663 template <class _InputIter1, class _InputIter2, class _OutputIter,
1664           class _Compare>
1665 _OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,
1666                                _InputIter2 __first2, _InputIter2 __last2,
1667                                _OutputIter __result, _Compare __comp) {
1668   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1669   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1670   while (__first1 != __last1 && __first2 != __last2)
1671     if (__comp(*__first1, *__first2)) {
1672       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1673       ++__first1;
1674     }
1675     else if (__comp(*__first2, *__first1))
1676       ++__first2;
1677     else {
1678       *__result = *__first1;
1679       ++__first1;
1680       ++__first2;
1681       ++__result;
1682     }
1683   return __result;
1684 }
1685
1686 _STLP_MOVE_TO_STD_NAMESPACE
1687
1688 template <class _InputIter1, class _InputIter2, class _OutputIter>
1689 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
1690                              _InputIter2 __first2, _InputIter2 __last2,
1691                              _OutputIter __result) {
1692   return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result,
1693                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1694 }
1695
1696 template <class _InputIter1, class _InputIter2, class _OutputIter,
1697           class _Compare>
1698 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
1699                              _InputIter2 __first2, _InputIter2 __last2,
1700                              _OutputIter __result, _Compare __comp) {
1701   return _STLP_PRIV __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
1702 }
1703
1704 _STLP_MOVE_TO_PRIV_NAMESPACE
1705
1706 template <class _InputIter1, class _InputIter2, class _OutputIter,
1707           class _Compare>
1708 _OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,
1709                              _InputIter2 __first2, _InputIter2 __last2,
1710                              _OutputIter __result, _Compare __comp) {
1711   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1712   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1713   while (__first1 != __last1 && __first2 != __last2)
1714     if (__comp(*__first1, *__first2)) {
1715       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1716       *__result = *__first1;
1717       ++__first1;
1718       ++__result;
1719     }
1720     else if (__comp(*__first2, *__first1))
1721       ++__first2;
1722     else {
1723       ++__first1;
1724       ++__first2;
1725     }
1726   return _STLP_STD::copy(__first1, __last1, __result);
1727 }
1728
1729 _STLP_MOVE_TO_STD_NAMESPACE
1730
1731 template <class _InputIter1, class _InputIter2, class _OutputIter>
1732 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
1733                            _InputIter2 __first2, _InputIter2 __last2,
1734                            _OutputIter __result) {
1735   return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result,
1736                                      _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1737 }
1738
1739 template <class _InputIter1, class _InputIter2, class _OutputIter,
1740           class _Compare>
1741 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
1742                            _InputIter2 __first2, _InputIter2 __last2,
1743                            _OutputIter __result, _Compare __comp) {
1744   return _STLP_PRIV __set_difference(__first1, __last1, __first2, __last2, __result, __comp);
1745 }
1746
1747 _STLP_MOVE_TO_PRIV_NAMESPACE
1748
1749 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
1750 _OutputIter
1751 __set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
1752                            _InputIter2 __first2, _InputIter2 __last2,
1753                            _OutputIter __result, _Compare __comp) {
1754   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first1, __last1))
1755   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first2, __last2))
1756   while (__first1 != __last1 && __first2 != __last2) {
1757     if (__comp(*__first1, *__first2)) {
1758       _STLP_VERBOSE_ASSERT(!__comp(*__first2, *__first1), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1759       *__result = *__first1;
1760       ++__first1;
1761       ++__result;
1762     }
1763     else if (__comp(*__first2, *__first1)) {
1764       *__result = *__first2;
1765       ++__first2;
1766       ++__result;
1767     }
1768     else {
1769       ++__first1;
1770       ++__first2;
1771     }
1772   }
1773   return _STLP_STD::copy(__first2, __last2, _STLP_STD::copy(__first1, __last1, __result));
1774 }
1775
1776 _STLP_MOVE_TO_STD_NAMESPACE
1777
1778 template <class _InputIter1, class _InputIter2, class _OutputIter>
1779 _OutputIter
1780 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
1781                          _InputIter2 __first2, _InputIter2 __last2,
1782                          _OutputIter __result) {
1783   return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
1784                                                _STLP_PRIV __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
1785 }
1786
1787 template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
1788 _OutputIter
1789 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
1790                          _InputIter2 __first2, _InputIter2 __last2,
1791                          _OutputIter __result,
1792                          _Compare __comp) {
1793   return _STLP_PRIV __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
1794 }
1795
1796 // min_element and max_element, with and without an explicitly supplied
1797 // comparison function.
1798
1799 template <class _ForwardIter>
1800 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
1801   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1802   if (__first == __last) return __first;
1803   _ForwardIter __result = __first;
1804   while (++__first != __last)
1805     if (*__result < *__first) {
1806       _STLP_VERBOSE_ASSERT(!(*__first < *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1807       __result = __first;
1808     }
1809   return __result;
1810 }
1811
1812 template <class _ForwardIter, class _Compare>
1813 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
1814                          _Compare __comp) {
1815   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1816   if (__first == __last) return __first;
1817   _ForwardIter __result = __first;
1818   while (++__first != __last) {
1819     if (__comp(*__result, *__first)) {
1820       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__result), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1821       __result = __first;
1822     }
1823   }
1824   return __result;
1825 }
1826
1827 template <class _ForwardIter>
1828 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
1829   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1830   if (__first == __last) return __first;
1831   _ForwardIter __result = __first;
1832   while (++__first != __last)
1833     if (*__first < *__result) {
1834       _STLP_VERBOSE_ASSERT(!(*__result < *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1835       __result = __first;
1836     }
1837   return __result;
1838 }
1839
1840 template <class _ForwardIter, class _Compare>
1841 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
1842                          _Compare __comp) {
1843   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1844   if (__first == __last) return __first;
1845   _ForwardIter __result = __first;
1846   while (++__first != __last) {
1847     if (__comp(*__first, *__result)) {
1848       _STLP_VERBOSE_ASSERT(!__comp(*__result, *__first), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1849       __result = __first;
1850     }
1851   }
1852   return __result;
1853 }
1854
1855 // next_permutation and prev_permutation, with and without an explicitly
1856 // supplied comparison function.
1857 _STLP_MOVE_TO_PRIV_NAMESPACE
1858
1859 template <class _BidirectionalIter, class _Compare>
1860 bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1861                         _Compare __comp) {
1862   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1863   if (__first == __last)
1864     return false;
1865   _BidirectionalIter __i = __first;
1866   ++__i;
1867   if (__i == __last)
1868     return false;
1869   __i = __last;
1870   --__i;
1871
1872   for(;;) {
1873     _BidirectionalIter __ii = __i;
1874     --__i;
1875     if (__comp(*__i, *__ii)) {
1876       _STLP_VERBOSE_ASSERT(!__comp(*__ii, *__i), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1877       _BidirectionalIter __j = __last;
1878       while (!__comp(*__i, *--__j)) {}
1879       iter_swap(__i, __j);
1880       reverse(__ii, __last);
1881       return true;
1882     }
1883     if (__i == __first) {
1884       reverse(__first, __last);
1885       return false;
1886     }
1887   }
1888 #if defined (_STLP_NEED_UNREACHABLE_RETURN)
1889     return false;
1890 #endif
1891 }
1892
1893 _STLP_MOVE_TO_STD_NAMESPACE
1894
1895 template <class _BidirectionalIter>
1896 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
1897   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1898   return _STLP_PRIV __next_permutation(__first, __last,
1899                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
1900 }
1901
1902 template <class _BidirectionalIter, class _Compare>
1903 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1904                       _Compare __comp) {
1905   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1906   return _STLP_PRIV __next_permutation(__first, __last, __comp);
1907 }
1908
1909 _STLP_MOVE_TO_PRIV_NAMESPACE
1910
1911 template <class _BidirectionalIter, class _Compare>
1912 bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1913                         _Compare __comp) {
1914   if (__first == __last)
1915     return false;
1916   _BidirectionalIter __i = __first;
1917   ++__i;
1918   if (__i == __last)
1919     return false;
1920   __i = __last;
1921   --__i;
1922
1923   for(;;) {
1924     _BidirectionalIter __ii = __i;
1925     --__i;
1926     if (__comp(*__ii, *__i)) {
1927       _STLP_VERBOSE_ASSERT(!__comp(*__i, *__ii), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1928       _BidirectionalIter __j = __last;
1929       while (!__comp(*--__j, *__i)) {}
1930       iter_swap(__i, __j);
1931       reverse(__ii, __last);
1932       return true;
1933     }
1934     if (__i == __first) {
1935       reverse(__first, __last);
1936       return false;
1937     }
1938   }
1939 #if defined (_STLP_NEED_UNREACHABLE_RETURN)
1940     return false;
1941 #endif
1942 }
1943
1944 _STLP_MOVE_TO_STD_NAMESPACE
1945
1946 template <class _BidirectionalIter>
1947 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
1948   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1949   return _STLP_PRIV __prev_permutation(__first, __last,
1950                                        _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
1951 }
1952
1953 template <class _BidirectionalIter, class _Compare>
1954 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
1955                       _Compare __comp) {
1956   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1957   return _STLP_PRIV __prev_permutation(__first, __last, __comp);
1958 }
1959
1960 #if !defined (_STLP_NO_EXTENSIONS)
1961
1962 // is_heap, a predicate testing whether or not a range is
1963 // a heap.  This function is an extension, not part of the C++
1964 // standard.
1965 _STLP_MOVE_TO_PRIV_NAMESPACE
1966
1967 template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
1968 bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
1969                _Distance __n) {
1970   _Distance __parent = 0;
1971   for (_Distance __child = 1; __child < __n; ++__child) {
1972     if (__comp(__first[__parent], __first[__child])) {
1973       _STLP_VERBOSE_ASSERT(!__comp(__first[__child], __first[__parent]), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1974       return false;
1975     }
1976     if ((__child & 1) == 0)
1977       ++__parent;
1978   }
1979   return true;
1980 }
1981
1982 _STLP_MOVE_TO_STD_NAMESPACE
1983
1984 template <class _RandomAccessIter>
1985 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last) {
1986   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1987   return _STLP_PRIV __is_heap(__first, _STLP_PRIV __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first);
1988 }
1989
1990 template <class _RandomAccessIter, class _StrictWeakOrdering>
1991 bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
1992              _StrictWeakOrdering __comp) {
1993   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
1994   return _STLP_PRIV __is_heap(__first, __comp, __last - __first);
1995 }
1996
1997
1998 _STLP_MOVE_TO_PRIV_NAMESPACE
1999
2000 template <class _ForwardIter, class _StrictWeakOrdering>
2001 bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
2002                  _StrictWeakOrdering __comp) {
2003   _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
2004   if (__first == __last)
2005     return true;
2006
2007   _ForwardIter __next = __first;
2008   for (++__next; __next != __last; __first = __next, ++__next) {
2009     if (__comp(*__next, *__first)) {
2010       _STLP_VERBOSE_ASSERT(!__comp(*__first, *__next), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
2011       return false;
2012     }
2013   }
2014
2015   return true;
2016 }
2017
2018 _STLP_MOVE_TO_STD_NAMESPACE
2019 #endif /* _STLP_NO_EXTENSIONS */
2020
2021 _STLP_END_NAMESPACE
2022
2023 #undef __stl_threshold
2024
2025 #endif /* _STLP_ALGO_C */
2026 // Local Variables:
2027 // mode:C++
2028 // End: