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