home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / libg++-2.7.1-bin.lha / lib / g++-include / algo.h < prev    next >
C/C++ Source or Header  |  1996-10-12  |  76KB  |  2,387 lines

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