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