home *** CD-ROM | disk | FTP | other *** search
/ PC Plus SuperCD (UK) 2000 May / PCP163A.iso / Runimage / Cbuilder4 / Include / ALGORITH.H < prev    next >
Encoding:
C/C++ Source or Header  |  1999-01-26  |  69.3 KB  |  1,697 lines
  1. #ifndef __ALGORITH_H
  2. #define __ALGORITH_H
  3. #pragma option push -b -a8 -pc -Vx- -Ve- -w-inl -w-aus -w-sig
  4. // -*- C++ -*-
  5. #ifndef __STD_ALGORITHM
  6. #define __STD_ALGORITHM
  7.  
  8. /***************************************************************************
  9.  *
  10.  * algorithm - Declarations and inline definitions 
  11.  *             for the Standard Library algorithms
  12.  *
  13.  ***************************************************************************
  14.  *
  15.  * Copyright (c) 1994
  16.  * Hewlett-Packard Company
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Hewlett-Packard Company makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  *
  26.  *
  27.  ***************************************************************************
  28.  *
  29.  * (c) Copyright 1994, 1998 Rogue Wave Software, Inc.
  30.  * ALL RIGHTS RESERVED
  31.  *
  32.  * The software and information contained herein are proprietary to, and
  33.  * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
  34.  * intends to preserve as trade secrets such software and information.
  35.  * This software is furnished pursuant to a written license agreement and
  36.  * may be used, copied, transmitted, and stored only in accordance with
  37.  * the terms of such license and with the inclusion of the above copyright
  38.  * notice.  This software and information or any other copies thereof may
  39.  * not be provided or otherwise made available to any other person.
  40.  *
  41.  * Notwithstanding any other lease or license that may pertain to, or
  42.  * accompany the delivery of, this computer software and information, the
  43.  * rights of the Government regarding its use, reproduction and disclosure
  44.  * are as set forth in Section 52.227-19 of the FARS Computer
  45.  * Software-Restricted Rights clause.
  46.  * 
  47.  * Use, duplication, or disclosure by the Government is subject to
  48.  * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
  49.  * Technical Data and Computer Software clause at DFARS 252.227-7013.
  50.  * Contractor/Manufacturer is Rogue Wave Software, Inc.,
  51.  * P.O. Box 2328, Corvallis, Oregon 97339.
  52.  *
  53.  * This computer software and information is distributed with "restricted
  54.  * rights."  Use, duplication or disclosure is subject to restrictions as
  55.  * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
  56.  * Computer Software-Restricted Rights (April 1985)."  If the Clause at
  57.  * 18-52.227-74 "Rights in Data General" is specified in the contract,
  58.  * then the "Alternate III" clause applies.
  59.  *
  60.  **************************************************************************/
  61.  
  62. #include <stdcomp.h>
  63.  
  64. #ifndef _RWSTD_NO_NEW_HEADER
  65. #include <cstdlib>
  66. #else
  67. #include <stdlib.h>
  68. #endif
  69.  
  70. #include <iterator>
  71. #include <memory>
  72. #include <utility>
  73.  
  74. // Some compilers have min and max macros
  75. // We use function templates in their stead
  76. #ifdef max
  77. # undef max
  78. # undef __MINMAX_DEFINED  // __BORLANDC__
  79. #endif
  80. #ifdef min
  81. # undef min
  82. # undef __MINMAX_DEFINED  // __BORLANDC__
  83. #endif
  84.  
  85. #ifndef _RWSTD_NO_NAMESPACE
  86. namespace std {
  87. #endif
  88.  
  89. //
  90. // Forward declare raw_storage_iterator
  91. //
  92.   template <class OutputIterator, class T>
  93.   class raw_storage_iterator;
  94.   template <class T>
  95. #ifndef __BORLANDC__
  96.   inline
  97. #endif
  98.   void __initialize (T& t, T val) { t = val; }
  99.  
  100. //
  101. // Non-modifying sequence operations.
  102. //
  103.  
  104.   template <class InputIterator, class Function>
  105.   Function for_each (InputIterator first, InputIterator last, Function f);
  106.  
  107.   template <class InputIterator, class T>
  108.   InputIterator find (InputIterator first, InputIterator last, const T& value);
  109.  
  110.   template <class InputIterator, class Predicate>
  111.   InputIterator find_if (InputIterator first, InputIterator last, Predicate pred);
  112.  
  113.   template <class ForwardIterator1, class ForwardIterator2, 
  114.   class Distance>
  115.   ForwardIterator1 __find_end (ForwardIterator1 first1,
  116.                                ForwardIterator1 last1,
  117.                                ForwardIterator2 first2,
  118.                                ForwardIterator2 last2,
  119.                                Distance*);
  120.  
  121.   template <class ForwardIterator1, class ForwardIterator2>
  122.   ForwardIterator1 find_end (ForwardIterator1 first1,
  123.                              ForwardIterator1 last1,
  124.                              ForwardIterator2 first2,
  125.                              ForwardIterator2 last2);
  126.  
  127.   template <class ForwardIterator1, class ForwardIterator2, 
  128.   class BinaryPredicate, class Distance>
  129.   ForwardIterator1 __find_end (ForwardIterator1 first1,
  130.                                ForwardIterator1 last1,
  131.                                ForwardIterator2 first2,
  132.                                ForwardIterator2 last2,
  133.                                BinaryPredicate pred,
  134.                                Distance*);
  135.  
  136.   template <class ForwardIterator1, class ForwardIterator2, 
  137.   class BinaryPredicate>
  138.   ForwardIterator1 find_end (ForwardIterator1 first1,
  139.                              ForwardIterator1 last1,
  140.                              ForwardIterator2 first2,
  141.                              ForwardIterator2 last2,
  142.                              BinaryPredicate pred);
  143.  
  144.   template <class ForwardIterator1, class ForwardIterator2>
  145.   ForwardIterator1 find_first_of (ForwardIterator1 first1, ForwardIterator1 last1,
  146.                                   ForwardIterator2 first2, ForwardIterator2 last2);
  147.  
  148.   template <class ForwardIterator1, class ForwardIterator2,
  149.   class BinaryPredicate>
  150.   ForwardIterator1 find_first_of (ForwardIterator1 first1,ForwardIterator1 last1,
  151.                                   ForwardIterator2 first2,ForwardIterator2 last2,
  152.                                   BinaryPredicate pred);
  153.  
  154.   template <class ForwardIterator>
  155.   ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last);
  156.  
  157.   template <class ForwardIterator, class BinaryPredicate>
  158.   ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last,
  159.                                  BinaryPredicate binary_pred);
  160.  
  161. #ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC
  162.   template <class InputIterator, class T>
  163.   _TYPENAME iterator_traits<InputIterator>::difference_type
  164.   count (InputIterator first, InputIterator last, const T& value);
  165.  
  166.   template <class InputIterator, class Predicate>
  167.   _TYPENAME iterator_traits<InputIterator>::difference_type
  168.   count_if (InputIterator first, InputIterator last, Predicate pred);
  169. #endif /* _RWSTD_NO_CLASS_PARTIAL_SPEC */
  170.  
  171. #ifndef _RWSTD_NO_OLD_COUNT
  172.   template <class InputIterator, class T, class Size>
  173.   void count (InputIterator first, InputIterator last, const T& value, Size& n);
  174.  
  175.   template <class InputIterator, class Predicate, class Size>
  176.   void count_if (InputIterator first, InputIterator last, Predicate pred,
  177.                  Size& n);
  178. #endif /* _RWSTD_NO_OLD_COUNT */
  179.  
  180.   template <class InputIterator1, class InputIterator2>
  181.   pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
  182.                                                 InputIterator1 last1,
  183.                                                 InputIterator2 first2);
  184.  
  185.   template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  186.   pair<InputIterator1, InputIterator2> mismatch (InputIterator1 first1,
  187.                                                  InputIterator1 last1,
  188.                                                  InputIterator2 first2,
  189.                                                  BinaryPredicate binary_pred);
  190.  
  191.   template <class InputIterator1, class InputIterator2>
  192.   inline bool equal (InputIterator1 first1, InputIterator1 last1,
  193.                      InputIterator2 first2)
  194.   {
  195.     return mismatch(first1, last1, first2).first == last1;
  196.   }
  197.  
  198.   template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  199.   inline bool equal (InputIterator1 first1, InputIterator1 last1,
  200.                      InputIterator2 first2, BinaryPredicate binary_pred)
  201.   {
  202.     return mismatch(first1, last1, first2, binary_pred).first == last1;
  203.   }
  204.  
  205.   template <class ForwardIterator1, class ForwardIterator2,
  206.   class Distance1, class Distance2>
  207.   ForwardIterator1 __search (ForwardIterator1 first1, ForwardIterator1 last1,
  208.                              ForwardIterator2 first2, ForwardIterator2 last2,
  209.                              Distance1*, Distance2*);
  210.  
  211.   template <class ForwardIterator1, class ForwardIterator2>
  212.   inline ForwardIterator1 search (ForwardIterator1 first1,ForwardIterator1 last1,
  213.                                   ForwardIterator2 first2,ForwardIterator2 last2)
  214.   {
  215.     return __search(first1, last1, first2, last2, __distance_type(first1),
  216.                     __distance_type(first2));
  217.   }
  218.  
  219.   template <class ForwardIterator1, class ForwardIterator2,
  220.   class BinaryPredicate, class Distance1, class Distance2>
  221.   ForwardIterator1 __search (ForwardIterator1 first1, ForwardIterator1 last1,
  222.                              ForwardIterator2 first2, ForwardIterator2 last2,
  223.                              BinaryPredicate binary_pred, Distance1*, Distance2*);
  224.  
  225.   template <class ForwardIterator1, class ForwardIterator2,
  226.   class BinaryPredicate>
  227.   inline ForwardIterator1 search (ForwardIterator1 first1,ForwardIterator1 last1,
  228.                                   ForwardIterator2 first2,ForwardIterator2 last2,
  229.                                   BinaryPredicate binary_pred)
  230.   {
  231.     return __search(first1, last1, first2, last2, binary_pred,
  232.                     __distance_type(first1), __distance_type(first2));
  233.   }
  234.  
  235.   template <class ForwardIterator, class Distance, class Size, class T>
  236.   ForwardIterator __search_n (ForwardIterator first, ForwardIterator last,
  237.                               Distance*, Size count, const T& value);
  238.  
  239.   template <class ForwardIterator, class Size, class T>
  240.   inline ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
  241.                                    Size count, const T& value)
  242.   {
  243.     if (count) 
  244.       return __search_n(first, last, __distance_type(first), count, value);
  245.     else
  246.       return first;
  247.   }
  248.  
  249.   template <class ForwardIterator, class Distance, class Size, class T,
  250.   class BinaryPredicate>
  251.   ForwardIterator __search_n (ForwardIterator first, ForwardIterator last,
  252.                               Distance*, Size count, const T& value,
  253.                               BinaryPredicate pred);
  254.  
  255.   template <class ForwardIterator, class Size, class T, class BinaryPredicate>
  256.   inline ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
  257.                                    Size count, const T& value,
  258.                                    BinaryPredicate pred)
  259.   {
  260.     if (count) 
  261.       return  __search_n(first, last, __distance_type(first), count,value, pred);
  262.     else
  263.       return first;
  264.   }
  265.  
  266. //
  267. // Modifying sequence operations.
  268. //
  269.  
  270.   template <class InputIterator, class OutputIterator>
  271.   OutputIterator copy (InputIterator first, InputIterator last,
  272.                        OutputIterator result);
  273.  
  274.   template <class BidirectionalIterator1, class BidirectionalIterator2>
  275.   BidirectionalIterator2 copy_backward (BidirectionalIterator1 first, 
  276.                                         BidirectionalIterator1 last, 
  277.                                         BidirectionalIterator2 result);
  278.  
  279.   template <class T>
  280.   inline void swap (T& a, T& b)
  281.   {
  282.     T tmp = a;
  283.     a = b;
  284.     b = tmp;
  285.   }
  286.  
  287.   template <class ForwardIterator1, class ForwardIterator2, class T>
  288.   inline void __iter_swap (ForwardIterator1 a, ForwardIterator2 b, T*)
  289.   {
  290.     T tmp = *a;
  291.     *a = *b;
  292.     *b = tmp;
  293.   }
  294.  
  295.   template <class ForwardIterator1, class ForwardIterator2>
  296.   inline void iter_swap (ForwardIterator1 a, ForwardIterator2 b)
  297.   {
  298.     __iter_swap(a, b, _RWSTD_VALUE_TYPE(a));
  299.   }
  300.  
  301.   template <class ForwardIterator1, class ForwardIterator2>
  302.   ForwardIterator2 swap_ranges (ForwardIterator1 first1, ForwardIterator1 last1,
  303.                                 ForwardIterator2 first2);
  304.  
  305.   template <class InputIterator, class OutputIterator, class UnaryOperation>
  306.   OutputIterator transform (InputIterator first, InputIterator last,
  307.                             OutputIterator result, UnaryOperation op);
  308.  
  309.   template <class InputIterator1, class InputIterator2, class OutputIterator,
  310.   class BinaryOperation>
  311.   OutputIterator transform (InputIterator1 first1, InputIterator1 last1,
  312.                             InputIterator2 first2, OutputIterator result,
  313.                             BinaryOperation binary_op);
  314.  
  315.   template <class ForwardIterator, class T>
  316.   void replace (ForwardIterator first, ForwardIterator last, const T& old_value,
  317.                 const T& new_value);
  318.  
  319.   template <class ForwardIterator, class Predicate, class T>
  320.   void replace_if (ForwardIterator first, ForwardIterator last, Predicate pred,
  321.                    const T& new_value);
  322.  
  323.   template <class InputIterator, class OutputIterator, class T>
  324.   OutputIterator replace_copy (InputIterator first, InputIterator last,
  325.                                OutputIterator result, const T& old_value,
  326.                                const T& new_value);
  327.  
  328.   template <class Iterator, class OutputIterator, class Predicate, class T>
  329.   OutputIterator replace_copy_if (Iterator first, Iterator last,
  330.                                   OutputIterator result, Predicate pred,
  331.                                   const T& new_value);
  332.  
  333.   template <class ForwardIterator, class T>
  334. #ifdef _RWSTD_FILL_NAME_CLASH
  335.   void std_fill (ForwardIterator first, ForwardIterator last, const T& value);
  336. #else
  337.   void fill (ForwardIterator first, ForwardIterator last, const T& value);
  338. #endif
  339.  
  340.   template <class OutputIterator, class Size, class T>
  341.   void fill_n (OutputIterator first, Size n, const T& value);
  342.  
  343.   template <class ForwardIterator, class Generator>
  344.   void generate (ForwardIterator first, ForwardIterator last, Generator gen);
  345.  
  346.   template <class OutputIterator, class Size, class Generator>
  347.   void generate_n (OutputIterator first, Size n, Generator gen);
  348.  
  349.   template <class InputIterator, class OutputIterator, class T>
  350.   OutputIterator remove_copy (InputIterator first, InputIterator last,
  351.                               OutputIterator result, const T& value);
  352.  
  353.   template <class InputIterator, class OutputIterator, class Predicate>
  354.   OutputIterator remove_copy_if (InputIterator first, InputIterator last,
  355.                                  OutputIterator result, Predicate pred);
  356.  
  357.   template <class ForwardIterator, class T>
  358.   inline ForwardIterator remove (ForwardIterator first, ForwardIterator last,
  359.                                  const T& value)
  360.   {
  361.     first = find(first, last, value);
  362.     ForwardIterator next = first;
  363.     return first == last ? first : remove_copy(++next, last, first, value);
  364.   }
  365.  
  366.   template <class ForwardIterator, class Predicate>
  367.   inline ForwardIterator remove_if (ForwardIterator first, ForwardIterator last,
  368.                                     Predicate pred)
  369.   {
  370.     first = find_if(first, last, pred);
  371.     ForwardIterator next = first;
  372.     return first == last ? first : remove_copy_if(++next, last, first, pred);
  373.   }
  374.  
  375.   template <class InputIterator, class ForwardIterator>
  376.   ForwardIterator __unique_copy (InputIterator first, InputIterator last,
  377.                                  ForwardIterator result, forward_iterator_tag);
  378.  
  379.   template <class InputIterator, class BidirectionalIterator>
  380.   inline BidirectionalIterator __unique_copy (InputIterator first, 
  381.                                               InputIterator last,
  382.                                               BidirectionalIterator result, 
  383.                                               bidirectional_iterator_tag)
  384.   {
  385.     return __unique_copy(first, last, result, forward_iterator_tag());
  386.   }
  387.  
  388.   template <class InputIterator, class RandomAccessIterator>
  389.   inline RandomAccessIterator __unique_copy (InputIterator first, 
  390.                                              InputIterator last,
  391.                                              RandomAccessIterator result, 
  392.                                              random_access_iterator_tag)
  393.   {
  394.     return __unique_copy(first, last, result, forward_iterator_tag());
  395.   }
  396.  
  397.   template <class InputIterator, class OutputIterator, class T>
  398.   OutputIterator __unique_copy (InputIterator first, InputIterator last,
  399.                                 OutputIterator result, T*);
  400.  
  401.   template <class InputIterator, class OutputIterator>
  402.   inline OutputIterator __unique_copy (InputIterator first, InputIterator last,
  403.                                        OutputIterator result, 
  404.                                        output_iterator_tag)
  405.   {
  406.     return __unique_copy(first, last, result, _RWSTD_VALUE_TYPE(first));
  407.   }
  408.  
  409.   template <class InputIterator, class OutputIterator>
  410.   inline OutputIterator unique_copy (InputIterator first, InputIterator last,
  411.                                      OutputIterator result)
  412.   {
  413.     return first == last ? result :
  414. #ifndef _RWSTD_NO_BASE_CLASS_MATCH
  415.     __unique_copy(first, last, result, __iterator_category(result));
  416. #else
  417.     __unique_copy(first, last, result, output_iterator_tag());
  418. #endif
  419.   }
  420.  
  421.   template <class InputIterator, class ForwardIterator, class BinaryPredicate>
  422.   ForwardIterator __unique_copy (InputIterator first, InputIterator last,
  423.                                  ForwardIterator result, 
  424.                                  BinaryPredicate binary_pred,
  425.                                  forward_iterator_tag);
  426.   template <class InputIterator, class BidirectionalIterator,
  427.   class BinaryPredicate>
  428.   inline BidirectionalIterator __unique_copy (InputIterator first, 
  429.                                               InputIterator last,
  430.                                               BidirectionalIterator result, 
  431.                                               BinaryPredicate binary_pred,
  432.                                               bidirectional_iterator_tag)
  433.   {
  434.     return __unique_copy(first, last, result, binary_pred,
  435.                          forward_iterator_tag());
  436.   }
  437.  
  438.   template <class InputIterator, class RandomAccessIterator,
  439.   class BinaryPredicate>
  440.   inline RandomAccessIterator __unique_copy (InputIterator first, 
  441.                                              InputIterator last,
  442.                                              RandomAccessIterator result, 
  443.                                              BinaryPredicate binary_pred,
  444.                                              random_access_iterator_tag)
  445.   {
  446.     return __unique_copy(first, last, result, binary_pred, 
  447.                          forward_iterator_tag());
  448.   }
  449.  
  450.   template <class InputIterator, class OutputIterator, class BinaryPredicate,
  451.   class T>
  452.   OutputIterator __unique_copy (InputIterator first, InputIterator last,
  453.                                 OutputIterator result,
  454.                                 BinaryPredicate binary_pred, T*);
  455.  
  456.   template <class InputIterator, class OutputIterator, class BinaryPredicate>
  457.   inline OutputIterator __unique_copy (InputIterator first, InputIterator last,
  458.                                        OutputIterator result,
  459.                                        BinaryPredicate binary_pred,
  460.                                        output_iterator_tag)
  461.   {
  462.     return __unique_copy(first, last, result, binary_pred,
  463.                          _RWSTD_VALUE_TYPE(first));
  464.   }
  465.  
  466.   template <class InputIterator, class OutputIterator, class BinaryPredicate>
  467.   inline OutputIterator unique_copy (InputIterator first, InputIterator last,
  468.                                      OutputIterator result,
  469.                                      BinaryPredicate binary_pred)
  470.   {
  471.     return first == last ? result :
  472. #ifndef _RWSTD_NO_BASE_CLASS_MATCH
  473.     __unique_copy(first, last, result, binary_pred, __iterator_category(result));
  474. #else
  475.     __unique_copy(first, last, result, binary_pred, output_iterator_tag());
  476. #endif
  477.   }
  478.  
  479.   template <class ForwardIterator>
  480.   inline ForwardIterator unique (ForwardIterator first, ForwardIterator last)
  481.   {
  482.     first = adjacent_find(first, last);
  483.     return unique_copy(first, last, first);
  484.   }
  485.  
  486.   template <class ForwardIterator, class BinaryPredicate>
  487.   inline ForwardIterator unique (ForwardIterator first, ForwardIterator last,
  488.                                  BinaryPredicate binary_pred)
  489.   {
  490.     first = adjacent_find(first, last, binary_pred);
  491.     return unique_copy(first, last, first, binary_pred);
  492.   }
  493.  
  494.   template <class BidirectionalIterator>
  495.   void __reverse (BidirectionalIterator first, BidirectionalIterator last, 
  496.                   bidirectional_iterator_tag);
  497.  
  498.   template <class RandomAccessIterator>
  499.   void __reverse (RandomAccessIterator first, RandomAccessIterator last,
  500.                   random_access_iterator_tag);
  501.  
  502.   template <class BidirectionalIterator>
  503.   inline void reverse (BidirectionalIterator first, BidirectionalIterator last)
  504.   {
  505. #ifndef _RWSTD_NO_BASE_CLASS_MATCH
  506.     __reverse(first, last, __iterator_category(first));
  507. #else
  508.     __reverse(first, last, bidirectional_iterator_tag());
  509. #endif
  510.   }
  511.  
  512.   template <class BidirectionalIterator, class OutputIterator>
  513.   OutputIterator reverse_copy (BidirectionalIterator first,
  514.                                BidirectionalIterator last,
  515.                                OutputIterator result);
  516.  
  517.   template <class ForwardIterator, class Distance>
  518.   void __rotate (ForwardIterator first, ForwardIterator middle,
  519.                  ForwardIterator last, Distance*, forward_iterator_tag);
  520.  
  521.   template <class BidirectionalIterator, class Distance>
  522.   inline void __rotate (BidirectionalIterator first, 
  523.                         BidirectionalIterator middle,
  524.                         BidirectionalIterator last, Distance*,
  525.                         bidirectional_iterator_tag)
  526.   {
  527.     reverse(first, middle);
  528.     reverse(middle, last);
  529.     reverse(first, last);
  530.   }
  531.  
  532.   template <class EuclideanRingElement>
  533.   EuclideanRingElement __gcd (EuclideanRingElement m, EuclideanRingElement n);
  534.  
  535.   template <class RandomAccessIterator, class Distance, class T>
  536.   void __rotate_cycle (RandomAccessIterator first, RandomAccessIterator last,
  537.                        RandomAccessIterator initial, Distance shift, T*);
  538.  
  539.   template <class RandomAccessIterator, class Distance>
  540.   void __rotate (RandomAccessIterator first, RandomAccessIterator middle,
  541.                  RandomAccessIterator last, Distance*,
  542.                  random_access_iterator_tag);
  543.  
  544.   template <class ForwardIterator>
  545.   inline void rotate (ForwardIterator first, ForwardIterator middle,
  546.                       ForwardIterator last)
  547.   {
  548.     if (!(first == middle || middle == last))
  549.     {
  550.  
  551. #ifndef _RWSTD_NO_BASE_CLASS_MATCH
  552.       __rotate(first, middle, last, __distance_type(first), __iterator_category(first));
  553. #else
  554.       __rotate(first, middle, last, __distance_type(first), forward_iterator_tag());
  555. #endif
  556.     }
  557.   }
  558.  
  559.   template <class ForwardIterator, class OutputIterator>
  560.   inline OutputIterator rotate_copy (ForwardIterator first,
  561.                                      ForwardIterator middle,
  562.                                      ForwardIterator last,
  563.                                      OutputIterator result)
  564.   {
  565.     return copy(first, middle, copy(middle, last, result));
  566.   }
  567.  
  568.   template <class RandomAccessIterator, class Distance>
  569.   void __random_shuffle (RandomAccessIterator first, RandomAccessIterator last,
  570.                          Distance*);
  571.  
  572.   template <class RandomAccessIterator>
  573.   inline void random_shuffle (RandomAccessIterator first,
  574.                               RandomAccessIterator last)
  575.   {
  576.     __random_shuffle(first, last, __distance_type(first));
  577.   }
  578.  
  579.   template <class RandomAccessIterator, class RandomNumberGenerator>
  580.   void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,
  581.                        RandomNumberGenerator& rand);
  582.  
  583.   template <class BidirectionalIterator, class Predicate>
  584.   BidirectionalIterator partition (BidirectionalIterator first,
  585.                                    BidirectionalIterator last, Predicate pred);
  586.  
  587.   template <class BidirectionalIterator, class Predicate, class Distance>
  588.   BidirectionalIterator __inplace_stable_partition (BidirectionalIterator first,
  589.                                                     BidirectionalIterator last,
  590.                                                     Predicate pred,
  591.                                                     Distance len);
  592.  
  593.   template <class BidirectionalIterator, class Pointer, class Predicate,
  594.   class Distance, class T>
  595.   BidirectionalIterator __stable_partition_adaptive (BidirectionalIterator first,
  596.                                                      BidirectionalIterator last,
  597.                                                      Predicate pred, Distance len,
  598.                                                      Pointer buffer,
  599.                                                      Distance buffer_size,
  600.                                                      Distance& fill_pointer, T*);
  601.  
  602.   template <class BidirectionalIterator, class Predicate, class Pointer,
  603.   class Distance>
  604.   BidirectionalIterator __stable_partition (BidirectionalIterator first,
  605.                                             BidirectionalIterator last,
  606.                                             Predicate pred, Distance len,
  607.                                             pair<Pointer, Distance> p);
  608.  
  609.   template <class BidirectionalIterator, class Predicate, class Distance>
  610.   inline BidirectionalIterator __stable_partition_aux (BidirectionalIterator first,
  611.                                                        BidirectionalIterator last, 
  612.                                                        Predicate pred,
  613.                                                        Distance*)
  614.   {
  615.     Distance len;
  616.     __initialize(len, Distance(0));
  617.     distance(first, last, len);
  618.  
  619.     return len == 0 ? last :
  620.     __stable_partition(first, last, pred, len,
  621. #ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
  622.            get_temporary_buffer<_TYPENAME 
  623.                iterator_traits<BidirectionalIterator>::value_type >(len));
  624. #else
  625.               get_temporary_buffer(len,_RWSTD_VALUE_TYPE(first)));
  626. #endif
  627.   }
  628.  
  629.   template <class BidirectionalIterator, class Predicate>
  630.   inline BidirectionalIterator stable_partition (BidirectionalIterator first,
  631.                                                  BidirectionalIterator last, 
  632.                                                  Predicate pred)
  633.   {
  634.     return __stable_partition_aux(first, last, pred, __distance_type(first));
  635.   }
  636.  
  637. //
  638. // Sorting and related operations.
  639. //
  640.  
  641.   template <class T>
  642.   inline const T& __median (const T& a, const T& b, const T& c)
  643.   {
  644.     if (a < b)
  645.       if (b < c)
  646.         return b;
  647.       else if (a < c)
  648.         return c;
  649.       else
  650.         return a;
  651.     else if (a < c)
  652.       return a;
  653.     else if (b < c)
  654.       return c;
  655.     else
  656.       return b;
  657.   }
  658.  
  659.   template <class T, class Compare>
  660.   inline const T& __median (const T& a, const T& b, const T& c, Compare comp)
  661.   {
  662.     if (comp(a, b))
  663.       if (comp(b, c))
  664.         return b;
  665.       else if (comp(a, c))
  666.         return c;
  667.       else
  668.         return a;
  669.     else if (comp(a, c))
  670.       return a;
  671.     else if (comp(b, c))
  672.       return c;
  673.     else
  674.       return b;
  675.   }
  676.  
  677.   template <class RandomAccessIterator, class T>
  678.   RandomAccessIterator __unguarded_partition (RandomAccessIterator first, 
  679.                                               RandomAccessIterator last, 
  680.                                               T pivot);
  681.  
  682.   template <class RandomAccessIterator, class T, class Compare>
  683.   RandomAccessIterator __unguarded_partition (RandomAccessIterator first, 
  684.                                               RandomAccessIterator last, 
  685.                                               T pivot, Compare comp);
  686.  
  687.   template <class RandomAccessIterator, class T>
  688.   void __quick_sort_loop_aux (RandomAccessIterator first,
  689.                               RandomAccessIterator last, T*);
  690.  
  691.   template <class RandomAccessIterator>
  692.   inline void __quick_sort_loop (RandomAccessIterator first,
  693.                                  RandomAccessIterator last)
  694.   {
  695.     __quick_sort_loop_aux(first, last, _RWSTD_VALUE_TYPE(first));
  696.   }
  697.  
  698.   template <class RandomAccessIterator, class T, class Compare>
  699.   void __quick_sort_loop_aux (RandomAccessIterator first, 
  700.                               RandomAccessIterator last, T*, Compare comp);
  701.  
  702.   template <class RandomAccessIterator, class Compare>
  703.   inline void __quick_sort_loop (RandomAccessIterator first, 
  704.                                  RandomAccessIterator last, Compare comp)
  705.   {
  706.     __quick_sort_loop_aux(first, last, _RWSTD_VALUE_TYPE(first), comp);
  707.   }
  708.  
  709.   template <class RandomAccessIterator, class T>
  710.   void __unguarded_linear_insert (RandomAccessIterator last, T value);
  711.  
  712.   template <class RandomAccessIterator, class T, class Compare>
  713.   void __unguarded_linear_insert (RandomAccessIterator last,T value,Compare comp);
  714.  
  715.   template <class RandomAccessIterator, class T>
  716.   inline void __linear_insert (RandomAccessIterator first, 
  717.                                RandomAccessIterator last, T*)
  718.   {
  719.     T value = *last;
  720.     if (value < *first)
  721.     {
  722.       copy_backward(first, last, last + 1);
  723.       *first = value;
  724.     }
  725.     else
  726.       __unguarded_linear_insert(last, value);
  727.   }
  728.  
  729.   template <class RandomAccessIterator, class T, class Compare>
  730.   inline void __linear_insert (RandomAccessIterator first, 
  731.                                RandomAccessIterator last, T*, Compare comp)
  732.   {
  733.     T value = *last;
  734.     if (comp(value, *first))
  735.     {
  736.       copy_backward(first, last, last + 1);
  737.       *first = value;
  738.     }
  739.     else
  740.       __unguarded_linear_insert(last, value, comp);
  741.   }
  742.  
  743.   template <class RandomAccessIterator>
  744.   void __insertion_sort (RandomAccessIterator first, RandomAccessIterator last);
  745.  
  746.   template <class RandomAccessIterator, class Compare>
  747.   void __insertion_sort (RandomAccessIterator first,
  748.                          RandomAccessIterator last, Compare comp);
  749.  
  750.   template <class RandomAccessIterator, class T>
  751.   void __unguarded_insertion_sort_aux (RandomAccessIterator first, 
  752.                                        RandomAccessIterator last, T*);
  753.  
  754.   template <class RandomAccessIterator>
  755.   inline void __unguarded_insertion_sort(RandomAccessIterator first, 
  756.                                          RandomAccessIterator last)
  757.   {
  758.     __unguarded_insertion_sort_aux(first, last, _RWSTD_VALUE_TYPE(first));
  759.   }
  760.  
  761.   template <class RandomAccessIterator, class T, class Compare>
  762.   void __unguarded_insertion_sort_aux (RandomAccessIterator first, 
  763.                                        RandomAccessIterator last,
  764.                                        T*, Compare comp);
  765.  
  766.   template <class RandomAccessIterator, class Compare>
  767.   inline void __unguarded_insertion_sort (RandomAccessIterator first, 
  768.                                           RandomAccessIterator last,
  769.                                           Compare comp)
  770.   {
  771.     __unguarded_insertion_sort_aux(first, last, _RWSTD_VALUE_TYPE(first), comp);
  772.   }
  773.  
  774.   template <class RandomAccessIterator>
  775.   void __final_insertion_sort (RandomAccessIterator first, 
  776.                                RandomAccessIterator last);
  777.  
  778.   template <class RandomAccessIterator, class Compare>
  779.   void __final_insertion_sort (RandomAccessIterator first, 
  780.                                RandomAccessIterator last, Compare comp);
  781.  
  782.   template <class RandomAccessIterator>
  783.   inline void sort (RandomAccessIterator first, RandomAccessIterator last)
  784.   {
  785.     if (!(first == last))
  786.     {
  787.       __quick_sort_loop(first, last);
  788.       __final_insertion_sort(first, last);
  789.     }
  790.   }
  791.  
  792.   template <class RandomAccessIterator, class Compare>
  793.   inline void sort (RandomAccessIterator first, 
  794.                     RandomAccessIterator last, Compare comp)
  795.   {
  796.     if (!(first == last))
  797.     {
  798.       __quick_sort_loop(first, last, comp);
  799.       __final_insertion_sort(first, last, comp);
  800.     }
  801.   }
  802.  
  803.   template <class RandomAccessIterator>
  804.   inline void __inplace_stable_sort (RandomAccessIterator first,
  805.                                      RandomAccessIterator last)
  806.   {
  807.     if (last - first < 15)
  808.       __insertion_sort(first, last);
  809.     else
  810.     {
  811.       RandomAccessIterator middle = first + (last - first) / 2;
  812.       __inplace_stable_sort(first, middle);
  813.       __inplace_stable_sort(middle, last);
  814.       __merge_without_buffer(first, middle, last, middle - first,
  815.                              last - middle);
  816.     }
  817.   }
  818.  
  819.   template <class RandomAccessIterator, class Compare>
  820.   inline void __inplace_stable_sort (RandomAccessIterator first,
  821.                                      RandomAccessIterator last, Compare comp)
  822.   {
  823.     if (last - first < 15)
  824.       __insertion_sort(first, last, comp);
  825.     else
  826.     {
  827.       RandomAccessIterator middle = first + (last - first) / 2;
  828.       __inplace_stable_sort(first, middle, comp);
  829.       __inplace_stable_sort(middle, last, comp);
  830.       __merge_without_buffer(first, middle, last, middle - first,
  831.                              last - middle, comp);
  832.     }
  833.   }
  834.  
  835.   template <class RandomAccessIterator1, class RandomAccessIterator2,
  836.   class Distance>
  837.   void __merge_sort_loop (RandomAccessIterator1 first,
  838.                           RandomAccessIterator1 last, 
  839.                           RandomAccessIterator2 result, Distance step_size);
  840.  
  841.   template <class RandomAccessIterator1, class RandomAccessIterator2,
  842.   class Distance, class Compare>
  843.   void __merge_sort_loop (RandomAccessIterator1 first,
  844.                           RandomAccessIterator1 last, 
  845.                           RandomAccessIterator2 result, Distance step_size,
  846.                           Compare comp);
  847.  
  848.   template <class RandomAccessIterator, class Distance>
  849.   void __chunk_insertion_sort (RandomAccessIterator first, 
  850.                                RandomAccessIterator last, Distance chunk_size);
  851.  
  852.   template <class RandomAccessIterator, class Distance, class Compare>
  853.   void __chunk_insertion_sort (RandomAccessIterator first, 
  854.                                RandomAccessIterator last,
  855.                                Distance chunk_size, Compare comp);
  856.  
  857.   template <class RandomAccessIterator, class Pointer, class Distance, class T>
  858.   void __merge_sort_with_buffer (RandomAccessIterator first, 
  859.                                  RandomAccessIterator last,
  860.                                  Pointer buffer, Distance*, T*);
  861.  
  862.   template <class RandomAccessIterator, class Pointer, class Distance, class T,
  863.   class Compare>
  864.   void __merge_sort_with_buffer (RandomAccessIterator first, 
  865.                                  RandomAccessIterator last, Pointer buffer,
  866.                                  Distance*, T*, Compare comp);
  867.  
  868.   template <class RandomAccessIterator, class Pointer, class Distance, class T>
  869.   void __stable_sort_adaptive (RandomAccessIterator first, 
  870.                                RandomAccessIterator last, Pointer buffer,
  871.                                Distance buffer_size, T*);
  872.  
  873.   template <class RandomAccessIterator, class Pointer, class Distance, class T,
  874.   class Compare>
  875.   void __stable_sort_adaptive (RandomAccessIterator first, 
  876.                                RandomAccessIterator last, Pointer buffer,
  877.                                Distance buffer_size, T*, Compare comp);
  878.  
  879.   template <class RandomAccessIterator, class Pointer, class Distance, class T>
  880.   inline void __stable_sort (RandomAccessIterator first,
  881.                              RandomAccessIterator last,
  882.                              pair<Pointer, Distance>& p, T*)
  883.   {
  884.     if (p.first == 0)
  885.       __inplace_stable_sort(first, last);
  886.     else
  887.     {
  888.       Distance len = min((int)p.second, (int)(last - first));
  889.       copy(first, first + len, raw_storage_iterator<Pointer, T>(p.first));
  890.       __stable_sort_adaptive(first, last, p.first, p.second, _RWSTD_STATIC_CAST(T*,0));
  891.       __RWSTD::__destroy(p.first, p.first + len);
  892.       return_temporary_buffer(p.first);
  893.     }
  894.   }
  895.  
  896.   template <class RandomAccessIterator, class Pointer, class Distance, class T,
  897.   class Compare>
  898.   inline void __stable_sort (RandomAccessIterator first,
  899.                              RandomAccessIterator last,
  900.                              pair<Pointer, Distance>& p, T*, Compare comp)
  901.   {
  902.     if (p.first == 0)
  903.       __inplace_stable_sort(first, last, comp);
  904.     else
  905.     {
  906.       Distance len = min((int)p.second, (int)(last - first));
  907.       copy(first, first + len, raw_storage_iterator<Pointer, T>(p.first));
  908.       __stable_sort_adaptive(first, last, p.first, p.second, _RWSTD_STATIC_CAST(T*,0), comp);
  909.       __RWSTD::__destroy(p.first, p.first + len);
  910.       return_temporary_buffer(p.first);
  911.     }
  912.   }
  913.  
  914.   template <class RandomAccessIterator, class T, class Distance>
  915.   inline void __stable_sort_aux (RandomAccessIterator first,
  916.                                  RandomAccessIterator last, T*, Distance*)
  917.   {
  918.  
  919.     pair<T*, Distance> tmp = 
  920. #ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
  921.          get_temporary_buffer<T>(Distance(last-first));
  922. #else
  923.          get_temporary_buffer(Distance(last-first),_RWSTD_STATIC_CAST(T*,0));
  924. #endif
  925.     __stable_sort(first, last, tmp, _RWSTD_STATIC_CAST(T*,0));
  926.   }
  927.  
  928.   template <class RandomAccessIterator, class T, class Distance, class Compare>
  929.   inline void __stable_sort_aux (RandomAccessIterator first,
  930.                                  RandomAccessIterator last, T*, Distance*,
  931.                                  Compare comp)
  932.   {
  933.     pair<T*, Distance> tmp = 
  934. #ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
  935.         get_temporary_buffer<T>(Distance(last-first));
  936. #else
  937.         get_temporary_buffer(Distance(last-first),_RWSTD_STATIC_CAST(T*,0));
  938. #endif
  939.     __stable_sort(first, last, tmp, _RWSTD_STATIC_CAST(T*,0), comp);
  940.   }
  941.  
  942.   template <class RandomAccessIterator>
  943.   inline void stable_sort (RandomAccessIterator first,
  944.                            RandomAccessIterator last)
  945.   {
  946.     if (!(first == last))
  947.     {
  948.       __stable_sort_aux(first, last, _RWSTD_VALUE_TYPE(first),
  949.                         __distance_type(first));
  950.     }
  951.   }
  952.  
  953.   template <class RandomAccessIterator, class Compare>
  954.   inline void stable_sort (RandomAccessIterator first,
  955.                            RandomAccessIterator last, Compare comp)
  956.   {
  957.     if (!(first == last))
  958.     {
  959.       __stable_sort_aux(first, last, _RWSTD_VALUE_TYPE(first),
  960.                         __distance_type(first), comp);
  961.     }
  962.   }
  963.  
  964.   template <class RandomAccessIterator, class T>
  965.   void __partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
  966.                        RandomAccessIterator last, T*);
  967.  
  968.   template <class RandomAccessIterator>
  969.   inline void partial_sort (RandomAccessIterator first,
  970.                             RandomAccessIterator middle,
  971.                             RandomAccessIterator last)
  972.   {
  973.     if (!(first == middle))
  974.       __partial_sort(first, middle, last, _RWSTD_VALUE_TYPE(first));
  975.   }
  976.  
  977.   template <class RandomAccessIterator, class T, class Compare>
  978.   void __partial_sort (RandomAccessIterator first, RandomAccessIterator middle,
  979.                        RandomAccessIterator last, T*, Compare comp);
  980.  
  981.   template <class RandomAccessIterator, class Compare>
  982.   inline void partial_sort (RandomAccessIterator first,
  983.                             RandomAccessIterator middle,
  984.                             RandomAccessIterator last, Compare comp)
  985.   {
  986.     if (!(first == middle))
  987.       __partial_sort(first, middle, last, _RWSTD_VALUE_TYPE(first), comp);
  988.   }
  989.  
  990.   template <class InputIterator, class RandomAccessIterator, class Distance,
  991.   class T>
  992.   RandomAccessIterator __partial_sort_copy (InputIterator first,
  993.                                             InputIterator last,
  994.                                             RandomAccessIterator result_first,
  995.                                             RandomAccessIterator result_last, 
  996.                                             Distance*, T*);
  997.  
  998.   template <class InputIterator, class RandomAccessIterator>
  999.   inline RandomAccessIterator
  1000.   partial_sort_copy (InputIterator first, InputIterator last,
  1001.                      RandomAccessIterator result_first,
  1002.                      RandomAccessIterator result_last)
  1003.   {
  1004.     return first == last ? result_first :
  1005.     __partial_sort_copy(first, last, result_first, result_last, 
  1006.                         __distance_type(result_first),
  1007.                         _RWSTD_VALUE_TYPE(first));
  1008.   }
  1009.  
  1010.   template <class InputIterator, class RandomAccessIterator, class Compare,
  1011.   class Distance, class T>
  1012.   RandomAccessIterator __partial_sort_copy (InputIterator first,
  1013.                                             InputIterator last,
  1014.                                             RandomAccessIterator result_first,
  1015.                                             RandomAccessIterator result_last,
  1016.                                             Compare comp, Distance*, T*);
  1017.  
  1018.   template <class InputIterator, class RandomAccessIterator, class Compare>
  1019.   inline RandomAccessIterator
  1020.   partial_sort_copy (InputIterator first, InputIterator last,
  1021.                      RandomAccessIterator result_first,
  1022.                      RandomAccessIterator result_last, Compare comp)
  1023.   {
  1024.     return first == last ? result_first :
  1025.     __partial_sort_copy(first, last, result_first, result_last, comp,
  1026.                         __distance_type(result_first),
  1027.                         _RWSTD_VALUE_TYPE(first));
  1028.   }
  1029.  
  1030.   template <class RandomAccessIterator, class T>
  1031.   void __nth_element (RandomAccessIterator first, RandomAccessIterator nth,
  1032.                       RandomAccessIterator last, T*);
  1033.  
  1034.   template <class RandomAccessIterator>
  1035.   inline void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
  1036.                            RandomAccessIterator last)
  1037.   {
  1038.     if (!(first == last))
  1039.       __nth_element(first, nth, last, _RWSTD_VALUE_TYPE(first));
  1040.   }
  1041.  
  1042.   template <class RandomAccessIterator, class T, class Compare>
  1043.   void __nth_element (RandomAccessIterator first, RandomAccessIterator nth,
  1044.                       RandomAccessIterator last, T*, Compare comp);
  1045.  
  1046.   template <class RandomAccessIterator, class Compare>
  1047.   inline void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
  1048.                            RandomAccessIterator last, Compare comp)
  1049.   {
  1050.     if (!(first == last))
  1051.       __nth_element(first, nth, last, _RWSTD_VALUE_TYPE(first), comp);
  1052.   }
  1053.  
  1054. //
  1055. // Binary search.
  1056. //
  1057.  
  1058.   template <class ForwardIterator, class T, class Distance>
  1059.   ForwardIterator __lower_bound (ForwardIterator first, ForwardIterator last,
  1060.                                  const T& value, Distance*,
  1061.                                  forward_iterator_tag);
  1062.  
  1063.   template <class ForwardIterator, class T, class Distance>
  1064.   inline ForwardIterator __lower_bound (ForwardIterator first,
  1065.                                         ForwardIterator last,
  1066.                                         const T& value, Distance*,
  1067.                                         bidirectional_iterator_tag)
  1068.   {
  1069.     return __lower_bound(first, last, value, _RWSTD_STATIC_CAST(Distance*,0),
  1070.                          forward_iterator_tag());
  1071.   }
  1072.  
  1073.   template <class RandomAccessIterator, class T, class Distance>
  1074.   RandomAccessIterator __lower_bound (RandomAccessIterator first,
  1075.                                       RandomAccessIterator last, const T& value,
  1076.                                       Distance*, random_access_iterator_tag);
  1077.  
  1078.   template <class ForwardIterator, class T>
  1079.   inline ForwardIterator lower_bound (ForwardIterator first,ForwardIterator last,
  1080.                                       const T& value)
  1081.   {
  1082.  
  1083. #ifndef _RWSTD_NO_BASE_CLASS_MATCH
  1084.     return __lower_bound(first, last, value, __distance_type(first),                         __iterator_category(first));
  1085. #else
  1086.     return __lower_bound(first, last, value, __distance_type(first), 
  1087.                          forward_iterator_tag());
  1088. #endif
  1089.   }
  1090.  
  1091.   template <class ForwardIterator, class T, class Compare, class Distance>
  1092.   ForwardIterator __lower_bound (ForwardIterator first, ForwardIterator last,
  1093.                                  const T& value, Compare comp, Distance*,
  1094.                                  forward_iterator_tag);
  1095.  
  1096.   template <class ForwardIterator, class T, class Compare, class Distance>
  1097.   inline ForwardIterator __lower_bound (ForwardIterator first,
  1098.                                         ForwardIterator last,
  1099.                                         const T& value, Compare comp, Distance*,
  1100.                                         bidirectional_iterator_tag)
  1101.   {
  1102.     return __lower_bound(first, last, value, comp,_RWSTD_STATIC_CAST(Distance*,0),
  1103.                          forward_iterator_tag());
  1104.   }
  1105.  
  1106.   template <class RandomAccessIterator, class T, class Compare, class Distance>
  1107.   RandomAccessIterator __lower_bound (RandomAccessIterator first,
  1108.                                       RandomAccessIterator last,
  1109.                                       const T& value, Compare comp, Distance*,
  1110.                                       random_access_iterator_tag);
  1111.  
  1112.   template <class ForwardIterator, class T, class Compare>
  1113.   inline ForwardIterator lower_bound (ForwardIterator first,ForwardIterator last,
  1114.                                       const T& value, Compare comp)
  1115.   {
  1116. #ifndef _RWSTD_NO_BASE_CLASS_MATCH
  1117.     return __lower_bound(first, last, value, comp, __distance_type(first),
  1118.                          __iterator_category(first));
  1119. #else
  1120.     return __lower_bound(first, last, value, comp, __distance_type(first),
  1121.                          forward_iterator_tag());
  1122. #endif
  1123.   }
  1124.  
  1125.   template <class ForwardIterator, class T, class Distance>
  1126.   ForwardIterator __upper_bound (ForwardIterator first, ForwardIterator last,
  1127.                                  const T& value, Distance*,
  1128.                                  forward_iterator_tag);
  1129.  
  1130.   template <class ForwardIterator, class T, class Distance>
  1131.   inline ForwardIterator __upper_bound (ForwardIterator first,
  1132.                                         ForwardIterator last,
  1133.                                         const T& value, Distance*,
  1134.                                         bidirectional_iterator_tag)
  1135.   {
  1136.     return __upper_bound(first, last, value, _RWSTD_STATIC_CAST(Distance*,0),
  1137.                          forward_iterator_tag());
  1138.   }
  1139.  
  1140.   template <class RandomAccessIterator, class T, class Distance>
  1141.   RandomAccessIterator __upper_bound (RandomAccessIterator first,
  1142.                                       RandomAccessIterator last, const T& value,
  1143.                                       Distance*, random_access_iterator_tag);
  1144.  
  1145.   template <class ForwardIterator, class T>
  1146.   inline ForwardIterator upper_bound (ForwardIterator first,ForwardIterator last,
  1147.                                       const T& value)
  1148.   {
  1149. #ifndef _RWSTD_NO_BASE_CLASS_MATCH
  1150.     return __upper_bound(first, last, value, __distance_type(first),
  1151.                          __iterator_category(first));
  1152. #else
  1153.     return __upper_bound(first, last, value, __distance_type(first),
  1154.                          forward_iterator_tag());
  1155. #endif
  1156.   }
  1157.  
  1158.   template <class ForwardIterator, class T, class Compare, class Distance>
  1159.   ForwardIterator __upper_bound (ForwardIterator first, ForwardIterator last,
  1160.                                  const T& value, Compare comp, Distance*,
  1161.                                  forward_iterator_tag);
  1162.  
  1163.   template <class ForwardIterator, class T, class Compare, class Distance>
  1164.   inline ForwardIterator __upper_bound (ForwardIterator first,
  1165.                                         ForwardIterator last,
  1166.                                         const T& value, Compare comp, Distance*,
  1167.                                         bidirectional_iterator_tag)
  1168.   {
  1169.     return __upper_bound(first, last, value, comp, _RWSTD_STATIC_CAST(Distance*,0),
  1170.                          forward_iterator_tag());
  1171.   }
  1172.  
  1173.   template <class RandomAccessIterator, class T, class Compare, class Distance>
  1174.   RandomAccessIterator __upper_bound (RandomAccessIterator first,
  1175.                                       RandomAccessIterator last,
  1176.                                       const T& value, Compare comp, Distance*,
  1177.                                       random_access_iterator_tag);
  1178.  
  1179.   template <class ForwardIterator, class T, class Compare>
  1180.   inline ForwardIterator upper_bound (ForwardIterator first,ForwardIterator last,
  1181.                                       const T& value, Compare comp)
  1182.   {
  1183. #ifndef _RWSTD_NO_BASE_CLASS_MATCH
  1184.     return __upper_bound(first, last, value, comp, __distance_type(first),
  1185.                          __iterator_category(first));
  1186. #else
  1187.     return __upper_bound(first, last, value, comp, __distance_type(first),
  1188.                          forward_iterator_tag());
  1189. #endif
  1190.   }
  1191.  
  1192.   template <class ForwardIterator, class T, class Distance>
  1193.   pair<ForwardIterator, ForwardIterator>
  1194.   __equal_range (ForwardIterator first, ForwardIterator last, const T& value,
  1195.                  Distance*, forward_iterator_tag);
  1196.  
  1197.   template <class ForwardIterator, class T, class Distance>
  1198.   inline pair<ForwardIterator, ForwardIterator>
  1199.   __equal_range (ForwardIterator first, ForwardIterator last, const T& value,
  1200.                  Distance*, bidirectional_iterator_tag)
  1201.   {
  1202.     return __equal_range(first, last, value, _RWSTD_STATIC_CAST(Distance*,0), 
  1203.                          forward_iterator_tag());
  1204.   }
  1205.  
  1206.   template <class RandomAccessIterator, class T, class Distance>
  1207.   pair<RandomAccessIterator, RandomAccessIterator>
  1208.   __equal_range (RandomAccessIterator first, RandomAccessIterator last,
  1209.                  const T& value, Distance*, random_access_iterator_tag);
  1210.  
  1211.   template <class ForwardIterator, class T>
  1212.   inline pair<ForwardIterator, ForwardIterator>
  1213.   equal_range (ForwardIterator first, ForwardIterator last, const T& value)
  1214.   {
  1215. #ifndef _RWSTD_NO_BASE_CLASS_MATCH
  1216.     return __equal_range(first, last, value, __distance_type(first),
  1217.                          __iterator_category(first));
  1218. #else
  1219.     return __equal_range(first, last, value, __distance_type(first),
  1220.                          forward_iterator_tag());
  1221. #endif
  1222.   }
  1223.  
  1224.   template <class ForwardIterator, class T, class Compare, class Distance>
  1225.   pair<ForwardIterator, ForwardIterator>
  1226.   __equal_range (ForwardIterator first, ForwardIterator last, const T& value,
  1227.                  Compare comp, Distance*, forward_iterator_tag);
  1228.  
  1229.   template <class ForwardIterator, class T, class Compare, class Distance>
  1230.   inline pair<ForwardIterator, ForwardIterator>
  1231.   __equal_range (ForwardIterator first, ForwardIterator last, const T& value,
  1232.                  Compare comp, Distance*, bidirectional_iterator_tag)
  1233.   {
  1234.     return __equal_range(first, last, value, comp, _RWSTD_STATIC_CAST(Distance*,0), 
  1235.                          forward_iterator_tag());
  1236.   }
  1237.  
  1238.   template <class RandomAccessIterator, class T, class Compare, class Distance>
  1239.   pair<RandomAccessIterator, RandomAccessIterator>
  1240.   __equal_range (RandomAccessIterator first, RandomAccessIterator last,
  1241.                  const T& value, Compare comp, Distance*,
  1242.                  random_access_iterator_tag);
  1243.  
  1244.   template <class ForwardIterator, class T, class Compare>
  1245.   inline pair<ForwardIterator, ForwardIterator>
  1246.   equal_range (ForwardIterator first, ForwardIterator last, const T& value,
  1247.                Compare comp)
  1248.   {
  1249. #ifndef _RWSTD_NO_BASE_CLASS_MATCH
  1250.     return __equal_range(first, last, value, comp, __distance_type(first),
  1251.                          __iterator_category(first));
  1252. #else
  1253.     return __equal_range(first, last, value, comp, __distance_type(first),
  1254.                          forward_iterator_tag());
  1255. #endif
  1256.   }    
  1257.  
  1258.   template <class ForwardIterator, class T>
  1259.   inline bool binary_search (ForwardIterator first, ForwardIterator last,
  1260.                              const T& value)
  1261.   {
  1262.     ForwardIterator i = lower_bound(first, last, value);
  1263.     return i != last && !(value < *i);
  1264.   }
  1265.  
  1266.   template <class ForwardIterator, class T, class Compare>
  1267.   inline bool binary_search (ForwardIterator first, ForwardIterator last,
  1268.                              const T& value, Compare comp)
  1269.   {
  1270.     ForwardIterator i = lower_bound(first, last, value, comp);
  1271.     return i != last && !comp(value, *i);
  1272.   }
  1273.  
  1274. //
  1275. // Merge
  1276. //
  1277.  
  1278.   template <class InputIterator1, class InputIterator2, class OutputIterator>
  1279.   OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
  1280.                         InputIterator2 first2, InputIterator2 last2,
  1281.                         OutputIterator result);
  1282.  
  1283.   template <class InputIterator1, class InputIterator2, class OutputIterator,
  1284.   class Compare>
  1285.   OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
  1286.                         InputIterator2 first2, InputIterator2 last2,
  1287.                         OutputIterator result, Compare comp);
  1288.  
  1289.   template <class BidirectionalIterator, class Distance>
  1290.   void __merge_without_buffer (BidirectionalIterator first,
  1291.                                BidirectionalIterator middle,
  1292.                                BidirectionalIterator last,
  1293.                                Distance len1, Distance len2);
  1294.  
  1295.   template <class BidirectionalIterator, class Distance, class Compare>
  1296.   void __merge_without_buffer (BidirectionalIterator first,
  1297.                                BidirectionalIterator middle,
  1298.                                BidirectionalIterator last,
  1299.                                Distance len1, Distance len2, Compare comp);
  1300.  
  1301.   template <class BidirectionalIterator1, class BidirectionalIterator2,
  1302.   class Distance>
  1303.   BidirectionalIterator1 __rotate_adaptive (BidirectionalIterator1 first,
  1304.                                             BidirectionalIterator1 middle,
  1305.                                             BidirectionalIterator1 last,
  1306.                                             Distance len1, Distance len2,
  1307.                                             BidirectionalIterator2 buffer,
  1308.                                             Distance buffer_size);
  1309.  
  1310.   template <class BidirectionalIterator1, class BidirectionalIterator2,
  1311.   class BidirectionalIterator3>
  1312.   BidirectionalIterator3 __merge_backward (BidirectionalIterator1 first1,
  1313.                                            BidirectionalIterator1 last1,
  1314.                                            BidirectionalIterator2 first2,
  1315.                                            BidirectionalIterator2 last2,
  1316.                                            BidirectionalIterator3 result);
  1317.  
  1318.   template <class BidirectionalIterator1, class BidirectionalIterator2,
  1319.   class BidirectionalIterator3, class Compare>
  1320.   BidirectionalIterator3 __merge_backward (BidirectionalIterator1 first1,
  1321.                                            BidirectionalIterator1 last1,
  1322.                                            BidirectionalIterator2 first2,
  1323.                                            BidirectionalIterator2 last2,
  1324.                                            BidirectionalIterator3 result,
  1325.                                            Compare comp);
  1326.  
  1327.   template <class BidirectionalIterator, class Distance, class Pointer, class T>
  1328.   void __merge_adaptive (BidirectionalIterator first,
  1329.                          BidirectionalIterator middle,
  1330.                          BidirectionalIterator last, Distance len1,Distance len2,
  1331.                          Pointer buffer, Distance buffer_size, T*);
  1332.  
  1333.   template <class BidirectionalIterator, class Distance, class Pointer, class T,
  1334.   class Compare>
  1335.   void __merge_adaptive (BidirectionalIterator first,
  1336.                          BidirectionalIterator middle,
  1337.                          BidirectionalIterator last, Distance len1,Distance len2,
  1338.                          Pointer buffer, Distance buffer_size, T*, Compare comp);
  1339.  
  1340.   template <class BidirectionalIterator, class Distance, class Pointer, class T>
  1341.   void __inplace_merge (BidirectionalIterator first,
  1342.                         BidirectionalIterator middle, 
  1343.                         BidirectionalIterator last, Distance len1,
  1344.                         Distance len2, pair<Pointer, Distance> p, T*);
  1345.  
  1346.   template <class BidirectionalIterator, class Distance, class Pointer, class T,
  1347.   class Compare>
  1348.   void __inplace_merge (BidirectionalIterator first,
  1349.                         BidirectionalIterator middle,
  1350.                         BidirectionalIterator last, Distance len1,
  1351.                         Distance len2, pair<Pointer, Distance> p, T*,
  1352.                         Compare comp);
  1353.  
  1354.   template <class BidirectionalIterator, class T, class Distance>
  1355.   inline void __inplace_merge_aux (BidirectionalIterator first,
  1356.                                    BidirectionalIterator middle,
  1357.                                    BidirectionalIterator last, T*, Distance*)
  1358.   {
  1359.     Distance len1;
  1360.     __initialize(len1, Distance(0));
  1361.     distance(first, middle, len1);
  1362.     Distance len2;
  1363.     __initialize(len2, Distance(0));
  1364.     distance(middle, last, len2);
  1365.     __inplace_merge(first, middle, last, len1, len2, 
  1366. #ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
  1367.         get_temporary_buffer<T>(len1+len2),_RWSTD_STATIC_CAST(T*,0));
  1368. #else
  1369.         get_temporary_buffer(len1+len2,_RWSTD_STATIC_CAST(T*,0)),_RWSTD_STATIC_CAST(T*,0));
  1370. #endif
  1371.  
  1372.   }
  1373.  
  1374.   template <class BidirectionalIterator, class T, class Distance, class Compare>
  1375.   inline void __inplace_merge_aux (BidirectionalIterator first,
  1376.                                    BidirectionalIterator middle,
  1377.                                    BidirectionalIterator last, T*, Distance*,
  1378.                                    Compare comp)
  1379.   {
  1380.     Distance len1;
  1381.     __initialize(len1, Distance(0));
  1382.     distance(first, middle, len1);
  1383.     Distance len2;
  1384.     __initialize(len2, Distance(0));
  1385.     distance(middle, last, len2);
  1386.     __inplace_merge(first, middle, last, len1, len2, 
  1387. #ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
  1388.         get_temporary_buffer<T>(len1+len2), _RWSTD_STATIC_CAST(T*,0), comp);
  1389. #else
  1390.         get_temporary_buffer(len1 + len2, _RWSTD_STATIC_CAST(T*,0)), _RWSTD_STATIC_CAST(T*,0), comp);
  1391. #endif
  1392.   }
  1393.  
  1394.   template <class BidirectionalIterator>
  1395.   inline void inplace_merge (BidirectionalIterator first,
  1396.                              BidirectionalIterator middle,
  1397.                              BidirectionalIterator last)
  1398.   {
  1399.     if (!(first == middle || middle == last))
  1400.       __inplace_merge_aux(first, middle, last, _RWSTD_VALUE_TYPE(first),
  1401.                           __distance_type(first));
  1402.   }
  1403.  
  1404.   template <class BidirectionalIterator, class Compare>
  1405.   inline void inplace_merge (BidirectionalIterator first,
  1406.                              BidirectionalIterator middle,
  1407.                              BidirectionalIterator last, Compare comp)
  1408.   {
  1409.     if (!(first == middle || middle == last))
  1410.       __inplace_merge_aux(first, middle, last, _RWSTD_VALUE_TYPE(first),
  1411.                           __distance_type(first), comp);
  1412.   }
  1413.  
  1414. //
  1415. // Set operations.
  1416. //
  1417.  
  1418.   template <class InputIterator1, class InputIterator2>
  1419.   bool includes (InputIterator1 first1, InputIterator1 last1,
  1420.                  InputIterator2 first2, InputIterator2 last2);
  1421.  
  1422.   template <class InputIterator1, class InputIterator2, class Compare>
  1423.   bool includes (InputIterator1 first1, InputIterator1 last1,
  1424.                  InputIterator2 first2, InputIterator2 last2, 
  1425.                  Compare comp);
  1426.  
  1427.   template <class InputIterator1, class InputIterator2, class OutputIterator>
  1428.   OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
  1429.                             InputIterator2 first2, InputIterator2 last2,
  1430.                             OutputIterator result);
  1431.  
  1432.   template <class InputIterator1, class InputIterator2, class OutputIterator,
  1433.   class Compare>
  1434.   OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
  1435.                             InputIterator2 first2, InputIterator2 last2,
  1436.                             OutputIterator result, Compare comp);
  1437.  
  1438.   template <class InputIterator1, class InputIterator2, class OutputIterator>
  1439.   OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
  1440.                                    InputIterator2 first2, InputIterator2 last2,
  1441.                                    OutputIterator result);
  1442.  
  1443.   template <class InputIterator1, class InputIterator2, class OutputIterator,
  1444.   class Compare>
  1445.   OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
  1446.                                    InputIterator2 first2, InputIterator2 last2,
  1447.                                    OutputIterator result, Compare comp);
  1448.  
  1449.   template <class InputIterator1, class InputIterator2, class OutputIterator>
  1450.   OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,
  1451.                                  InputIterator2 first2, InputIterator2 last2,
  1452.                                  OutputIterator result);
  1453.  
  1454.   template <class InputIterator1, class InputIterator2, class OutputIterator, 
  1455.   class Compare>
  1456.   OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,
  1457.                                  InputIterator2 first2, InputIterator2 last2, 
  1458.                                  OutputIterator result, Compare comp);
  1459.  
  1460.   template <class InputIterator1, class InputIterator2, class OutputIterator>
  1461.   OutputIterator set_symmetric_difference (InputIterator1 first1,
  1462.                                            InputIterator1 last1,
  1463.                                            InputIterator2 first2,
  1464.                                            InputIterator2 last2,
  1465.                                            OutputIterator result);
  1466.  
  1467.   template <class InputIterator1, class InputIterator2, class OutputIterator,
  1468.   class Compare>
  1469.   OutputIterator set_symmetric_difference (InputIterator1 first1,
  1470.                                            InputIterator1 last1,
  1471.                                            InputIterator2 first2,
  1472.                                            InputIterator2 last2,
  1473.                                            OutputIterator result, 
  1474.                                            Compare comp);
  1475.  
  1476. //
  1477. // Heap operations.
  1478. //
  1479.  
  1480.   template <class RandomAccessIterator, class Distance, class T>
  1481.   void __push_heap (RandomAccessIterator first, Distance holeIndex,
  1482.                     Distance topIndex, T value);
  1483.  
  1484.   template <class RandomAccessIterator, class Distance, class T>
  1485.   inline void __push_heap_aux (RandomAccessIterator first,
  1486.                                RandomAccessIterator last, Distance*, T*)
  1487.   {
  1488.     __push_heap(first, Distance((last-first)-1), Distance(0), T(*(last-1)));
  1489.   }
  1490.  
  1491.   template <class RandomAccessIterator>
  1492.   inline void push_heap (RandomAccessIterator first, RandomAccessIterator last)
  1493.   {
  1494.     if (!(first == last))
  1495.       __push_heap_aux(first, last, __distance_type(first),
  1496.                       _RWSTD_VALUE_TYPE(first));
  1497.   }
  1498.  
  1499.   template <class RandomAccessIterator, class Distance, class T, class Compare>
  1500.   void __push_heap (RandomAccessIterator first, Distance holeIndex,
  1501.                     Distance topIndex, T value, Compare comp);
  1502.  
  1503.   template <class RandomAccessIterator, class Compare,  class Distance, class T>
  1504.   inline void __push_heap_aux (RandomAccessIterator first,
  1505.                                RandomAccessIterator last, Compare comp,
  1506.                                Distance*, T*)
  1507.   {
  1508.     __push_heap(first, Distance((last-first)-1), Distance(0),
  1509.                 T(*(last - 1)), comp);
  1510.   }
  1511.  
  1512.   template <class RandomAccessIterator, class Compare>
  1513.   inline void push_heap (RandomAccessIterator first, RandomAccessIterator last,
  1514.                          Compare comp)
  1515.   {
  1516.     if (!(first == last))
  1517.       __push_heap_aux(first, last, comp, __distance_type(first),
  1518.                       _RWSTD_VALUE_TYPE(first));
  1519.   }
  1520.  
  1521.   template <class RandomAccessIterator, class Distance, class T>
  1522.   void __adjust_heap (RandomAccessIterator first, Distance holeIndex,
  1523.                       Distance len, T value);
  1524.  
  1525.   template <class RandomAccessIterator, class T, class Distance>
  1526.   inline void __pop_heap (RandomAccessIterator first, RandomAccessIterator last,
  1527.                           RandomAccessIterator result, T value, Distance*)
  1528.   {
  1529.     *result = *first;
  1530.     __adjust_heap(first, Distance(0), Distance(last - first), value);
  1531.   }
  1532.  
  1533.   template <class RandomAccessIterator, class T>
  1534.   inline void __pop_heap_aux (RandomAccessIterator first,
  1535.                               RandomAccessIterator last, T*)
  1536.   {
  1537.     __pop_heap(first, last-1, last-1, T(*(last-1)), __distance_type(first));
  1538.   }
  1539.  
  1540.   template <class RandomAccessIterator>
  1541.   inline void pop_heap (RandomAccessIterator first, RandomAccessIterator last)
  1542.   {
  1543.     if (!(first == last))
  1544.       __pop_heap_aux(first, last, _RWSTD_VALUE_TYPE(first));
  1545.   }
  1546.  
  1547.   template <class RandomAccessIterator, class Distance, class T, class Compare>
  1548.   void __adjust_heap (RandomAccessIterator first, Distance holeIndex,
  1549.                       Distance len, T value, Compare comp);
  1550.  
  1551.   template <class RandomAccessIterator, class T, class Compare, class Distance>
  1552.   inline void __pop_heap (RandomAccessIterator first, RandomAccessIterator last,
  1553.                           RandomAccessIterator result, T value, Compare comp,
  1554.                           Distance*)
  1555.   {
  1556.     *result = *first;
  1557.     __adjust_heap(first, Distance(0), Distance(last - first), value, comp);
  1558.   }
  1559.  
  1560.   template <class RandomAccessIterator, class T, class Compare>
  1561.   inline void __pop_heap_aux (RandomAccessIterator first,
  1562.                               RandomAccessIterator last, T*, Compare comp)
  1563.   {
  1564.     __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,
  1565.                __distance_type(first));
  1566.   }
  1567.  
  1568.   template <class RandomAccessIterator, class Compare>
  1569.   inline void pop_heap (RandomAccessIterator first, RandomAccessIterator last,
  1570.                         Compare comp)
  1571.   {
  1572.     if (!(first == last))
  1573.       __pop_heap_aux(first, last, _RWSTD_VALUE_TYPE(first), comp);
  1574.   }
  1575.  
  1576.   template <class RandomAccessIterator, class T, class Distance>
  1577.   void __make_heap (RandomAccessIterator first, RandomAccessIterator last, T*,
  1578.                     Distance*);
  1579.  
  1580.   template <class RandomAccessIterator>
  1581.   inline void make_heap (RandomAccessIterator first, RandomAccessIterator last)
  1582.   {
  1583.     if (!(last - first < 2))
  1584.       __make_heap(first, last, _RWSTD_VALUE_TYPE(first),
  1585.                   __distance_type(first));
  1586.   }
  1587.  
  1588.   template <class RandomAccessIterator, class Compare, class T, class Distance>
  1589.   void __make_heap (RandomAccessIterator first, RandomAccessIterator last,
  1590.                     Compare comp, T*, Distance*);
  1591.  
  1592.   template <class RandomAccessIterator, class Compare>
  1593.   inline void make_heap (RandomAccessIterator first, RandomAccessIterator last,
  1594.                          Compare comp)
  1595.   {
  1596.     if (!(last - first < 2))
  1597.       __make_heap(first, last, comp, _RWSTD_VALUE_TYPE(first),
  1598.                   __distance_type(first));
  1599.   }
  1600.  
  1601.   template <class RandomAccessIterator>
  1602.   void sort_heap (RandomAccessIterator first, RandomAccessIterator last);
  1603.  
  1604.   template <class RandomAccessIterator, class Compare>
  1605.   void sort_heap (RandomAccessIterator first, RandomAccessIterator last,
  1606.                   Compare comp);
  1607.  
  1608. //
  1609. // Minimum and maximum.
  1610. //
  1611.  
  1612. #if !defined(__MINMAX_DEFINED)
  1613.   template <class T>
  1614.   inline const T& min (const T& a, const T& b)
  1615.   {
  1616.     return b < a ? b : a;
  1617.   }
  1618. #endif
  1619.  
  1620.   template <class T, class Compare>
  1621.   inline const T& min (const T& a, const T& b, Compare comp)
  1622.   {
  1623.     return comp(b, a) ? b : a;
  1624.   }
  1625.  
  1626. #if !defined(__MINMAX_DEFINED)
  1627.   template <class T>
  1628.   inline const T& max (const T& a, const T& b)
  1629.   {
  1630.     return  a < b ? b : a;
  1631.   }
  1632. #endif
  1633.  
  1634.   template <class T, class Compare>
  1635.   inline const T& max (const T& a, const T& b, Compare comp)
  1636.   {
  1637.     return comp(a, b) ? b : a;
  1638.   }
  1639.  
  1640.   template <class ForwardIterator>
  1641.   ForwardIterator min_element (ForwardIterator first, ForwardIterator last);
  1642.  
  1643.   template <class ForwardIterator, class Compare>
  1644.   ForwardIterator min_element (ForwardIterator first, ForwardIterator last,
  1645.                                Compare comp);
  1646.  
  1647.   template <class ForwardIterator>
  1648.   ForwardIterator max_element (ForwardIterator first, ForwardIterator last);
  1649.  
  1650.   template <class ForwardIterator, class Compare>
  1651.   ForwardIterator max_element (ForwardIterator first, ForwardIterator last,
  1652.                                Compare comp);
  1653.  
  1654.   template <class InputIterator1, class InputIterator2>
  1655.   bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
  1656.                                 InputIterator2 first2, InputIterator2 last2);
  1657.  
  1658.   template <class InputIterator1, class InputIterator2, class Compare>
  1659.   bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
  1660.                                InputIterator2 first2, InputIterator2 last2,
  1661.                                Compare comp);
  1662.  
  1663. //
  1664. // Permutations.
  1665. //
  1666.  
  1667.   template <class BidirectionalIterator>
  1668.   bool next_permutation (BidirectionalIterator first,
  1669.                          BidirectionalIterator last);
  1670.  
  1671.   template <class BidirectionalIterator, class Compare>
  1672.   bool next_permutation (BidirectionalIterator first, BidirectionalIterator last,
  1673.                          Compare comp);
  1674.  
  1675.   template <class BidirectionalIterator>
  1676.   bool prev_permutation (BidirectionalIterator first,
  1677.                          BidirectionalIterator last);
  1678.  
  1679.   template <class BidirectionalIterator, class Compare>
  1680.   bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last,
  1681.                          Compare comp);
  1682.  
  1683. #ifndef _RWSTD_NO_NAMESPACE
  1684. }
  1685. #endif
  1686.  
  1687. #ifdef _RWSTD_NO_TEMPLATE_REPOSITORY
  1688. #include <algorith.cc> 
  1689. #endif
  1690.  
  1691. #ifndef __USING_STD_NAMES__
  1692.   using namespace std;
  1693. #endif
  1694. #endif /*__STD_ALGORITHM*/
  1695. #pragma option pop
  1696. #endif /* __ALGORITH_H */
  1697.