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