home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _algo.c < prev    next >
C/C++ Source or Header  |  2002-02-02  |  61KB  |  1,766 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Copyright (c) 1996,1997
  7.  * Silicon Graphics Computer Systems, Inc.
  8.  *
  9.  * Copyright (c) 1997
  10.  * Moscow Center for SPARC Technology
  11.  *
  12.  * Copyright (c) 1999 
  13.  * Boris Fomitchev
  14.  *
  15.  * This material is provided "as is", with absolutely no warranty expressed
  16.  * or implied. Any use is at your own risk.
  17.  *
  18.  * Permission to use or copy this software for any purpose is hereby granted 
  19.  * without fee, provided the above notices are retained on all copies.
  20.  * Permission to modify the code and to distribute modified code is granted,
  21.  * provided the above notices are retained, and a notice that the code was
  22.  * modified is included with the above copyright notice.
  23.  *
  24.  */
  25.  
  26. #ifndef _STLP_ALGO_C
  27. # define _STLP_ALGO_C
  28.  
  29. # if !defined (_STLP_INTERNAL_ALGO_H)
  30. #  include <stl/_algo.h>
  31. # endif
  32.  
  33. _STLP_BEGIN_NAMESPACE
  34.  
  35. template <class _BidirectionalIter, class _Distance, class _Compare>
  36. void __merge_without_buffer(_BidirectionalIter __first,
  37.                             _BidirectionalIter __middle,
  38.                             _BidirectionalIter __last,
  39.                             _Distance __len1, _Distance __len2,
  40.                             _Compare __comp);
  41.  
  42.  
  43. template <class _BidirectionalIter1, class _BidirectionalIter2,
  44.           class _BidirectionalIter3, class _Compare>
  45. _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
  46.                                      _BidirectionalIter1 __last1,
  47.                                      _BidirectionalIter2 __first2,
  48.                                      _BidirectionalIter2 __last2,
  49.                                      _BidirectionalIter3 __result,
  50.                                      _Compare __comp);
  51.  
  52. template <class _Tp>
  53. # if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
  54. inline 
  55. # endif
  56. const _Tp& __median(const _Tp& __a, const _Tp& __b, const _Tp& __c) {
  57.   if (__a < __b)
  58.     if (__b < __c)
  59.       return __b;
  60.     else if (__a < __c)
  61.       return __c;
  62.     else
  63.       return __a;
  64.   else if (__a < __c)
  65.     return __a;
  66.   else if (__b < __c)
  67.     return __c;
  68.   else
  69.     return __b;
  70. }
  71.  
  72. template <class _Tp, class _Compare>
  73. # if !(defined (__SUNPRO_CC) && (__SUNPRO_CC < 0x420 ))
  74. inline 
  75. # endif
  76. const _Tp&
  77. __median(const _Tp& __a, const _Tp& __b, const _Tp& __c, _Compare __comp) {
  78.   if (__comp(__a, __b))
  79.     if (__comp(__b, __c))
  80.       return __b;
  81.     else if (__comp(__a, __c))
  82.       return __c;
  83.     else
  84.       return __a;
  85.   else if (__comp(__a, __c))
  86.     return __a;
  87.   else if (__comp(__b, __c))
  88.     return __c;
  89.   else
  90.     return __b;
  91. }
  92.  
  93. template <class _ForwardIter1, class _ForwardIter2>
  94. _ForwardIter1 search(_ForwardIter1 __first1, _ForwardIter1 __last1,
  95.                      _ForwardIter2 __first2, _ForwardIter2 __last2) 
  96. {
  97.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  98.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  99.   // Test for empty ranges
  100.   if (__first1 == __last1 || __first2 == __last2)
  101.     return __first1;
  102.  
  103.   // Test for a pattern of length 1.
  104.   _ForwardIter2 __tmp(__first2);
  105.   ++__tmp;
  106.   if (__tmp == __last2)
  107.     return find(__first1, __last1, *__first2);
  108.  
  109.   // General case.
  110.   _ForwardIter2 __p1 = __first2; 
  111.   ++__p1;
  112.  
  113.   _ForwardIter1 __current = __first1;
  114.  
  115.   while (__first1 != __last1) {
  116.     __first1 = find(__first1, __last1, *__first2);
  117.     if (__first1 == __last1)
  118.       return __last1;
  119.  
  120.     _ForwardIter2 __p = __p1;
  121.     __current = __first1; 
  122.     if (++__current == __last1)
  123.       return __last1;
  124.  
  125.     while (*__current == *__p) {
  126.       if (++__p == __last2)
  127.         return __first1;
  128.       if (++__current == __last1)
  129.         return __last1;
  130.     }
  131.  
  132.     ++__first1;
  133.   }
  134.   return __first1;
  135. }
  136.  
  137. // search_n.  Search for __count consecutive copies of __val.
  138.  
  139. template <class _ForwardIter, class _Integer, class _Tp>
  140. _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
  141.                       _Integer __count, const _Tp& __val) {
  142.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  143.   if (__count <= 0)
  144.     return __first;
  145.   else {
  146.     __first = find(__first, __last, __val);
  147.     while (__first != __last) {
  148.       _Integer __n = __count - 1;
  149.       _ForwardIter __i = __first;
  150.       ++__i;
  151.       while (__i != __last && __n != 0 && *__i == __val) {
  152.         ++__i;
  153.         --__n;
  154.       }
  155.       if (__n == 0)
  156.         return __first;
  157.       else
  158.         __first = find(__i, __last, __val);
  159.     }
  160.     return __last;
  161.   }
  162. }
  163.  
  164. template <class _ForwardIter, class _Integer, class _Tp, class _BinaryPred>
  165. _ForwardIter search_n(_ForwardIter __first, _ForwardIter __last,
  166.                       _Integer __count, const _Tp& __val,
  167.                       _BinaryPred __binary_pred) {
  168.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  169.   if (__count <= 0)
  170.     return __first;
  171.   else {
  172.     while (__first != __last) {
  173.       if (__binary_pred(*__first, __val))
  174.         break;
  175.       ++__first;
  176.     }
  177.     while (__first != __last) {
  178.       _Integer __n = __count - 1;
  179.       _ForwardIter __i = __first;
  180.       ++__i;
  181.       while (__i != __last && __n != 0 && __binary_pred(*__i, __val)) {
  182.         ++__i;
  183.         --__n;
  184.       }
  185.       if (__n == 0)
  186.         return __first;
  187.       else {
  188.         while (__i != __last) {
  189.           if (__binary_pred(*__i, __val))
  190.             break;
  191.           ++__i;
  192.         }
  193.         __first = __i;
  194.       }
  195.     }
  196.     return __last;
  197.   }
  198. } 
  199.  
  200. template <class _ForwardIter1, class _ForwardIter2>
  201. _ForwardIter1 
  202. find_end(_ForwardIter1 __first1, _ForwardIter1 __last1, 
  203.          _ForwardIter2 __first2, _ForwardIter2 __last2)
  204. {
  205.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  206.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  207.   return __find_end(__first1, __last1, __first2, __last2,
  208. # if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
  209.                     _STLP_ITERATOR_CATEGORY(__first1, _ForwardIter1),
  210.                     _STLP_ITERATOR_CATEGORY(__first2, _ForwardIter2),
  211. # else
  212.             forward_iterator_tag(),
  213.                     forward_iterator_tag(),
  214. # endif
  215.                     __equal_to(_STLP_VALUE_TYPE(__first1, _ForwardIter1))
  216.     );
  217. }
  218.  
  219. // unique and unique_copy
  220. template <class _InputIterator, class _OutputIterator, class _BinaryPredicate,
  221.                         class _Tp>
  222. _STLP_INLINE_LOOP _OutputIterator 
  223. __unique_copy(_InputIterator __first, _InputIterator __last,
  224.               _OutputIterator __result,
  225.               _BinaryPredicate __binary_pred, _Tp*) {
  226.   _Tp __val = *__first;
  227.   *__result = __val;
  228.   while (++__first != __last)
  229.     if (!__binary_pred(__val, *__first)) {
  230.       __val = *__first;
  231.       *++__result = __val;
  232.     }
  233.   return ++__result;
  234. }
  235.  
  236. template <class _InputIter, class _OutputIter, class _BinaryPredicate>
  237. inline _OutputIter 
  238. __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
  239.               _BinaryPredicate __binary_pred, const output_iterator_tag &) {
  240.   return __unique_copy(__first, __last, __result, __binary_pred, _STLP_VALUE_TYPE(__first, _InputIter));
  241. }
  242.  
  243. template <class _InputIter, class _ForwardIter, class _BinaryPredicate>
  244. _STLP_INLINE_LOOP _ForwardIter 
  245. __unique_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, 
  246.               _BinaryPredicate __binary_pred, const forward_iterator_tag &) {
  247.   *__result = *__first;
  248.   while (++__first != __last)
  249.     if (!__binary_pred(*__result, *__first)) *++__result = *__first;
  250.   return ++__result;
  251. }
  252.  
  253. # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
  254. template <class _InputIterator, class _BidirectionalIterator, class _BinaryPredicate>
  255. inline _BidirectionalIterator 
  256. __unique_copy(_InputIterator __first, _InputIterator __last,
  257.               _BidirectionalIterator __result, _BinaryPredicate __binary_pred,
  258.               const bidirectional_iterator_tag &) {
  259.   return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
  260. }
  261.  
  262. template <class _InputIterator, class _RandomAccessIterator, class _BinaryPredicate>
  263. inline _RandomAccessIterator 
  264. __unique_copy(_InputIterator __first, _InputIterator __last,
  265.               _RandomAccessIterator __result, _BinaryPredicate __binary_pred,
  266.               const random_access_iterator_tag &) {
  267.   return __unique_copy(__first, __last, __result, __binary_pred, forward_iterator_tag());
  268. }
  269. # endif /* _STLP_NONTEMPL_BASE_MATCH_BUG */
  270.  
  271.  
  272. template <class _InputIter, class _OutputIter>
  273. _OutputIter 
  274. unique_copy(_InputIter __first, _InputIter __last, _OutputIter __result) {
  275.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  276.   if (__first == __last) return __result;
  277.   return __unique_copy(__first, __last, __result, __equal_to(_STLP_VALUE_TYPE(__first, _InputIter)),
  278.                        _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
  279. }
  280.  
  281. template <class _InputIter, class _OutputIter, class _BinaryPredicate>
  282. _OutputIter 
  283. unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result,
  284.             _BinaryPredicate __binary_pred) {
  285.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  286.   if (__first == __last) return __result;
  287.   return __unique_copy(__first, __last, __result, __binary_pred,
  288.                        _STLP_ITERATOR_CATEGORY(__result, _OutputIter));
  289. }
  290.  
  291. // rotate and rotate_copy, and their auxiliary functions
  292.  
  293. template <class _ForwardIter, class _Distance>
  294. _ForwardIter __rotate(_ForwardIter __first,
  295.                       _ForwardIter __middle,
  296.                       _ForwardIter __last,
  297.                       _Distance*,
  298.                       const forward_iterator_tag &) {
  299.   if (__first == __middle)
  300.     return __last;
  301.   if (__last  == __middle)
  302.     return __first;
  303.  
  304.   _ForwardIter __first2 = __middle;
  305.   do {
  306.     swap(*__first++, *__first2++);
  307.     if (__first == __middle)
  308.       __middle = __first2;
  309.   } while (__first2 != __last);
  310.  
  311.   _ForwardIter __new_middle = __first;
  312.  
  313.   __first2 = __middle;
  314.  
  315.   while (__first2 != __last) {
  316.     swap (*__first++, *__first2++);
  317.     if (__first == __middle)
  318.       __middle = __first2;
  319.     else if (__first2 == __last)
  320.       __first2 = __middle;
  321.   }
  322.  
  323.   return __new_middle;
  324. }
  325.  
  326. template <class _BidirectionalIter, class _Distance>
  327. _BidirectionalIter __rotate(_BidirectionalIter __first,
  328.                             _BidirectionalIter __middle,
  329.                             _BidirectionalIter __last,
  330.                             _Distance*,
  331.                             const bidirectional_iterator_tag &) {
  332.   if (__first == __middle)
  333.     return __last;
  334.   if (__last  == __middle)
  335.     return __first;
  336.  
  337.   __reverse(__first,  __middle, bidirectional_iterator_tag());
  338.   __reverse(__middle, __last,   bidirectional_iterator_tag());
  339.  
  340.   while (__first != __middle && __middle != __last)
  341.     swap (*__first++, *--__last);
  342.  
  343.   if (__first == __middle) {
  344.     __reverse(__middle, __last,   bidirectional_iterator_tag());
  345.     return __last;
  346.   }
  347.   else {
  348.     __reverse(__first,  __middle, bidirectional_iterator_tag());
  349.     return __first;
  350.   }
  351. }
  352.  
  353. template <class _RandomAccessIter, class _Distance, class _Tp>
  354. _RandomAccessIter __rotate(_RandomAccessIter __first,
  355.                            _RandomAccessIter __middle,
  356.                            _RandomAccessIter __last,
  357.                            _Distance *, _Tp *) {
  358.  
  359.   _Distance __n = __last   - __first;
  360.   _Distance __k = __middle - __first;
  361.   _Distance __l = __n - __k;
  362.   _RandomAccessIter __result = __first + (__last - __middle);
  363.  
  364.   if (__k==0)  /* __first == middle */
  365.     return __last;
  366.  
  367.   if (__k == __l) {
  368.     swap_ranges(__first, __middle, __middle);
  369.     return __result;
  370.   }
  371.  
  372.   _Distance __d = __gcd(__n, __k);
  373.  
  374.   for (_Distance __i = 0; __i < __d; __i++) {
  375.     _Tp __tmp = *__first;
  376.     _RandomAccessIter __p = __first;
  377.  
  378.     if (__k < __l) {
  379.       for (_Distance __j = 0; __j < __l/__d; __j++) {
  380.     if (__p > __first + __l) {
  381.           *__p = *(__p - __l);
  382.           __p -= __l;
  383.         }
  384.  
  385.         *__p = *(__p + __k);
  386.         __p += __k;
  387.       }
  388.     }
  389.  
  390.     else {
  391.       for (_Distance __j = 0; __j < __k/__d - 1; __j ++) {
  392.         if (__p < __last - __k) {
  393.           *__p = *(__p + __k);
  394.           __p += __k;
  395.         }
  396.  
  397.         *__p = * (__p - __l);
  398.         __p -= __l;
  399.       }
  400.     }
  401.  
  402.     *__p = __tmp;
  403.     ++__first;
  404.   }
  405.  
  406.   return __result;
  407. }
  408.  
  409. template <class _RandomAccessIter, class _Distance>
  410. inline _RandomAccessIter 
  411. __rotate(_RandomAccessIter __first, _RandomAccessIter __middle, _RandomAccessIter __last,
  412.          _Distance * __dis, const random_access_iterator_tag &) {
  413.   return __rotate(__first, __middle, __last,
  414.                   __dis, _STLP_VALUE_TYPE(__first, _RandomAccessIter));
  415. }
  416.  
  417. template <class _ForwardIter>
  418. _ForwardIter 
  419. rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last) {
  420.   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
  421.   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
  422.   return __rotate(__first, __middle, __last,
  423.                   _STLP_DISTANCE_TYPE(__first, _ForwardIter),
  424.                   _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
  425. }
  426.  
  427. // Return a random number in the range [0, __n).  This function encapsulates
  428. // whether we're using rand (part of the standard C library) or lrand48
  429. // (not standard, but a much better choice whenever it's available).
  430.  
  431. template <class _Distance>
  432. inline _Distance __random_number(_Distance __n) {
  433. #ifdef _STLP_NO_DRAND48
  434.   return rand() % __n;
  435. #else
  436.   return lrand48() % __n;
  437. #endif
  438. }
  439.  
  440. template <class _RandomAccessIter>
  441. void random_shuffle(_RandomAccessIter __first,
  442.             _RandomAccessIter __last) {
  443.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  444.   if (__first == __last) return;
  445.   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  446.     iter_swap(__i, __first + __random_number((__i - __first) + 1));
  447. }
  448.  
  449. template <class _RandomAccessIter, class _RandomNumberGenerator>
  450. void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
  451.                     _RandomNumberGenerator& __rand) {
  452.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  453.   if (__first == __last) return;
  454.   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  455.     iter_swap(__i, __first + __rand((__i - __first) + 1));
  456. }
  457.  
  458. # ifndef _STLP_NO_EXTENSIONS
  459.  
  460. // random_sample and random_sample_n (extensions, not part of the standard).
  461.  
  462. template <class _ForwardIter, class _OutputIter, class _Distance>
  463. _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
  464.                             _OutputIter __out, const _Distance __n)
  465. {
  466.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  467.   _Distance __remaining = distance(__first, __last);
  468.   _Distance __m = (min) (__n, __remaining);
  469.  
  470.   while (__m > 0) {
  471.     if (__random_number(__remaining) < __m) {
  472.       *__out = *__first;
  473.       ++__out;
  474.       --__m;
  475.     }
  476.  
  477.     --__remaining;
  478.     ++__first;
  479.   }
  480.   return __out;
  481. }
  482.  
  483.  
  484. template <class _ForwardIter, class _OutputIter, class _Distance,
  485.           class _RandomNumberGenerator>
  486. _OutputIter random_sample_n(_ForwardIter __first, _ForwardIter __last,
  487.                             _OutputIter __out, const _Distance __n,
  488.                             _RandomNumberGenerator& __rand)
  489. {
  490.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  491.   _Distance __remaining = distance(__first, __last);
  492.   _Distance __m = (min) (__n, __remaining);
  493.  
  494.   while (__m > 0) {
  495.     if (__rand(__remaining) < __m) {
  496.       *__out = *__first;
  497.       ++__out;
  498.       --__m;
  499.     }
  500.  
  501.     --__remaining;
  502.     ++__first;
  503.   }
  504.   return __out;
  505. }
  506.  
  507. template <class _InputIter, class _RandomAccessIter, class _Distance>
  508. _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
  509.                                   _RandomAccessIter __out,
  510.                                   const _Distance __n)
  511. {
  512.   _Distance __m = 0;
  513.   _Distance __t = __n;
  514.   for ( ; __first != __last && __m < __n; ++__m, ++__first) 
  515.     __out[__m] = *__first;
  516.  
  517.   while (__first != __last) {
  518.     ++__t;
  519.     _Distance __M = __random_number(__t);
  520.     if (__M < __n)
  521.       __out[__M] = *__first;
  522.     ++__first;
  523.   }
  524.  
  525.   return __out + __m;
  526. }
  527.  
  528. template <class _InputIter, class _RandomAccessIter,
  529.           class _RandomNumberGenerator, class _Distance>
  530. _RandomAccessIter __random_sample(_InputIter __first, _InputIter __last,
  531.                                   _RandomAccessIter __out,
  532.                                   _RandomNumberGenerator& __rand,
  533.                                   const _Distance __n)
  534. {
  535.   _Distance __m = 0;
  536.   _Distance __t = __n;
  537.   for ( ; __first != __last && __m < __n; ++__m, ++__first)
  538.     __out[__m] = *__first;
  539.  
  540.   while (__first != __last) {
  541.     ++__t;
  542.     _Distance __M = __rand(__t);
  543.     if (__M < __n)
  544.       __out[__M] = *__first;
  545.     ++__first;
  546.   }
  547.  
  548.   return __out + __m;
  549. }
  550.  
  551. template <class _InputIter, class _RandomAccessIter>
  552. _RandomAccessIter
  553. random_sample(_InputIter __first, _InputIter __last,
  554.               _RandomAccessIter __out_first, _RandomAccessIter __out_last) 
  555. {
  556.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  557.   _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last))
  558.   return __random_sample(__first, __last,
  559.                          __out_first, __out_last - __out_first);
  560. }
  561.  
  562. template <class _InputIter, class _RandomAccessIter, class _RandomNumberGenerator>
  563. _RandomAccessIter
  564. random_sample(_InputIter __first, _InputIter __last,
  565.               _RandomAccessIter __out_first, _RandomAccessIter __out_last,
  566.               _RandomNumberGenerator& __rand) 
  567. {
  568.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  569.   _STLP_DEBUG_CHECK(__check_range(__out_first, __out_last))
  570.   return __random_sample(__first, __last,
  571.                          __out_first, __rand,
  572.                          __out_last - __out_first);
  573. }
  574.  
  575. # endif /* _STLP_NO_EXTENSIONS */
  576.  
  577. // partition, stable_partition, and their auxiliary functions
  578.  
  579. template <class _ForwardIter, class _Predicate>
  580. _STLP_INLINE_LOOP _ForwardIter __partition(_ForwardIter __first,
  581.                                            _ForwardIter __last,
  582.                                            _Predicate   __pred,
  583.                                            const forward_iterator_tag &) {
  584.   if (__first == __last) return __first;
  585.  
  586.   while (__pred(*__first))
  587.     if (++__first == __last) return __first;
  588.  
  589.   _ForwardIter __next = __first;
  590.  
  591.   while (++__next != __last)
  592.     if (__pred(*__next)) {
  593.       swap(*__first, *__next);
  594.       ++__first;
  595.     }
  596.   return __first;
  597. }
  598.  
  599. template <class _BidirectionalIter, class _Predicate>
  600. _STLP_INLINE_LOOP _BidirectionalIter __partition(_BidirectionalIter __first,
  601.                                                  _BidirectionalIter __last,
  602.                                                  _Predicate __pred,
  603.                                                  const bidirectional_iterator_tag &) {
  604.   while (true) {
  605.     while (true)
  606.       if (__first == __last)
  607.         return __first;
  608.       else if (__pred(*__first))
  609.         ++__first;
  610.       else
  611.         break;
  612.     --__last;
  613.     while (true)
  614.       if (__first == __last)
  615.         return __first;
  616.       else if (!__pred(*__last))
  617.         --__last;
  618.       else
  619.         break;
  620.     iter_swap(__first, __last);
  621.     ++__first;
  622.   }
  623. }
  624.  
  625. # if defined (_STLP_NONTEMPL_BASE_MATCH_BUG)
  626. template <class _BidirectionalIter, class _Predicate>
  627. inline
  628. _BidirectionalIter __partition(_BidirectionalIter __first,
  629.                                _BidirectionalIter __last,
  630.                    _Predicate __pred,
  631.                    const random_access_iterator_tag &) {
  632.   return __partition(__first, __last, __pred, bidirectional_iterator_tag());
  633. }
  634. # endif
  635.  
  636. template <class _ForwardIter, class _Predicate>
  637. _ForwardIter partition(_ForwardIter __first, _ForwardIter __last, _Predicate   __pred) {
  638.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  639.   return __partition(__first, __last, __pred, _STLP_ITERATOR_CATEGORY(__first, _ForwardIter));
  640. }
  641.  
  642.  
  643. template <class _ForwardIter, class _Predicate, class _Distance>
  644. _ForwardIter __inplace_stable_partition(_ForwardIter __first,
  645.                                         _ForwardIter __last,
  646.                                         _Predicate __pred, _Distance __len) {
  647.   if (__len == 1)
  648.     return __pred(*__first) ? __last : __first;
  649.   _ForwardIter __middle = __first;
  650.   advance(__middle, __len / 2);
  651.   return rotate(__inplace_stable_partition(__first, __middle, __pred, 
  652.                                            __len / 2),
  653.                 __middle,
  654.                 __inplace_stable_partition(__middle, __last, __pred,
  655.                                            __len - __len / 2));
  656. }
  657.  
  658. template <class _ForwardIter, class _Pointer, class _Predicate, 
  659.           class _Distance>
  660. _ForwardIter __stable_partition_adaptive(_ForwardIter __first,
  661.                                          _ForwardIter __last,
  662.                                          _Predicate __pred, _Distance __len,
  663.                                          _Pointer __buffer,
  664.                                          _Distance __buffer_size) 
  665. {
  666.   if (__len <= __buffer_size) {
  667.     _ForwardIter __result1 = __first;
  668.     _Pointer __result2 = __buffer;
  669.     for ( ; __first != __last ; ++__first)
  670.       if (__pred(*__first)) {
  671.         *__result1 = *__first;
  672.         ++__result1;
  673.       }
  674.       else {
  675.         *__result2 = *__first;
  676.         ++__result2;
  677.       }
  678.     copy(__buffer, __result2, __result1);
  679.     return __result1;
  680.   }
  681.   else {
  682.     _ForwardIter __middle = __first;
  683.     advance(__middle, __len / 2);
  684.     return rotate(__stable_partition_adaptive(
  685.                           __first, __middle, __pred,
  686.                           __len / 2, __buffer, __buffer_size),
  687.                     __middle,
  688.                     __stable_partition_adaptive(
  689.                           __middle, __last, __pred,
  690.                           __len - __len / 2, __buffer, __buffer_size));
  691.   }
  692. }
  693.  
  694. template <class _ForwardIter, class _Predicate, class _Tp, class _Distance>
  695. inline _ForwardIter
  696. __stable_partition_aux(_ForwardIter __first, _ForwardIter __last, 
  697.                        _Predicate __pred, _Tp*, _Distance*)
  698. {
  699.   _Temporary_buffer<_ForwardIter, _Tp> __buf(__first, __last);
  700.   _STLP_MPWFIX_TRY        //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
  701.   return (__buf.size() > 0) ?
  702.     __stable_partition_adaptive(__first, __last, __pred,
  703.                 _Distance(__buf.requested_size()),
  704.                 __buf.begin(), __buf.size())  :
  705.     __inplace_stable_partition(__first, __last, __pred, 
  706.                    _Distance(__buf.requested_size()));
  707.   _STLP_MPWFIX_CATCH    //*TY 06/01/2000 - they forget to call dtor for _Temporary_buffer if no try/catch block is present
  708. }
  709.  
  710. template <class _ForwardIter, class _Predicate>
  711. _ForwardIter 
  712. stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred) {
  713.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  714.   if (__first == __last)
  715.     return __first;
  716.   else
  717.     return __stable_partition_aux(__first, __last, __pred,
  718.                                   _STLP_VALUE_TYPE(__first, _ForwardIter),
  719.                                   _STLP_DISTANCE_TYPE(__first, _ForwardIter));
  720. }
  721.  
  722. template <class _RandomAccessIter, class _Tp, class _Compare>
  723. _RandomAccessIter __unguarded_partition(_RandomAccessIter __first, 
  724.                                         _RandomAccessIter __last, 
  725.                                         _Tp __pivot, _Compare __comp) 
  726. {
  727.   while (true) {
  728.     while (__comp(*__first, __pivot))
  729.       ++__first;
  730.     --__last;
  731.     while (__comp(__pivot, *__last))
  732.       --__last;
  733.     if (!(__first < __last))
  734.       return __first;
  735.     iter_swap(__first, __last);
  736.     ++__first;
  737.   }
  738. }
  739.  
  740. // sort() and its auxiliary functions. 
  741.  
  742. # define  __stl_threshold  16
  743.  
  744. template <class _RandomAccessIter, class _Tp, class _Compare>
  745. void __unguarded_linear_insert(_RandomAccessIter __last, _Tp __val, 
  746.                                _Compare __comp) {
  747.   _RandomAccessIter __next = __last;
  748.   --__next;  
  749.   while (__comp(__val, *__next)) {
  750.     *__last = *__next;
  751.     __last = __next;
  752.     --__next;
  753.   }
  754.   *__last = __val;
  755. }
  756.  
  757. template <class _RandomAccessIter, class _Tp, class _Compare>
  758. inline void __linear_insert(_RandomAccessIter __first, 
  759.                             _RandomAccessIter __last, _Tp __val, _Compare __comp) {        
  760.   //*TY 12/26/1998 - added __val as a paramter
  761.   //  _Tp __val = *__last;            //*TY 12/26/1998 - __val supplied by caller
  762.   if (__comp(__val, *__first)) {
  763.     copy_backward(__first, __last, __last + 1);
  764.     *__first = __val;
  765.   }
  766.   else
  767.     __unguarded_linear_insert(__last, __val, __comp);
  768. }
  769.  
  770. template <class _RandomAccessIter, class _Compare>
  771. void __insertion_sort(_RandomAccessIter __first,
  772.                       _RandomAccessIter __last, _Compare __comp) {
  773.   if (__first == __last) return;
  774.   for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
  775.     __linear_insert(__first, __i, *__i, __comp);    //*TY 12/26/1998 - supply *__i as __val
  776. }
  777.  
  778. template <class _RandomAccessIter, class _Tp, class _Compare>
  779. void __unguarded_insertion_sort_aux(_RandomAccessIter __first, 
  780.                                     _RandomAccessIter __last,
  781.                                     _Tp*, _Compare __comp) {
  782.   for (_RandomAccessIter __i = __first; __i != __last; ++__i)
  783.     __unguarded_linear_insert(__i, _Tp(*__i), __comp);
  784. }
  785.  
  786. template <class _RandomAccessIter, class _Compare>
  787. inline void __unguarded_insertion_sort(_RandomAccessIter __first, 
  788.                                        _RandomAccessIter __last,
  789.                                        _Compare __comp) {
  790.   __unguarded_insertion_sort_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
  791. }
  792.  
  793. template <class _RandomAccessIter, class _Compare>
  794. void __final_insertion_sort(_RandomAccessIter __first, 
  795.                             _RandomAccessIter __last, _Compare __comp) {
  796.   if (__last - __first > __stl_threshold) {
  797.     __insertion_sort(__first, __first + __stl_threshold, __comp);
  798.     __unguarded_insertion_sort(__first + __stl_threshold, __last, __comp);
  799.   }
  800.   else
  801.     __insertion_sort(__first, __last, __comp);
  802. }
  803.  
  804. template <class _RandomAccessIter, class _Tp, class _Size, class _Compare>
  805. void __introsort_loop(_RandomAccessIter __first,
  806.                       _RandomAccessIter __last, _Tp*,
  807.                       _Size __depth_limit, _Compare __comp)
  808. {
  809.   while (__last - __first > __stl_threshold) {
  810.     if (__depth_limit == 0) {
  811.       partial_sort(__first, __last, __last, __comp);
  812.       return;
  813.     }
  814.     --__depth_limit;
  815.     _RandomAccessIter __cut =
  816.       __unguarded_partition(__first, __last,
  817.                             _Tp(__median(*__first,
  818.                                          *(__first + (__last - __first)/2),
  819.                                          *(__last - 1), __comp)),
  820.        __comp);
  821.     __introsort_loop(__cut, __last, (_Tp*) 0, __depth_limit, __comp);
  822.     __last = __cut;
  823.   }
  824. }
  825.  
  826. template <class _RandomAccessIter>
  827. void sort(_RandomAccessIter __first, _RandomAccessIter __last) {
  828.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  829.   if (__first != __last) {
  830.     __introsort_loop(__first, __last,
  831.                      _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  832.                      __lg(__last - __first) * 2, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)) );
  833.     __final_insertion_sort(__first, __last, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  834.   }
  835. }
  836.  
  837. template <class _RandomAccessIter, class _Compare>
  838. void sort(_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp) {
  839.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  840.   if (__first != __last) {
  841.     __introsort_loop(__first, __last,
  842.                      _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  843.                      __lg(__last - __first) * 2,
  844.                      __comp);
  845.     __final_insertion_sort(__first, __last, __comp);
  846.   }
  847. }
  848.  
  849. // stable_sort() and its auxiliary functions.
  850.  
  851. template <class _RandomAccessIter, class _Compare>
  852. void __inplace_stable_sort(_RandomAccessIter __first,
  853.                            _RandomAccessIter __last, _Compare __comp) {
  854.   if (__last - __first < 15) {
  855.     __insertion_sort(__first, __last, __comp);
  856.     return;
  857.   }
  858.   _RandomAccessIter __middle = __first + (__last - __first) / 2;
  859.   __inplace_stable_sort(__first, __middle, __comp);
  860.   __inplace_stable_sort(__middle, __last, __comp);
  861.   __merge_without_buffer(__first, __middle, __last,
  862.                          __middle - __first,
  863.                          __last - __middle,
  864.                          __comp);
  865. }
  866.  
  867. template <class _RandomAccessIter1, class _RandomAccessIter2,
  868.           class _Distance, class _Compare>
  869. void __merge_sort_loop(_RandomAccessIter1 __first,
  870.                        _RandomAccessIter1 __last, 
  871.                        _RandomAccessIter2 __result, _Distance __step_size,
  872.                        _Compare __comp) {
  873.   _Distance __two_step = 2 * __step_size;
  874.  
  875.   while (__last - __first >= __two_step) {
  876.     __result = merge(__first, __first + __step_size,
  877.                      __first + __step_size, __first + __two_step,
  878.                      __result,
  879.                      __comp);
  880.     __first += __two_step;
  881.   }
  882.   __step_size = (min) (_Distance(__last - __first), __step_size);
  883.  
  884.   merge(__first, __first + __step_size,
  885.         __first + __step_size, __last,
  886.         __result,
  887.         __comp);
  888. }
  889.  
  890. const int __stl_chunk_size = 7;
  891.         
  892. template <class _RandomAccessIter, class _Distance, class _Compare>
  893. void __chunk_insertion_sort(_RandomAccessIter __first, 
  894.                             _RandomAccessIter __last,
  895.                             _Distance __chunk_size, _Compare __comp)
  896. {
  897.   while (__last - __first >= __chunk_size) {
  898.     __insertion_sort(__first, __first + __chunk_size, __comp);
  899.     __first += __chunk_size;
  900.   }
  901.   __insertion_sort(__first, __last, __comp);
  902. }
  903.  
  904. template <class _RandomAccessIter, class _Pointer, class _Distance,
  905.           class _Compare>
  906. void __merge_sort_with_buffer(_RandomAccessIter __first, 
  907.                               _RandomAccessIter __last, _Pointer __buffer,
  908.                               _Distance*, _Compare __comp) {
  909.   _Distance __len = __last - __first;
  910.   _Pointer __buffer_last = __buffer + __len;
  911.  
  912.   _Distance __step_size = __stl_chunk_size;
  913.   __chunk_insertion_sort(__first, __last, __step_size, __comp);
  914.  
  915.   while (__step_size < __len) {
  916.     __merge_sort_loop(__first, __last, __buffer, __step_size, __comp);
  917.     __step_size *= 2;
  918.     __merge_sort_loop(__buffer, __buffer_last, __first, __step_size, __comp);
  919.     __step_size *= 2;
  920.   }
  921. }
  922.  
  923. template <class _BidirectionalIter1, class _BidirectionalIter2,
  924.           class _Distance>
  925. _BidirectionalIter1 __rotate_adaptive(_BidirectionalIter1 __first,
  926.                                       _BidirectionalIter1 __middle,
  927.                                       _BidirectionalIter1 __last,
  928.                                       _Distance __len1, _Distance __len2,
  929.                                       _BidirectionalIter2 __buffer,
  930.                                       _Distance __buffer_size) {
  931.   if (__len1 > __len2 && __len2 <= __buffer_size) {
  932.     _BidirectionalIter2 __buffer_end = copy(__middle, __last, __buffer);
  933.     copy_backward(__first, __middle, __last);
  934.     return copy(__buffer, __buffer_end, __first);
  935.   }
  936.   else if (__len1 <= __buffer_size) {
  937.     _BidirectionalIter2 __buffer_end = copy(__first, __middle, __buffer);
  938.     copy(__middle, __last, __first);
  939.     return copy_backward(__buffer, __buffer_end, __last);
  940.   }
  941.   else
  942.     return rotate(__first, __middle, __last);
  943. }
  944.  
  945. template <class _BidirectionalIter, class _Distance, class _Pointer,
  946.           class _Compare>
  947. void __merge_adaptive(_BidirectionalIter __first, 
  948.                       _BidirectionalIter __middle, 
  949.                       _BidirectionalIter __last,
  950.                       _Distance __len1, _Distance __len2,
  951.                       _Pointer __buffer, _Distance __buffer_size,
  952.                       _Compare __comp) {
  953.   if (__len1 <= __len2 && __len1 <= __buffer_size) {
  954.     _Pointer __buffer_end = copy(__first, __middle, __buffer);
  955.     merge(__buffer, __buffer_end, __middle, __last, __first, __comp);
  956.   }
  957.   else if (__len2 <= __buffer_size) {
  958.     _Pointer __buffer_end = copy(__middle, __last, __buffer);
  959.     __merge_backward(__first, __middle, __buffer, __buffer_end, __last,
  960.                      __comp);
  961.   }
  962.   else {
  963.     _BidirectionalIter __first_cut = __first;
  964.     _BidirectionalIter __second_cut = __middle;
  965.     _Distance __len11 = 0;
  966.     _Distance __len22 = 0;
  967.     if (__len1 > __len2) {
  968.       __len11 = __len1 / 2;
  969.       advance(__first_cut, __len11);
  970.       __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
  971.       __len22 += distance(__middle, __second_cut);   
  972.     }
  973.     else {
  974.       __len22 = __len2 / 2;
  975.       advance(__second_cut, __len22);
  976.       __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
  977.       __len11 += distance(__first, __first_cut);
  978.     }
  979.     _BidirectionalIter __new_middle =
  980.       __rotate_adaptive(__first_cut, __middle, __second_cut, __len1 - __len11,
  981.                         __len22, __buffer, __buffer_size);
  982.     __merge_adaptive(__first, __first_cut, __new_middle, __len11,
  983.                      __len22, __buffer, __buffer_size, __comp);
  984.     __merge_adaptive(__new_middle, __second_cut, __last, __len1 - __len11,
  985.                      __len2 - __len22, __buffer, __buffer_size, __comp);
  986.   }
  987. }
  988.  
  989. template <class _RandomAccessIter, class _Pointer, class _Distance, 
  990.           class _Compare>
  991. void __stable_sort_adaptive(_RandomAccessIter __first, 
  992.                             _RandomAccessIter __last, _Pointer __buffer,
  993.                             _Distance __buffer_size, _Compare __comp) {
  994.   _Distance __len = (__last - __first + 1) / 2;
  995.   _RandomAccessIter __middle = __first + __len;
  996.   if (__len > __buffer_size) {
  997.     __stable_sort_adaptive(__first, __middle, __buffer, __buffer_size, 
  998.                            __comp);
  999.     __stable_sort_adaptive(__middle, __last, __buffer, __buffer_size, 
  1000.                            __comp);
  1001.   }
  1002.   else {
  1003.     __merge_sort_with_buffer(__first, __middle, __buffer, (_Distance*)0,
  1004.                                __comp);
  1005.     __merge_sort_with_buffer(__middle, __last, __buffer, (_Distance*)0,
  1006.                                __comp);
  1007.   }
  1008.   __merge_adaptive(__first, __middle, __last, _Distance(__middle - __first), 
  1009.                    _Distance(__last - __middle), __buffer, __buffer_size,
  1010.                    __comp);
  1011. }
  1012.  
  1013. template <class _RandomAccessIter, class _Tp, class _Distance, class _Compare>
  1014. void __stable_sort_aux(_RandomAccessIter __first,
  1015.                   _RandomAccessIter __last, _Tp*, _Distance*,
  1016.                   _Compare __comp) {
  1017.   _Temporary_buffer<_RandomAccessIter, _Tp> buf(__first, __last);
  1018.   if (buf.begin() == 0)
  1019.     __inplace_stable_sort(__first, __last, __comp);
  1020.   else 
  1021.     __stable_sort_adaptive(__first, __last, buf.begin(),
  1022.                            _Distance(buf.size()),
  1023.                            __comp);
  1024. }
  1025.  
  1026. template <class _RandomAccessIter>
  1027. void stable_sort(_RandomAccessIter __first,
  1028.          _RandomAccessIter __last) {
  1029.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1030.   __stable_sort_aux(__first, __last,
  1031.                     _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1032.                     _STLP_DISTANCE_TYPE(__first, _RandomAccessIter),
  1033.                     __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  1034. }
  1035.  
  1036. template <class _RandomAccessIter, class _Compare>
  1037. void stable_sort(_RandomAccessIter __first,
  1038.          _RandomAccessIter __last, _Compare __comp) {
  1039.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1040.   __stable_sort_aux(__first, __last,
  1041.                     _STLP_VALUE_TYPE(__first, _RandomAccessIter),
  1042.                     _STLP_DISTANCE_TYPE(__first, _RandomAccessIter), 
  1043.                     __comp);
  1044. }
  1045.  
  1046. // partial_sort, partial_sort_copy, and auxiliary functions.
  1047.  
  1048. template <class _RandomAccessIter, class _Tp, class _Compare>
  1049. void __partial_sort(_RandomAccessIter __first, _RandomAccessIter __middle,
  1050.                     _RandomAccessIter __last, _Tp*, _Compare __comp) {
  1051.   make_heap(__first, __middle, __comp);
  1052.   for (_RandomAccessIter __i = __middle; __i < __last; ++__i)
  1053.     if (__comp(*__i, *__first))
  1054.       __pop_heap(__first, __middle, __i, _Tp(*__i), __comp,
  1055.                  _STLP_DISTANCE_TYPE(__first, _RandomAccessIter));
  1056.   sort_heap(__first, __middle, __comp);
  1057. }
  1058.  
  1059.  
  1060. template <class _RandomAccessIter>
  1061. void 
  1062. partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle, _RandomAccessIter __last) {
  1063.   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
  1064.   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
  1065.   __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), 
  1066.                  __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  1067. }
  1068.  
  1069. template <class _RandomAccessIter, class _Compare>
  1070. void partial_sort(_RandomAccessIter __first,_RandomAccessIter __middle,
  1071.                   _RandomAccessIter __last, _Compare __comp) {
  1072.   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
  1073.   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
  1074.   __partial_sort(__first, __middle, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
  1075. }
  1076.  
  1077. template <class _InputIter, class _RandomAccessIter, class _Compare,
  1078.           class _Distance, class _Tp>
  1079. _RandomAccessIter __partial_sort_copy(_InputIter __first,
  1080.                                          _InputIter __last,
  1081.                                          _RandomAccessIter __result_first,
  1082.                                          _RandomAccessIter __result_last,
  1083.                                          _Compare __comp, _Distance*, _Tp*) {
  1084.   if (__result_first == __result_last) return __result_last;
  1085.   _RandomAccessIter __result_real_last = __result_first;
  1086.   while(__first != __last && __result_real_last != __result_last) {
  1087.     *__result_real_last = *__first;
  1088.     ++__result_real_last;
  1089.     ++__first;
  1090.   }
  1091.   make_heap(__result_first, __result_real_last, __comp);
  1092.   while (__first != __last) {
  1093.     if (__comp(*__first, *__result_first))
  1094.       __adjust_heap(__result_first, _Distance(0),
  1095.                     _Distance(__result_real_last - __result_first),
  1096.                     _Tp(*__first),
  1097.                     __comp);
  1098.     ++__first;
  1099.   }
  1100.   sort_heap(__result_first, __result_real_last, __comp);
  1101.   return __result_real_last;
  1102. }
  1103.  
  1104. template <class _InputIter, class _RandomAccessIter>
  1105. _RandomAccessIter
  1106. partial_sort_copy(_InputIter __first, _InputIter __last,
  1107.                   _RandomAccessIter __result_first, _RandomAccessIter __result_last) {
  1108.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1109.   _STLP_DEBUG_CHECK(__check_range(__result_first, __result_last))
  1110.   return __partial_sort_copy(__first, __last, __result_first, __result_last, 
  1111.                              __less(_STLP_VALUE_TYPE(__first, _InputIter)),
  1112.                              _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
  1113.                              _STLP_VALUE_TYPE(__first, _InputIter));
  1114. }
  1115.  
  1116. template <class _InputIter, class _RandomAccessIter, class _Compare>
  1117. _RandomAccessIter
  1118. partial_sort_copy(_InputIter __first, _InputIter __last,
  1119.                   _RandomAccessIter __result_first,
  1120.                   _RandomAccessIter __result_last, _Compare __comp) {
  1121.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1122.   _STLP_DEBUG_CHECK(__check_range(__result_first, __result_last))
  1123.   return __partial_sort_copy(__first, __last, __result_first, __result_last,
  1124.                              __comp,
  1125.                              _STLP_DISTANCE_TYPE(__result_first, _RandomAccessIter),
  1126.                              _STLP_VALUE_TYPE(__first, _InputIter));
  1127. }
  1128.  
  1129. // nth_element() and its auxiliary functions.  
  1130.  
  1131. template <class _RandomAccessIter, class _Tp, class _Compare>
  1132. void __nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1133.                    _RandomAccessIter __last, _Tp*, _Compare __comp) {
  1134.   while (__last - __first > 3) {
  1135.     _RandomAccessIter __cut =
  1136.       __unguarded_partition(__first, __last,
  1137.                             _Tp(__median(*__first,
  1138.                                          *(__first + (__last - __first)/2), 
  1139.                                          *(__last - 1),
  1140.                                          __comp)),
  1141.                             __comp);
  1142.     if (__cut <= __nth)
  1143.       __first = __cut;
  1144.     else 
  1145.       __last = __cut;
  1146.   }
  1147.   __insertion_sort(__first, __last, __comp);
  1148. }
  1149.  
  1150.  
  1151. template <class _RandomAccessIter>
  1152. void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1153.                  _RandomAccessIter __last) {
  1154.   _STLP_DEBUG_CHECK(__check_range(__first, __nth))
  1155.   _STLP_DEBUG_CHECK(__check_range(__nth, __last))
  1156.   __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), 
  1157.                 __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)));
  1158. }
  1159.  
  1160. template <class _RandomAccessIter, class _Compare>
  1161. void nth_element(_RandomAccessIter __first, _RandomAccessIter __nth,
  1162.                  _RandomAccessIter __last, _Compare __comp) {
  1163.   _STLP_DEBUG_CHECK(__check_range(__first, __nth))
  1164.   _STLP_DEBUG_CHECK(__check_range(__nth, __last))
  1165.   __nth_element(__first, __nth, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIter), __comp);
  1166. }
  1167.  
  1168. // Binary search (lower_bound, upper_bound, equal_range, binary_search).
  1169.  
  1170. template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
  1171. _ForwardIter __upper_bound(_ForwardIter __first, _ForwardIter __last,
  1172.                            const _Tp& __val, _Compare __comp, _Distance*)
  1173. {
  1174.   _Distance __len = distance(__first, __last);
  1175.   _Distance __half;
  1176.  
  1177.   while (__len > 0) {
  1178.     __half = __len >> 1;
  1179.     _ForwardIter __middle = __first;
  1180.     advance(__middle, __half);
  1181.     if (__comp(__val, *__middle))
  1182.       __len = __half;
  1183.     else {
  1184.       __first = __middle;
  1185.       ++__first;
  1186.       __len = __len - __half - 1;
  1187.     }
  1188.   }
  1189.   return __first;
  1190. }
  1191.  
  1192. template <class _ForwardIter, class _Tp, class _Compare, class _Distance>
  1193. pair<_ForwardIter, _ForwardIter>
  1194. __equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp& __val,
  1195.               _Compare __comp, _Distance*)
  1196. {
  1197.   _Distance __len = distance(__first, __last);
  1198.   _Distance __half;
  1199.  
  1200.   while (__len > 0) {
  1201.     __half = __len >> 1;
  1202.     _ForwardIter __middle = __first;
  1203.     advance(__middle, __half);
  1204.     if (__comp(*__middle, __val)) {
  1205.       __first = __middle;
  1206.       ++__first;
  1207.       __len = __len - __half - 1;
  1208.     }
  1209.     else if (__comp(__val, *__middle))
  1210.       __len = __half;
  1211.     else {
  1212.       _ForwardIter __left = lower_bound(__first, __middle, __val, __comp);
  1213.       advance(__first, __len);
  1214.       _ForwardIter __right = upper_bound(++__middle, __first, __val, __comp);
  1215.       return pair<_ForwardIter, _ForwardIter>(__left, __right);
  1216.     }
  1217.   }
  1218.   return pair<_ForwardIter, _ForwardIter>(__first, __first);
  1219. }           
  1220.  
  1221. template <class _InputIter1, class _InputIter2, class _OutputIter>
  1222. _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  1223.                   _InputIter2 __first2, _InputIter2 __last2,
  1224.                   _OutputIter __result) {
  1225.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1226.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1227.   while (__first1 != __last1 && __first2 != __last2) {
  1228.     if (*__first2 < *__first1) {
  1229.       *__result = *__first2;
  1230.       ++__first2;
  1231.     }
  1232.     else {
  1233.       *__result = *__first1;
  1234.       ++__first1;
  1235.     }
  1236.     ++__result;
  1237.   }
  1238.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  1239. }
  1240.  
  1241. template <class _InputIter1, class _InputIter2, class _OutputIter,
  1242.           class _Compare>
  1243. _OutputIter merge(_InputIter1 __first1, _InputIter1 __last1,
  1244.                   _InputIter2 __first2, _InputIter2 __last2,
  1245.                   _OutputIter __result, _Compare __comp) {
  1246.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1247.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1248.   while (__first1 != __last1 && __first2 != __last2) {
  1249.     if (__comp(*__first2, *__first1)) {
  1250.       *__result = *__first2;
  1251.       ++__first2;
  1252.     }
  1253.     else {
  1254.       *__result = *__first1;
  1255.       ++__first1;
  1256.     }
  1257.     ++__result;
  1258.   }
  1259.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  1260. }
  1261.  
  1262. template <class _BidirectionalIter, class _Distance, class _Compare>
  1263. void __merge_without_buffer(_BidirectionalIter __first,
  1264.                             _BidirectionalIter __middle,
  1265.                             _BidirectionalIter __last,
  1266.                             _Distance __len1, _Distance __len2,
  1267.                             _Compare __comp) {
  1268.   if (__len1 == 0 || __len2 == 0)
  1269.     return;
  1270.   if (__len1 + __len2 == 2) {
  1271.     if (__comp(*__middle, *__first))
  1272.       iter_swap(__first, __middle);
  1273.     return;
  1274.   }
  1275.   _BidirectionalIter __first_cut = __first;
  1276.   _BidirectionalIter __second_cut = __middle;
  1277.   _Distance __len11 = 0;
  1278.   _Distance __len22 = 0;
  1279.   if (__len1 > __len2) {
  1280.     __len11 = __len1 / 2;
  1281.     advance(__first_cut, __len11);
  1282.     __second_cut = lower_bound(__middle, __last, *__first_cut, __comp);
  1283.     __len22 += distance(__middle, __second_cut);
  1284.   }
  1285.   else {
  1286.     __len22 = __len2 / 2;
  1287.     advance(__second_cut, __len22);
  1288.     __first_cut = upper_bound(__first, __middle, *__second_cut, __comp);
  1289.     __len11 +=distance(__first, __first_cut);
  1290.   }
  1291.   _BidirectionalIter __new_middle
  1292.     = rotate(__first_cut, __middle, __second_cut);
  1293.   __merge_without_buffer(__first, __first_cut, __new_middle, __len11, __len22,
  1294.                          __comp);
  1295.   __merge_without_buffer(__new_middle, __second_cut, __last, __len1 - __len11,
  1296.                          __len2 - __len22, __comp);
  1297. }
  1298.  
  1299. template <class _BidirectionalIter1, class _BidirectionalIter2,
  1300.           class _BidirectionalIter3, class _Compare>
  1301. _BidirectionalIter3 __merge_backward(_BidirectionalIter1 __first1,
  1302.                                      _BidirectionalIter1 __last1,
  1303.                                      _BidirectionalIter2 __first2,
  1304.                                      _BidirectionalIter2 __last2,
  1305.                                      _BidirectionalIter3 __result,
  1306.                                      _Compare __comp) {
  1307.   if (__first1 == __last1)
  1308.     return copy_backward(__first2, __last2, __result);
  1309.   if (__first2 == __last2)
  1310.     return copy_backward(__first1, __last1, __result);
  1311.   --__last1;
  1312.   --__last2;
  1313.   while (true) {
  1314.     if (__comp(*__last2, *__last1)) {
  1315.       *--__result = *__last1;
  1316.       if (__first1 == __last1)
  1317.         return copy_backward(__first2, ++__last2, __result);
  1318.       --__last1;
  1319.     }
  1320.     else {
  1321.       *--__result = *__last2;
  1322.       if (__first2 == __last2)
  1323.         return copy_backward(__first1, ++__last1, __result);
  1324.       --__last2;
  1325.     }
  1326.   }
  1327. }
  1328.  
  1329. template <class _BidirectionalIter, class _Tp, 
  1330.           class _Distance, class _Compare>
  1331. inline void __inplace_merge_aux(_BidirectionalIter __first,
  1332.                                 _BidirectionalIter __middle,
  1333.                                 _BidirectionalIter __last, _Tp*, _Distance*,
  1334.                                 _Compare __comp) {
  1335.   _Distance __len1 = distance(__first, __middle);
  1336.   _Distance __len2 = distance(__middle, __last);
  1337.  
  1338.   _Temporary_buffer<_BidirectionalIter, _Tp> __buf(__first, __last);
  1339.   if (__buf.begin() == 0)
  1340.     __merge_without_buffer(__first, __middle, __last, __len1, __len2, __comp);
  1341.   else
  1342.     __merge_adaptive(__first, __middle, __last, __len1, __len2,
  1343.                      __buf.begin(), _Distance(__buf.size()),
  1344.                      __comp);
  1345. }
  1346.  
  1347. template <class _BidirectionalIter>
  1348. void inplace_merge(_BidirectionalIter __first,
  1349.            _BidirectionalIter __middle,
  1350.            _BidirectionalIter __last) {
  1351.   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
  1352.   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
  1353.   if (__first == __middle || __middle == __last)
  1354.     return;
  1355.   __inplace_merge_aux(__first, __middle, __last,
  1356.                       _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
  1357.                       __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
  1358. }
  1359.  
  1360. template <class _BidirectionalIter, class _Compare>
  1361. void inplace_merge(_BidirectionalIter __first,
  1362.            _BidirectionalIter __middle,
  1363.            _BidirectionalIter __last, _Compare __comp) {
  1364.   _STLP_DEBUG_CHECK(__check_range(__first, __middle))
  1365.   _STLP_DEBUG_CHECK(__check_range(__middle, __last))
  1366.   if (__first == __middle || __middle == __last)
  1367.     return;
  1368.   __inplace_merge_aux(__first, __middle, __last,
  1369.                       _STLP_VALUE_TYPE(__first, _BidirectionalIter), _STLP_DISTANCE_TYPE(__first, _BidirectionalIter),
  1370.                       __comp);
  1371. }
  1372.  
  1373.  
  1374. template <class _InputIter1, class _InputIter2, class _Compare>
  1375. bool __includes(_InputIter1 __first1, _InputIter1 __last1,
  1376.                 _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  1377.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1378.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1379.   while (__first1 != __last1 && __first2 != __last2)
  1380.     if (__comp(*__first2, *__first1))
  1381.       return false;
  1382.     else if(__comp(*__first1, *__first2)) 
  1383.       ++__first1;
  1384.     else
  1385.       ++__first1, ++__first2;
  1386.  
  1387.   return __first2 == __last2;
  1388. }
  1389.  
  1390. template <class _InputIter1, class _InputIter2, class _Compare>
  1391. bool includes(_InputIter1 __first1, _InputIter1 __last1,
  1392.               _InputIter2 __first2, _InputIter2 __last2, _Compare __comp) {
  1393.   return __includes(__first1, __last1, __first2, __last2, __comp);
  1394. }
  1395.  
  1396. template <class _InputIter1, class _InputIter2>
  1397. bool includes(_InputIter1 __first1, _InputIter1 __last1,
  1398.               _InputIter2 __first2, _InputIter2 __last2) {
  1399.   return __includes(__first1, __last1, __first2, __last2, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));
  1400. }
  1401.  
  1402. template <class _InputIter1, class _InputIter2, class _OutputIter,
  1403.           class _Compare>
  1404. _OutputIter __set_union(_InputIter1 __first1, _InputIter1 __last1,
  1405.                         _InputIter2 __first2, _InputIter2 __last2,
  1406.                         _OutputIter __result, _Compare __comp) {
  1407.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1408.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1409.   while (__first1 != __last1 && __first2 != __last2) {
  1410.     if (__comp(*__first1, *__first2)) {
  1411.       *__result = *__first1;
  1412.       ++__first1;
  1413.     }
  1414.     else if (__comp(*__first2, *__first1)) {
  1415.       *__result = *__first2;
  1416.       ++__first2;
  1417.     }
  1418.     else {
  1419.       *__result = *__first1;
  1420.       ++__first1;
  1421.       ++__first2;
  1422.     }
  1423.     ++__result;
  1424.   }
  1425.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  1426. }
  1427.  
  1428. template <class _InputIter1, class _InputIter2, class _OutputIter>
  1429. _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  1430.                       _InputIter2 __first2, _InputIter2 __last2,
  1431.                       _OutputIter __result) {
  1432.   return __set_union(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
  1433. }
  1434.  
  1435. template <class _InputIter1, class _InputIter2, class _OutputIter,
  1436.           class _Compare>
  1437. _OutputIter set_union(_InputIter1 __first1, _InputIter1 __last1,
  1438.                       _InputIter2 __first2, _InputIter2 __last2,
  1439.                       _OutputIter __result, _Compare __comp) {
  1440.   return __set_union(__first1, __last1, __first2, __last2, __result, __comp);
  1441. }
  1442.  
  1443. template <class _InputIter1, class _InputIter2, class _OutputIter,
  1444.           class _Compare>
  1445. _OutputIter __set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  1446.                                _InputIter2 __first2, _InputIter2 __last2,
  1447.                                _OutputIter __result, _Compare __comp) {
  1448.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1449.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1450.   while (__first1 != __last1 && __first2 != __last2)
  1451.     if (__comp(*__first1, *__first2))
  1452.       ++__first1;
  1453.     else if (__comp(*__first2, *__first1))
  1454.       ++__first2;
  1455.     else {
  1456.       *__result = *__first1;
  1457.       ++__first1;
  1458.       ++__first2;
  1459.       ++__result;
  1460.     }
  1461.   return __result;
  1462. }
  1463.  
  1464. template <class _InputIter1, class _InputIter2, class _OutputIter>
  1465. _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  1466.                              _InputIter2 __first2, _InputIter2 __last2,
  1467.                              _OutputIter __result) {
  1468.   return __set_intersection(__first1, __last1, __first2, __last2, __result, __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
  1469. }
  1470.  
  1471. template <class _InputIter1, class _InputIter2, class _OutputIter,
  1472.           class _Compare>
  1473. _OutputIter set_intersection(_InputIter1 __first1, _InputIter1 __last1,
  1474.                              _InputIter2 __first2, _InputIter2 __last2,
  1475.                              _OutputIter __result, _Compare __comp) {
  1476.   return __set_intersection(__first1, __last1, __first2, __last2, __result, __comp);
  1477. }
  1478.  
  1479. template <class _InputIter1, class _InputIter2, class _OutputIter, 
  1480.           class _Compare>
  1481. _OutputIter __set_difference(_InputIter1 __first1, _InputIter1 __last1,
  1482.                              _InputIter2 __first2, _InputIter2 __last2, 
  1483.                              _OutputIter __result, _Compare __comp) {
  1484.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1485.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1486.   while (__first1 != __last1 && __first2 != __last2)
  1487.     if (__comp(*__first1, *__first2)) {
  1488.       *__result = *__first1;
  1489.       ++__first1;
  1490.       ++__result;
  1491.     }
  1492.     else if (__comp(*__first2, *__first1))
  1493.       ++__first2;
  1494.     else {
  1495.       ++__first1;
  1496.       ++__first2;
  1497.     }
  1498.   return copy(__first1, __last1, __result);
  1499. }
  1500.  
  1501. template <class _InputIter1, class _InputIter2, class _OutputIter>
  1502. _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  1503.                            _InputIter2 __first2, _InputIter2 __last2,
  1504.                            _OutputIter __result) {
  1505.   return __set_difference(__first1, __last1, __first2, __last2, __result, 
  1506.                           __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
  1507. }
  1508.  
  1509. template <class _InputIter1, class _InputIter2, class _OutputIter, 
  1510.           class _Compare>
  1511. _OutputIter set_difference(_InputIter1 __first1, _InputIter1 __last1,
  1512.                            _InputIter2 __first2, _InputIter2 __last2, 
  1513.                            _OutputIter __result, _Compare __comp) {
  1514.   return __set_difference(__first1, __last1, __first2, __last2, __result, __comp);
  1515. }
  1516.  
  1517. template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
  1518. _OutputIter 
  1519. __set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  1520.                            _InputIter2 __first2, _InputIter2 __last2,
  1521.                            _OutputIter __result, _Compare __comp) {
  1522.   _STLP_DEBUG_CHECK(__check_range(__first1, __last1))
  1523.   _STLP_DEBUG_CHECK(__check_range(__first2, __last2))
  1524.   while (__first1 != __last1 && __first2 != __last2)
  1525.     if (__comp(*__first1, *__first2)) {
  1526.       *__result = *__first1;
  1527.       ++__first1;
  1528.       ++__result;
  1529.     }
  1530.     else if (__comp(*__first2, *__first1)) {
  1531.       *__result = *__first2;
  1532.       ++__first2;
  1533.       ++__result;
  1534.     }
  1535.     else {
  1536.       ++__first1;
  1537.       ++__first2;
  1538.     }
  1539.   return copy(__first2, __last2, copy(__first1, __last1, __result));
  1540. }
  1541.  
  1542. template <class _InputIter1, class _InputIter2, class _OutputIter>
  1543. _OutputIter 
  1544. set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  1545.                          _InputIter2 __first2, _InputIter2 __last2,
  1546.                          _OutputIter __result) {
  1547.   return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result,
  1548.                                     __less(_STLP_VALUE_TYPE(__first1, _InputIter1)));  
  1549. }
  1550.  
  1551. template <class _InputIter1, class _InputIter2, class _OutputIter, class _Compare>
  1552. _OutputIter 
  1553. set_symmetric_difference(_InputIter1 __first1, _InputIter1 __last1,
  1554.                          _InputIter2 __first2, _InputIter2 __last2,
  1555.                          _OutputIter __result,
  1556.                          _Compare __comp) {
  1557.   return __set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __comp);
  1558. }
  1559.  
  1560. // min_element and max_element, with and without an explicitly supplied
  1561. // comparison function.
  1562.  
  1563. template <class _ForwardIter, class _Compare>
  1564. _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last,
  1565.                             _Compare __comp) {
  1566.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1567.   if (__first == __last) return __first;
  1568.   _ForwardIter __result = __first;
  1569.   while (++__first != __last) 
  1570.     if (__comp(*__result, *__first)) __result = __first;
  1571.   return __result;
  1572. }
  1573.  
  1574. template <class _ForwardIter>
  1575. _ForwardIter max_element(_ForwardIter __first, _ForwardIter __last) {
  1576.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1577.   if (__first == __last) return __first;
  1578.   _ForwardIter __result = __first;
  1579.   while (++__first != __last) 
  1580.     if (*__result < *__first)
  1581.       __result = __first;
  1582.   return __result;
  1583. }
  1584.  
  1585. template <class _ForwardIter>
  1586. _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last) {
  1587.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1588.   if (__first == __last) return __first;
  1589.   _ForwardIter __result = __first;
  1590.   while (++__first != __last) 
  1591.     if (*__first < *__result)
  1592.       __result = __first;
  1593.   return __result;
  1594. }
  1595.  
  1596. template <class _ForwardIter, class _Compare>
  1597. _ForwardIter min_element(_ForwardIter __first, _ForwardIter __last,
  1598.                             _Compare __comp) {
  1599.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1600.   if (__first == __last) return __first;
  1601.   _ForwardIter __result = __first;
  1602.   while (++__first != __last) 
  1603.     if (__comp(*__first, *__result)) __result = __first;
  1604.   return __result;
  1605. }
  1606.  
  1607. // next_permutation and prev_permutation, with and without an explicitly 
  1608. // supplied comparison function.
  1609. template <class _BidirectionalIter, class _Compare>
  1610. bool __next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1611.                         _Compare __comp) {
  1612.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1613.   if (__first == __last)
  1614.     return false;
  1615.   _BidirectionalIter __i = __first;
  1616.   ++__i;
  1617.   if (__i == __last)
  1618.     return false;
  1619.   __i = __last;
  1620.   --__i;
  1621.  
  1622.   for(;;) {
  1623.     _BidirectionalIter __ii = __i;
  1624.     --__i;
  1625.     if (__comp(*__i, *__ii)) {
  1626.       _BidirectionalIter __j = __last;
  1627.       while (!__comp(*__i, *--__j))
  1628.         {}
  1629.       iter_swap(__i, __j);
  1630.       reverse(__ii, __last);
  1631.       return true;
  1632.     }
  1633.     if (__i == __first) {
  1634.       reverse(__first, __last);
  1635.       return false;
  1636.     }
  1637.   }
  1638. #if defined(_STLP_NEED_UNREACHABLE_RETURN)
  1639.     return 0;
  1640. #endif
  1641. }
  1642.  
  1643. template <class _BidirectionalIter>
  1644. bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  1645.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1646.   return __next_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
  1647. }
  1648.  
  1649. template <class _BidirectionalIter, class _Compare>
  1650. bool next_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1651.                       _Compare __comp) {
  1652.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1653.   return __next_permutation(__first, __last, __comp);
  1654. }
  1655.  
  1656. template <class _BidirectionalIter, class _Compare>
  1657. bool __prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1658.                       _Compare __comp) {
  1659.   if (__first == __last)
  1660.     return false;
  1661.   _BidirectionalIter __i = __first;
  1662.   ++__i;
  1663.   if (__i == __last)
  1664.     return false;
  1665.   __i = __last;
  1666.   --__i;
  1667.  
  1668.   for(;;) {
  1669.     _BidirectionalIter __ii = __i;
  1670.     --__i;
  1671.     if (__comp(*__ii, *__i)) {
  1672.       _BidirectionalIter __j = __last;
  1673.       while (!__comp(*--__j, *__i))
  1674.         {}
  1675.       iter_swap(__i, __j);
  1676.       reverse(__ii, __last);
  1677.       return true;
  1678.     }
  1679.     if (__i == __first) {
  1680.       reverse(__first, __last);
  1681.       return false;
  1682.     }
  1683.   }
  1684. #if defined(_STLP_NEED_UNREACHABLE_RETURN)
  1685.     return 0;
  1686. #endif
  1687. }
  1688.  
  1689. template <class _BidirectionalIter>
  1690. bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last) {
  1691.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1692.   return __prev_permutation(__first, __last, __less(_STLP_VALUE_TYPE(__first, _BidirectionalIter)));
  1693. }
  1694.  
  1695. template <class _BidirectionalIter, class _Compare>
  1696. bool prev_permutation(_BidirectionalIter __first, _BidirectionalIter __last,
  1697.                       _Compare __comp) {
  1698.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1699.   return __prev_permutation(__first, __last, __comp);
  1700. }
  1701.  
  1702. # ifndef _STLP_NO_EXTENSIONS
  1703.  
  1704. // is_heap, a predicate testing whether or not a range is
  1705. // a heap.  This function is an extension, not part of the C++
  1706. // standard.
  1707.  
  1708.  
  1709. template <class _RandomAccessIter, class _Distance, class _StrictWeakOrdering>
  1710. bool __is_heap(_RandomAccessIter __first, _StrictWeakOrdering __comp,
  1711.                _Distance __n)
  1712. {
  1713.   _Distance __parent = 0;
  1714.   for (_Distance __child = 1; __child < __n; ++__child) {
  1715.     if (__comp(__first[__parent], __first[__child]))
  1716.       return false;
  1717.     if ((__child & 1) == 0)
  1718.       ++__parent;
  1719.   }
  1720.   return true;
  1721. }
  1722.  
  1723. template <class _RandomAccessIter>
  1724. bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last)
  1725. {
  1726.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1727.   return __is_heap(__first, __less(_STLP_VALUE_TYPE(__first, _RandomAccessIter)), __last - __first);
  1728. }
  1729.  
  1730. template <class _RandomAccessIter, class _StrictWeakOrdering>
  1731. bool is_heap(_RandomAccessIter __first, _RandomAccessIter __last,
  1732.          _StrictWeakOrdering __comp)
  1733. {
  1734.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1735.   return __is_heap(__first, __comp, __last - __first);
  1736. }
  1737.  
  1738.  
  1739. template <class _ForwardIter, class _StrictWeakOrdering>
  1740. bool __is_sorted(_ForwardIter __first, _ForwardIter __last,
  1741.                  _StrictWeakOrdering __comp)
  1742. {
  1743.   _STLP_DEBUG_CHECK(__check_range(__first, __last))
  1744.   if (__first == __last)
  1745.     return true;
  1746.  
  1747.   _ForwardIter __next = __first;
  1748.   for (++__next; __next != __last; __first = __next, ++__next) {
  1749.     if (__comp(*__next, *__first))
  1750.       return false;
  1751.   }
  1752.  
  1753.   return true;
  1754. }
  1755.  
  1756. # endif /* _STLP_NO_EXTENSIONS */
  1757.  
  1758. _STLP_END_NAMESPACE
  1759.  
  1760. # undef __stl_threshold
  1761.  
  1762. #endif /* _STLP_ALGO_C */
  1763. // Local Variables:
  1764. // mode:C++
  1765. // End:
  1766.