contrib/libstdc++/stl/stl_algo.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Hewlett-Packard Company makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  *
  15  * Copyright (c) 1996
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  18  * Permission to use, copy, modify, distribute and sell this software
  19  * and its documentation for any purpose is hereby granted without fee,
  20  * provided that the above copyright notice appear in all copies and
  21  * that both that copyright notice and this permission notice appear
  22  * in supporting documentation.  Silicon Graphics makes no
  23  * representations about the suitability of this software for any
  24  * purpose.  It is provided "as is" without express or implied warranty.
  25  */
  26
  27 /* NOTE: This is an internal header file, included by other STL headers.
  28  *   You should not attempt to use it directly.
  29  */
  30
  31 #ifndef __SGI_STL_INTERNAL_ALGO_H
  32 #define __SGI_STL_INTERNAL_ALGO_H
  33
  34 #include <stl_heap.h>
  35
  36 __STL_BEGIN_NAMESPACE
  37
  38 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  39 #pragma set woff 1209
  40 #endif
  41
  42 // __median (an extension, not present in the C++ standard).
  43
  44 template <class _Tp>
  45 inline const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
  46   if (__a < __b)
  47     if (__b < __c)
  48       return __b;
  49     else if (__a < __c)
  50       return __c;
  51     else
  52       return __a;
  53   else if (__a < __c)
  54     return __a;
  55   else if (__b < __c)
  56     return __c;
  57   else
  58     return __b;
  59 }
  60
  61 template <class _Tp, class _Compare>
  62 inline const _Tp&
  63 __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
  64   if (__comp(__a, __b))
  65     if (__comp(__b, __c))
  66       return __b;
  67     else if (__comp(__a, __c))
  68       return __c;
  69     else
  70       return __a;
  71   else if (__comp(__a, __c))
  72     return __a;
  73   else if (__comp(__b, __c))
  74     return __c;
  75   else
  76     return __b;
  77 }
  78
  79 // for_each.  Apply a function to every element of a range.
  80 template <class _InputIter, class _Function>
  81 _Function for_each(_InputIter __first, _InputIter __last, _Function __f) {
  82   for ( ; __first != __last; ++__first)
  83     __f(*__first);
  84   return __f;
  85 }
  86
  87 // find and find_if.
  88
  89 template <class _InputIter, class _Tp>
  90 inline _InputIter find(_InputIter __first, _InputIter __last,
  91                        const _Tp& __val,
  92                        input_iterator_tag)
  93 {
  94   while (__first != __last && *__first != __val)
  95     ++__first;
  96   return __first;
  97 }
  98
  99 template <class _InputIter, class _Predicate>
 100 inline _InputIter find_if(_InputIter __first, _InputIter __last,
 101                           _Predicate __pred,
 102                           input_iterator_tag)
 103 {
 104   while (__first != __last && !__pred(*__first))
 105     ++__first;
 106   return __first;
 107 }
 108
 109 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
 110
 111 template <class _RandomAccessIter, class _Tp>
 112 _RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,
 113                        const _Tp& __val,
 114                        random_access_iterator_tag)
 115 {
 116   typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
 117     = (__last - __first) >> 2;
 118
 119   for ( ; __trip_count > 0 ; --__trip_count) {
 120     if (*__first == __val) return __first;
 121     ++__first;
 122
 123     if (*__first == __val) return __first;
 124     ++__first;
 125
 126     if (*__first == __val) return __first;
 127     ++__first;
 128
 129     if (*__first == __val) return __first;
 130     ++__first;
 131   }
 132
 133   switch(__last - __first) {
 134   case 3:
 135     if (*__first == __val) return __first;
 136     ++__first;
 137   case 2:
 138     if (*__first == __val) return __first;
 139     ++__first;
 140   case 1:
 141     if (*__first == __val) return __first;
 142     ++__first;
 143   case 0:
 144   default:
 145     return __last;
 146   }
 147 }
 148
 149 template <class _RandomAccessIter, class _Predicate>
 150 _RandomAccessIter find_if(_RandomAccessIter __first, _RandomAccessIter __last,
 151                           _Predicate __pred,
 152                           random_access_iterator_tag)
 153 {
 154   typename iterator_traits<_RandomAccessIter>::difference_type __trip_count
 155     = (__last - __first) >> 2;
 156
 157   for ( ; __trip_count > 0 ; --__trip_count) {
 158     if (__pred(*__first)) return __first;
 159     ++__first;
 160
 161     if (__pred(*__first)) return __first;
 162     ++__first;
 163
 164     if (__pred(*__first)) return __first;
 165     ++__first;
 166
 167     if (__pred(*__first)) return __first;
 168     ++__first;
 169   }
 170
 171   switch(__last - __first) {
 172   case 3:
 173     if (__pred(*__first)) return __first;
 174     ++__first;
 175   case 2:
 176     if (__pred(*__first)) return __first;
 177     ++__first;
 178   case 1:
 179     if (__pred(*__first)) return __first;
 180     ++__first;
 181   case 0:
 182   default:
 183     return __last;
 184   }
 185 }
 186
 187 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 188
 189 template <class _InputIter, class _Tp>
 190 inline _InputIter find(_InputIter __first, _InputIter __last,
 191                        const _Tp& __val)
 192 {
 193   return find(__first, __last, __val, __ITERATOR_CATEGORY(__first));
 194 }
 195
 196 template <class _InputIter, class _Predicate>
 197 inline _InputIter find_if(_InputIter __first, _InputIter __last,
 198                           _Predicate __pred) {
 199   return find_if(__first, __last, __pred, __ITERATOR_CATEGORY(__first));
 200 }
 201
 202 // adjacent_find.
 203
 204 template <class _ForwardIter>
 205 _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last) {
 206   if (__first == __last)
 207     return __last;
 208   _ForwardIter __next = __first;
 209   while(++__next != __last) {
 210     if (*__first == *__next)
 211       return __first;
 212     __first = __next;
 213   }
 214   return __last;
 215 }
 216
 217 template <class _ForwardIter, class _BinaryPredicate>
 218 _ForwardIter adjacent_find(_ForwardIter __first, _ForwardIter __last,
 219                            _BinaryPredicate __binary_pred) {
 220   if (__first == __last)
 221     return __last;
 222   _ForwardIter __next = __first;
 223   while(++__next != __last) {
 224     if (__binary_pred(*__first, *__next))
 225       return __first;
 226     __first = __next;
 227   }
 228   return __last;
 229 }
 230
 231 // count and count_if.  There are two version of each, one whose return type
 232 // type is void and one (present only if we have partial specialization)
 233 // whose return type is iterator_traits<_InputIter>::difference_type.  The
 234 // C++ standard only has the latter version, but the former, which was present
 235 // in the HP STL, is retained for backward compatibility.
 236
 237 template <class _InputIter, class _Tp, class _Size>
 238 void count(_InputIter __first, _InputIter __last, const _Tp& __value,
 239            _Size& __n) {
 240   for ( ; __first != __last; ++__first)
 241     if (*__first == __value)
 242       ++__n;
 243 }
 244
 245 template <class _InputIter, class _Predicate, class _Size>
 246 void count_if(_InputIter __first, _InputIter __last, _Predicate __pred,
 247               _Size& __n) {
 248   for ( ; __first != __last; ++__first)
 249     if (__pred(*__first))
 250       ++__n;
 251 }
 252
 253 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
 254
 255 template <class _InputIter, class _Tp>
 256 typename iterator_traits<_InputIter>::difference_type
 257 count(_InputIter __first, _InputIter __last, const _Tp& __value) {
 258   typename iterator_traits<_InputIter>::difference_type __n = 0;
 259   for ( ; __first != __last; ++__first)
 260     if (*__first == __value)
 261       ++__n;
 262   return __n;
 263 }
 264
 265 template <class _InputIter, class _Predicate>
 266 typename iterator_traits<_InputIter>::difference_type
 267 count_if(_InputIter __first, _InputIter __last, _Predicate __pred) {
 268   typename iterator_traits<_InputIter>::difference_type __n = 0;
 269   for ( ; __first != __last; ++__first)
 270     if (__pred(*__first))
 271       ++__n;
 272   return __n;
 273 }
 274
 275
 276 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
 277
 278 // search.
 279
 280 template <class _ForwardIter1, class _ForwardIter2>
 281 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
 282                      _ForwardIter2 __first2, _ForwardIter2 __last2)
 283 {
 284   // Test for empty ranges
 285   if (__first1 == __last1 || __first2 == __last2)
 286     return __first1;
 287
 288   // Test for a pattern of length 1.
 289   _ForwardIter2 __tmp(__first2);
 290   ++__tmp;
 291   if (__tmp == __last2)
 292     return find(__first1, __last1, *__first2);
 293
 294   // General case.
 295
 296   _ForwardIter2 __p1, __p;
 297
 298   __p1 = __first2; ++__p1;
 299
 300   _ForwardIter1 __current = __first1;
 301
 302   while (__first1 != __last1) {
 303     __first1 = find(__first1, __last1, *__first2);
 304     if (__first1 == __last1)
 305       return __last1;
 306
 307     __p = __p1;
 308     __current = __first1;
 309     if (++__current == __last1)
 310       return __last1;
 311
 312     while (*__current == *__p) {
 313       if (++__p == __last2)
 314         return __first1;
 315       if (++__current == __last1)
 316         return __last1;
 317     }
 318
 319     ++__first1;
 320   }
 321   return __first1;
 322 }
 323
 324 template <class _ForwardIter1, class _ForwardIter2, class _BinaryPred>
 325 _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
 326                      _ForwardIter2 __first2, _ForwardIter2 __last2,
 327                      _BinaryPred  __predicate)
 328 {
 329   // Test for empty ranges
 330   if (__first1 == __last1 || __first2 == __last2)
 331     return __first1;
 332
 333   // Test for a pattern of length 1.
 334   _ForwardIter2 __tmp(__first2);
 335   ++__tmp;
 336   if (__tmp == __last2)
 337     return find(__first1, __last1, *__first2);
 338
 339   // General case.
 340
 341   _ForwardIter2 __p1, __p;
 342
 343   __p1 = __first2; ++__p1;
 344
 345   _ForwardIter1 __current = __first1;
 346
 347   while (__first1 != __last1) {
 348     while (__first1 != __last1) {
 349       if (__predicate(*__first1, *__first2))
 350         break;
 351       ++__first1;
 352     }
 353     while (__first1 != __last1 && !__predicate(*__first1, *__first2))
 354       ++__first1;
 355     if (__first1 == __last1)
 356       return __last1;
 357
 358     __p = __p1;
 359     __current = __first1;
 360     if (++__current == __last1) return __last1;
 361
 362     while (__predicate(*__current, *__p)) {
 363       if (++__p == __last2)
 364         return __first1;
 365       if (++__current == __last1)
 366         return __last1;
 367     }
 368
 369     ++__first1;
 370   }
 371   return __first1;
 372 }
 373
 374 // search_n.  Search for __count consecutive copies of __val.
 375
 376 template <class _ForwardIter, class _Integer, class _Tp>
 377 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
 378                       _Integer __count, const _Tp& __val) {
 379   if (__count <= 0)
 380     return __first;
 381   else {
 382     __first = find(__first, __last, __val);
 383     while (__first != __last) {
 384       _Integer __n = __count - 1;
 385       _ForwardIter __i = __first;
 386       ++__i;
 387       while (__i != __last && __n != 0 && *__i == __val) {
 388         ++__i;
 389         --__n;
 390       }
 391       if (__n == 0)
 392         return __first;
 393       else
 394         __first = find(__i, __last, __val);
 395     }
 396     return __last;
 397   }
 398 }
 399
 400 template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
 401 _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
 402                       _Integer __count, const _Tp& __val,
 403                       _BinaryPred __binary_pred) {
 404   if (__count <= 0)
 405     return __first;
 406   else {
 407     while (__first != __last) {
 408       if (__binary_pred(*__first, __val))
 409         break;
 410       ++__first;
 411     }
 412     while (__first != __last) {
 413       _Integer __n = __count - 1;
 414       _ForwardIter __i = __first;
 415       ++__i;
 416       while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
 417         ++__i;
 418         --__n;
 419       }
 420       if (__n == 0)
 421         return __first;
 422       else {
 423         while (__i != __last) {
 424           if (__binary_pred(*__i, __val))
 425             break;
 426           ++__i;
 427         }
 428         __first = __i;
 429       }
 430     }
 431     return __last;
 432   }
 433 }
 434
 435 // swap_ranges
 436
 437 template <class _ForwardIter1, class _ForwardIter2>
 438 _ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
 439                           _ForwardIter2 __first2) {
 440   for ( ; __first1 != __last1; ++__first1, ++__first2)
 441     iter_swap(__first1, __first2);
 442   return __first2;
 443 }
 444
 445 // transform
 446
 447 template <class _InputIter, class _OutputIter, class _UnaryOperation>
 448 _OutputIter transform(_InputIter __first, _InputIter __last,
 449                       _OutputIter __result, _UnaryOperation __oper) {
 450   for ( ; __first != __last; ++__first, ++__result)
 451     *__result = __oper(*__first);
 452   return __result;
 453 }
 454
 455 template <class _InputIter1, class _InputIter2, class _OutputIter,
 456           class _BinaryOperation>
 457 _OutputIter transform(_InputIter1 __first1, _InputIter1 __last1,
 458                       _InputIter2 __first2, _OutputIter __result,
 459                       _BinaryOperation __binary_op) {
 460   for ( ; __first1 != __last1; ++__first1, ++__first2, ++__result)
 461     *__result = __binary_op(*__first1, *__first2);
 462   return __result;
 463 }
 464
 465 // replace, replace_if, replace_copy, replace_copy_if
 466
 467 template <class _ForwardIter, class _Tp>
 468 void replace(_ForwardIter __first, _ForwardIter __last,
 469              const _Tp& __old_value, const _Tp& __new_value) {
 470   for ( ; __first != __last; ++__first)
 471     if (*__first == __old_value)
 472       *__first = __new_value;
 473 }
 474
 475 template <class _ForwardIter, class _Predicate, class _Tp>
 476 void replace_if(_ForwardIter __first, _ForwardIter __last,
 477                 _Predicate __pred, const _Tp& __new_value) {
 478   for ( ; __first != __last; ++__first)
 479     if (__pred(*__first))
 480       *__first = __new_value;
 481 }
 482
 483 template <class _InputIter, class _OutputIter, class _Tp>
 484 _OutputIter replace_copy(_InputIter __first, _InputIter __last,
 485                          _OutputIter __result,
 486                          const _Tp& __old_value, const _Tp& __new_value) {
 487   for ( ; __first != __last; ++__first, ++__result)
 488     *__result = *__first == __old_value ? __new_value : *__first;
 489   return __result;
 490 }
 491
 492 template <class Iterator, class _OutputIter, class _Predicate, class _Tp>
 493 _OutputIter replace_copy_if(Iterator __first, Iterator __last,
 494                             _OutputIter __result,
 495                             _Predicate __pred, const _Tp& __new_value) {
 496   for ( ; __first != __last; ++__first, ++__result)
 497     *__result = __pred(*__first) ? __new_value : *__first;
 498   return __result;
 499 }
 500
 501 // generate and generate_n
 502
 503 template <class _ForwardIter, class _Generator>
 504 void generate(_ForwardIter __first, _ForwardIter __last, _Generator __gen) {
 505   for ( ; __first != __last; ++__first)
 506     *__first = __gen();
 507 }
 508
 509 template <class _OutputIter, class _Size, class _Generator>
 510 _OutputIter generate_n(_OutputIter __first, _Size __n, _Generator __gen) {
 511   for ( ; __n > 0; --__n, ++__first)
 512     *__first = __gen();
 513   return __first;
 514 }
 515
 516 // remove, remove_if, remove_copy, remove_copy_if
 517
 518 template <class _InputIter, class _OutputIter, class _Tp>
 519 _OutputIter remove_copy(_InputIter __first, _InputIter __last,
 520                         _OutputIter __result, const _Tp& __value) {
 521   for ( ; __first != __last; ++__first)
 522     if (*__first != __value) {
 523       *__result = *__first;
 524       ++__result;
 525     }
 526   return __result;
 527 }
 528
 529 template <class _InputIter, class _OutputIter, class _Predicate>
 530 _OutputIter remove_copy_if(_InputIter __first, _InputIter __last,
 531                            _OutputIter __result, _Predicate __pred) {
 532   for ( ; __first != __last; ++__first)
 533     if (!__pred(*__first)) {
 534       *__result = *__first;
 535       ++__result;
 536     }
 537   return __result;
 538 }
 539
 540 template <class _ForwardIter, class _Tp>
 541 _ForwardIter remove(_ForwardIter __first, _ForwardIter __last,
 542                     const _Tp& __value) {
 543   __first = find(__first, __last, __value);
 544   _ForwardIter __i = __first;
 545   return __first == __last ? __first
 546                            : remove_copy(++__i, __last, __first, __value);
 547 }
 548
 549 template <class _ForwardIter, class _Predicate>
 550 _ForwardIter remove_if(_ForwardIter __first, _ForwardIter __last,
 551                        _Predicate __pred) {
 552   __first = find_if(__first, __last, __pred);
 553   _ForwardIter __i = __first;
 554   return __first == __last ? __first
 555                            : remove_copy_if(++__i, __last, __first, __pred);
 556 }
 557
 558 // unique and unique_copy
 559
 560 template <class _InputIter, class _OutputIter, class _Tp>
 561 _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
 562                           _OutputIter __result, _Tp*) {
 563   _Tp __value = *__first;
 564   *__result = __value;
 565   while (++__first != __last)
 566     if (__value != *__first) {
 567       __value = *__first;
 568       *++__result = __value;
 569     }
 570   return ++__result;
 571 }
 572
 573 template <class _InputIter, class _OutputIter>
 574 inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
 575                                  _OutputIter __result,
 576                                  output_iterator_tag) {
 577   return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first));
 578 }
 579
 580 template <class _InputIter, class _ForwardIter>
 581 _ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
 582                            _ForwardIter __result, forward_iterator_tag) {
 583   *__result = *__first;
 584   while (++__first != __last)
 585     if (*__result != *__first) *++__result = *__first;
 586   return ++__result;
 587 }
 588
 589 template <class _InputIter, class _OutputIter>
 590 inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
 591                                _OutputIter __result) {
 592   if (__first == __last) return __result;
 593   return __unique_copy(__first, __last, __result,
 594                        __ITERATOR_CATEGORY(__result));
 595 }
 596
 597 template <class _InputIter, class _OutputIter, class _BinaryPredicate,
 598           class _Tp>
 599 _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
 600                           _OutputIter __result,
 601                           _BinaryPredicate __binary_pred, _Tp*) {
 602   _Tp __value = *__first;
 603   *__result = __value;
 604   while (++__first != __last)
 605     if (!__binary_pred(__value, *__first)) {
 606       __value = *__first;
 607       *++__result = __value;
 608     }
 609   return ++__result;
 610 }
 611
 612 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
 613 inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,
 614                                  _OutputIter __result,
 615                                  _BinaryPredicate __binary_pred,
 616                                  output_iterator_tag) {
 617   return __unique_copy(__first, __last, __result, __binary_pred,
 618                        __VALUE_TYPE(__first));
 619 }
 620
 621 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
 622 _ForwardIter __unique_copy(_InputIter __first, _InputIter __last,
 623                            _ForwardIter __result,
 624                            _BinaryPredicate __binary_pred,
 625                            forward_iterator_tag) {
 626   *__result = *__first;
 627   while (++__first != __last)
 628     if (!__binary_pred(*__result, *__first)) *++__result = *__first;
 629   return ++__result;
 630 }
 631
 632 template <class _InputIter, class _OutputIter, class _BinaryPredicate>
 633 inline _OutputIter unique_copy(_InputIter __first, _InputIter __last,
 634                                _OutputIter __result,
 635                                _BinaryPredicate __binary_pred) {
 636   if (__first == __last) return __result;
 637   return __unique_copy(__first, __last, __result, __binary_pred,
 638                        __ITERATOR_CATEGORY(__result));
 639 }
 640
 641 template <class _ForwardIter>
 642 _ForwardIter unique(_ForwardIter __first, _ForwardIter __last) {
 643   __first = adjacent_find(__first, __last);
 644   return unique_copy(__first, __last, __first);
 645 }
 646
 647 template <class _ForwardIter, class _BinaryPredicate>
 648 _ForwardIter unique(_ForwardIter __first, _ForwardIter __last,
 649                     _BinaryPredicate __binary_pred) {
 650   __first = adjacent_find(__first, __last, __binary_pred);
 651   return unique_copy(__first, __last, __first, __binary_pred);
 652 }
 653
 654 // reverse and reverse_copy, and their auxiliary functions
 655
 656 template <class _BidirectionalIter>
 657 void __reverse(_BidirectionalIter __first, _BidirectionalIter __last,
 658                bidirectional_iterator_tag) {
 659   while (true)
 660     if (__first == __last || __first == --__last)
 661       return;
 662     else
 663       iter_swap(__first++, __last);
 664 }
 665
 666 template <class _RandomAccessIter>
 667 void __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
 668                random_access_iterator_tag) {
 669   while (__first < __last)
 670     iter_swap(__first++, --__last);
 671 }
 672
 673 template <class _BidirectionalIter>
 674 inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
 675   __reverse(__first, __last, __ITERATOR_CATEGORY(__first));
 676 }
 677
 678 template <class _BidirectionalIter, class _OutputIter>
 679 _OutputIter reverse_copy(_BidirectionalIter __first,
 680                             _BidirectionalIter __last,
 681                             _OutputIter __result) {
 682   while (__first != __last) {
 683     --__last;
 684     *__result = *__last;
 685     ++__result;
 686   }
 687   return __result;
 688 }
 689
 690 // rotate and rotate_copy, and their auxiliary functions
 691
 692 template <class _EuclideanRingElement>
 693 _EuclideanRingElement __gcd(_EuclideanRingElement __m,
 694                             _EuclideanRingElement __n)
 695 {
 696   while (__n != 0) {
 697     _EuclideanRingElement __t = __m % __n;
 698     __m = __n;
 699     __n = __t;
 700   }
 701   return __m;
 702 }
 703
 704 template <class _ForwardIter, class _Distance>
 705 _ForwardIter __rotate(_ForwardIter __first,
 706                       _ForwardIter __middle,
 707                       _ForwardIter __last,
 708                       _Distance*,
 709                       forward_iterator_tag) {
 710   if (__first == __middle)
 711     return __last;
 712   if (__last  == __middle)
 713     return __first;
 714
 715   _ForwardIter __first2 = __middle;
 716   do {
 717     swap(*__first++, *__first2++);
 718     if (__first == __middle)
 719       __middle = __first2;
 720   } while (__first2 != __last);
 721
 722   _ForwardIter __new_middle = __first;
 723
 724   __first2 = __middle;
 725
 726   while (__first2 != __last) {
 727     swap (*__first++, *__first2++);
 728     if (__first == __middle)
 729       __middle = __first2;
 730     else if (__first2 == __last)
 731       __first2 = __middle;
 732   }
 733
 734   return __new_middle;
 735 }
 736
 737
 738 template <class _BidirectionalIter, class _Distance>
 739 _BidirectionalIter __rotate(_BidirectionalIter __first,
 740                             _BidirectionalIter __middle,
 741                             _BidirectionalIter __last,
 742                             _Distance*,
 743                             bidirectional_iterator_tag) {
 744   if (__first == __middle)
 745     return __last;
 746   if (__last  == __middle)
 747     return __first;
 748
 749   __reverse(__first,  __middle, bidirectional_iterator_tag());
 750   __reverse(__middle, __last,   bidirectional_iterator_tag());
 751
 752   while (__first != __middle && __middle != __last)
 753     swap (*__first++, *--__last);
 754
 755   if (__first == __middle) {
 756     __reverse(__middle, __last,   bidirectional_iterator_tag());
 757     return __last;
 758   }
 759   else {
 760     __reverse(__first,  __middle, bidirectional_iterator_tag());
 761     return __first;
 762   }
 763 }
 764
 765 template <class _RandomAccessIter, class _Distance, class _Tp>
 766 _RandomAccessIter __rotate(_RandomAccessIter __first,
 767                            _RandomAccessIter __middle,
 768                            _RandomAccessIter __last,
 769                            _Distance *, _Tp *) {
 770
 771   _Distance __n = __last   - __first;
 772   _Distance __k = __middle - __first;
 773   _Distance __l = __n - __k;
 774   _RandomAccessIter __result = __first + (__last - __middle);
 775
 776   if (__k == __l) {
 777     swap_ranges(__first, __middle, __middle);
 778     return __result;
 779   }
 780
 781   _Distance __d = __gcd(__n, __k);
 782
 783   for (_Distance __i = 0; __i < __d; __i++) {
 784     _Tp __tmp = *__first;
 785     _RandomAccessIter __p = __first;
 786
 787     if (__k < __l) {
 788       for (_Distance __j = 0; __j < __l/__d; __j++) {
 789         if (__p > __first + __l) {
 790           *__p = *(__p - __l);
 791           __p -= __l;
 792         }
 793
 794         *__p = *(__p + __k);
 795         __p += __k;
 796       }
 797     }
 798
 799     else {
 800       for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
 801         if (__p < __last - __k) {
 802           *__p = *(__p + __k);
 803           __p += __k;
 804         }
 805
 806         *__p = * (__p - __l);
 807         __p -= __l;
 808       }
 809     }
 810
 811     *__p = __tmp;
 812     ++__first;
 813   }
 814
 815   return __result;
 816 }
 817
 818 template <class _ForwardIter>
 819 inline _ForwardIter rotate(_ForwardIter __first, _ForwardIter __middle,
 820                            _ForwardIter __last) {
 821   return __rotate(__first, __middle, __last,
 822                   __DISTANCE_TYPE(__first),
 823                   __ITERATOR_CATEGORY(__first));
 824 }
 825
 826 template <class _ForwardIter, class _OutputIter>
 827 _OutputIter rotate_copy(_ForwardIter __first, _ForwardIter __middle,
 828                             _ForwardIter __last, _OutputIter __result) {
 829   return copy(__first, __middle, copy(__middle, __last, __result));
 830 }
 831
 832 // Return a random number in the range [0, __n).  This function encapsulates
 833 // whether we're using rand (part of the standard C library) or lrand48
 834 // (not standard, but a much better choice whenever it's available).
 835
 836 template <class _Distance>
 837 inline _Distance __random_number(_Distance __n) {
 838 #ifdef __STL_NO_DRAND48
 839   return rand() % __n;
 840 #else
 841   return lrand48() % __n;
 842 #endif
 843 }
 844
 845 // random_shuffle
 846
 847 template <class _RandomAccessIter>
 848 inline void random_shuffle(_RandomAccessIter __first,
 849                            _RandomAccessIter __last) {
 850   if (__first == __last) return;
 851   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
 852     iter_swap(__i, __first + __random_number((__i - __first) + 1));
 853 }
 854
 855 template <class _RandomAccessIter, class _RandomNumberGenerator>
 856 void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
 857                     _RandomNumberGenerator& __rand) {
 858   if (__first == __last) return;
 859   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
 860     iter_swap(__i, __first + __rand((__i - __first) + 1));
 861 }
 862
 863 // random_sample and random_sample_n (extensions, not part of the standard).
 864
 865 template <class _ForwardIter, class _OutputIter, class _Distance>
 866 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
 867                             _OutputIter __out, const _Distance __n)
 868 {
 869   _Distance __remaining = 0;
 870   distance(__first, __last, __remaining);
 871   _Distance __m = min(__n, __remaining);
 872
 873   while (__m > 0) {
 874     if (__random_number(__remaining) < __m) {
 875       *__out = *__first;
 876       ++__out;
 877       --__m;
 878     }
 879
 880     --__remaining;
 881     ++__first;
 882   }
 883   return __out;
 884 }
 885
 886 template <class _ForwardIter, class _OutputIter, class _Distance,
 887           class _RandomNumberGenerator>
 888 _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
 889                             _OutputIter __out, const _Distance __n,
 890                             _RandomNumberGenerator& __rand)
 891 {
 892   _Distance __remaining = 0;
 893   distance(__first, __last, __remaining);
 894   _Distance __m = min(__n, __remaining);
 895
 896   while (__m > 0) {
 897     if (__rand(__remaining) < __m) {
 898       *__out = *__first;
 899       ++__out;
 900       --__m;
 901     }
 902
 903     --__remaining;
 904     ++__first;
 905   }
 906   return __out;
 907 }
 908
 909 template <class _InputIter, class _RandomAccessIter, class _Distance>
 910 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
 911                                   _RandomAccessIter __out,
 912                                   const _Distance __n)
 913 {
 914   _Distance __m = 0;
 915   _Distance __t = __n;
 916   for ( ; __first != __last && __m < __n; ++__m, ++__first)
 917     __out[__m] = *__first;
 918
 919   while (__first != __last) {
 920     ++__t;
 921     _Distance __M = __random_number(__t);
 922     if (__M < __n)
 923       __out[__M] = *__first;
 924     ++__first;
 925   }
 926
 927   return __out + __m;
 928 }
 929
 930 template <class _InputIter, class _RandomAccessIter,
 931           class _RandomNumberGenerator, class _Distance>
 932 _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
 933                                   _RandomAccessIter __out,
 934                                   _RandomNumberGenerator& __rand,
 935                                   const _Distance __n)
 936 {
 937   _Distance __m = 0;
 938   _Distance __t = __n;
 939   for ( ; __first != __last && __m < __n; ++__m, ++__first)
 940     __out[__m] = *__first;
 941
 942   while (__first != __last) {
 943     ++__t;
 944     _Distance __M = __rand(__t);
 945     if (__M < __n)
 946       __out[__M] = *__first;
 947     ++__first;
 948   }
 949
 950   return __out + __m;
 951 }
 952
 953 template <class _InputIter, class _RandomAccessIter>
 954 inline _RandomAccessIter
 955 random_sample(_InputIter __first, _InputIter __last,
 956               _RandomAccessIter __out_first, _RandomAccessIter __out_last)
 957 {
 958   return __random_sample(__first, __last,
 959                          __out_first, __out_last - __out_first);
 960 }
 961
 962
 963 template <class _InputIter, class _RandomAccessIter,
 964           class _RandomNumberGenerator>
 965 inline _RandomAccessIter
 966 random_sample(_InputIter __first, _InputIter __last,
 967               _RandomAccessIter __out_first, _RandomAccessIter __out_last,
 968               _RandomNumberGenerator& __rand)
 969 {
 970   return __random_sample(__first, __last,
 971                          __out_first, __rand,
 972                          __out_last - __out_first);
 973 }
 974
 975 // partition, stable_partition, and their auxiliary functions
 976
 977 template <class _ForwardIter, class _Predicate>
 978 _ForwardIter __partition(_ForwardIter __first,
 979                          _ForwardIter __last,
 980                          _Predicate   __pred,
 981                          forward_iterator_tag) {
 982   if (__first == __last) return __first;
 983
 984   while (__pred(*__first))
 985     if (++__first == __last) return __first;
 986
 987   _ForwardIter __next = __first;
 988
 989   while (++__next != __last)
 990     if (__pred(*__next)) {
 991       swap(*__first, *__next);
 992       ++__first;
 993     }
 994
 995   return __first;
 996 }
 997
 998 template <class _BidirectionalIter, class _Predicate>
 999 _BidirectionalIter __partition(_BidirectionalIter __first,
1000                                _BidirectionalIter __last,
1001                                _Predicate __pred,
1002                                bidirectional_iterator_tag) {
1003   while (true) {
1004     while (true)
1005       if (__first == __last)
1006         return __first;
1007       else if (__pred(*__first))
1008         ++__first;
1009       else
1010         break;
1011     --__last;
1012     while (true)
1013       if (__first == __last)
1014         return __first;
1015       else if (!__pred(*__last))
1016         --__last;
1017       else
1018         break;
1019     iter_swap(__first, __last);
1020     ++__first;
1021   }
1022 }
1023
1024 template <class _ForwardIter, class _Predicate>
1025 inline _ForwardIter partition(_ForwardIter __first,
1026                               _ForwardIter __last,
1027                               _Predicate   __pred) {
1028   return __partition(__first, __last, __pred, __ITERATOR_CATEGORY(__first));
1029 }
1030
1031
1032 template <class _ForwardIter, class _Predicate, class _Distance>
1033 _ForwardIter __inplace_stable_partition(_ForwardIter __first,
1034                                         _ForwardIter __last,
1035                                         _Predicate __pred, _Distance __len) {
1036   if (__len == 1)
1037     return __pred(*__first) ? __last : __first;
1038   _ForwardIter __middle = __first;
1039   advance(__middle, __len / 2);
1040   return rotate(__inplace_stable_partition(__first, __middle, __pred,
1041                                            __len / 2),
1042                 __middle,
1043                 __inplace_stable_partition(__middle, __last, __pred,
1044                                            __len - __len / 2));
1045 }
1046
1047 template <class _ForwardIter, class _Pointer, class _Predicate,
1048           class _Distance>
1049 _ForwardIter __stable_partition_adaptive(_ForwardIter __first,
1050                                          _ForwardIter __last,
1051                                          _Predicate __pred, _Distance __len,
1052                                          _Pointer __buffer,
1053                                          _Distance __buffer_size)
1054 {
1055   if (__len <= __buffer_size) {
1056     _ForwardIter __result1 = __first;
1057     _Pointer __result2 = __buffer;
1058     for ( ; __first != __last ; ++__first)
1059       if (__pred(*__first)) {
1060         *__result1 = *__first;
1061         ++__result1;
1062       }
1063       else {
1064         *__result2 = *__first;
1065         ++__result2;
1066       }
1067     copy(__buffer, __result2, __result1);
1068     return __result1;
1069   }
1070   else {
1071     _ForwardIter __middle = __first;
1072     advance(__middle, __len / 2);
1073     return rotate(__stable_partition_adaptive(
1074                           __first, __middle, __pred,
1075                           __len / 2, __buffer, __buffer_size),
1076                     __middle,
1077                     __stable_partition_adaptive(
1078                           __middle, __last, __pred,
1079                           __len - __len / 2, __buffer, __buffer_size));
1080   }
1081 }
1082
1083 template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
1084 inline _ForwardIter
1085 __stable_partition_aux(_ForwardIter __first, _ForwardIter __last,
1086                        _Predicate __pred, _Tp*, _Distance*)
1087 {
1088   _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
1089   if (__buf.size() > 0)
1090     return __stable_partition_adaptive(__first, __last, __pred,
1091                                        _Distance(__buf.requested_size()),
1092                                        __buf.begin(), __buf.size());
1093   else
1094     return __inplace_stable_partition(__first, __last, __pred,
1095                                       _Distance(__buf.requested_size()));
1096 }
1097
1098 template <class _ForwardIter, class _Predicate>
1099 inline _ForwardIter stable_partition(_ForwardIter __first,
1100                                      _ForwardIter __last,
1101                                      _Predicate __pred) {
1102   if (__first == __last)
1103     return __first;
1104   else
1105     return __stable_partition_aux(__first, __last, __pred,
1106                                   __VALUE_TYPE(__first),
1107                                   __DISTANCE_TYPE(__first));
1108 }
1109
1110 template <class _RandomAccessIter, class _Tp>
1111 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
1112                                         _RandomAccessIter __last,
1113                                         _Tp __pivot)
1114 {
1115   while (true) {
1116     while (*__first < __pivot)
1117       ++__first;
1118     --__last;
1119     while (__pivot < *__last)
1120       --__last;
1121     if (!(__first < __last))
1122       return __first;
1123     iter_swap(__first, __last);
1124     ++__first;
1125   }
1126 }
1127
1128 template <class _RandomAccessIter, class _Tp, class _Compare>
1129 _RandomAccessIter __unguarded_partition(_RandomAccessIter __first,
1130                                         _RandomAccessIter __last,
1131                                         _Tp __pivot, _Compare __comp)
1132 {
1133   while (true) {
1134     while (__comp(*__first, __pivot))
1135       ++__first;
1136     --__last;
1137     while (__comp(__pivot, *__last))
1138       --__last;
1139     if (!(__first < __last))
1140       return __first;
1141     iter_swap(__first, __last);
1142     ++__first;
1143   }
1144 }
1145
1146 const int __stl_threshold = 16;
1147
1148 // sort() and its auxiliary functions.
1149
1150 template <class _RandomAccessIter, class _Tp>
1151 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val) {
1152   _RandomAccessIter __next = __last;
1153   --__next;
1154   while (__val < *__next) {
1155     *__last = *__next;
1156     __last = __next;
1157     --__next;
1158   }
1159   *__last = __val;
1160 }
1161
1162 template <class _RandomAccessIter, class _Tp, class _Compare>
1163 void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val,
1164                                _Compare __comp) {
1165   _RandomAccessIter __next = __last;
1166   --__next;
1167   while (__comp(__val, *__next)) {
1168     *__last = *__next;
1169     __last = __next;
1170     --__next;
1171   }
1172   *__last = __val;
1173 }
1174
1175 template <class _RandomAccessIter, class _Tp>
1176 inline void __linear_insert(_RandomAccessIter __first,
1177                             _RandomAccessIter __last, _Tp*) {
1178   _Tp __val = *__last;
1179   if (__val < *__first) {
1180     copy_backward(__first, __last, __last + 1);
1181     *__first = __val;
1182   }
1183   else
1184     __unguarded_linear_insert(__last, __val);
1185 }
1186
1187 template <class _RandomAccessIter, class _Tp, class _Compare>
1188 inline void __linear_insert(_RandomAccessIter __first,
1189                             _RandomAccessIter __last, _Tp*, _Compare __comp) {
1190   _Tp __val = *__last;
1191   if (__comp(__val, *__first)) {
1192     copy_backward(__first, __last, __last + 1);
1193     *__first = __val;
1194   }
1195   else
1196     __unguarded_linear_insert(__last, __val, __comp);
1197 }
1198
1199 template <class _RandomAccessIter>
1200 void __insertion_sort(_RandomAccessIter __first, _RandomAccessIter __last) {
1201   if (__first == __last) return;
1202   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1203     __linear_insert(__first, __i, __VALUE_TYPE(__first));
1204 }
1205
1206 template <class _RandomAccessIter, class _Compare>
1207 void __insertion_sort(_RandomAccessIter __first,
1208                       _RandomAccessIter __last, _Compare __comp) {
1209   if (__first == __last) return;
1210   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
1211     __linear_insert(__first, __i, __VALUE_TYPE(__first), __comp);
1212 }
1213
1214 template <class _RandomAccessIter, class _Tp>
1215 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
1216                                     _RandomAccessIter __last, _Tp*) {
1217   for (_RandomAccessIter __i = __first; __i != __last; ++__i)
1218     __unguarded_linear_insert(__i, _Tp(*__i));
1219 }
1220
1221 template <class _RandomAccessIter>
1222 inline void __unguarded_insertion_sort(_RandomAccessIter __first,
1223                                 _RandomAccessIter __last) {
1224   __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first));
1225 }
1226
1227 template <class _RandomAccessIter, class _Tp, class _Compare>
1228 void __unguarded_insertion_sort_aux(_RandomAccessIter __first,
1229                                     _RandomAccessIter __last,
1230                                     _Tp*, _Compare __comp) {
1231   for (_RandomAccessIter __i = __first; __i != __last; ++__i)
1232     __unguarded_linear_insert(__i, _Tp(*__i), __comp);
1233 }
1234
1235 template <class _RandomAccessIter, class _Compare>
1236 inline void __unguarded_insertion_sort(_RandomAccessIter __first,
1237                                        _RandomAccessIter __last,
1238                                        _Compare __comp) {
1239   __unguarded_insertion_sort_aux(__first, __last, __VALUE_TYPE(__first),
1240                                  __comp);
1241 }
1242
1243 template <class _RandomAccessIter>
1244 void __final_insertion_sort(_RandomAccessIter __first,
1245                             _RandomAccessIter __last) {
1246   if (__last - __first > __stl_threshold) {
1247     __insertion_sort(__first, __first + __stl_threshold);
1248     __unguarded_insertion_sort(__first + __stl_threshold, __last);
1249   }
1250   else
1251     __insertion_sort(__first, __last);
1252 }
1253
1254 template <class _RandomAccessIter, class _Compare>
1255 void __final_insertion_sort(_RandomAccessIter __first,
1256                             _RandomAccessIter __last, _Compare __comp) {
1257   if (__last - __first > __stl_threshold) {
1258     __insertion_sort(__first, __first + __stl_threshold, __comp);
1259     __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
1260   }
1261   else
1262     __insertion_sort(__first, __last, __comp);
1263 }
1264
1265 template <class _Size>
1266 inline _Size __lg(_Size __n) {
1267   _Size __k;
1268   for (__k = 0; __n != 1; __n >>= 1) ++__k;
1269   return __k;
1270 }
1271
1272 template <class _RandomAccessIter, class _Tp, class _Size>
1273 void __introsort_loop(_RandomAccessIter __first,
1274                       _RandomAccessIter __last, _Tp*,
1275                       _Size __depth_limit)
1276 {
1277   while (__last - __first > __stl_threshold) {
1278     if (__depth_limit == 0) {
1279       partial_sort(__first, __last, __last);
1280       return;
1281     }
1282     --__depth_limit;
1283     _RandomAccessIter __cut =
1284       __unguarded_partition(__first, __last,
1285                             _Tp(__median(*__first,
1286                                          *(__first + (__last - __first)/2),
1287                                          *(__last - 1))));
1288     __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit);
1289     __last = __cut;
1290   }
1291 }
1292
1293 template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
1294 void __introsort_loop(_RandomAccessIter __first,
1295                       _RandomAccessIter __last, _Tp*,
1296                       _Size __depth_limit, _Compare __comp)
1297 {
1298   while (__last - __first > __stl_threshold) {
1299     if (__depth_limit == 0) {
1300       partial_sort(__first, __last, __last, __comp);
1301       return;
1302     }
1303     --__depth_limit;
1304     _RandomAccessIter __cut =
1305       __unguarded_partition(__first, __last,
1306                             _Tp(__median(*__first,
1307                                          *(__first + (__last - __first)/2),
1308                                          *(__last - 1), __comp)),
1309        __comp);
1310     __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
1311     __last = __cut;
1312   }
1313 }
1314
1315 template <class _RandomAccessIter>
1316 inline void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
1317   if (__first != __last) {
1318     __introsort_loop(__first, __last,
1319                      __VALUE_TYPE(__first),
1320                      __lg(__last - __first) * 2);
1321     __final_insertion_sort(__first, __last);
1322   }
1323 }
1324
1325 template <class _RandomAccessIter, class _Compare>
1326 inline void sort(_RandomAccessIter __first, _RandomAccessIter __last,
1327                  _Compare __comp) {
1328   if (__first != __last) {
1329     __introsort_loop(__first, __last,
1330                      __VALUE_TYPE(__first),
1331                      __lg(__last - __first) * 2,
1332                      __comp);
1333     __final_insertion_sort(__first, __last, __comp);
1334   }
1335 }
1336
1337 // stable_sort() and its auxiliary functions.
1338
1339 template <class _RandomAccessIter>
1340 void __inplace_stable_sort(_RandomAccessIter __first,
1341                            _RandomAccessIter __last) {
1342   if (__last - __first < 15) {
1343     __insertion_sort(__first, __last);
1344     return;
1345   }
1346   _RandomAccessIter __middle = __first + (__last - __first) / 2;
1347   __inplace_stable_sort(__first, __middle);
1348   __inplace_stable_sort(__middle, __last);
1349   __merge_without_buffer(__first, __middle, __last,
1350                          __middle - __first,
1351                          __last - __middle);
1352 }
1353
1354 template <class _RandomAccessIter, class _Compare>
1355 void __inplace_stable_sort(_RandomAccessIter __first,
1356                            _RandomAccessIter __last, _Compare __comp) {
1357   if (__last - __first < 15) {
1358     __insertion_sort(__first, __last, __comp);
1359     return;
1360   }
1361   _RandomAccessIter __middle = __first + (__last - __first) / 2;
1362   __inplace_stable_sort(__first, __middle, __comp);
1363   __inplace_stable_sort(__middle, __last, __comp);
1364   __merge_without_buffer(__first, __middle, __last,
1365                          __middle - __first,
1366                          __last - __middle,
1367                          __comp);
1368 }
1369
1370 template <class _RandomAccessIter1, class _RandomAccessIter2,
1371           class _Distance>
1372 void __merge_sort_loop(_RandomAccessIter1 __first,
1373                        _RandomAccessIter1 __last,
1374                        _RandomAccessIter2 __result, _Distance __step_size) {
1375   _Distance __two_step = 2 * __step_size;
1376
1377   while (__last - __first >= __two_step) {
1378     __result = merge(__first, __first + __step_size,
1379                      __first + __step_size, __first + __two_step,
1380                      __result);
1381     __first += __two_step;
1382   }
1383
1384   __step_size = min(_Distance(__last - __first), __step_size);
1385   merge(__first, __first + __step_size, __first + __step_size, __last,
1386         __result);
1387 }
1388
1389 template <class _RandomAccessIter1, class _RandomAccessIter2,
1390           class _Distance, class _Compare>
1391 void __merge_sort_loop(_RandomAccessIter1 __first,
1392                        _RandomAccessIter1 __last,
1393                        _RandomAccessIter2 __result, _Distance __step_size,
1394                        _Compare __comp) {
1395   _Distance __two_step = 2 * __step_size;
1396
1397   while (__last - __first >= __two_step) {
1398     __result = merge(__first, __first + __step_size,
1399                      __first + __step_size, __first + __two_step,
1400                      __result,
1401                      __comp);
1402     __first += __two_step;
1403   }
1404   __step_size = min(_Distance(__last - __first), __step_size);
1405
1406   merge(__first, __first + __step_size,
1407         __first + __step_size, __last,
1408         __result,
1409         __comp);
1410 }
1411
1412 const int __stl_chunk_size = 7;
1413
1414 template <class _RandomAccessIter, class _Distance>
1415 void __chunk_insertion_sort(_RandomAccessIter __first,
1416                             _RandomAccessIter __last, _Distance __chunk_size)
1417 {
1418   while (__last - __first >= __chunk_size) {
1419     __insertion_sort(__first, __first + __chunk_size);
1420     __first += __chunk_size;
1421   }
1422   __insertion_sort(__first, __last);
1423 }
1424
1425 template <class _RandomAccessIter, class _Distance, class _Compare>
1426 void __chunk_insertion_sort(_RandomAccessIter __first,
1427                             _RandomAccessIter __last,
1428                             _Distance __chunk_size, _Compare __comp)
1429 {
1430   while (__last - __first >= __chunk_size) {
1431     __insertion_sort(__first, __first + __chunk_size, __comp);
1432     __first += __chunk_size;
1433   }
1434   __insertion_sort(__first, __last, __comp);
1435 }
1436
1437 template <class _RandomAccessIter, class _Pointer, class _Distance>
1438 void __merge_sort_with_buffer(_RandomAccessIter __first,
1439                               _RandomAccessIter __last,
1440                               _Pointer __buffer, _Distance*) {
1441   _Distance __len = __last - __first;
1442   _Pointer __buffer_last = __buffer + __len;
1443
1444   _Distance __step_size = __stl_chunk_size;
1445   __chunk_insertion_sort(__first, __last, __step_size);
1446
1447   while (__step_size < __len) {
1448     __merge_sort_loop(__first, __last, __buffer, __step_size);
1449     __step_size *= 2;
1450     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
1451     __step_size *= 2;
1452   }
1453 }
1454
1455 template <class _RandomAccessIter, class _Pointer, class _Distance,
1456           class _Compare>
1457 void __merge_sort_with_buffer(_RandomAccessIter __first,
1458                               _RandomAccessIter __last, _Pointer __buffer,
1459                               _Distance*, _Compare __comp) {
1460   _Distance __len = __last - __first;
1461   _Pointer __buffer_last = __buffer + __len;
1462
1463   _Distance __step_size = __stl_chunk_size;
1464   __chunk_insertion_sort(__first, __last, __step_size, __comp);
1465
1466   while (__step_size < __len) {
1467     __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
1468     __step_size *= 2;
1469     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
1470     __step_size *= 2;
1471   }
1472 }
1473
1474 template <class _RandomAccessIter, class _Pointer, class _Distance>
1475 void __stable_sort_adaptive(_RandomAccessIter __first,
1476                             _RandomAccessIter __last, _Pointer __buffer,
1477                             _Distance __buffer_size) {
1478   _Distance __len = (__last - __first + 1) / 2;
1479   _RandomAccessIter __middle = __first + __len;
1480   if (__len > __buffer_size) {
1481     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size);
1482     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size);
1483   }
1484   else {
1485     __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0);
1486     __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0);
1487   }
1488   __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
1489                    _Distance(__last - __middle), __buffer, __buffer_size);
1490 }
1491
1492 template <class _RandomAccessIter, class _Pointer, class _Distance,
1493           class _Compare>
1494 void __stable_sort_adaptive(_RandomAccessIter __first,
1495                             _RandomAccessIter __last, _Pointer __buffer,
1496                             _Distance __buffer_size, _Compare __comp) {
1497   _Distance __len = (__last - __first + 1) / 2;
1498   _RandomAccessIter __middle = __first + __len;
1499   if (__len > __buffer_size) {
1500     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size,
1501                            __comp);
1502     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size,
1503                            __comp);
1504   }
1505   else {
1506     __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
1507                                __comp);
1508     __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
1509                                __comp);
1510   }
1511   __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first),
1512                    _Distance(__last - __middle), __buffer, __buffer_size,
1513                    __comp);
1514 }
1515
1516 template <class _RandomAccessIter, class _Tp, class _Distance>
1517 inline void __stable_sort_aux(_RandomAccessIter __first,
1518                               _RandomAccessIter __last, _Tp*, _Distance*) {
1519   _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
1520   if (buf.begin() == 0)
1521     __inplace_stable_sort(__first, __last);
1522   else
1523     __stable_sort_adaptive(__first, __last, buf.begin(),
1524                            _Distance(buf.size()));
1525 }
1526
1527 template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
1528 inline void __stable_sort_aux(_RandomAccessIter __first,
1529                               _RandomAccessIter __last, _Tp*, _Distance*,
1530                               _Compare __comp) {
1531   _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
1532   if (buf.begin() == 0)
1533     __inplace_stable_sort(__first, __last, __comp);
1534   else
1535     __stable_sort_adaptive(__first, __last, buf.begin(),
1536                            _Distance(buf.size()),
1537                            __comp);
1538 }
1539
1540 template <class _RandomAccessIter>
1541 inline void stable_sort(_RandomAccessIter __first,
1542                         _RandomAccessIter __last) {
1543   __stable_sort_aux(__first, __last,
1544                     __VALUE_TYPE(__first),
1545                     __DISTANCE_TYPE(__first));
1546 }
1547
1548 template <class _RandomAccessIter, class _Compare>
1549 inline void stable_sort(_RandomAccessIter __first,
1550                         _RandomAccessIter __last, _Compare __comp) {
1551   __stable_sort_aux(__first, __last,
1552                     __VALUE_TYPE(__first),
1553                     __DISTANCE_TYPE(__first),
1554                     __comp);
1555 }
1556
1557 // partial_sort, partial_sort_copy, and auxiliary functions.
1558
1559 template <class _RandomAccessIter, class _Tp>
1560 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
1561                     _RandomAccessIter __last, _Tp*) {
1562   make_heap(__first, __middle);
1563   for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
1564     if (*__i < *__first)
1565       __pop_heap(__first, __middle, __i, _Tp(*__i),
1566                  __DISTANCE_TYPE(__first));
1567   sort_heap(__first, __middle);
1568 }
1569
1570 template <class _RandomAccessIter>
1571 inline void partial_sort(_RandomAccessIter __first,
1572                          _RandomAccessIter __middle,
1573                          _RandomAccessIter __last) {
1574   __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first));
1575 }
1576
1577 template <class _RandomAccessIter, class _Tp, class _Compare>
1578 void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
1579                     _RandomAccessIter __last, _Tp*, _Compare __comp) {
1580   make_heap(__first, __middle, __comp);
1581   for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
1582     if (__comp(*__i, *__first))
1583       __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
1584                  __DISTANCE_TYPE(__first));
1585   sort_heap(__first, __middle, __comp);
1586 }
1587
1588 template <class _RandomAccessIter, class _Compare>
1589 inline void partial_sort(_RandomAccessIter __first,
1590                          _RandomAccessIter __middle,
1591                          _RandomAccessIter __last, _Compare __comp) {
1592   __partial_sort(__first, __middle, __last, __VALUE_TYPE(__first), __comp);
1593 }
1594
1595 template <class _InputIter, class _RandomAccessIter, class _Distance,
1596           class _Tp>
1597 _RandomAccessIter __partial_sort_copy(_InputIter __first,
1598                                          _InputIter __last,
1599                                          _RandomAccessIter __result_first,
1600                                          _RandomAccessIter __result_last,
1601                                          _Distance*, _Tp*) {
1602   if (__result_first == __result_last) return __result_last;
1603   _RandomAccessIter __result_real_last = __result_first;
1604   while(__first != __last && __result_real_last != __result_last) {
1605     *__result_real_last = *__first;
1606     ++__result_real_last;
1607     ++__first;
1608   }
1609   make_heap(__result_first, __result_real_last);
1610   while (__first != __last) {
1611     if (*__first < *__result_first)
1612       __adjust_heap(__result_first, _Distance(0),
1613                     _Distance(__result_real_last - __result_first),
1614                     _Tp(*__first));
1615     ++__first;
1616   }
1617   sort_heap(__result_first, __result_real_last);
1618   return __result_real_last;
1619 }
1620
1621 template <class _InputIter, class _RandomAccessIter>
1622 inline _RandomAccessIter
1623 partial_sort_copy(_InputIter __first, _InputIter __last,
1624                   _RandomAccessIter __result_first,
1625                   _RandomAccessIter __result_last) {
1626   return __partial_sort_copy(__first, __last, __result_first, __result_last,
1627                              __DISTANCE_TYPE(__result_first),
1628                              __VALUE_TYPE(__first));
1629 }
1630
1631 template <class _InputIter, class _RandomAccessIter, class _Compare,
1632           class _Distance, class _Tp>
1633 _RandomAccessIter __partial_sort_copy(_InputIter __first,
1634                                          _InputIter __last,
1635                                          _RandomAccessIter __result_first,
1636                                          _RandomAccessIter __result_last,
1637                                          _Compare __comp, _Distance*, _Tp*) {
1638   if (__result_first == __result_last) return __result_last;
1639   _RandomAccessIter __result_real_last = __result_first;
1640   while(__first != __last && __result_real_last != __result_last) {
1641     *__result_real_last = *__first;
1642     ++__result_real_last;
1643     ++__first;
1644   }
1645   make_heap(__result_first, __result_real_last, __comp);
1646   while (__first != __last) {
1647     if (__comp(*__first, *__result_first))
1648       __adjust_heap(__result_first, _Distance(0),
1649                     _Distance(__result_real_last - __result_first),
1650                     _Tp(*__first),
1651                     __comp);
1652     ++__first;
1653   }
1654   sort_heap(__result_first, __result_real_last, __comp);
1655   return __result_real_last;
1656 }
1657
1658 template <class _InputIter, class _RandomAccessIter, class _Compare>
1659 inline _RandomAccessIter
1660 partial_sort_copy(_InputIter __first, _InputIter __last,
1661                   _RandomAccessIter __result_first,
1662                   _RandomAccessIter __result_last, _Compare __comp) {
1663   return __partial_sort_copy(__first, __last, __result_first, __result_last,
1664                              __comp,
1665                              __DISTANCE_TYPE(__result_first),
1666                              __VALUE_TYPE(__first));
1667 }
1668
1669 // nth_element() and its auxiliary functions.
1670
1671 template <class _RandomAccessIter, class _Tp>
1672 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1673                    _RandomAccessIter __last, _Tp*) {
1674   while (__last - __first > 3) {
1675     _RandomAccessIter __cut =
1676       __unguarded_partition(__first, __last,
1677                             _Tp(__median(*__first,
1678                                          *(__first + (__last - __first)/2),
1679                                          *(__last - 1))));
1680     if (__cut <= __nth)
1681       __first = __cut;
1682     else
1683       __last = __cut;
1684   }
1685   __insertion_sort(__first, __last);
1686 }
1687
1688 template <class _RandomAccessIter>
1689 inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1690                         _RandomAccessIter __last) {
1691   __nth_element(__first, __nth, __last, __VALUE_TYPE(__first));
1692 }
1693
1694 template <class _RandomAccessIter, class _Tp, class _Compare>
1695 void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1696                    _RandomAccessIter __last, _Tp*, _Compare __comp) {
1697   while (__last - __first > 3) {
1698     _RandomAccessIter __cut =
1699       __unguarded_partition(__first, __last,
1700                             _Tp(__median(*__first,
1701                                          *(__first + (__last - __first)/2),
1702                                          *(__last - 1),
1703                                          __comp)),
1704                             __comp);
1705     if (__cut <= __nth)
1706       __first = __cut;
1707     else
1708       __last = __cut;
1709   }
1710   __insertion_sort(__first, __last, __comp);
1711 }
1712
1713 template <class _RandomAccessIter, class _Compare>
1714 inline void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
1715                  _RandomAccessIter __last, _Compare __comp) {
1716   __nth_element(__first, __nth, __last, __VALUE_TYPE(__first), __comp);
1717 }
1718
1719
1720 // Binary search (lower_bound, upper_bound, equal_range, binary_search).
1721
1722 template <class _ForwardIter, class _Tp, class _Distance>
1723 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
1724                            const _Tp& __val, _Distance*)
1725 {
1726   _Distance __len = 0;
1727   distance(__first, __last, __len);
1728   _Distance __half;
1729   _ForwardIter __middle;
1730
1731   while (__len > 0) {
1732     __half = __len >> 1;
1733     __middle = __first;
1734     advance(__middle, __half);
1735     if (*__middle < __val) {
1736       __first = __middle;
1737       ++__first;
1738       __len = __len - __half - 1;
1739     }
1740     else
1741       __len = __half;
1742   }
1743   return __first;
1744 }
1745
1746 template <class _ForwardIter, class _Tp>
1747 inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
1748                                    const _Tp& __val) {
1749   return __lower_bound(__first, __last, __val,
1750                        __DISTANCE_TYPE(__first));
1751 }
1752
1753 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
1754 _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
1755                               const _Tp& __val, _Compare __comp, _Distance*)
1756 {
1757   _Distance __len = 0;
1758   distance(__first, __last, __len);
1759   _Distance __half;
1760   _ForwardIter __middle;
1761
1762   while (__len > 0) {
1763     __half = __len >> 1;
1764     __middle = __first;
1765     advance(__middle, __half);
1766     if (__comp(*__middle, __val)) {
1767       __first = __middle;
1768       ++__first;
1769       __len = __len - __half - 1;
1770     }
1771     else
1772       __len = __half;
1773   }
1774   return __first;
1775 }
1776
1777 template <class _ForwardIter, class _Tp, class _Compare>
1778 inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
1779                                 const _Tp& __val, _Compare __comp) {
1780   return __lower_bound(__first, __last, __val, __comp,
1781                        __DISTANCE_TYPE(__first));
1782 }
1783
1784 template <class _ForwardIter, class _Tp, class _Distance>
1785 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
1786                            const _Tp& __val, _Distance*)
1787 {
1788   _Distance __len = 0;
1789   distance(__first, __last, __len);
1790   _Distance __half;
1791   _ForwardIter __middle;
1792
1793   while (__len > 0) {
1794     __half = __len >> 1;
1795     __middle = __first;
1796     advance(__middle, __half);
1797     if (__val < *__middle)
1798       __len = __half;
1799     else {
1800       __first = __middle;
1801       ++__first;
1802       __len = __len - __half - 1;
1803     }
1804   }
1805   return __first;
1806 }
1807
1808 template <class _ForwardIter, class _Tp>
1809 inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
1810                                 const _Tp& __val) {
1811   return __upper_bound(__first, __last, __val,
1812                        __DISTANCE_TYPE(__first));
1813 }
1814
1815 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
1816 _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
1817                            const _Tp& __val, _Compare __comp, _Distance*)
1818 {
1819   _Distance __len = 0;
1820   distance(__first, __last, __len);
1821   _Distance __half;
1822   _ForwardIter __middle;
1823
1824   while (__len > 0) {
1825     __half = __len >> 1;
1826     __middle = __first;
1827     advance(__middle, __half);
1828     if (__comp(__val, *__middle))
1829       __len = __half;
1830     else {
1831       __first = __middle;
1832       ++__first;
1833       __len = __len - __half - 1;
1834     }
1835   }
1836   return __first;
1837 }
1838
1839 template <class _ForwardIter, class _Tp, class _Compare>
1840 inline _ForwardIter upper_bound(_ForwardIter __first, _ForwardIter __last,
1841                                 const _Tp& __val, _Compare __comp) {
1842   return __upper_bound(__first, __last, __val, __comp,
1843                        __DISTANCE_TYPE(__first));
1844 }
1845
1846 template <class _ForwardIter, class _Tp, class _Distance>
1847 pair<_ForwardIter, _ForwardIter>
1848 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1849               _Distance*)
1850 {
1851   _Distance __len = 0;
1852   distance(__first, __last, __len);
1853   _Distance __half;
1854   _ForwardIter __middle, __left, __right;
1855
1856   while (__len > 0) {
1857     __half = __len >> 1;
1858     __middle = __first;
1859     advance(__middle, __half);
1860     if (*__middle < __val) {
1861       __first = __middle;
1862       ++__first;
1863       __len = __len - __half - 1;
1864     }
1865     else if (__val < *__middle)
1866       __len = __half;
1867     else {
1868       __left = lower_bound(__first, __middle, __val);
1869       advance(__first, __len);
1870       __right = upper_bound(++__middle, __first, __val);
1871       return pair<_ForwardIter, _ForwardIter>(__left, __right);
1872     }
1873   }
1874   return pair<_ForwardIter, _ForwardIter>(__first, __first);
1875 }
1876
1877 template <class _ForwardIter, class _Tp>
1878 inline pair<_ForwardIter, _ForwardIter>
1879 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val) {
1880   return __equal_range(__first, __last, __val,
1881                        __DISTANCE_TYPE(__first));
1882 }
1883
1884 template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
1885 pair<_ForwardIter, _ForwardIter>
1886 __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1887               _Compare __comp, _Distance*)
1888 {
1889   _Distance __len = 0;
1890   distance(__first, __last, __len);
1891   _Distance __half;
1892   _ForwardIter __middle, __left, __right;
1893
1894   while (__len > 0) {
1895     __half = __len >> 1;
1896     __middle = __first;
1897     advance(__middle, __half);
1898     if (__comp(*__middle, __val)) {
1899       __first = __middle;
1900       ++__first;
1901       __len = __len - __half - 1;
1902     }
1903     else if (__comp(__val, *__middle))
1904       __len = __half;
1905     else {
1906       __left = lower_bound(__first, __middle, __val, __comp);
1907       advance(__first, __len);
1908       __right = upper_bound(++__middle, __first, __val, __comp);
1909       return pair<_ForwardIter, _ForwardIter>(__left, __right);
1910     }
1911   }
1912   return pair<_ForwardIter, _ForwardIter>(__first, __first);
1913 }
1914
1915 template <class _ForwardIter, class _Tp, class _Compare>
1916 inline pair<_ForwardIter, _ForwardIter>
1917 equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
1918             _Compare __comp) {
1919   return __equal_range(__first, __last, __val, __comp,
1920                        __DISTANCE_TYPE(__first));
1921 }
1922
1923 template <class _ForwardIter, class _Tp>
1924 bool binary_search(_ForwardIter __first, _ForwardIter __last,
1925                    const _Tp& __val) {
1926   _ForwardIter __i = lower_bound(__first, __last, __val);
1927   return __i != __last && !(__val < *__i);
1928 }
1929
1930 template <class _ForwardIter, class _Tp, class _Compare>
1931 bool binary_search(_ForwardIter __first, _ForwardIter __last,
1932                    const _Tp& __val,
1933                    _Compare __comp) {
1934   _ForwardIter __i = lower_bound(__first, __last, __val, __comp);
1935   return __i != __last && !__comp(__val, *__i);
1936 }
1937
1938 // merge, with and without an explicitly supplied comparison function.
1939
1940 template <class _InputIter1, class _InputIter2, class _OutputIter>
1941 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
1942                   _InputIter2 __first2, _InputIter2 __last2,
1943                   _OutputIter __result) {
1944   while (__first1 != __last1 && __first2 != __last2) {
1945     if (*__first2 < *__first1) {
1946       *__result = *__first2;
1947       ++__first2;
1948     }
1949     else {
1950       *__result = *__first1;
1951       ++__first1;
1952     }
1953     ++__result;
1954   }
1955   return copy(__first2, __last2, copy(__first1, __last1, __result));
1956 }
1957
1958 template <class _InputIter1, class _InputIter2, class _OutputIter,
1959           class _Compare>
1960 _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
1961                   _InputIter2 __first2, _InputIter2 __last2,
1962                   _OutputIter __result, _Compare __comp) {
1963   while (__first1 != __last1 && __first2 != __last2) {
1964     if (__comp(*__first2, *__first1)) {
1965       *__result = *__first2;
1966       ++__first2;
1967     }
1968     else {
1969       *__result = *__first1;
1970       ++__first1;
1971     }
1972     ++__result;
1973   }
1974   return copy(__first2, __last2, copy(__first1, __last1, __result));
1975 }
1976
1977 // inplace_merge and its auxiliary functions.
1978
1979 template <class _BidirectionalIter, class _Distance>
1980 void __merge_without_buffer(_BidirectionalIter __first,
1981                             _BidirectionalIter __middle,
1982                             _BidirectionalIter __last,
1983                             _Distance __len1, _Distance __len2) {
1984   if (__len1 == 0 || __len2 == 0)
1985     return;
1986   if (__len1 + __len2 == 2) {
1987     if (*__middle < *__first)
1988       iter_swap(__first, __middle);
1989     return;
1990   }
1991   _BidirectionalIter __first_cut = __first;
1992   _BidirectionalIter __second_cut = __middle;
1993   _Distance __len11 = 0;
1994   _Distance __len22 = 0;
1995   if (__len1 > __len2) {
1996     __len11 = __len1 / 2;
1997     advance(__first_cut, __len11);
1998     __second_cut = lower_bound(__middle, __last, *__first_cut);
1999     distance(__middle, __second_cut, __len22);
2000   }
2001   else {
2002     __len22 = __len2 / 2;
2003     advance(__second_cut, __len22);
2004     __first_cut = upper_bound(__first, __middle, *__second_cut);
2005     distance(__first, __first_cut, __len11);
2006   }
2007   _BidirectionalIter __new_middle
2008     = rotate(__first_cut, __middle, __second_cut);
2009   __merge_without_buffer(__first, __first_cut, __new_middle,
2010                          __len11, __len22);
2011   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
2012                          __len2 - __len22);
2013 }
2014
2015 template <class _BidirectionalIter, class _Distance, class _Compare>
2016 void __merge_without_buffer(_BidirectionalIter __first,
2017                             _BidirectionalIter __middle,
2018                             _BidirectionalIter __last,
2019                             _Distance __len1, _Distance __len2,
2020                             _Compare __comp) {
2021   if (__len1 == 0 || __len2 == 0)
2022     return;
2023   if (__len1 + __len2 == 2) {
2024     if (__comp(*__middle, *__first))
2025       iter_swap(__first, __middle);
2026     return;
2027   }
2028   _BidirectionalIter __first_cut = __first;
2029   _BidirectionalIter __second_cut = __middle;
2030   _Distance __len11 = 0;
2031   _Distance __len22 = 0;
2032   if (__len1 > __len2) {
2033     __len11 = __len1 / 2;
2034     advance(__first_cut, __len11);
2035     __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
2036     distance(__middle, __second_cut, __len22);
2037   }
2038   else {
2039     __len22 = __len2 / 2;
2040     advance(__second_cut, __len22);
2041     __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
2042     distance(__first, __first_cut, __len11);
2043   }
2044   _BidirectionalIter __new_middle
2045     = rotate(__first_cut, __middle, __second_cut);
2046   __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
2047                          __comp);
2048   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
2049                          __len2 - __len22, __comp);
2050 }
2051
2052 template <class _BidirectionalIter1, class _BidirectionalIter2,
2053           class _Distance>
2054 _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
2055                                       _BidirectionalIter1 __middle,
2056                                       _BidirectionalIter1 __last,
2057                                       _Distance __len1, _Distance __len2,
2058                                       _BidirectionalIter2 __buffer,
2059                                       _Distance __buffer_size) {
2060   _BidirectionalIter2 __buffer_end;
2061   if (__len1 > __len2 && __len2 <= __buffer_size) {
2062     __buffer_end = copy(__middle, __last, __buffer);
2063     copy_backward(__first, __middle, __last);
2064     return copy(__buffer, __buffer_end, __first);
2065   }
2066   else if (__len1 <= __buffer_size) {
2067     __buffer_end = copy(__first, __middle, __buffer);
2068     copy(__middle, __last, __first);
2069     return copy_backward(__buffer, __buffer_end, __last);
2070   }
2071   else
2072     return rotate(__first, __middle, __last);
2073 }
2074
2075 template <class _BidirectionalIter1, class _BidirectionalIter2,
2076           class _BidirectionalIter3>
2077 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
2078                                      _BidirectionalIter1 __last1,
2079                                      _BidirectionalIter2 __first2,
2080                                      _BidirectionalIter2 __last2,
2081                                      _BidirectionalIter3 __result) {
2082   if (__first1 == __last1)
2083     return copy_backward(__first2, __last2, __result);
2084   if (__first2 == __last2)
2085     return copy_backward(__first1, __last1, __result);
2086   --__last1;
2087   --__last2;
2088   while (true) {
2089     if (*__last2 < *__last1) {
2090       *--__result = *__last1;
2091       if (__first1 == __last1)
2092         return copy_backward(__first2, ++__last2, __result);
2093       --__last1;
2094     }
2095     else {
2096       *--__result = *__last2;
2097       if (__first2 == __last2)
2098         return copy_backward(__first1, ++__last1, __result);
2099       --__last2;
2100     }
2101   }
2102 }
2103
2104 template <class _BidirectionalIter1, class _BidirectionalIter2,
2105           class _BidirectionalIter3, class _Compare>
2106 _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
2107                                      _BidirectionalIter1 __last1,
2108                                      _BidirectionalIter2 __first2,
2109                                      _BidirectionalIter2 __last2,
2110                                      _BidirectionalIter3 __result,
2111                                      _Compare __comp) {
2112   if (__first1 == __last1)
2113     return copy_backward(__first2, __last2, __result);
2114   if (__first2 == __last2)
2115     return copy_backward(__first1, __last1, __result);
2116   --__last1;
2117   --__last2;
2118   while (true) {
2119     if (__comp(*__last2, *__last1)) {
2120       *--__result = *__last1;
2121       if (__first1 == __last1)
2122         return copy_backward(__first2, ++__last2, __result);
2123       --__last1;
2124     }
2125     else {
2126       *--__result = *__last2;
2127       if (__first2 == __last2)
2128         return copy_backward(__first1, ++__last1, __result);
2129       --__last2;
2130     }
2131   }
2132 }
2133
2134 template <class _BidirectionalIter, class _Distance, class _Pointer>
2135 void __merge_adaptive(_BidirectionalIter __first,
2136                       _BidirectionalIter __middle,
2137                       _BidirectionalIter __last,
2138                       _Distance __len1, _Distance __len2,
2139                       _Pointer __buffer, _Distance __buffer_size) {
2140   if (__len1 <= __len2 && __len1 <= __buffer_size) {
2141     _Pointer __buffer_end = copy(__first, __middle, __buffer);
2142     merge(__buffer, __buffer_end, __middle, __last, __first);
2143   }
2144   else if (__len2 <= __buffer_size) {
2145     _Pointer __buffer_end = copy(__middle, __last, __buffer);
2146     __merge_backward(__first, __middle, __buffer, __buffer_end, __last);
2147   }
2148   else {
2149     _BidirectionalIter __first_cut = __first;
2150     _BidirectionalIter __second_cut = __middle;
2151     _Distance __len11 = 0;
2152     _Distance __len22 = 0;
2153     if (__len1 > __len2) {
2154       __len11 = __len1 / 2;
2155       advance(__first_cut, __len11);
2156       __second_cut = lower_bound(__middle, __last, *__first_cut);
2157       distance(__middle, __second_cut, __len22);
2158     }
2159     else {
2160       __len22 = __len2 / 2;
2161       advance(__second_cut, __len22);
2162       __first_cut = upper_bound(__first, __middle, *__second_cut);
2163       distance(__first, __first_cut, __len11);
2164     }
2165     _BidirectionalIter __new_middle =
2166       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
2167                         __len22, __buffer, __buffer_size);
2168     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
2169                      __len22, __buffer, __buffer_size);
2170     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
2171                      __len2 - __len22, __buffer, __buffer_size);
2172   }
2173 }
2174
2175 template <class _BidirectionalIter, class _Distance, class _Pointer,
2176           class _Compare>
2177 void __merge_adaptive(_BidirectionalIter __first,
2178                       _BidirectionalIter __middle,
2179                       _BidirectionalIter __last,
2180                       _Distance __len1, _Distance __len2,
2181                       _Pointer __buffer, _Distance __buffer_size,
2182                       _Compare __comp) {
2183   if (__len1 <= __len2 && __len1 <= __buffer_size) {
2184     _Pointer __buffer_end = copy(__first, __middle, __buffer);
2185     merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
2186   }
2187   else if (__len2 <= __buffer_size) {
2188     _Pointer __buffer_end = copy(__middle, __last, __buffer);
2189     __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
2190                      __comp);
2191   }
2192   else {
2193     _BidirectionalIter __first_cut = __first;
2194     _BidirectionalIter __second_cut = __middle;
2195     _Distance __len11 = 0;
2196     _Distance __len22 = 0;
2197     if (__len1 > __len2) {
2198       __len11 = __len1 / 2;
2199       advance(__first_cut, __len11);
2200       __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
2201       distance(__middle, __second_cut, __len22);
2202     }
2203     else {
2204       __len22 = __len2 / 2;
2205       advance(__second_cut, __len22);
2206       __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
2207       distance(__first, __first_cut, __len11);
2208     }
2209     _BidirectionalIter __new_middle =
2210       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
2211                         __len22, __buffer, __buffer_size);
2212     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
2213                      __len22, __buffer, __buffer_size, __comp);
2214     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
2215                      __len2 - __len22, __buffer, __buffer_size, __comp);
2216   }
2217 }
2218
2219 template <class _BidirectionalIter, class _Tp, class _Distance>
2220 inline void __inplace_merge_aux(_BidirectionalIter __first,
2221                                 _BidirectionalIter __middle,
2222                                 _BidirectionalIter __last, _Tp*, _Distance*) {
2223   _Distance __len1 = 0;
2224   distance(__first, __middle, __len1);
2225   _Distance __len2 = 0;
2226   distance(__middle, __last, __len2);
2227
2228   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
2229   if (__buf.begin() == 0)
2230     __merge_without_buffer(__first, __middle, __last, __len1, __len2);
2231   else
2232     __merge_adaptive(__first, __middle, __last, __len1, __len2,
2233                      __buf.begin(), _Distance(__buf.size()));
2234 }
2235
2236 template <class _BidirectionalIter, class _Tp,
2237           class _Distance, class _Compare>
2238 inline void __inplace_merge_aux(_BidirectionalIter __first,
2239                                 _BidirectionalIter __middle,
2240                                 _BidirectionalIter __last, _Tp*, _Distance*,
2241                                 _Compare __comp) {
2242   _Distance __len1 = 0;
2243   distance(__first, __middle, __len1);
2244   _Distance __len2 = 0;
2245   distance(__middle, __last, __len2);
2246
2247   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
2248   if (__buf.begin() == 0)
2249     __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
2250   else
2251     __merge_adaptive(__first, __middle, __last, __len1, __len2,
2252                      __buf.begin(), _Distance(__buf.size()),
2253                      __comp);
2254 }
2255
2256 template <class _BidirectionalIter>
2257 inline void inplace_merge(_BidirectionalIter __first,
2258                           _BidirectionalIter __middle,
2259                           _BidirectionalIter __last) {
2260   if (__first == __middle || __middle == __last)
2261     return;
2262   __inplace_merge_aux(__first, __middle, __last,
2263                       __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
2264 }
2265
2266 template <class _BidirectionalIter, class _Compare>
2267 inline void inplace_merge(_BidirectionalIter __first,
2268                           _BidirectionalIter __middle,
2269                           _BidirectionalIter __last, _Compare __comp) {
2270   if (__first == __middle || __middle == __last)
2271     return;
2272   __inplace_merge_aux(__first, __middle, __last,
2273                       __VALUE_TYPE(__first), __DISTANCE_TYPE(__first),
2274                       __comp);
2275 }
2276
2277 // Set algorithms: includes, set_union, set_intersection, set_difference,
2278 // set_symmetric_difference.  All of these algorithms have the precondition
2279 // that their input ranges are sorted and the postcondition that their output
2280 // ranges are sorted.
2281
2282 template <class _InputIter1, class _InputIter2>
2283 bool includes(_InputIter1 __first1, _InputIter1 __last1,
2284               _InputIter2 __first2, _InputIter2 __last2) {
2285   while (__first1 != __last1 && __first2 != __last2)
2286     if (*__first2 < *__first1)
2287       return false;
2288     else if(*__first1 < *__first2)
2289       ++__first1;
2290     else
2291       ++__first1, ++__first2;
2292
2293   return __first2 == __last2;
2294 }
2295
2296 template <class _InputIter1, class _InputIter2, class _Compare>
2297 bool includes(_InputIter1 __first1, _InputIter1 __last1,
2298               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
2299   while (__first1 != __last1 && __first2 != __last2)
2300     if (__comp(*__first2, *__first1))
2301       return false;
2302     else if(__comp(*__first1, *__first2))
2303       ++__first1;
2304     else
2305       ++__first1, ++__first2;
2306
2307   return __first2 == __last2;
2308 }
2309
2310 template <class _InputIter1, class _InputIter2, class _OutputIter>
2311 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
2312                       _InputIter2 __first2, _InputIter2 __last2,
2313                       _OutputIter __result) {
2314   while (__first1 != __last1 && __first2 != __last2) {
2315     if (*__first1 < *__first2) {
2316       *__result = *__first1;
2317       ++__first1;
2318     }
2319     else if (*__first2 < *__first1) {
2320       *__result = *__first2;
2321       ++__first2;
2322     }
2323     else {
2324       *__result = *__first1;
2325       ++__first1;
2326       ++__first2;
2327     }
2328     ++__result;
2329   }
2330   return copy(__first2, __last2, copy(__first1, __last1, __result));
2331 }
2332
2333 template <class _InputIter1, class _InputIter2, class _OutputIter,
2334           class _Compare>
2335 _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
2336                       _InputIter2 __first2, _InputIter2 __last2,
2337                       _OutputIter __result, _Compare __comp) {
2338   while (__first1 != __last1 && __first2 != __last2) {
2339     if (__comp(*__first1, *__first2)) {
2340       *__result = *__first1;
2341       ++__first1;
2342     }
2343     else if (__comp(*__first2, *__first1)) {
2344       *__result = *__first2;
2345       ++__first2;
2346     }
2347     else {
2348       *__result = *__first1;
2349       ++__first1;
2350       ++__first2;
2351     }
2352     ++__result;
2353   }
2354   return copy(__first2, __last2, copy(__first1, __last1, __result));
2355 }
2356
2357 template <class _InputIter1, class _InputIter2, class _OutputIter>
2358 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
2359                              _InputIter2 __first2, _InputIter2 __last2,
2360                              _OutputIter __result) {
2361   while (__first1 != __last1 && __first2 != __last2)
2362     if (*__first1 < *__first2)
2363       ++__first1;
2364     else if (*__first2 < *__first1)
2365       ++__first2;
2366     else {
2367       *__result = *__first1;
2368       ++__first1;
2369       ++__first2;
2370       ++__result;
2371     }
2372   return __result;
2373 }
2374
2375 template <class _InputIter1, class _InputIter2, class _OutputIter,
2376           class _Compare>
2377 _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
2378                              _InputIter2 __first2, _InputIter2 __last2,
2379                              _OutputIter __result, _Compare __comp) {
2380   while (__first1 != __last1 && __first2 != __last2)
2381     if (__comp(*__first1, *__first2))
2382       ++__first1;
2383     else if (__comp(*__first2, *__first1))
2384       ++__first2;
2385     else {
2386       *__result = *__first1;
2387       ++__first1;
2388       ++__first2;
2389       ++__result;
2390     }
2391   return __result;
2392 }
2393
2394 template <class _InputIter1, class _InputIter2, class _OutputIter>
2395 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
2396                            _InputIter2 __first2, _InputIter2 __last2,
2397                            _OutputIter __result) {
2398   while (__first1 != __last1 && __first2 != __last2)
2399     if (*__first1 < *__first2) {
2400       *__result = *__first1;
2401       ++__first1;
2402       ++__result;
2403     }
2404     else if (*__first2 < *__first1)
2405       ++__first2;
2406     else {
2407       ++__first1;
2408       ++__first2;
2409     }
2410   return copy(__first1, __last1, __result);
2411 }
2412
2413 template <class _InputIter1, class _InputIter2, class _OutputIter,
2414           class _Compare>
2415 _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
2416                            _InputIter2 __first2, _InputIter2 __last2,
2417                            _OutputIter __result, _Compare __comp) {
2418   while (__first1 != __last1 && __first2 != __last2)
2419     if (__comp(*__first1, *__first2)) {
2420       *__result = *__first1;
2421       ++__first1;
2422       ++__result;
2423     }
2424     else if (__comp(*__first2, *__first1))
2425       ++__first2;
2426     else {
2427       ++__first1;
2428       ++__first2;
2429     }
2430   return copy(__first1, __last1, __result);
2431 }
2432
2433 template <class _InputIter1, class _InputIter2, class _OutputIter>
2434 _OutputIter
2435 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
2436                          _InputIter2 __first2, _InputIter2 __last2,
2437                          _OutputIter __result) {
2438   while (__first1 != __last1 && __first2 != __last2)
2439     if (*__first1 < *__first2) {
2440       *__result = *__first1;
2441       ++__first1;
2442       ++__result;
2443     }
2444     else if (*__first2 < *__first1) {
2445       *__result = *__first2;
2446       ++__first2;
2447       ++__result;
2448     }
2449     else {
2450       ++__first1;
2451       ++__first2;
2452     }
2453   return copy(__first2, __last2, copy(__first1, __last1, __result));
2454 }
2455
2456 template <class _InputIter1, class _InputIter2, class _OutputIter,
2457           class _Compare>
2458 _OutputIter
2459 set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
2460                          _InputIter2 __first2, _InputIter2 __last2,
2461                          _OutputIter __result,
2462                          _Compare __comp) {
2463   while (__first1 != __last1 && __first2 != __last2)
2464     if (__comp(*__first1, *__first2)) {
2465       *__result = *__first1;
2466       ++__first1;
2467       ++__result;
2468     }
2469     else if (__comp(*__first2, *__first1)) {
2470       *__result = *__first2;
2471       ++__first2;
2472       ++__result;
2473     }
2474     else {
2475       ++__first1;
2476       ++__first2;
2477     }
2478   return copy(__first2, __last2, copy(__first1, __last1, __result));
2479 }
2480
2481 // min_element and max_element, with and without an explicitly supplied
2482 // comparison function.
2483
2484 template <class _ForwardIter>
2485 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
2486   if (__first == __last) return __first;
2487   _ForwardIter __result = __first;
2488   while (++__first != __last)
2489     if (*__result < *__first)
2490       __result = __first;
2491   return __result;
2492 }
2493
2494 template <class _ForwardIter, class _Compare>
2495 _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
2496                             _Compare __comp) {
2497   if (__first == __last) return __first;
2498   _ForwardIter __result = __first;
2499   while (++__first != __last)
2500     if (__comp(*__result, *__first)) __result = __first;
2501   return __result;
2502 }
2503
2504 template <class _ForwardIter>
2505 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
2506   if (__first == __last) return __first;
2507   _ForwardIter __result = __first;
2508   while (++__first != __last)
2509     if (*__first < *__result)
2510       __result = __first;
2511   return __result;
2512 }
2513
2514 template <class _ForwardIter, class _Compare>
2515 _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
2516                             _Compare __comp) {
2517   if (__first == __last) return __first;
2518   _ForwardIter __result = __first;
2519   while (++__first != __last)
2520     if (__comp(*__first, *__result))
2521       __result = __first;
2522   return __result;
2523 }
2524
2525 // next_permutation and prev_permutation, with and without an explicitly
2526 // supplied comparison function.
2527
2528 template <class _BidirectionalIter>
2529 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
2530   if (__first == __last)
2531     return false;
2532   _BidirectionalIter __i = __first;
2533   ++__i;
2534   if (__i == __last)
2535     return false;
2536   __i = __last;
2537   --__i;
2538
2539   for(;;) {
2540     _BidirectionalIter __ii = __i;
2541     --__i;
2542     if (*__i < *__ii) {
2543       _BidirectionalIter __j = __last;
2544       while (!(*__i < *--__j))
2545         {}
2546       iter_swap(__i, __j);
2547       reverse(__ii, __last);
2548       return true;
2549     }
2550     if (__i == __first) {
2551       reverse(__first, __last);
2552       return false;
2553     }
2554   }
2555 }
2556
2557 template <class _BidirectionalIter, class _Compare>
2558 bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
2559                       _Compare __comp) {
2560   if (__first == __last)
2561     return false;
2562   _BidirectionalIter __i = __first;
2563   ++__i;
2564   if (__i == __last)
2565     return false;
2566   __i = __last;
2567   --__i;
2568
2569   for(;;) {
2570     _BidirectionalIter __ii = __i;
2571     --__i;
2572     if (__comp(*__i, *__ii)) {
2573       _BidirectionalIter __j = __last;
2574       while (!__comp(*__i, *--__j))
2575         {}
2576       iter_swap(__i, __j);
2577       reverse(__ii, __last);
2578       return true;
2579     }
2580     if (__i == __first) {
2581       reverse(__first, __last);
2582       return false;
2583     }
2584   }
2585 }
2586
2587 template <class _BidirectionalIter>
2588 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
2589   if (__first == __last)
2590     return false;
2591   _BidirectionalIter __i = __first;
2592   ++__i;
2593   if (__i == __last)
2594     return false;
2595   __i = __last;
2596   --__i;
2597
2598   for(;;) {
2599     _BidirectionalIter __ii = __i;
2600     --__i;
2601     if (*__ii < *__i) {
2602       _BidirectionalIter __j = __last;
2603       while (!(*--__j < *__i))
2604         {}
2605       iter_swap(__i, __j);
2606       reverse(__ii, __last);
2607       return true;
2608     }
2609     if (__i == __first) {
2610       reverse(__first, __last);
2611       return false;
2612     }
2613   }
2614 }
2615
2616 template <class _BidirectionalIter, class _Compare>
2617 bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
2618                       _Compare __comp) {
2619   if (__first == __last)
2620     return false;
2621   _BidirectionalIter __i = __first;
2622   ++__i;
2623   if (__i == __last)
2624     return false;
2625   __i = __last;
2626   --__i;
2627
2628   for(;;) {
2629     _BidirectionalIter __ii = __i;
2630     --__i;
2631     if (__comp(*__ii, *__i)) {
2632       _BidirectionalIter __j = __last;
2633       while (!__comp(*--__j, *__i))
2634         {}
2635       iter_swap(__i, __j);
2636       reverse(__ii, __last);
2637       return true;
2638     }
2639     if (__i == __first) {
2640       reverse(__first, __last);
2641       return false;
2642     }
2643   }
2644 }
2645
2646 // find_first_of, with and without an explicitly supplied comparison function.
2647
2648 template <class _InputIter, class _ForwardIter>
2649 _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
2650                          _ForwardIter __first2, _ForwardIter __last2)
2651 {
2652   for ( ; __first1 != __last1; ++__first1)
2653     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
2654       if (*__first1 == *__iter)
2655         return __first1;
2656   return __last1;
2657 }
2658
2659 template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
2660 _InputIter find_first_of(_InputIter __first1, _InputIter __last1,
2661                          _ForwardIter __first2, _ForwardIter __last2,
2662                          _BinaryPredicate __comp)
2663 {
2664   for ( ; __first1 != __last1; ++__first1)
2665     for (_ForwardIter __iter = __first2; __iter != __last2; ++__iter)
2666       if (__comp(*__first1, *__iter))
2667         return __first1;
2668   return __last1;
2669 }
2670
2671
2672 // find_end, with and without an explicitly supplied comparison function.
2673 // Search [first2, last2) as a subsequence in [first1, last1), and return
2674 // the *last* possible match.  Note that find_end for bidirectional iterators
2675 // is much faster than for forward iterators.
2676
2677 // find_end for forward iterators.
2678 template <class _ForwardIter1, class _ForwardIter2>
2679 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
2680                          _ForwardIter2 __first2, _ForwardIter2 __last2,
2681                          forward_iterator_tag, forward_iterator_tag)
2682 {
2683   if (__first2 == __last2)
2684     return __last1;
2685   else {
2686     _ForwardIter1 __result = __last1;
2687     while (1) {
2688       _ForwardIter1 __new_result
2689         = search(__first1, __last1, __first2, __last2);
2690       if (__new_result == __last1)
2691         return __result;
2692       else {
2693         __result = __new_result;
2694         __first1 = __new_result;
2695         ++__first1;
2696       }
2697     }
2698   }
2699 }
2700
2701 template <class _ForwardIter1, class _ForwardIter2,
2702           class _BinaryPredicate>
2703 _ForwardIter1 __find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
2704                          _ForwardIter2 __first2, _ForwardIter2 __last2,
2705                          forward_iterator_tag, forward_iterator_tag,
2706                          _BinaryPredicate __comp)
2707 {
2708   if (__first2 == __last2)
2709     return __last1;
2710   else {
2711     _ForwardIter1 __result = __last1;
2712     while (1) {
2713       _ForwardIter1 __new_result
2714         = search(__first1, __last1, __first2, __last2, __comp);
2715       if (__new_result == __last1)
2716         return __result;
2717       else {
2718         __result = __new_result;
2719         __first1 = __new_result;
2720         ++__first1;
2721       }
2722     }
2723   }
2724 }
2725
2726 // find_end for bidirectional iterators.  Requires partial specialization.
2727 #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
2728
2729 template <class _BidirectionalIter1, class _BidirectionalIter2>
2730 _BidirectionalIter1
2731 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
2732            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
2733            bidirectional_iterator_tag, bidirectional_iterator_tag)
2734 {
2735   typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
2736   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
2737
2738   _RevIter1 __rlast1(__first1);
2739   _RevIter2 __rlast2(__first2);
2740   _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
2741                                _RevIter2(__last2), __rlast2);
2742
2743   if (__rresult == __rlast1)
2744     return __last1;
2745   else {
2746     _BidirectionalIter1 __result = __rresult.base();
2747     advance(__result, -distance(__first2, __last2));
2748     return __result;
2749   }
2750 }
2751
2752 template <class _BidirectionalIter1, class _BidirectionalIter2,
2753           class _BinaryPredicate>
2754 _BidirectionalIter1
2755 __find_end(_BidirectionalIter1 __first1, _BidirectionalIter1 __last1,
2756            _BidirectionalIter2 __first2, _BidirectionalIter2 __last2,
2757            bidirectional_iterator_tag, bidirectional_iterator_tag,
2758            _BinaryPredicate __comp)
2759 {
2760   typedef reverse_iterator<_BidirectionalIter1> _RevIter1;
2761   typedef reverse_iterator<_BidirectionalIter2> _RevIter2;
2762
2763   _RevIter1 __rlast1(__first1);
2764   _RevIter2 __rlast2(__first2);
2765   _RevIter1 __rresult = search(_RevIter1(__last1), __rlast1,
2766                                _RevIter2(__last2), __rlast2,
2767                                __comp);
2768
2769   if (__rresult == __rlast1)
2770     return __last1;
2771   else {
2772     _BidirectionalIter1 __result = __rresult.base();
2773     advance(__result, -distance(__first2, __last2));
2774     return __result;
2775   }
2776 }
2777 #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
2778
2779 // Dispatching functions for find_end.
2780
2781 template <class _ForwardIter1, class _ForwardIter2>
2782 inline _ForwardIter1
2783 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
2784          _ForwardIter2 __first2, _ForwardIter2 __last2)
2785 {
2786   return __find_end(__first1, __last1, __first2, __last2,
2787                     __ITERATOR_CATEGORY(__first1),
2788                     __ITERATOR_CATEGORY(__first2));
2789 }
2790
2791 template <class _ForwardIter1, class _ForwardIter2,
2792           class _BinaryPredicate>
2793 inline _ForwardIter1
2794 find_end(_ForwardIter1 __first1, _ForwardIter1 __last1,
2795          _ForwardIter2 __first2, _ForwardIter2 __last2,
2796          _BinaryPredicate __comp)
2797 {
2798   return __find_end(__first1, __last1, __first2, __last2,
2799                     __ITERATOR_CATEGORY(__first1),
2800                     __ITERATOR_CATEGORY(__first2),
2801                     __comp);
2802 }
2803
2804 // is_heap, a predicate testing whether or not a range is
2805 // a heap.  This function is an extension, not part of the C++
2806 // standard.
2807
2808 template <class _RandomAccessIter, class _Distance>
2809 bool __is_heap(_RandomAccessIter __first, _Distance __n)
2810 {
2811   _Distance __parent = 0;
2812   for (_Distance __child = 1; __child < __n; ++__child) {
2813     if (__first[__parent] < __first[__child])
2814       return false;
2815     if ((__child & 1) == 0)
2816       ++__parent;
2817   }
2818   return true;
2819 }
2820
2821 template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
2822 bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
2823                _Distance __n)
2824 {
2825   _Distance __parent = 0;
2826   for (_Distance __child = 1; __child < __n; ++__child) {
2827     if (__comp(__first[__parent], __first[__child]))
2828       return false;
2829     if ((__child & 1) == 0)
2830       ++__parent;
2831   }
2832   return true;
2833 }
2834
2835 template <class _RandomAccessIter>
2836 inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
2837 {
2838   return __is_heap(__first, __last - __first);
2839 }
2840
2841
2842 template <class _RandomAccessIter, class _StrictWeakOrdering>
2843 inline bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
2844                     _StrictWeakOrdering __comp)
2845 {
2846   return __is_heap(__first, __comp, __last - __first);
2847 }
2848
2849 // is_sorted, a predicated testing whether a range is sorted in
2850 // nondescending order.  This is an extension, not part of the C++
2851 // standard.
2852
2853 template <class _ForwardIter>
2854 bool is_sorted(_ForwardIter __first, _ForwardIter __last)
2855 {
2856   if (__first == __last)
2857     return true;
2858
2859   _ForwardIter __next = __first;
2860   for (++__next; __next != __last; __first = __next, ++__next) {
2861     if (*__next < *__first)
2862       return false;
2863   }
2864
2865   return true;
2866 }
2867
2868 template <class _ForwardIter, class _StrictWeakOrdering>
2869 bool is_sorted(_ForwardIter __first, _ForwardIter __last,
2870                _StrictWeakOrdering __comp)
2871 {
2872   if (__first == __last)
2873     return true;
2874
2875   _ForwardIter __next = __first;
2876   for (++__next; __next != __last; __first = __next, ++__next) {
2877     if (__comp(*__next, *__first))
2878       return false;
2879   }
2880
2881   return true;
2882 }
2883
2884 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
2885 #pragma reset woff 1209
2886 #endif
2887
2888 __STL_END_NAMESPACE
2889
2890 #endif /* __SGI_STL_INTERNAL_ALGO_H */
2891
2892 // Local Variables:
2893 // mode:C++
2894 // End: