libstdc++-v3/include/bits/stl_algo.h

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