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

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