Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

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