stl_algo.h
上传用户:sichengcw
上传日期:2009-02-17
资源大小:202k
文件大小:84k
源码类别:

STL

开发平台:

Visual C++

  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. /* NOTE: This is an internal header file, included by other STL headers.
  27.  *   You should not attempt to use it directly.
  28.  */
  29. #ifndef __SGI_STL_INTERNAL_ALGO_H
  30. #define __SGI_STL_INTERNAL_ALGO_H
  31. #include <stl_heap.h>
  32. __STL_BEGIN_NAMESPACE
  33. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  34. #pragma set woff 1209
  35. #endif
  36. template <class T>
  37. inline const T& __median(const T& a, const T& b, const T& c) {
  38.   if (a < b)
  39.     if (b < c)
  40.       return b;
  41.     else if (a < c)
  42.       return c;
  43.     else
  44.       return a;
  45.   else if (a < c)
  46.     return a;
  47.   else if (b < c)
  48.     return c;
  49.   else
  50.     return b;
  51. }
  52. template <class T, class Compare>
  53. inline const T& __median(const T& a, const T& b, const T& c, Compare comp) {
  54.   if (comp(a, b))
  55.     if (comp(b, c))
  56.       return b;
  57.     else if (comp(a, c))
  58.       return c;
  59.     else
  60.       return a;
  61.   else if (comp(a, c))
  62.     return a;
  63.   else if (comp(b, c))
  64.     return c;
  65.   else
  66.     return b;
  67. }
  68. template <class InputIterator, class Function>
  69. Function for_each(InputIterator first, InputIterator last, Function f) {
  70.   for ( ; first != last; ++first)
  71.     f(*first);
  72.   return f;
  73. }
  74. template <class InputIterator, class T>
  75. InputIterator find(InputIterator first, InputIterator last, const T& value) {
  76.   while (first != last && *first != value) ++first;
  77.   return first;
  78. }
  79. template <class InputIterator, class Predicate>
  80. InputIterator find_if(InputIterator first, InputIterator last,
  81.                       Predicate pred) {
  82.   while (first != last && !pred(*first)) ++first;
  83.   return first;
  84. }
  85. template <class ForwardIterator>
  86. ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last) {
  87.   if (first == last) return last;
  88.   ForwardIterator next = first;
  89.   while(++next != last) {
  90.     if (*first == *next) return first;
  91.     first = next;
  92.   }
  93.   return last;
  94. }
  95. template <class ForwardIterator, class BinaryPredicate>
  96. ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last,
  97.                               BinaryPredicate binary_pred) {
  98.   if (first == last) return last;
  99.   ForwardIterator next = first;
  100.   while(++next != last) {
  101.     if (binary_pred(*first, *next)) return first;
  102.     first = next;
  103.   }
  104.   return last;
  105. }
  106. template <class InputIterator, class T, class Size>
  107. void count(InputIterator first, InputIterator last, const T& value,
  108.            Size& n) {
  109.   for ( ; first != last; ++first)
  110.     if (*first == value)
  111.       ++n;
  112. }
  113. template <class InputIterator, class Predicate, class Size>
  114. void count_if(InputIterator first, InputIterator last, Predicate pred,
  115.               Size& n) {
  116.   for ( ; first != last; ++first)
  117.     if (pred(*first))
  118.       ++n;
  119. }
  120. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  121. template <class InputIterator, class T>
  122. typename iterator_traits<InputIterator>::difference_type
  123. count(InputIterator first, InputIterator last, const T& value) {
  124.   typename iterator_traits<InputIterator>::difference_type n = 0;
  125.   for ( ; first != last; ++first)
  126.     if (*first == value)
  127.       ++n;
  128.   return n;
  129. }
  130. template <class InputIterator, class Predicate>
  131. typename iterator_traits<InputIterator>::difference_type
  132. count_if(InputIterator first, InputIterator last, Predicate pred) {
  133.   typename iterator_traits<InputIterator>::difference_type n = 0;
  134.   for ( ; first != last; ++first)
  135.     if (pred(*first))
  136.       ++n;
  137.   return n;
  138. }
  139. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  140. template <class ForwardIterator1, class ForwardIterator2, class Distance1,
  141.           class Distance2>
  142. ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1,
  143.                           ForwardIterator2 first2, ForwardIterator2 last2,
  144.                           Distance1*, Distance2*) {
  145.   Distance1 d1 = 0;
  146.   distance(first1, last1, d1);
  147.   Distance2 d2 = 0;
  148.   distance(first2, last2, d2);
  149.   if (d1 < d2) return last1;
  150.   ForwardIterator1 current1 = first1;
  151.   ForwardIterator2 current2 = first2;
  152.   while (current2 != last2) 
  153.     if (*current1 == *current2) {
  154.       ++current1;
  155.       ++current2;
  156.     }
  157.     else {
  158.       if (d1 == d2)
  159.         return last1;
  160.       else {
  161.         current1 = ++first1;
  162.         current2 = first2;
  163.         --d1;
  164.       }
  165.     }
  166.   return first1;
  167. }
  168. template <class ForwardIterator1, class ForwardIterator2>
  169. inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
  170.                                ForwardIterator2 first2, ForwardIterator2 last2)
  171. {
  172.   return __search(first1, last1, first2, last2, distance_type(first1),
  173.                   distance_type(first2));
  174. }
  175. template <class ForwardIterator1, class ForwardIterator2,
  176.           class BinaryPredicate, class Distance1, class Distance2>
  177. ForwardIterator1 __search(ForwardIterator1 first1, ForwardIterator1 last1,
  178.                           ForwardIterator2 first2, ForwardIterator2 last2,
  179.                           BinaryPredicate binary_pred, Distance1*, Distance2*) {
  180.   Distance1 d1 = 0;
  181.   distance(first1, last1, d1);
  182.   Distance2 d2 = 0;
  183.   distance(first2, last2, d2);
  184.   if (d1 < d2) return last1;
  185.   ForwardIterator1 current1 = first1;
  186.   ForwardIterator2 current2 = first2;
  187.   while (current2 != last2)
  188.     if (binary_pred(*current1, *current2)) {
  189.       ++current1;
  190.       ++current2;
  191.     }
  192.     else {
  193.       if (d1 == d2)
  194.         return last1;
  195.       else {
  196.         current1 = ++first1;
  197.         current2 = first2;
  198.         --d1;
  199.       }
  200.     }
  201.   return first1;
  202. }
  203. template <class ForwardIterator1, class ForwardIterator2,
  204.           class BinaryPredicate>
  205. inline ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
  206.                                ForwardIterator2 first2, ForwardIterator2 last2,
  207.                                BinaryPredicate binary_pred) {
  208.   return __search(first1, last1, first2, last2, binary_pred,
  209.                   distance_type(first1), distance_type(first2));
  210. }
  211. template <class ForwardIterator, class Integer, class T>
  212. ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
  213.                          Integer count, const T& value) {
  214.   if (count <= 0)
  215.     return first;
  216.   else {
  217.     first = find(first, last, value);
  218.     while (first != last) {
  219.       Integer n = count - 1;
  220.       ForwardIterator i = first;
  221.       ++i;
  222.       while (i != last && n != 0 && *i == value) {
  223.         ++i;
  224.         --n;
  225.       }
  226.       if (n == 0)
  227.         return first;
  228.       else
  229.         first = find(i, last, value);
  230.     }
  231.     return last;
  232.   }
  233. }
  234. template <class ForwardIterator, class Integer, class T, class BinaryPredicate>
  235. ForwardIterator search_n(ForwardIterator first, ForwardIterator last,
  236.                          Integer count, const T& value,
  237.                          BinaryPredicate binary_pred) {
  238.   if (count <= 0)
  239.     return first;
  240.   else {
  241.     while (first != last) {
  242.       if (binary_pred(*first, value)) break;
  243.       ++first;
  244.     }
  245.     while (first != last) {
  246.       Integer n = count - 1;
  247.       ForwardIterator i = first;
  248.       ++i;
  249.       while (i != last && n != 0 && binary_pred(*i, value)) {
  250.         ++i;
  251.         --n;
  252.       }
  253.       if (n == 0)
  254.         return first;
  255.       else {
  256.         while (i != last) {
  257.           if (binary_pred(*i, value)) break;
  258.           ++i;
  259.         }
  260.         first = i;
  261.       }
  262.     }
  263.     return last;
  264.   }
  265. template <class ForwardIterator1, class ForwardIterator2>
  266. ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1,
  267.                              ForwardIterator2 first2) {
  268.   for ( ; first1 != last1; ++first1, ++first2)
  269.     iter_swap(first1, first2);
  270.   return first2;
  271. }
  272. template <class InputIterator, class OutputIterator, class UnaryOperation>
  273. OutputIterator transform(InputIterator first, InputIterator last,
  274.                          OutputIterator result, UnaryOperation op) {
  275.   for ( ; first != last; ++first, ++result)
  276.     *result = op(*first);
  277.   return result;
  278. }
  279. template <class InputIterator1, class InputIterator2, class OutputIterator,
  280.           class BinaryOperation>
  281. OutputIterator transform(InputIterator1 first1, InputIterator1 last1,
  282.                          InputIterator2 first2, OutputIterator result,
  283.                          BinaryOperation binary_op) {
  284.   for ( ; first1 != last1; ++first1, ++first2, ++result)
  285.     *result = binary_op(*first1, *first2);
  286.   return result;
  287. }
  288. template <class ForwardIterator, class T>
  289. void replace(ForwardIterator first, ForwardIterator last, const T& old_value,
  290.              const T& new_value) {
  291.   for ( ; first != last; ++first)
  292.     if (*first == old_value) *first = new_value;
  293. }
  294. template <class ForwardIterator, class Predicate, class T>
  295. void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred,
  296.                 const T& new_value) {
  297.   for ( ; first != last; ++first)
  298.     if (pred(*first)) *first = new_value;
  299. }
  300. template <class InputIterator, class OutputIterator, class T>
  301. OutputIterator replace_copy(InputIterator first, InputIterator last,
  302.                             OutputIterator result, const T& old_value,
  303.                             const T& new_value) {
  304.   for ( ; first != last; ++first, ++result)
  305.     *result = *first == old_value ? new_value : *first;
  306.   return result;
  307. }
  308. template <class Iterator, class OutputIterator, class Predicate, class T>
  309. OutputIterator replace_copy_if(Iterator first, Iterator last,
  310.                                OutputIterator result, Predicate pred,
  311.                                const T& new_value) {
  312.   for ( ; first != last; ++first, ++result)
  313.     *result = pred(*first) ? new_value : *first;
  314.   return result;
  315. }
  316. template <class ForwardIterator, class Generator>
  317. void generate(ForwardIterator first, ForwardIterator last, Generator gen) {
  318.   for ( ; first != last; ++first)
  319.     *first = gen();
  320. }
  321. template <class OutputIterator, class Size, class Generator>
  322. OutputIterator generate_n(OutputIterator first, Size n, Generator gen) {
  323.   for ( ; n > 0; --n, ++first)
  324.     *first = gen();
  325.   return first;
  326. }
  327. template <class InputIterator, class OutputIterator, class T>
  328. OutputIterator remove_copy(InputIterator first, InputIterator last,
  329.                            OutputIterator result, const T& value) {
  330.   for ( ; first != last; ++first)
  331.     if (*first != value) {
  332.       *result = *first;
  333.       ++result;
  334.     }
  335.   return result;
  336. }
  337. template <class InputIterator, class OutputIterator, class Predicate>
  338. OutputIterator remove_copy_if(InputIterator first, InputIterator last,
  339.                               OutputIterator result, Predicate pred) {
  340.   for ( ; first != last; ++first)
  341.     if (!pred(*first)) {
  342.       *result = *first;
  343.       ++result;
  344.     }
  345.   return result;
  346. }
  347. template <class ForwardIterator, class T>
  348. ForwardIterator remove(ForwardIterator first, ForwardIterator last,
  349.                        const T& value) {
  350.   first = find(first, last, value);
  351.   ForwardIterator next = first;
  352.   return first == last ? first : remove_copy(++next, last, first, value);
  353. }
  354. template <class ForwardIterator, class Predicate>
  355. ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
  356.                           Predicate pred) {
  357.   first = find_if(first, last, pred);
  358.   ForwardIterator next = first;
  359.   return first == last ? first : remove_copy_if(++next, last, first, pred);
  360. }
  361. template <class InputIterator, class ForwardIterator>
  362. ForwardIterator __unique_copy(InputIterator first, InputIterator last,
  363.                               ForwardIterator result, forward_iterator_tag) {
  364.   *result = *first;
  365.   while (++first != last)
  366.     if (*result != *first) *++result = *first;
  367.   return ++result;
  368. }
  369. template <class InputIterator, class OutputIterator, class T>
  370. OutputIterator __unique_copy(InputIterator first, InputIterator last,
  371.                              OutputIterator result, T*) {
  372.   T value = *first;
  373.   *result = value;
  374.   while (++first != last)
  375.     if (value != *first) {
  376.       value = *first;
  377.       *++result = value;
  378.     }
  379.   return ++result;
  380. }
  381. template <class InputIterator, class OutputIterator>
  382. inline OutputIterator __unique_copy(InputIterator first, InputIterator last,
  383.                                     OutputIterator result, 
  384.                                     output_iterator_tag) {
  385.   return __unique_copy(first, last, result, value_type(first));
  386. }
  387. template <class InputIterator, class OutputIterator>
  388. inline OutputIterator unique_copy(InputIterator first, InputIterator last,
  389.                                   OutputIterator result) {
  390.   if (first == last) return result;
  391.   return __unique_copy(first, last, result, iterator_category(result));
  392. }
  393. template <class InputIterator, class ForwardIterator, class BinaryPredicate>
  394. ForwardIterator __unique_copy(InputIterator first, InputIterator last,
  395.                               ForwardIterator result, 
  396.                               BinaryPredicate binary_pred,
  397.                               forward_iterator_tag) {
  398.   *result = *first;
  399.   while (++first != last)
  400.     if (!binary_pred(*result, *first)) *++result = *first;
  401.   return ++result;
  402. }
  403. template <class InputIterator, class OutputIterator, class BinaryPredicate,
  404.           class T>
  405. OutputIterator __unique_copy(InputIterator first, InputIterator last,
  406.                              OutputIterator result,
  407.                              BinaryPredicate binary_pred, T*) {
  408.   T value = *first;
  409.   *result = value;
  410.   while (++first != last)
  411.     if (!binary_pred(value, *first)) {
  412.       value = *first;
  413.       *++result = value;
  414.     }
  415.   return ++result;
  416. }
  417. template <class InputIterator, class OutputIterator, class BinaryPredicate>
  418. inline OutputIterator __unique_copy(InputIterator first, InputIterator last,
  419.                                     OutputIterator result,
  420.                                     BinaryPredicate binary_pred,
  421.                                     output_iterator_tag) {
  422.   return __unique_copy(first, last, result, binary_pred, value_type(first));
  423. }
  424. template <class InputIterator, class OutputIterator, class BinaryPredicate>
  425. inline OutputIterator unique_copy(InputIterator first, InputIterator last,
  426.                                   OutputIterator result,
  427.                                   BinaryPredicate binary_pred) {
  428.   if (first == last) return result;
  429.   return __unique_copy(first, last, result, binary_pred,
  430.                        iterator_category(result));
  431. }
  432. template <class ForwardIterator>
  433. ForwardIterator unique(ForwardIterator first, ForwardIterator last) {
  434.   first = adjacent_find(first, last);
  435.   return unique_copy(first, last, first);
  436. }
  437. template <class ForwardIterator, class BinaryPredicate>
  438. ForwardIterator unique(ForwardIterator first, ForwardIterator last,
  439.                        BinaryPredicate binary_pred) {
  440.   first = adjacent_find(first, last, binary_pred);
  441.   return unique_copy(first, last, first, binary_pred);
  442. }
  443. template <class BidirectionalIterator>
  444. void __reverse(BidirectionalIterator first, BidirectionalIterator last, 
  445.                bidirectional_iterator_tag) {
  446.   while (true)
  447.     if (first == last || first == --last)
  448.       return;
  449.     else
  450.       iter_swap(first++, last);
  451. }
  452. template <class RandomAccessIterator>
  453. void __reverse(RandomAccessIterator first, RandomAccessIterator last,
  454.                random_access_iterator_tag) {
  455.   while (first < last) iter_swap(first++, --last);
  456. }
  457. template <class BidirectionalIterator>
  458. inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {
  459.   __reverse(first, last, iterator_category(first));
  460. }
  461. template <class BidirectionalIterator, class OutputIterator>
  462. OutputIterator reverse_copy(BidirectionalIterator first,
  463.                             BidirectionalIterator last,
  464.                             OutputIterator result) {
  465.   while (first != last) {
  466.     --last;
  467.     *result = *last;
  468.     ++result;
  469.   }
  470.   return result;
  471. }
  472. template <class ForwardIterator, class Distance>
  473. void __rotate(ForwardIterator first, ForwardIterator middle,
  474.               ForwardIterator last, Distance*, forward_iterator_tag) {
  475.   for (ForwardIterator i = middle; ;) {
  476.     iter_swap(first, i);
  477.     ++first;
  478.     ++i;
  479.     if (first == middle) {
  480.       if (i == last) return;
  481.       middle = i;
  482.     }
  483.     else if (i == last)
  484.       i = middle;
  485.   }
  486. }
  487. template <class BidirectionalIterator, class Distance>
  488. void __rotate(BidirectionalIterator first, BidirectionalIterator middle,
  489.               BidirectionalIterator last, Distance*,
  490.               bidirectional_iterator_tag) {
  491.   reverse(first, middle);
  492.   reverse(middle, last);
  493.   reverse(first, last);
  494. }
  495. template <class EuclideanRingElement>
  496. EuclideanRingElement __gcd(EuclideanRingElement m, EuclideanRingElement n)
  497. {
  498.   while (n != 0) {
  499.     EuclideanRingElement t = m % n;
  500.     m = n;
  501.     n = t;
  502.   }
  503.   return m;
  504. }
  505. template <class RandomAccessIterator, class Distance, class T>
  506. void __rotate_cycle(RandomAccessIterator first, RandomAccessIterator last,
  507.                     RandomAccessIterator initial, Distance shift, T*) {
  508.   T value = *initial;
  509.   RandomAccessIterator ptr1 = initial;
  510.   RandomAccessIterator ptr2 = ptr1 + shift;
  511.   while (ptr2 != initial) {
  512.     *ptr1 = *ptr2;
  513.     ptr1 = ptr2;
  514.     if (last - ptr2 > shift)
  515.       ptr2 += shift;
  516.     else
  517.       ptr2 = first + (shift - (last - ptr2));
  518.   }
  519.   *ptr1 = value;
  520. }
  521. template <class RandomAccessIterator, class Distance>
  522. void __rotate(RandomAccessIterator first, RandomAccessIterator middle,
  523.               RandomAccessIterator last, Distance*,
  524.               random_access_iterator_tag) {
  525.   Distance n = __gcd(last - first, middle - first);
  526.   while (n--)
  527.     __rotate_cycle(first, last, first + n, middle - first,
  528.                    value_type(first));
  529. }
  530. template <class ForwardIterator>
  531. inline void rotate(ForwardIterator first, ForwardIterator middle,
  532.                    ForwardIterator last) {
  533.   if (first == middle || middle == last) return;
  534.   __rotate(first, middle, last, distance_type(first),
  535.            iterator_category(first));
  536. }
  537. template <class ForwardIterator, class OutputIterator>
  538. OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle,
  539.                            ForwardIterator last, OutputIterator result) {
  540.   return copy(first, middle, copy(middle, last, result));
  541. }
  542. template <class RandomAccessIterator, class Distance>
  543. void __random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
  544.                       Distance*) {
  545.   if (first == last) return;
  546.   for (RandomAccessIterator i = first + 1; i != last; ++i) 
  547. #ifdef __STL_NO_DRAND48
  548.     iter_swap(i, first + Distance(rand() % ((i - first) + 1)));
  549. #else
  550.   iter_swap(i, first + Distance(lrand48() % ((i - first) + 1)));
  551. #endif
  552. }
  553. template <class RandomAccessIterator>
  554. inline void random_shuffle(RandomAccessIterator first,
  555.                            RandomAccessIterator last) {
  556.   __random_shuffle(first, last, distance_type(first));
  557. }
  558. template <class RandomAccessIterator, class RandomNumberGenerator>
  559. void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
  560.                     RandomNumberGenerator& rand) {
  561.   if (first == last) return;
  562.   for (RandomAccessIterator i = first + 1; i != last; ++i)
  563.     iter_swap(i, first + rand((i - first) + 1));
  564. }
  565. template <class ForwardIterator, class OutputIterator, class Distance>
  566. OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last,
  567.                                OutputIterator out, const Distance n)
  568. {
  569.   Distance remaining = 0;
  570.   distance(first, last, remaining);
  571.   Distance m = min(n, remaining);
  572.   while (m > 0) {
  573. #ifdef __STL_NO_DRAND48
  574.     if (rand() % remaining < m) {
  575. #else
  576.     if (lrand48() % remaining < m) {
  577. #endif
  578.       *out = *first;
  579.       ++out;
  580.       --m;
  581.     }
  582.     --remaining;
  583.     ++first;
  584.   }
  585.   return out;
  586. }
  587. template <class ForwardIterator, class OutputIterator, class Distance,
  588.           class RandomNumberGenerator>
  589. OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last,
  590.                                OutputIterator out, const Distance n,
  591.                                RandomNumberGenerator& rand)
  592. {
  593.   Distance remaining = 0;
  594.   distance(first, last, remaining);
  595.   Distance m = min(n, remaining);
  596.   while (m > 0) {
  597.     if (rand(remaining) < m) {
  598.       *out = *first;
  599.       ++out;
  600.       --m;
  601.     }
  602.     --remaining;
  603.     ++first;
  604.   }
  605.   return out;
  606. }
  607. template <class InputIterator, class RandomAccessIterator, class Distance>
  608. RandomAccessIterator __random_sample(InputIterator first, InputIterator last,
  609.                                      RandomAccessIterator out,
  610.                                      const Distance n)
  611. {
  612.   Distance m = 0;
  613.   Distance t = n;
  614.   for ( ; first != last && m < n; ++m, ++first) 
  615.     out[m] = *first;
  616.   while (first != last) {
  617.     ++t;
  618. #ifdef __STL_NO_DRAND48
  619.     Distance M = rand() % t;
  620. #else
  621.     Distance M = lrand48() % t;
  622. #endif
  623.     if (M < n)
  624.       out[M] = *first;
  625.     ++first;
  626.   }
  627.   return out + m;
  628. }
  629. template <class InputIterator, class RandomAccessIterator,
  630.           class RandomNumberGenerator, class Distance>
  631. RandomAccessIterator __random_sample(InputIterator first, InputIterator last,
  632.                                      RandomAccessIterator out,
  633.                                      RandomNumberGenerator& rand,
  634.                                      const Distance n)
  635. {
  636.   Distance m = 0;
  637.   Distance t = n;
  638.   for ( ; first != last && m < n; ++m, ++first)
  639.     out[m] = *first;
  640.   while (first != last) {
  641.     ++t;
  642.     Distance M = rand(t);
  643.     if (M < n)
  644.       out[M] = *first;
  645.     ++first;
  646.   }
  647.   return out + m;
  648. }
  649. template <class InputIterator, class RandomAccessIterator>
  650. inline RandomAccessIterator
  651. random_sample(InputIterator first, InputIterator last,
  652.               RandomAccessIterator out_first, RandomAccessIterator out_last) 
  653. {
  654.   return __random_sample(first, last, out_first, out_last - out_first);
  655. }
  656. template <class InputIterator, class RandomAccessIterator, 
  657.           class RandomNumberGenerator>
  658. inline RandomAccessIterator
  659. random_sample(InputIterator first, InputIterator last,
  660.               RandomAccessIterator out_first, RandomAccessIterator out_last,
  661.               RandomNumberGenerator& rand) 
  662. {
  663.   return __random_sample(first, last, out_first, rand, out_last - out_first);
  664. }
  665. template <class BidirectionalIterator, class Predicate>
  666. BidirectionalIterator partition(BidirectionalIterator first,
  667.                                 BidirectionalIterator last, Predicate pred) {
  668.   while (true) {
  669.     while (true)
  670.       if (first == last)
  671.         return first;
  672.       else if (pred(*first))
  673.         ++first;
  674.       else
  675.         break;
  676.     --last;
  677.     while (true)
  678.       if (first == last)
  679.         return first;
  680.       else if (!pred(*last))
  681.         --last;
  682.       else
  683.         break;
  684.     iter_swap(first, last);
  685.     ++first;
  686.   }
  687. }
  688. template <class ForwardIterator, class Predicate, class Distance>
  689. ForwardIterator __inplace_stable_partition(ForwardIterator first,
  690.                                            ForwardIterator last,
  691.                                            Predicate pred, Distance len) {
  692.   if (len == 1) return pred(*first) ? last : first;
  693.   ForwardIterator middle = first;
  694.   advance(middle, len / 2);
  695.   ForwardIterator 
  696.     first_cut = __inplace_stable_partition(first, middle, pred, len / 2);
  697.   ForwardIterator 
  698.     second_cut = __inplace_stable_partition(middle, last, pred,
  699.                                             len - len / 2);
  700.   rotate(first_cut, middle, second_cut);
  701.   len = 0;
  702.   distance(middle, second_cut, len);
  703.   advance(first_cut, len);
  704.   return first_cut;
  705. }
  706. template <class ForwardIterator, class Pointer, class Predicate, 
  707.           class Distance>
  708. ForwardIterator __stable_partition_adaptive(ForwardIterator first,
  709.                                             ForwardIterator last,
  710.                                             Predicate pred, Distance len,
  711.                                             Pointer buffer,
  712.                                             Distance buffer_size) {
  713.   if (len <= buffer_size) {
  714.     ForwardIterator result1 = first;
  715.     Pointer result2 = buffer;
  716.     for ( ; first != last ; ++first)
  717.       if (pred(*first)) {
  718.         *result1 = *first;
  719.         ++result1;
  720.       }
  721.       else {
  722.         *result2 = *first;
  723.         ++result2;
  724.       }
  725.     copy(buffer, result2, result1);
  726.     return result1;
  727.   }
  728.   else {
  729.     ForwardIterator middle = first;
  730.     advance(middle, len / 2);
  731.     ForwardIterator first_cut =
  732.       __stable_partition_adaptive(first, middle, pred, len / 2,
  733.                                   buffer, buffer_size);
  734.     ForwardIterator second_cut =
  735.       __stable_partition_adaptive(middle, last, pred, len - len / 2,
  736.                                   buffer, buffer_size);
  737.     rotate(first_cut, middle, second_cut);
  738.     len = 0;
  739.     distance(middle, second_cut, len);
  740.     advance(first_cut, len);
  741.     return first_cut;
  742.   }
  743. }
  744. template <class ForwardIterator, class Predicate, class T, class Distance>
  745. inline ForwardIterator __stable_partition_aux(ForwardIterator first,
  746.                                               ForwardIterator last, 
  747.                                               Predicate pred, T*, Distance*) {
  748.   temporary_buffer<ForwardIterator, T> buf(first, last);
  749.   if (buf.size() > 0)
  750.     return __stable_partition_adaptive(first, last, pred,
  751.                                        Distance(buf.requested_size()),
  752.                                        buf.begin(), buf.size());
  753.   else
  754.     return __inplace_stable_partition(first, last, pred, 
  755.                                       Distance(buf.requested_size()));
  756. }
  757. template <class ForwardIterator, class Predicate>
  758. inline ForwardIterator stable_partition(ForwardIterator first,
  759.                                         ForwardIterator last, 
  760.                                         Predicate pred) {
  761.   if (first == last)
  762.     return first;
  763.   else
  764.     return __stable_partition_aux(first, last, pred,
  765.                                   value_type(first), distance_type(first));
  766. }
  767. template <class RandomAccessIterator, class T>
  768. RandomAccessIterator __unguarded_partition(RandomAccessIterator first, 
  769.                                            RandomAccessIterator last, 
  770.                                            T pivot) {
  771.   while (true) {
  772.     while (*first < pivot) ++first;
  773.     --last;
  774.     while (pivot < *last) --last;
  775.     if (!(first < last)) return first;
  776.     iter_swap(first, last);
  777.     ++first;
  778.   }
  779. }    
  780. template <class RandomAccessIterator, class T, class Compare>
  781. RandomAccessIterator __unguarded_partition(RandomAccessIterator first, 
  782.                                            RandomAccessIterator last, 
  783.                                            T pivot, Compare comp) {
  784.   while (1) {
  785.     while (comp(*first, pivot)) ++first;
  786.     --last;
  787.     while (comp(pivot, *last)) --last;
  788.     if (!(first < last)) return first;
  789.     iter_swap(first, last);
  790.     ++first;
  791.   }
  792. }
  793. const int __stl_threshold = 16;
  794. template <class RandomAccessIterator, class T>
  795. void __unguarded_linear_insert(RandomAccessIterator last, T value) {
  796.   RandomAccessIterator next = last;
  797.   --next;
  798.   while (value < *next) {
  799.     *last = *next;
  800.     last = next;
  801.     --next;
  802.   }
  803.   *last = value;
  804. }
  805. template <class RandomAccessIterator, class T, class Compare>
  806. void __unguarded_linear_insert(RandomAccessIterator last, T value, 
  807.                                Compare comp) {
  808.   RandomAccessIterator next = last;
  809.   --next;  
  810.   while (comp(value , *next)) {
  811.     *last = *next;
  812.     last = next;
  813.     --next;
  814.   }
  815.   *last = value;
  816. }
  817. template <class RandomAccessIterator, class T>
  818. inline void __linear_insert(RandomAccessIterator first, 
  819.                             RandomAccessIterator last, T*) {
  820.   T value = *last;
  821.   if (value < *first) {
  822.     copy_backward(first, last, last + 1);
  823.     *first = value;
  824.   }
  825.   else
  826.     __unguarded_linear_insert(last, value);
  827. }
  828. template <class RandomAccessIterator, class T, class Compare>
  829. inline void __linear_insert(RandomAccessIterator first, 
  830.                             RandomAccessIterator last, T*, Compare comp) {
  831.   T value = *last;
  832.   if (comp(value, *first)) {
  833.     copy_backward(first, last, last + 1);
  834.     *first = value;
  835.   }
  836.   else
  837.     __unguarded_linear_insert(last, value, comp);
  838. }
  839. template <class RandomAccessIterator>
  840. void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
  841.   if (first == last) return; 
  842.   for (RandomAccessIterator i = first + 1; i != last; ++i)
  843.     __linear_insert(first, i, value_type(first));
  844. }
  845. template <class RandomAccessIterator, class Compare>
  846. void __insertion_sort(RandomAccessIterator first,
  847.                       RandomAccessIterator last, Compare comp) {
  848.   if (first == last) return;
  849.   for (RandomAccessIterator i = first + 1; i != last; ++i)
  850.     __linear_insert(first, i, value_type(first), comp);
  851. }
  852. template <class RandomAccessIterator, class T>
  853. void __unguarded_insertion_sort_aux(RandomAccessIterator first, 
  854.                                     RandomAccessIterator last, T*) {
  855.   for (RandomAccessIterator i = first; i != last; ++i)
  856.     __unguarded_linear_insert(i, T(*i));
  857. }
  858. template <class RandomAccessIterator>
  859. inline void __unguarded_insertion_sort(RandomAccessIterator first, 
  860.                                 RandomAccessIterator last) {
  861.   __unguarded_insertion_sort_aux(first, last, value_type(first));
  862. }
  863. template <class RandomAccessIterator, class T, class Compare>
  864. void __unguarded_insertion_sort_aux(RandomAccessIterator first, 
  865.                                     RandomAccessIterator last,
  866.                                     T*, Compare comp) {
  867.   for (RandomAccessIterator i = first; i != last; ++i)
  868.     __unguarded_linear_insert(i, T(*i), comp);
  869. }
  870. template <class RandomAccessIterator, class Compare>
  871. inline void __unguarded_insertion_sort(RandomAccessIterator first, 
  872.                                        RandomAccessIterator last,
  873.                                        Compare comp) {
  874.   __unguarded_insertion_sort_aux(first, last, value_type(first), comp);
  875. }
  876. template <class RandomAccessIterator>
  877. void __final_insertion_sort(RandomAccessIterator first, 
  878.                             RandomAccessIterator last) {
  879.   if (last - first > __stl_threshold) {
  880.     __insertion_sort(first, first + __stl_threshold);
  881.     __unguarded_insertion_sort(first + __stl_threshold, last);
  882.   }
  883.   else
  884.     __insertion_sort(first, last);
  885. }
  886. template <class RandomAccessIterator, class Compare>
  887. void __final_insertion_sort(RandomAccessIterator first, 
  888.                             RandomAccessIterator last, Compare comp) {
  889.   if (last - first > __stl_threshold) {
  890.     __insertion_sort(first, first + __stl_threshold, comp);
  891.     __unguarded_insertion_sort(first + __stl_threshold, last, comp);
  892.   }
  893.   else
  894.     __insertion_sort(first, last, comp);
  895. }
  896. template <class Size>
  897. inline Size __lg(Size n) {
  898.   Size k;
  899.   for (k = 0; n > 1; n >>= 1) ++k;
  900.   return k;
  901. }
  902. template <class RandomAccessIterator, class T, class Size>
  903. void __introsort_loop(RandomAccessIterator first,
  904.                       RandomAccessIterator last, T*,
  905.                       Size depth_limit) {
  906.   while (last - first > __stl_threshold) {
  907.     if (depth_limit == 0) {
  908.       partial_sort(first, last, last);
  909.       return;
  910.     }
  911.     --depth_limit;
  912.     RandomAccessIterator cut = __unguarded_partition
  913.       (first, last, T(__median(*first, *(first + (last - first)/2),
  914.                                *(last - 1))));
  915.     __introsort_loop(cut, last, value_type(first), depth_limit);
  916.     last = cut;
  917.   }
  918. }
  919. template <class RandomAccessIterator, class T, class Size, class Compare>
  920. void __introsort_loop(RandomAccessIterator first,
  921.                       RandomAccessIterator last, T*,
  922.                       Size depth_limit, Compare comp) {
  923.   while (last - first > __stl_threshold) {
  924.     if (depth_limit == 0) {
  925.       partial_sort(first, last, last, comp);
  926.       return;
  927.     }
  928.     --depth_limit;
  929.     RandomAccessIterator cut = __unguarded_partition
  930.       (first, last, T(__median(*first, *(first + (last - first)/2),
  931.                                *(last - 1), comp)), comp);
  932.     __introsort_loop(cut, last, value_type(first), depth_limit, comp);
  933.     last = cut;
  934.   }
  935. }
  936. template <class RandomAccessIterator>
  937. inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
  938.   if (first != last) {
  939.     __introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
  940.     __final_insertion_sort(first, last);
  941.   }
  942. }
  943. template <class RandomAccessIterator, class Compare>
  944. inline void sort(RandomAccessIterator first, RandomAccessIterator last,
  945.                  Compare comp) {
  946.   if (first != last) {
  947.     __introsort_loop(first, last, value_type(first), __lg(last - first) * 2,
  948.                      comp);
  949.     __final_insertion_sort(first, last, comp);
  950.   }
  951. }
  952. template <class RandomAccessIterator>
  953. void __inplace_stable_sort(RandomAccessIterator first,
  954.                            RandomAccessIterator last) {
  955.   if (last - first < 15) {
  956.     __insertion_sort(first, last);
  957.     return;
  958.   }
  959.   RandomAccessIterator middle = first + (last - first) / 2;
  960.   __inplace_stable_sort(first, middle);
  961.   __inplace_stable_sort(middle, last);
  962.   __merge_without_buffer(first, middle, last, middle - first, last - middle);
  963. }
  964. template <class RandomAccessIterator, class Compare>
  965. void __inplace_stable_sort(RandomAccessIterator first,
  966.                            RandomAccessIterator last, Compare comp) {
  967.   if (last - first < 15) {
  968.     __insertion_sort(first, last, comp);
  969.     return;
  970.   }
  971.   RandomAccessIterator middle = first + (last - first) / 2;
  972.   __inplace_stable_sort(first, middle, comp);
  973.   __inplace_stable_sort(middle, last, comp);
  974.   __merge_without_buffer(first, middle, last, middle - first,
  975.                          last - middle, comp);
  976. }
  977. template <class RandomAccessIterator1, class RandomAccessIterator2,
  978.           class Distance>
  979. void __merge_sort_loop(RandomAccessIterator1 first,
  980.                        RandomAccessIterator1 last, 
  981.                        RandomAccessIterator2 result, Distance step_size) {
  982.   Distance two_step = 2 * step_size;
  983.   while (last - first >= two_step) {
  984.     result = merge(first, first + step_size,
  985.                    first + step_size, first + two_step, result);
  986.     first += two_step;
  987.   }
  988.   step_size = min(Distance(last - first), step_size);
  989.   merge(first, first + step_size, first + step_size, last, result);
  990. }
  991. template <class RandomAccessIterator1, class RandomAccessIterator2,
  992.           class Distance, class Compare>
  993. void __merge_sort_loop(RandomAccessIterator1 first,
  994.                        RandomAccessIterator1 last, 
  995.                        RandomAccessIterator2 result, Distance step_size,
  996.                        Compare comp) {
  997.   Distance two_step = 2 * step_size;
  998.   while (last - first >= two_step) {
  999.     result = merge(first, first + step_size,
  1000.                    first + step_size, first + two_step, result, comp);
  1001.     first += two_step;
  1002.   }
  1003.   step_size = min(Distance(last - first), step_size);
  1004.   merge(first, first + step_size, first + step_size, last, result, comp);
  1005. }
  1006. const int __stl_chunk_size = 7;
  1007.         
  1008. template <class RandomAccessIterator, class Distance>
  1009. void __chunk_insertion_sort(RandomAccessIterator first, 
  1010.                             RandomAccessIterator last, Distance chunk_size) {
  1011.   while (last - first >= chunk_size) {
  1012.     __insertion_sort(first, first + chunk_size);
  1013.     first += chunk_size;
  1014.   }
  1015.   __insertion_sort(first, last);
  1016. }
  1017. template <class RandomAccessIterator, class Distance, class Compare>
  1018. void __chunk_insertion_sort(RandomAccessIterator first, 
  1019.                             RandomAccessIterator last,
  1020.                             Distance chunk_size, Compare comp) {
  1021.   while (last - first >= chunk_size) {
  1022.     __insertion_sort(first, first + chunk_size, comp);
  1023.     first += chunk_size;
  1024.   }
  1025.   __insertion_sort(first, last, comp);
  1026. }
  1027. template <class RandomAccessIterator, class Pointer, class Distance>
  1028. void __merge_sort_with_buffer(RandomAccessIterator first, 
  1029.                               RandomAccessIterator last,
  1030.                               Pointer buffer, Distance*) {
  1031.   Distance len = last - first;
  1032.   Pointer buffer_last = buffer + len;
  1033.   Distance step_size = __stl_chunk_size;
  1034.   __chunk_insertion_sort(first, last, step_size);
  1035.   while (step_size < len) {
  1036.     __merge_sort_loop(first, last, buffer, step_size);
  1037.     step_size *= 2;
  1038.     __merge_sort_loop(buffer, buffer_last, first, step_size);
  1039.     step_size *= 2;
  1040.   }
  1041. }
  1042. template <class RandomAccessIterator, class Pointer, class Distance,
  1043.           class Compare>
  1044. void __merge_sort_with_buffer(RandomAccessIterator first, 
  1045.                               RandomAccessIterator last, Pointer buffer,
  1046.                               Distance*, Compare comp) {
  1047.   Distance len = last - first;
  1048.   Pointer buffer_last = buffer + len;
  1049.   Distance step_size = __stl_chunk_size;
  1050.   __chunk_insertion_sort(first, last, step_size, comp);
  1051.   while (step_size < len) {
  1052.     __merge_sort_loop(first, last, buffer, step_size, comp);
  1053.     step_size *= 2;
  1054.     __merge_sort_loop(buffer, buffer_last, first, step_size, comp);
  1055.     step_size *= 2;
  1056.   }
  1057. }
  1058. template <class RandomAccessIterator, class Pointer, class Distance>
  1059. void __stable_sort_adaptive(RandomAccessIterator first, 
  1060.                             RandomAccessIterator last, Pointer buffer,
  1061.                             Distance buffer_size) {
  1062.   Distance len = (last - first + 1) / 2;
  1063.   RandomAccessIterator middle = first + len;
  1064.   if (len > buffer_size) {
  1065.     __stable_sort_adaptive(first, middle, buffer, buffer_size);
  1066.     __stable_sort_adaptive(middle, last, buffer, buffer_size);
  1067.   } else {
  1068.     __merge_sort_with_buffer(first, middle, buffer, (Distance*)0);
  1069.     __merge_sort_with_buffer(middle, last, buffer, (Distance*)0);
  1070.   }
  1071.   __merge_adaptive(first, middle, last, Distance(middle - first), 
  1072.                    Distance(last - middle), buffer, buffer_size);
  1073. }
  1074. template <class RandomAccessIterator, class Pointer, class Distance, 
  1075.           class Compare>
  1076. void __stable_sort_adaptive(RandomAccessIterator first, 
  1077.                             RandomAccessIterator last, Pointer buffer,
  1078.                             Distance buffer_size, Compare comp) {
  1079.   Distance len = (last - first + 1) / 2;
  1080.   RandomAccessIterator middle = first + len;
  1081.   if (len > buffer_size) {
  1082.     __stable_sort_adaptive(first, middle, buffer, buffer_size, 
  1083.                            comp);
  1084.     __stable_sort_adaptive(middle, last, buffer, buffer_size, 
  1085.                            comp);
  1086.   } else {
  1087.     __merge_sort_with_buffer(first, middle, buffer, (Distance*)0, comp);
  1088.     __merge_sort_with_buffer(middle, last, buffer, (Distance*)0, comp);
  1089.   }
  1090.   __merge_adaptive(first, middle, last, Distance(middle - first), 
  1091.                    Distance(last - middle), buffer, buffer_size,
  1092.                    comp);
  1093. }
  1094. template <class RandomAccessIterator, class T, class Distance>
  1095. inline void __stable_sort_aux(RandomAccessIterator first,
  1096.                               RandomAccessIterator last, T*, Distance*) {
  1097.   temporary_buffer<RandomAccessIterator, T> buf(first, last);
  1098.   if (buf.begin() == 0)
  1099.     __inplace_stable_sort(first, last);
  1100.   else 
  1101.     __stable_sort_adaptive(first, last, buf.begin(), Distance(buf.size()));
  1102. }
  1103. template <class RandomAccessIterator, class T, class Distance, class Compare>
  1104. inline void __stable_sort_aux(RandomAccessIterator first,
  1105.                               RandomAccessIterator last, T*, Distance*,
  1106.                               Compare comp) {
  1107.   temporary_buffer<RandomAccessIterator, T> buf(first, last);
  1108.   if (buf.begin() == 0)
  1109.     __inplace_stable_sort(first, last, comp);
  1110.   else 
  1111.     __stable_sort_adaptive(first, last, buf.begin(), Distance(buf.size()),
  1112.                            comp);
  1113. }
  1114. template <class RandomAccessIterator>
  1115. inline void stable_sort(RandomAccessIterator first,
  1116.                         RandomAccessIterator last) {
  1117.   __stable_sort_aux(first, last, value_type(first), distance_type(first));
  1118. }
  1119. template <class RandomAccessIterator, class Compare>
  1120. inline void stable_sort(RandomAccessIterator first,
  1121.                         RandomAccessIterator last, Compare comp) {
  1122.   __stable_sort_aux(first, last, value_type(first), distance_type(first), 
  1123.                     comp);
  1124. }
  1125. template <class RandomAccessIterator, class T>
  1126. void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
  1127.                     RandomAccessIterator last, T*) {
  1128.   make_heap(first, middle);
  1129.   for (RandomAccessIterator i = middle; i < last; ++i)
  1130.     if (*i < *first) 
  1131.       __pop_heap(first, middle, i, T(*i), distance_type(first));
  1132.   sort_heap(first, middle);
  1133. }
  1134. template <class RandomAccessIterator>
  1135. inline void partial_sort(RandomAccessIterator first,
  1136.                          RandomAccessIterator middle,
  1137.                          RandomAccessIterator last) {
  1138.   __partial_sort(first, middle, last, value_type(first));
  1139. }
  1140. template <class RandomAccessIterator, class T, class Compare>
  1141. void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
  1142.                     RandomAccessIterator last, T*, Compare comp) {
  1143.   make_heap(first, middle, comp);
  1144.   for (RandomAccessIterator i = middle; i < last; ++i)
  1145.     if (comp(*i, *first))
  1146.       __pop_heap(first, middle, i, T(*i), comp, distance_type(first));
  1147.   sort_heap(first, middle, comp);
  1148. }
  1149. template <class RandomAccessIterator, class Compare>
  1150. inline void partial_sort(RandomAccessIterator first,
  1151.                          RandomAccessIterator middle,
  1152.                          RandomAccessIterator last, Compare comp) {
  1153.   __partial_sort(first, middle, last, value_type(first), comp);
  1154. }
  1155. template <class InputIterator, class RandomAccessIterator, class Distance,
  1156.           class T>
  1157. RandomAccessIterator __partial_sort_copy(InputIterator first,
  1158.                                          InputIterator last,
  1159.                                          RandomAccessIterator result_first,
  1160.                                          RandomAccessIterator result_last, 
  1161.                                          Distance*, T*) {
  1162.   if (result_first == result_last) return result_last;
  1163.   RandomAccessIterator result_real_last = result_first;
  1164.   while(first != last && result_real_last != result_last) {
  1165.     *result_real_last = *first;
  1166.     ++result_real_last;
  1167.     ++first;
  1168.   }
  1169.   make_heap(result_first, result_real_last);
  1170.   while (first != last) {
  1171.     if (*first < *result_first) 
  1172.       __adjust_heap(result_first, Distance(0),
  1173.                     Distance(result_real_last - result_first), T(*first));
  1174.     ++first;
  1175.   }
  1176.   sort_heap(result_first, result_real_last);
  1177.   return result_real_last;
  1178. }
  1179. template <class InputIterator, class RandomAccessIterator>
  1180. inline RandomAccessIterator
  1181. partial_sort_copy(InputIterator first, InputIterator last,
  1182.                   RandomAccessIterator result_first,
  1183.                   RandomAccessIterator result_last) {
  1184.   return __partial_sort_copy(first, last, result_first, result_last, 
  1185.                              distance_type(result_first), value_type(first));
  1186. }
  1187. template <class InputIterator, class RandomAccessIterator, class Compare,
  1188.           class Distance, class T>
  1189. RandomAccessIterator __partial_sort_copy(InputIterator first,
  1190.                                          InputIterator last,
  1191.                                          RandomAccessIterator result_first,
  1192.                                          RandomAccessIterator result_last,
  1193.                                          Compare comp, Distance*, T*) {
  1194.   if (result_first == result_last) return result_last;
  1195.   RandomAccessIterator result_real_last = result_first;
  1196.   while(first != last && result_real_last != result_last) {
  1197.     *result_real_last = *first;
  1198.     ++result_real_last;
  1199.     ++first;
  1200.   }
  1201.   make_heap(result_first, result_real_last, comp);
  1202.   while (first != last) {
  1203.     if (comp(*first, *result_first))
  1204.       __adjust_heap(result_first, Distance(0),
  1205.                     Distance(result_real_last - result_first), T(*first),
  1206.                     comp);
  1207.     ++first;
  1208.   }
  1209.   sort_heap(result_first, result_real_last, comp);
  1210.   return result_real_last;
  1211. }
  1212. template <class InputIterator, class RandomAccessIterator, class Compare>
  1213. inline RandomAccessIterator
  1214. partial_sort_copy(InputIterator first, InputIterator last,
  1215.                   RandomAccessIterator result_first,
  1216.                   RandomAccessIterator result_last, Compare comp) {
  1217.   return __partial_sort_copy(first, last, result_first, result_last, comp,
  1218.                              distance_type(result_first), value_type(first));
  1219. }
  1220. template <class RandomAccessIterator, class T>
  1221. void __nth_element(RandomAccessIterator first, RandomAccessIterator nth,
  1222.                    RandomAccessIterator last, T*) {
  1223.   while (last - first > 3) {
  1224.     RandomAccessIterator cut = __unguarded_partition
  1225.       (first, last, T(__median(*first, *(first + (last - first)/2),
  1226.                                *(last - 1))));
  1227.     if (cut <= nth)
  1228.       first = cut;
  1229.     else 
  1230.       last = cut;
  1231.   }
  1232.   __insertion_sort(first, last);
  1233. }
  1234. template <class RandomAccessIterator>
  1235. inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
  1236.                         RandomAccessIterator last) {
  1237.   __nth_element(first, nth, last, value_type(first));
  1238. }
  1239. template <class RandomAccessIterator, class T, class Compare>
  1240. void __nth_element(RandomAccessIterator first, RandomAccessIterator nth,
  1241.                    RandomAccessIterator last, T*, Compare comp) {
  1242.   while (last - first > 3) {
  1243.     RandomAccessIterator cut = __unguarded_partition
  1244.       (first, last, T(__median(*first, *(first + (last - first)/2), 
  1245.                                *(last - 1), comp)), comp);
  1246.     if (cut <= nth)
  1247.       first = cut;
  1248.     else 
  1249.       last = cut;
  1250.   }
  1251.   __insertion_sort(first, last, comp);
  1252. }
  1253. template <class RandomAccessIterator, class Compare>
  1254. inline void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
  1255.                  RandomAccessIterator last, Compare comp) {
  1256.   __nth_element(first, nth, last, value_type(first), comp);
  1257. }
  1258. template <class ForwardIterator, class T, class Distance>
  1259. ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
  1260.                               const T& value, Distance*,
  1261.                               forward_iterator_tag) {
  1262.   Distance len = 0;
  1263.   distance(first, last, len);
  1264.   Distance half;
  1265.   ForwardIterator middle;
  1266.   while (len > 0) {
  1267.     half = len >> 1;
  1268.     middle = first;
  1269.     advance(middle, half);
  1270.     if (*middle < value) {
  1271.       first = middle;
  1272.       ++first;
  1273.       len = len - half - 1;
  1274.     }
  1275.     else
  1276.       len = half;
  1277.   }
  1278.   return first;
  1279. }
  1280. template <class RandomAccessIterator, class T, class Distance>
  1281. RandomAccessIterator __lower_bound(RandomAccessIterator first,
  1282.                                    RandomAccessIterator last, const T& value,
  1283.                                    Distance*, random_access_iterator_tag) {
  1284.   Distance len = last - first;
  1285.   Distance half;
  1286.   RandomAccessIterator middle;
  1287.   while (len > 0) {
  1288.     half = len >> 1;
  1289.     middle = first + half;
  1290.     if (*middle < value) {
  1291.       first = middle + 1;
  1292.       len = len - half - 1;
  1293.     }
  1294.     else
  1295.       len = half;
  1296.   }
  1297.   return first;
  1298. }
  1299. template <class ForwardIterator, class T>
  1300. inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
  1301.                                    const T& value) {
  1302.   return __lower_bound(first, last, value, distance_type(first),
  1303.                        iterator_category(first));
  1304. }
  1305. template <class ForwardIterator, class T, class Compare, class Distance>
  1306. ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
  1307.                               const T& value, Compare comp, Distance*,
  1308.                               forward_iterator_tag) {
  1309.   Distance len = 0;
  1310.   distance(first, last, len);
  1311.   Distance half;
  1312.   ForwardIterator middle;
  1313.   while (len > 0) {
  1314.     half = len >> 1;
  1315.     middle = first;
  1316.     advance(middle, half);
  1317.     if (comp(*middle, value)) {
  1318.       first = middle;
  1319.       ++first;
  1320.       len = len - half - 1;
  1321.     }
  1322.     else
  1323.       len = half;
  1324.   }
  1325.   return first;
  1326. }
  1327. template <class RandomAccessIterator, class T, class Compare, class Distance>
  1328. RandomAccessIterator __lower_bound(RandomAccessIterator first,
  1329.                                    RandomAccessIterator last,
  1330.                                    const T& value, Compare comp, Distance*,
  1331.                                    random_access_iterator_tag) {
  1332.   Distance len = last - first;
  1333.   Distance half;
  1334.   RandomAccessIterator middle;
  1335.   while (len > 0) {
  1336.     half = len >> 1;
  1337.     middle = first + half;
  1338.     if (comp(*middle, value)) {
  1339.       first = middle + 1;
  1340.       len = len - half - 1;
  1341.     }
  1342.     else
  1343.       len = half;
  1344.   }
  1345.   return first;
  1346. }
  1347. template <class ForwardIterator, class T, class Compare>
  1348. inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
  1349.                                    const T& value, Compare comp) {
  1350.   return __lower_bound(first, last, value, comp, distance_type(first),
  1351.                        iterator_category(first));
  1352. }
  1353. template <class ForwardIterator, class T, class Distance>
  1354. ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
  1355.                               const T& value, Distance*,
  1356.                               forward_iterator_tag) {
  1357.   Distance len = 0;
  1358.   distance(first, last, len);
  1359.   Distance half;
  1360.   ForwardIterator middle;
  1361.   while (len > 0) {
  1362.     half = len >> 1;
  1363.     middle = first;
  1364.     advance(middle, half);
  1365.     if (value < *middle)
  1366.       len = half;
  1367.     else {
  1368.       first = middle;
  1369.       ++first;
  1370.       len = len - half - 1;
  1371.     }
  1372.   }
  1373.   return first;
  1374. }
  1375. template <class RandomAccessIterator, class T, class Distance>
  1376. RandomAccessIterator __upper_bound(RandomAccessIterator first,
  1377.                                    RandomAccessIterator last, const T& value,
  1378.                                    Distance*, random_access_iterator_tag) {
  1379.   Distance len = last - first;
  1380.   Distance half;
  1381.   RandomAccessIterator middle;
  1382.   while (len > 0) {
  1383.     half = len >> 1;
  1384.     middle = first + half;
  1385.     if (value < *middle)
  1386.       len = half;
  1387.     else {
  1388.       first = middle + 1;
  1389.       len = len - half - 1;
  1390.     }
  1391.   }
  1392.   return first;
  1393. }
  1394. template <class ForwardIterator, class T>
  1395. inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
  1396.                                    const T& value) {
  1397.   return __upper_bound(first, last, value, distance_type(first),
  1398.                        iterator_category(first));
  1399. }
  1400. template <class ForwardIterator, class T, class Compare, class Distance>
  1401. ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
  1402.                               const T& value, Compare comp, Distance*,
  1403.                               forward_iterator_tag) {
  1404.   Distance len = 0;
  1405.   distance(first, last, len);
  1406.   Distance half;
  1407.   ForwardIterator middle;
  1408.   while (len > 0) {
  1409.     half = len >> 1;
  1410.     middle = first;
  1411.     advance(middle, half);
  1412.     if (comp(value, *middle))
  1413.       len = half;
  1414.     else {
  1415.       first = middle;
  1416.       ++first;
  1417.       len = len - half - 1;
  1418.     }
  1419.   }
  1420.   return first;
  1421. }
  1422. template <class RandomAccessIterator, class T, class Compare, class Distance>
  1423. RandomAccessIterator __upper_bound(RandomAccessIterator first,
  1424.                                    RandomAccessIterator last,
  1425.                                    const T& value, Compare comp, Distance*,
  1426.                                    random_access_iterator_tag) {
  1427.   Distance len = last - first;
  1428.   Distance half;
  1429.   RandomAccessIterator middle;
  1430.   while (len > 0) {
  1431.     half = len >> 1;
  1432.     middle = first + half;
  1433.     if (comp(value, *middle))
  1434.       len = half;
  1435.     else {
  1436.       first = middle + 1;
  1437.       len = len - half - 1;
  1438.     }
  1439.   }
  1440.   return first;
  1441. }
  1442. template <class ForwardIterator, class T, class Compare>
  1443. inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
  1444.                                    const T& value, Compare comp) {
  1445.   return __upper_bound(first, last, value, comp, distance_type(first),
  1446.                        iterator_category(first));
  1447. }
  1448. template <class ForwardIterator, class T, class Distance>
  1449. pair<ForwardIterator, ForwardIterator>
  1450. __equal_range(ForwardIterator first, ForwardIterator last, const T& value,
  1451.               Distance*, forward_iterator_tag) {
  1452.   Distance len = 0;
  1453.   distance(first, last, len);
  1454.   Distance half;
  1455.   ForwardIterator middle, left, right;
  1456.   while (len > 0) {
  1457.     half = len >> 1;
  1458.     middle = first;
  1459.     advance(middle, half);
  1460.     if (*middle < value) {
  1461.       first = middle;
  1462.       ++first;
  1463.       len = len - half - 1;
  1464.     }
  1465.     else if (value < *middle)
  1466.       len = half;
  1467.     else {
  1468.       left = lower_bound(first, middle, value);
  1469.       advance(first, len);
  1470.       right = upper_bound(++middle, first, value);
  1471.       return pair<ForwardIterator, ForwardIterator>(left, right);
  1472.     }
  1473.   }
  1474.   return pair<ForwardIterator, ForwardIterator>(first, first);
  1475. }
  1476. template <class RandomAccessIterator, class T, class Distance>
  1477. pair<RandomAccessIterator, RandomAccessIterator>
  1478. __equal_range(RandomAccessIterator first, RandomAccessIterator last,
  1479.               const T& value, Distance*, random_access_iterator_tag) {
  1480.   Distance len = last - first;
  1481.   Distance half;
  1482.   RandomAccessIterator middle, left, right;
  1483.   while (len > 0) {
  1484.     half = len >> 1;
  1485.     middle = first + half;
  1486.     if (*middle < value) {
  1487.       first = middle + 1;
  1488.       len = len - half - 1;
  1489.     }
  1490.     else if (value < *middle)
  1491.       len = half;
  1492.     else {
  1493.       left = lower_bound(first, middle, value);
  1494.       right = upper_bound(++middle, first + len, value);
  1495.       return pair<RandomAccessIterator, RandomAccessIterator>(left,
  1496.                                                               right);
  1497.     }
  1498.   }
  1499.   return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
  1500. }
  1501. template <class ForwardIterator, class T>
  1502. inline pair<ForwardIterator, ForwardIterator>
  1503. equal_range(ForwardIterator first, ForwardIterator last, const T& value) {
  1504.   return __equal_range(first, last, value, distance_type(first),
  1505.                        iterator_category(first));
  1506. }
  1507. template <class ForwardIterator, class T, class Compare, class Distance>
  1508. pair<ForwardIterator, ForwardIterator>
  1509. __equal_range(ForwardIterator first, ForwardIterator last, const T& value,
  1510.               Compare comp, Distance*, forward_iterator_tag) {
  1511.   Distance len = 0;
  1512.   distance(first, last, len);
  1513.   Distance half;
  1514.   ForwardIterator middle, left, right;
  1515.   while (len > 0) {
  1516.     half = len >> 1;
  1517.     middle = first;
  1518.     advance(middle, half);
  1519.     if (comp(*middle, value)) {
  1520.       first = middle;
  1521.       ++first;
  1522.       len = len - half - 1;
  1523.     }
  1524.     else if (comp(value, *middle))
  1525.       len = half;
  1526.     else {
  1527.       left = lower_bound(first, middle, value, comp);
  1528.       advance(first, len);
  1529.       right = upper_bound(++middle, first, value, comp);
  1530.       return pair<ForwardIterator, ForwardIterator>(left, right);
  1531.     }
  1532.   }
  1533.   return pair<ForwardIterator, ForwardIterator>(first, first);
  1534. }           
  1535. template <class RandomAccessIterator, class T, class Compare, class Distance>
  1536. pair<RandomAccessIterator, RandomAccessIterator>
  1537. __equal_range(RandomAccessIterator first, RandomAccessIterator last,
  1538.               const T& value, Compare comp, Distance*,
  1539.               random_access_iterator_tag) {
  1540.   Distance len = last - first;
  1541.   Distance half;
  1542.   RandomAccessIterator middle, left, right;
  1543.   while (len > 0) {
  1544.     half = len >> 1;
  1545.     middle = first + half;
  1546.     if (comp(*middle, value)) {
  1547.       first = middle + 1;
  1548.       len = len - half - 1;
  1549.     }
  1550.     else if (comp(value, *middle))
  1551.       len = half;
  1552.     else {
  1553.       left = lower_bound(first, middle, value, comp);
  1554.       right = upper_bound(++middle, first + len, value, comp);
  1555.       return pair<RandomAccessIterator, RandomAccessIterator>(left,
  1556.                                                               right);
  1557.     }
  1558.   }
  1559.   return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
  1560. }           
  1561. template <class ForwardIterator, class T, class Compare>
  1562. inline pair<ForwardIterator, ForwardIterator>
  1563. equal_range(ForwardIterator first, ForwardIterator last, const T& value,
  1564.             Compare comp) {
  1565.   return __equal_range(first, last, value, comp, distance_type(first),
  1566.                        iterator_category(first));
  1567. }    
  1568. template <class ForwardIterator, class T>
  1569. bool binary_search(ForwardIterator first, ForwardIterator last,
  1570.                    const T& value) {
  1571.   ForwardIterator i = lower_bound(first, last, value);
  1572.   return i != last && !(value < *i);
  1573. }
  1574. template <class ForwardIterator, class T, class Compare>
  1575. bool binary_search(ForwardIterator first, ForwardIterator last, const T& value,
  1576.                    Compare comp) {
  1577.   ForwardIterator i = lower_bound(first, last, value, comp);
  1578.   return i != last && !comp(value, *i);
  1579. }
  1580. template <class InputIterator1, class InputIterator2, class OutputIterator>
  1581. OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
  1582.                      InputIterator2 first2, InputIterator2 last2,
  1583.                      OutputIterator result) {
  1584.   while (first1 != last1 && first2 != last2) {
  1585.     if (*first2 < *first1) {
  1586.       *result = *first2;
  1587.       ++first2;
  1588.     }
  1589.     else {
  1590.       *result = *first1;
  1591.       ++first1;
  1592.     }
  1593.     ++result;
  1594.   }
  1595.   return copy(first2, last2, copy(first1, last1, result));
  1596. }
  1597. template <class InputIterator1, class InputIterator2, class OutputIterator,
  1598.           class Compare>
  1599. OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
  1600.                      InputIterator2 first2, InputIterator2 last2,
  1601.                      OutputIterator result, Compare comp) {
  1602.   while (first1 != last1 && first2 != last2) {
  1603.     if (comp(*first2, *first1)) {
  1604.       *result = *first2;
  1605.       ++first2;
  1606.     }
  1607.     else {
  1608.       *result = *first1;
  1609.       ++first1;
  1610.     }
  1611.     ++result;
  1612.   }
  1613.   return copy(first2, last2, copy(first1, last1, result));
  1614. }
  1615. template <class BidirectionalIterator, class Distance>
  1616. void __merge_without_buffer(BidirectionalIterator first,
  1617.                             BidirectionalIterator middle,
  1618.                             BidirectionalIterator last,
  1619.                             Distance len1, Distance len2) {
  1620.   if (len1 == 0 || len2 == 0) return;
  1621.   if (len1 + len2 == 2) {
  1622.     if (*middle < *first) iter_swap(first, middle);
  1623.     return;
  1624.   }
  1625.   BidirectionalIterator first_cut = first;
  1626.   BidirectionalIterator second_cut = middle;
  1627.   Distance len11 = 0;
  1628.   Distance len22 = 0;
  1629.   if (len1 > len2) {
  1630.     len11 = len1 / 2;
  1631.     advance(first_cut, len11);
  1632.     second_cut = lower_bound(middle, last, *first_cut);
  1633.     distance(middle, second_cut, len22);
  1634.   }
  1635.   else {
  1636.     len22 = len2 / 2;
  1637.     advance(second_cut, len22);
  1638.     first_cut = upper_bound(first, middle, *second_cut);
  1639.     distance(first, first_cut, len11);
  1640.   }
  1641.   rotate(first_cut, middle, second_cut);
  1642.   BidirectionalIterator new_middle = first_cut;
  1643.   advance(new_middle, len22);
  1644.   __merge_without_buffer(first, first_cut, new_middle, len11, len22);
  1645.   __merge_without_buffer(new_middle, second_cut, last, len1 - len11,
  1646.                          len2 - len22);
  1647. }
  1648. template <class BidirectionalIterator, class Distance, class Compare>
  1649. void __merge_without_buffer(BidirectionalIterator first,
  1650.                             BidirectionalIterator middle,
  1651.                             BidirectionalIterator last,
  1652.                             Distance len1, Distance len2, Compare comp) {
  1653.   if (len1 == 0 || len2 == 0) return;
  1654.   if (len1 + len2 == 2) {
  1655.     if (comp(*middle, *first)) iter_swap(first, middle);
  1656.     return;
  1657.   }
  1658.   BidirectionalIterator first_cut = first;
  1659.   BidirectionalIterator second_cut = middle;
  1660.   Distance len11 = 0;
  1661.   Distance len22 = 0;
  1662.   if (len1 > len2) {
  1663.     len11 = len1 / 2;
  1664.     advance(first_cut, len11);
  1665.     second_cut = lower_bound(middle, last, *first_cut, comp);
  1666.     distance(middle, second_cut, len22);
  1667.   }
  1668.   else {
  1669.     len22 = len2 / 2;
  1670.     advance(second_cut, len22);
  1671.     first_cut = upper_bound(first, middle, *second_cut, comp);
  1672.     distance(first, first_cut, len11);
  1673.   }
  1674.   rotate(first_cut, middle, second_cut);
  1675.   BidirectionalIterator new_middle = first_cut;
  1676.   advance(new_middle, len22);
  1677.   __merge_without_buffer(first, first_cut, new_middle, len11, len22, comp);
  1678.   __merge_without_buffer(new_middle, second_cut, last, len1 - len11,
  1679.                          len2 - len22, comp);
  1680. }
  1681. template <class BidirectionalIterator1, class BidirectionalIterator2,
  1682.           class Distance>
  1683. BidirectionalIterator1 __rotate_adaptive(BidirectionalIterator1 first,
  1684.                                          BidirectionalIterator1 middle,
  1685.                                          BidirectionalIterator1 last,
  1686.                                          Distance len1, Distance len2,
  1687.                                          BidirectionalIterator2 buffer,
  1688.                                          Distance buffer_size) {
  1689.   BidirectionalIterator2 buffer_end;
  1690.   if (len1 > len2 && len2 <= buffer_size) {
  1691.     buffer_end = copy(middle, last, buffer);
  1692.     copy_backward(first, middle, last);
  1693.     return copy(buffer, buffer_end, first);
  1694.   } else if (len1 <= buffer_size) {
  1695.     buffer_end = copy(first, middle, buffer);
  1696.     copy(middle, last, first);
  1697.     return copy_backward(buffer, buffer_end, last);
  1698.   } else  {
  1699.     rotate(first, middle, last);
  1700.     advance(first, len2);
  1701.     return first;
  1702.   }
  1703. }
  1704. template <class BidirectionalIterator1, class BidirectionalIterator2,
  1705.           class BidirectionalIterator3>
  1706. BidirectionalIterator3 __merge_backward(BidirectionalIterator1 first1,
  1707.                                         BidirectionalIterator1 last1,
  1708.                                         BidirectionalIterator2 first2,
  1709.                                         BidirectionalIterator2 last2,
  1710.                                         BidirectionalIterator3 result) {
  1711.   if (first1 == last1) return copy_backward(first2, last2, result);
  1712.   if (first2 == last2) return copy_backward(first1, last1, result);
  1713.   --last1;
  1714.   --last2;
  1715.   while (true) {
  1716.     if (*last2 < *last1) {
  1717.       *--result = *last1;
  1718.       if (first1 == last1) return copy_backward(first2, ++last2, result);
  1719.       --last1;
  1720.     }
  1721.     else {
  1722.       *--result = *last2;
  1723.       if (first2 == last2) return copy_backward(first1, ++last1, result);
  1724.       --last2;
  1725.     }
  1726.   }
  1727. }
  1728. template <class BidirectionalIterator1, class BidirectionalIterator2,
  1729.           class BidirectionalIterator3, class Compare>
  1730. BidirectionalIterator3 __merge_backward(BidirectionalIterator1 first1,
  1731.                                         BidirectionalIterator1 last1,
  1732.                                         BidirectionalIterator2 first2,
  1733.                                         BidirectionalIterator2 last2,
  1734.                                         BidirectionalIterator3 result,
  1735.                                         Compare comp) {
  1736.   if (first1 == last1) return copy_backward(first2, last2, result);
  1737.   if (first2 == last2) return copy_backward(first1, last1, result);
  1738.   --last1;
  1739.   --last2;
  1740.   while (true) {
  1741.     if (comp(*last2, *last1)) {
  1742.       *--result = *last1;
  1743.       if (first1 == last1) return copy_backward(first2, ++last2, result);
  1744.       --last1;
  1745.     }
  1746.     else {
  1747.       *--result = *last2;
  1748.       if (first2 == last2) return copy_backward(first1, ++last1, result);
  1749.       --last2;
  1750.     }
  1751.   }
  1752. }
  1753. template <class BidirectionalIterator, class Distance, class Pointer>
  1754. void __merge_adaptive(BidirectionalIterator first, 
  1755.                       BidirectionalIterator middle, 
  1756.                       BidirectionalIterator last, Distance len1, Distance len2,
  1757.                       Pointer buffer, Distance buffer_size) {
  1758.   if (len1 <= len2 && len1 <= buffer_size) {
  1759.     Pointer end_buffer = copy(first, middle, buffer);
  1760.     merge(buffer, end_buffer, middle, last, first);
  1761.   }
  1762.   else if (len2 <= buffer_size) {
  1763.     Pointer end_buffer = copy(middle, last, buffer);
  1764.     __merge_backward(first, middle, buffer, end_buffer, last);
  1765.   }
  1766.   else {
  1767.     BidirectionalIterator first_cut = first;
  1768.     BidirectionalIterator second_cut = middle;
  1769.     Distance len11 = 0;
  1770.     Distance len22 = 0;
  1771.     if (len1 > len2) {
  1772.       len11 = len1 / 2;
  1773.       advance(first_cut, len11);
  1774.       second_cut = lower_bound(middle, last, *first_cut);
  1775.       distance(middle, second_cut, len22);   
  1776.     }
  1777.     else {
  1778.       len22 = len2 / 2;
  1779.       advance(second_cut, len22);
  1780.       first_cut = upper_bound(first, middle, *second_cut);
  1781.       distance(first, first_cut, len11);
  1782.     }
  1783.     BidirectionalIterator new_middle =
  1784.       __rotate_adaptive(first_cut, middle, second_cut, len1 - len11,
  1785.                         len22, buffer, buffer_size);
  1786.     __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer,
  1787.                      buffer_size);
  1788.     __merge_adaptive(new_middle, second_cut, last, len1 - len11,
  1789.                      len2 - len22, buffer, buffer_size);
  1790.   }
  1791. }
  1792. template <class BidirectionalIterator, class Distance, class Pointer,
  1793.           class Compare>
  1794. void __merge_adaptive(BidirectionalIterator first, 
  1795.                       BidirectionalIterator middle, 
  1796.                       BidirectionalIterator last, Distance len1, Distance len2,
  1797.                       Pointer buffer, Distance buffer_size, Compare comp) {
  1798.   if (len1 <= len2 && len1 <= buffer_size) {
  1799.     Pointer end_buffer = copy(first, middle, buffer);
  1800.     merge(buffer, end_buffer, middle, last, first, comp);
  1801.   }
  1802.   else if (len2 <= buffer_size) {
  1803.     Pointer end_buffer = copy(middle, last, buffer);
  1804.     __merge_backward(first, middle, buffer, end_buffer, last, comp);
  1805.   }
  1806.   else {
  1807.     BidirectionalIterator first_cut = first;
  1808.     BidirectionalIterator second_cut = middle;
  1809.     Distance len11 = 0;
  1810.     Distance len22 = 0;
  1811.     if (len1 > len2) {
  1812.       len11 = len1 / 2;
  1813.       advance(first_cut, len11);
  1814.       second_cut = lower_bound(middle, last, *first_cut, comp);
  1815.       distance(middle, second_cut, len22);   
  1816.     }
  1817.     else {
  1818.       len22 = len2 / 2;
  1819.       advance(second_cut, len22);
  1820.       first_cut = upper_bound(first, middle, *second_cut, comp);
  1821.       distance(first, first_cut, len11);
  1822.     }
  1823.     BidirectionalIterator new_middle =
  1824.       __rotate_adaptive(first_cut, middle, second_cut, len1 - len11,
  1825.                         len22, buffer, buffer_size);
  1826.     __merge_adaptive(first, first_cut, new_middle, len11, len22, buffer,
  1827.                      buffer_size, comp);
  1828.     __merge_adaptive(new_middle, second_cut, last, len1 - len11,
  1829.                      len2 - len22, buffer, buffer_size, comp);
  1830.   }
  1831. }
  1832. template <class BidirectionalIterator, class T, class Distance>
  1833. inline void __inplace_merge_aux(BidirectionalIterator first,
  1834.                                 BidirectionalIterator middle,
  1835.                                 BidirectionalIterator last, T*, Distance*) {
  1836.   Distance len1 = 0;
  1837.   distance(first, middle, len1);
  1838.   Distance len2 = 0;
  1839.   distance(middle, last, len2);
  1840.   temporary_buffer<BidirectionalIterator, T> buf(first, last);
  1841.   if (buf.begin() == 0)
  1842.     __merge_without_buffer(first, middle, last, len1, len2);
  1843.   else
  1844.     __merge_adaptive(first, middle, last, len1, len2,
  1845.                      buf.begin(), Distance(buf.size()));
  1846. }
  1847. template <class BidirectionalIterator, class T, class Distance, class Compare>
  1848. inline void __inplace_merge_aux(BidirectionalIterator first,
  1849.                                 BidirectionalIterator middle,
  1850.                                 BidirectionalIterator last, T*, Distance*,
  1851.                                 Compare comp) {
  1852.   Distance len1 = 0;
  1853.   distance(first, middle, len1);
  1854.   Distance len2 = 0;
  1855.   distance(middle, last, len2);
  1856.   temporary_buffer<BidirectionalIterator, T> buf(first, last);
  1857.   if (buf.begin() == 0)
  1858.     __merge_without_buffer(first, middle, last, len1, len2, comp);
  1859.   else
  1860.     __merge_adaptive(first, middle, last, len1, len2,
  1861.                      buf.begin(), Distance(buf.size()),
  1862.                      comp);
  1863. }
  1864. template <class BidirectionalIterator>
  1865. inline void inplace_merge(BidirectionalIterator first,
  1866.                           BidirectionalIterator middle,
  1867.                           BidirectionalIterator last) {
  1868.   if (first == middle || middle == last) return;
  1869.   __inplace_merge_aux(first, middle, last, value_type(first),
  1870.                       distance_type(first));
  1871. }
  1872. template <class BidirectionalIterator, class Compare>
  1873. inline void inplace_merge(BidirectionalIterator first,
  1874.                           BidirectionalIterator middle,
  1875.                           BidirectionalIterator last, Compare comp) {
  1876.   if (first == middle || middle == last) return;
  1877.   __inplace_merge_aux(first, middle, last, value_type(first),
  1878.                       distance_type(first), comp);
  1879. }
  1880. template <class InputIterator1, class InputIterator2>
  1881. bool includes(InputIterator1 first1, InputIterator1 last1,
  1882.               InputIterator2 first2, InputIterator2 last2) {
  1883.   while (first1 != last1 && first2 != last2)
  1884.     if (*first2 < *first1)
  1885.       return false;
  1886.     else if(*first1 < *first2) 
  1887.       ++first1;
  1888.     else
  1889.       ++first1, ++first2;
  1890.   return first2 == last2;
  1891. }
  1892. template <class InputIterator1, class InputIterator2, class Compare>
  1893. bool includes(InputIterator1 first1, InputIterator1 last1,
  1894.               InputIterator2 first2, InputIterator2 last2, Compare comp) {
  1895.   while (first1 != last1 && first2 != last2)
  1896.     if (comp(*first2, *first1))
  1897.       return false;
  1898.     else if(comp(*first1, *first2)) 
  1899.       ++first1;
  1900.     else
  1901.       ++first1, ++first2;
  1902.   return first2 == last2;
  1903. }
  1904. template <class InputIterator1, class InputIterator2, class OutputIterator>
  1905. OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
  1906.                          InputIterator2 first2, InputIterator2 last2,
  1907.                          OutputIterator result) {
  1908.   while (first1 != last1 && first2 != last2) {
  1909.     if (*first1 < *first2) {
  1910.       *result = *first1;
  1911.       ++first1;
  1912.     }
  1913.     else if (*first2 < *first1) {
  1914.       *result = *first2;
  1915.       ++first2;
  1916.     }
  1917.     else {
  1918.       *result = *first1;
  1919.       ++first1;
  1920.       ++first2;
  1921.     }
  1922.     ++result;
  1923.   }
  1924.   return copy(first2, last2, copy(first1, last1, result));
  1925. }
  1926. template <class InputIterator1, class InputIterator2, class OutputIterator,
  1927.           class Compare>
  1928. OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
  1929.                          InputIterator2 first2, InputIterator2 last2,
  1930.                          OutputIterator result, Compare comp) {
  1931.   while (first1 != last1 && first2 != last2) {
  1932.     if (comp(*first1, *first2)) {
  1933.       *result = *first1;
  1934.       ++first1;
  1935.     }
  1936.     else if (comp(*first2, *first1)) {
  1937.       *result = *first2;
  1938.       ++first2;
  1939.     }
  1940.     else {
  1941.       *result = *first1;
  1942.       ++first1;
  1943.       ++first2;
  1944.     }
  1945.     ++result;
  1946.   }
  1947.   return copy(first2, last2, copy(first1, last1, result));
  1948. }
  1949. template <class InputIterator1, class InputIterator2, class OutputIterator>
  1950. OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
  1951.                                 InputIterator2 first2, InputIterator2 last2,
  1952.                                 OutputIterator result) {
  1953.   while (first1 != last1 && first2 != last2) 
  1954.     if (*first1 < *first2) 
  1955.       ++first1;
  1956.     else if (*first2 < *first1) 
  1957.       ++first2;
  1958.     else {
  1959.       *result = *first1;
  1960.       ++first1;
  1961.       ++first2;
  1962.       ++result;
  1963.     }
  1964.   return result;
  1965. }
  1966. template <class InputIterator1, class InputIterator2, class OutputIterator,
  1967.           class Compare>
  1968. OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
  1969.                                 InputIterator2 first2, InputIterator2 last2,
  1970.                                 OutputIterator result, Compare comp) {
  1971.   while (first1 != last1 && first2 != last2)
  1972.     if (comp(*first1, *first2))
  1973.       ++first1;
  1974.     else if (comp(*first2, *first1))
  1975.       ++first2;
  1976.     else {
  1977.       *result = *first1;
  1978.       ++first1;
  1979.       ++first2;
  1980.       ++result;
  1981.     }
  1982.   return result;
  1983. }
  1984. template <class InputIterator1, class InputIterator2, class OutputIterator>
  1985. OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
  1986.                               InputIterator2 first2, InputIterator2 last2,
  1987.                               OutputIterator result) {
  1988.   while (first1 != last1 && first2 != last2)
  1989.     if (*first1 < *first2) {
  1990.       *result = *first1;
  1991.       ++first1;
  1992.       ++result;
  1993.     }
  1994.     else if (*first2 < *first1)
  1995.       ++first2;
  1996.     else {
  1997.       ++first1;
  1998.       ++first2;
  1999.     }
  2000.   return copy(first1, last1, result);
  2001. }
  2002. template <class InputIterator1, class InputIterator2, class OutputIterator, 
  2003.           class Compare>
  2004. OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
  2005.                               InputIterator2 first2, InputIterator2 last2, 
  2006.                               OutputIterator result, Compare comp) {
  2007.   while (first1 != last1 && first2 != last2)
  2008.     if (comp(*first1, *first2)) {
  2009.       *result = *first1;
  2010.       ++first1;
  2011.       ++result;
  2012.     }
  2013.     else if (comp(*first2, *first1))
  2014.       ++first2;
  2015.     else {
  2016.       ++first1;
  2017.       ++first2;
  2018.     }
  2019.   return copy(first1, last1, result);
  2020. }
  2021. template <class InputIterator1, class InputIterator2, class OutputIterator>
  2022. OutputIterator set_symmetric_difference(InputIterator1 first1,
  2023.                                         InputIterator1 last1,
  2024.                                         InputIterator2 first2,
  2025.                                         InputIterator2 last2,
  2026.                                         OutputIterator result) {
  2027.   while (first1 != last1 && first2 != last2)
  2028.     if (*first1 < *first2) {
  2029.       *result = *first1;
  2030.       ++first1;
  2031.       ++result;
  2032.     }
  2033.     else if (*first2 < *first1) {
  2034.       *result = *first2;
  2035.       ++first2;
  2036.       ++result;
  2037.     }
  2038.     else {
  2039.       ++first1;
  2040.       ++first2;
  2041.     }
  2042.   return copy(first2, last2, copy(first1, last1, result));
  2043. }
  2044. template <class InputIterator1, class InputIterator2, class OutputIterator,
  2045.           class Compare>
  2046. OutputIterator set_symmetric_difference(InputIterator1 first1,
  2047.                                         InputIterator1 last1,
  2048.                                         InputIterator2 first2,
  2049.                                         InputIterator2 last2,
  2050.                                         OutputIterator result, Compare comp) {
  2051.   while (first1 != last1 && first2 != last2)
  2052.     if (comp(*first1, *first2)) {
  2053.       *result = *first1;
  2054.       ++first1;
  2055.       ++result;
  2056.     }
  2057.     else if (comp(*first2, *first1)) {
  2058.       *result = *first2;
  2059.       ++first2;
  2060.       ++result;
  2061.     }
  2062.     else {
  2063.       ++first1;
  2064.       ++first2;
  2065.     }
  2066.   return copy(first2, last2, copy(first1, last1, result));
  2067. }
  2068. template <class ForwardIterator>
  2069. ForwardIterator max_element(ForwardIterator first, ForwardIterator last) {
  2070.   if (first == last) return first;
  2071.   ForwardIterator result = first;
  2072.   while (++first != last) 
  2073.     if (*result < *first) result = first;
  2074.   return result;
  2075. }
  2076. template <class ForwardIterator, class Compare>
  2077. ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
  2078.                             Compare comp) {
  2079.   if (first == last) return first;
  2080.   ForwardIterator result = first;
  2081.   while (++first != last) 
  2082.     if (comp(*result, *first)) result = first;
  2083.   return result;
  2084. }
  2085. template <class ForwardIterator>
  2086. ForwardIterator min_element(ForwardIterator first, ForwardIterator last) {
  2087.   if (first == last) return first;
  2088.   ForwardIterator result = first;
  2089.   while (++first != last) 
  2090.     if (*first < *result) result = first;
  2091.   return result;
  2092. }
  2093. template <class ForwardIterator, class Compare>
  2094. ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
  2095.                             Compare comp) {
  2096.   if (first == last) return first;
  2097.   ForwardIterator result = first;
  2098.   while (++first != last) 
  2099.     if (comp(*first, *result)) result = first;
  2100.   return result;
  2101. }
  2102. template <class BidirectionalIterator>
  2103. bool next_permutation(BidirectionalIterator first,
  2104.                       BidirectionalIterator last) {
  2105.   if (first == last) return false;
  2106.   BidirectionalIterator i = first;
  2107.   ++i;
  2108.   if (i == last) return false;
  2109.   i = last;
  2110.   --i;
  2111.   for(;;) {
  2112.     BidirectionalIterator ii = i;
  2113.     --i;
  2114.     if (*i < *ii) {
  2115.       BidirectionalIterator j = last;
  2116.       while (!(*i < *--j));
  2117.       iter_swap(i, j);
  2118.       reverse(ii, last);
  2119.       return true;
  2120.     }
  2121.     if (i == first) {
  2122.       reverse(first, last);
  2123.       return false;
  2124.     }
  2125.   }
  2126. }
  2127. template <class BidirectionalIterator, class Compare>
  2128. bool next_permutation(BidirectionalIterator first, BidirectionalIterator last,
  2129.                       Compare comp) {
  2130.   if (first == last) return false;
  2131.   BidirectionalIterator i = first;
  2132.   ++i;
  2133.   if (i == last) return false;
  2134.   i = last;
  2135.   --i;
  2136.   for(;;) {
  2137.     BidirectionalIterator ii = i;
  2138.     --i;
  2139.     if (comp(*i, *ii)) {
  2140.       BidirectionalIterator j = last;
  2141.       while (!comp(*i, *--j));
  2142.       iter_swap(i, j);
  2143.       reverse(ii, last);
  2144.       return true;
  2145.     }
  2146.     if (i == first) {
  2147.       reverse(first, last);
  2148.       return false;
  2149.     }
  2150.   }
  2151. }
  2152. template <class BidirectionalIterator>
  2153. bool prev_permutation(BidirectionalIterator first,
  2154.                       BidirectionalIterator last) {
  2155.   if (first == last) return false;
  2156.   BidirectionalIterator i = first;
  2157.   ++i;
  2158.   if (i == last) return false;
  2159.   i = last;
  2160.   --i;
  2161.   for(;;) {
  2162.     BidirectionalIterator ii = i;
  2163.     --i;
  2164.     if (*ii < *i) {
  2165.       BidirectionalIterator j = last;
  2166.       while (!(*--j < *i));
  2167.       iter_swap(i, j);
  2168.       reverse(ii, last);
  2169.       return true;
  2170.     }
  2171.     if (i == first) {
  2172.       reverse(first, last);
  2173.       return false;
  2174.     }
  2175.   }
  2176. }
  2177. template <class BidirectionalIterator, class Compare>
  2178. bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last,
  2179.                       Compare comp) {
  2180.   if (first == last) return false;
  2181.   BidirectionalIterator i = first;
  2182.   ++i;
  2183.   if (i == last) return false;
  2184.   i = last;
  2185.   --i;
  2186.   for(;;) {
  2187.     BidirectionalIterator ii = i;
  2188.     --i;
  2189.     if (comp(*ii, *i)) {
  2190.       BidirectionalIterator j = last;
  2191.       while (!comp(*--j, *i));
  2192.       iter_swap(i, j);
  2193.       reverse(ii, last);
  2194.       return true;
  2195.     }
  2196.     if (i == first) {
  2197.       reverse(first, last);
  2198.       return false;
  2199.     }
  2200.   }
  2201. }
  2202. template <class InputIterator, class ForwardIterator>
  2203. InputIterator find_first_of(InputIterator first1, InputIterator last1,
  2204.                             ForwardIterator first2, ForwardIterator last2)
  2205. {
  2206.   for ( ; first1 != last1; ++first1) 
  2207.     for (ForwardIterator iter = first2; iter != last2; ++iter)
  2208.       if (*first1 == *iter)
  2209.         return first1;
  2210.   return last1;
  2211. }
  2212. template <class InputIterator, class ForwardIterator, class BinaryPredicate>
  2213. InputIterator find_first_of(InputIterator first1, InputIterator last1,
  2214.                             ForwardIterator first2, ForwardIterator last2,
  2215.                             BinaryPredicate comp)
  2216. {
  2217.   for ( ; first1 != last1; ++first1) 
  2218.     for (ForwardIterator iter = first2; iter != last2; ++iter)
  2219.       if (comp(*first1, *iter))
  2220.         return first1;
  2221.   return last1;
  2222. }
  2223. // Search [first2, last2) as a subsequence in [first1, last1).
  2224. // find_end for forward iterators. 
  2225. template <class ForwardIterator1, class ForwardIterator2>
  2226. ForwardIterator1 __find_end(ForwardIterator1 first1, ForwardIterator1 last1,
  2227.                             ForwardIterator2 first2, ForwardIterator2 last2,
  2228.                             forward_iterator_tag, forward_iterator_tag)
  2229. {
  2230.   if (first2 == last2)
  2231.     return last1;
  2232.   else {
  2233.     ForwardIterator1 result = last1;
  2234.     while (1) {
  2235.       ForwardIterator1 new_result = search(first1, last1, first2, last2);
  2236.       if (new_result == last1)
  2237.         return result;
  2238.       else {
  2239.         result = new_result;
  2240.         first1 = new_result;
  2241.         ++first1;
  2242.       }
  2243.     }
  2244.   }
  2245. }
  2246. template <class ForwardIterator1, class ForwardIterator2,
  2247.           class BinaryPredicate>
  2248. ForwardIterator1 __find_end(ForwardIterator1 first1, ForwardIterator1 last1,
  2249.                             ForwardIterator2 first2, ForwardIterator2 last2,
  2250.                             forward_iterator_tag, forward_iterator_tag,
  2251.                             BinaryPredicate comp)
  2252. {
  2253.   if (first2 == last2)
  2254.     return last1;
  2255.   else {
  2256.     ForwardIterator1 result = last1;
  2257.     while (1) {
  2258.       ForwardIterator1 new_result = search(first1, last1, first2, last2, comp);
  2259.       if (new_result == last1)
  2260.         return result;
  2261.       else {
  2262.         result = new_result;
  2263.         first1 = new_result;
  2264.         ++first1;
  2265.       }
  2266.     }
  2267.   }
  2268. }
  2269. // find_end for bidirectional iterators.  Requires partial specialization.
  2270. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  2271. template <class BidirectionalIterator1, class BidirectionalIterator2>
  2272. BidirectionalIterator1
  2273. __find_end(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
  2274.            BidirectionalIterator2 first2, BidirectionalIterator2 last2,
  2275.            bidirectional_iterator_tag, bidirectional_iterator_tag)
  2276. {
  2277.   typedef reverse_iterator<BidirectionalIterator1> reviter1;
  2278.   typedef reverse_iterator<BidirectionalIterator2> reviter2;
  2279.   reviter1 rlast1(first1);
  2280.   reviter2 rlast2(first2);
  2281.   reviter1 rresult = search(reviter1(last1), rlast1, reviter2(last2), rlast2);
  2282.   if (rresult == rlast1)
  2283.     return last1;
  2284.   else {
  2285.     BidirectionalIterator1 result = rresult.base();
  2286.     advance(result, -distance(first2, last2));
  2287.     return result;
  2288.   }
  2289. }
  2290. template <class BidirectionalIterator1, class BidirectionalIterator2,
  2291.           class BinaryPredicate>
  2292. BidirectionalIterator1
  2293. __find_end(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
  2294.            BidirectionalIterator2 first2, BidirectionalIterator2 last2,
  2295.            bidirectional_iterator_tag, bidirectional_iterator_tag, 
  2296.            BinaryPredicate comp)
  2297. {
  2298.   typedef reverse_iterator<BidirectionalIterator1> reviter1;
  2299.   typedef reverse_iterator<BidirectionalIterator2> reviter2;
  2300.   reviter1 rlast1(first1);
  2301.   reviter2 rlast2(first2);
  2302.   reviter1 rresult = search(reviter1(last1), rlast1, reviter2(last2), rlast2,
  2303.                             comp);
  2304.   if (rresult == rlast1)
  2305.     return last1;
  2306.   else {
  2307.     BidirectionalIterator1 result = rresult.base();
  2308.     advance(result, -distance(first2, last2));
  2309.     return result;
  2310.   }
  2311. }
  2312. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  2313. // Dispatching functions.
  2314. template <class ForwardIterator1, class ForwardIterator2>
  2315. inline ForwardIterator1 
  2316. find_end(ForwardIterator1 first1, ForwardIterator1 last1, 
  2317.          ForwardIterator2 first2, ForwardIterator2 last2)
  2318. {
  2319. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  2320.   typedef typename iterator_traits<ForwardIterator1>::iterator_category
  2321.           category1;
  2322.   typedef typename iterator_traits<ForwardIterator2>::iterator_category
  2323.           category2;
  2324.   return __find_end(first1, last1, first2, last2, category1(), category2());
  2325. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  2326.   return __find_end(first1, last1, first2, last2,
  2327.                     forward_iterator_tag(), forward_iterator_tag());
  2328. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  2329. }
  2330. template <class ForwardIterator1, class ForwardIterator2, 
  2331.           class BinaryPredicate>
  2332. inline ForwardIterator1 
  2333. find_end(ForwardIterator1 first1, ForwardIterator1 last1, 
  2334.          ForwardIterator2 first2, ForwardIterator2 last2,
  2335.          BinaryPredicate comp)
  2336. {
  2337. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  2338.   typedef typename iterator_traits<ForwardIterator1>::iterator_category
  2339.           category1;
  2340.   typedef typename iterator_traits<ForwardIterator2>::iterator_category
  2341.           category2;
  2342.   return __find_end(first1, last1, first2, last2, category1(), category2(),
  2343.                     comp);
  2344. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  2345.   return __find_end(first1, last1, first2, last2,
  2346.                     forward_iterator_tag(), forward_iterator_tag(),
  2347.                     comp);
  2348. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  2349. }
  2350. template <class RandomAccessIterator, class Distance>
  2351. bool __is_heap(RandomAccessIterator first, RandomAccessIterator last,
  2352.                Distance*)
  2353. {
  2354.   const Distance n = last - first;
  2355.   Distance parent = 0;
  2356.   for (Distance child = 1; child < n; ++child) {
  2357.     if (first[parent] < first[child]) 
  2358.       return false;
  2359.     if ((child & 1) == 0)
  2360.       ++parent;
  2361.   }
  2362.   return true;
  2363. }
  2364. template <class RandomAccessIterator>
  2365. inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last)
  2366. {
  2367.   return __is_heap(first, last, distance_type(first));
  2368. }
  2369. template <class RandomAccessIterator, class Distance, class StrictWeakOrdering>
  2370. bool __is_heap(RandomAccessIterator first, RandomAccessIterator last,
  2371.                StrictWeakOrdering comp,
  2372.                Distance*)
  2373. {
  2374.   const Distance n = last - first;
  2375.   Distance parent = 0;
  2376.   for (Distance child = 1; child < n; ++child) {
  2377.     if (comp(first[parent], first[child]))
  2378.       return false;
  2379.     if ((child & 1) == 0)
  2380.       ++parent;
  2381.   }
  2382.   return true;
  2383. }
  2384. template <class RandomAccessIterator, class StrictWeakOrdering>
  2385. inline bool is_heap(RandomAccessIterator first, RandomAccessIterator last,
  2386.                     StrictWeakOrdering comp)
  2387. {
  2388.   return __is_heap(first, last, comp, distance_type(first));
  2389. }
  2390. template <class ForwardIterator>
  2391. bool is_sorted(ForwardIterator first, ForwardIterator last)
  2392. {
  2393.   if (first == last)
  2394.     return true;
  2395.   ForwardIterator next = first;
  2396.   for (++next; next != last; first = next, ++next) {
  2397.     if (*next < *first)
  2398.       return false;
  2399.   }
  2400.   return true;
  2401. }
  2402. template <class ForwardIterator, class StrictWeakOrdering>
  2403. bool is_sorted(ForwardIterator first, ForwardIterator last,
  2404.                StrictWeakOrdering comp)
  2405. {
  2406.   if (first == last)
  2407.     return true;
  2408.   ForwardIterator next = first;
  2409.   for (++next; next != last; first = next, ++next) {
  2410.     if (comp(*next, *first))
  2411.       return false;
  2412.   }
  2413.   return true;
  2414. }
  2415. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  2416. #pragma reset woff 1209
  2417. #endif
  2418. __STL_END_NAMESPACE
  2419. #endif /* __SGI_STL_INTERNAL_ALGO_H */
  2420. // Local Variables:
  2421. // mode:C++
  2422. // End: