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