// -*- C++ -*-
#ifndef __STD_ALGORITHM
#define __STD_ALGORITHM 

/***************************************************************************
 *
 * algorithm - Declarations and inline definitions 
 *             for the Standard Library algorithms
 *
 ***************************************************************************
 *    
 *  Copyright 2000 Compaq Computer Corporation
 *
 *  COMPAQ Registered in U.S. Patent and Trademark Office.
 *
 *  Confidential computer software. Valid license from Compaq required for
 *  possession, use or copying. Consistent with FAR 12.211 and 12.212,
 *  Commercial Computer Software, Computer Software Documentation, and
 *  Technical Data for Commercial Items are licensed to the U.S. Government
 *  under vendor's standard commercial license.
 *
 ****************************************************************************
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 ***************************************************************************
 *
 * (c) Copyright 1994, 1998 Rogue Wave Software, Inc.
 * ALL RIGHTS RESERVED
 *
 * The software and information contained herein are proprietary to, and
 * comprise valuable trade secrets of, Rogue Wave Software, Inc., which
 * intends to preserve as trade secrets such software and information.
 * This software is furnished pursuant to a written license agreement and
 * may be used, copied, transmitted, and stored only in accordance with
 * the terms of such license and with the inclusion of the above copyright
 * notice.  This software and information or any other copies thereof may
 * not be provided or otherwise made available to any other person.
 *
 * Notwithstanding any other lease or license that may pertain to, or
 * accompany the delivery of, this computer software and information, the
 * rights of the Government regarding its use, reproduction and disclosure
 * are as set forth in Section 52.227-19 of the FARS Computer
 * Software-Restricted Rights clause.
 * 
 * Use, duplication, or disclosure by the Government is subject to
 * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in
 * Technical Data and Computer Software clause at DFARS 252.227-7013.
 * Contractor/Manufacturer is Rogue Wave Software, Inc.,
 * P.O. Box 2328, Corvallis, Oregon 97339.
 *
 * This computer software and information is distributed with "restricted
 * rights."  Use, duplication or disclosure is subject to restrictions as
 * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial
 * Computer Software-Restricted Rights (April 1985)."  If the Clause at
 * 18-52.227-74 "Rights in Data General" is specified in the contract,
 * then the "Alternate III" clause applies.
 *
 **************************************************************************/

#include <stdcomp>

#ifndef _RWSTD_NO_NEW_HEADER
#include <cstdlib>
#else
#include <stdlib.h>
#endif
#include <iterator>
#include <memory>
#include <utility>

#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __save
#      pragma __environment __header_defaults
#   endif
#endif

#if defined(__VMS) && defined(__DECCXX) && !defined(__DECFIXCXXL1158)
#pragma __extern_prefix __save
#pragma __extern_prefix "CXXL$" 
#endif

// Some compilers have min and max macros
// We use function templates in their stead
#ifdef max
# undef max
#endif
#ifdef min
# undef min
#endif

#ifndef _RWSTD_NO_NAMESPACE
namespace std {
#endif

//
// Forward declare raw_storage_iterator 
//   
  template <class OutputIterator, class T>
  class raw_storage_iterator;


  template <class T>
#ifndef __BORLANDC__
  inline
#endif
  void _RWinitialize (T& t, T val) { t = val; }

//
// Non-modifying sequence operations.
//

  template <class InputIterator, class Function>
  Function for_each (InputIterator first, InputIterator last, Function f);

  template <class InputIterator, class T>
  InputIterator find (InputIterator first, InputIterator last, const T& value);

  template <class InputIterator, class Predicate>
  InputIterator find_if (InputIterator first, InputIterator last, Predicate pred);

  template <class ForwardIterator1, class ForwardIterator2, 
  class Distance>
  ForwardIterator1 _RWfind_end (ForwardIterator1 first1,
                               ForwardIterator1 last1,
                               ForwardIterator2 first2,
                               ForwardIterator2 last2,
                               Distance*);

  template <class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 find_end (ForwardIterator1 first1,
                             ForwardIterator1 last1,
                             ForwardIterator2 first2,
                             ForwardIterator2 last2);

  template <class ForwardIterator1, class ForwardIterator2, 
  class BinaryPredicate, class Distance>
  ForwardIterator1 _RWfind_end (ForwardIterator1 first1,
                               ForwardIterator1 last1,
                               ForwardIterator2 first2,
                               ForwardIterator2 last2,
                               BinaryPredicate pred,
                               Distance*);

  template <class ForwardIterator1, class ForwardIterator2, 
  class BinaryPredicate>
  ForwardIterator1 find_end (ForwardIterator1 first1,
                             ForwardIterator1 last1,
                             ForwardIterator2 first2,
                             ForwardIterator2 last2,
                             BinaryPredicate pred);

  template <class ForwardIterator1, class ForwardIterator2>
  ForwardIterator1 find_first_of (ForwardIterator1 first1, ForwardIterator1 last1,
                                  ForwardIterator2 first2, ForwardIterator2 last2);

  template <class ForwardIterator1, class ForwardIterator2,
  class BinaryPredicate>
  ForwardIterator1 find_first_of (ForwardIterator1 first1,ForwardIterator1 last1,
                                  ForwardIterator2 first2,ForwardIterator2 last2,
                                  BinaryPredicate pred);

  template <class ForwardIterator>
  ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last);

  template <class ForwardIterator, class BinaryPredicate>
  ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last,
                                 BinaryPredicate binary_pred);

#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC
  template <class InputIterator, class T>
  _TYPENAME iterator_traits<InputIterator>::difference_type
  count (InputIterator first, InputIterator last, const T& value);

  template <class InputIterator, class Predicate>
  _TYPENAME iterator_traits<InputIterator>::difference_type
  count_if (InputIterator first, InputIterator last, Predicate pred);
#endif /* _RWSTD_NO_CLASS_PARTIAL_SPEC */

#ifndef _RWSTD_NO_OLD_COUNT
  template <class InputIterator, class T, class Size>
  void count (InputIterator first, InputIterator last, const T& value, Size& n);

  template <class InputIterator, class Predicate, class Size>
  void count_if (InputIterator first, InputIterator last, Predicate pred, 
                 Size& n);
#endif /* _RWSTD_NO_OLD_COUNT */

  template <class InputIterator1, class InputIterator2>
  pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
                                                InputIterator1 last1,
                                                InputIterator2 first2);

  template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  pair<InputIterator1, InputIterator2> mismatch (InputIterator1 first1,
                                                 InputIterator1 last1,
                                                 InputIterator2 first2,
                                                 BinaryPredicate binary_pred);

  template <class InputIterator1, class InputIterator2>
  inline bool equal (InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2)
  {
    return mismatch(first1, last1, first2).first == last1;
  }

  template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  inline bool equal (InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, BinaryPredicate binary_pred)
  {
    return mismatch(first1, last1, first2, binary_pred).first == last1;
  }

  template <class ForwardIterator1, class ForwardIterator2,
  class Distance1, class Distance2>
  ForwardIterator1 _RWsearch (ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2,
                             Distance1*, Distance2*);

  template <class ForwardIterator1, class ForwardIterator2>
  inline ForwardIterator1 search (ForwardIterator1 first1,ForwardIterator1 last1,
                                  ForwardIterator2 first2,ForwardIterator2 last2)
  {
    return _RWsearch(first1, last1, first2, last2, _RWdistance_type(first1),
                    _RWdistance_type(first2));
  }

  template <class ForwardIterator1, class ForwardIterator2,
  class BinaryPredicate, class Distance1, class Distance2>
  ForwardIterator1 _RWsearch (ForwardIterator1 first1, ForwardIterator1 last1,
                             ForwardIterator2 first2, ForwardIterator2 last2,
                             BinaryPredicate binary_pred, Distance1*, Distance2*);

  template <class ForwardIterator1, class ForwardIterator2,
  class BinaryPredicate>
  inline ForwardIterator1 search (ForwardIterator1 first1,ForwardIterator1 last1,
                                  ForwardIterator2 first2,ForwardIterator2 last2,
                                  BinaryPredicate binary_pred)
  {
    return _RWsearch(first1, last1, first2, last2, binary_pred,
                    _RWdistance_type(first1), _RWdistance_type(first2));
  }

  template <class ForwardIterator, class Distance, class Size, class T>
  ForwardIterator _RWsearch_n (ForwardIterator first, ForwardIterator last,
                              Distance*, Size count, const T& value);
 
  template <class ForwardIterator, class Size, class T>
  inline ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                                   Size count, const T& value)
  {
    if (count) 
      return _RWsearch_n(first, last, _RWdistance_type(first), count, value);
    else
      return first;
  }

  template <class ForwardIterator, class Distance, class Size, class T,
  class BinaryPredicate>
  ForwardIterator _RWsearch_n (ForwardIterator first, ForwardIterator last,
                              Distance*, Size count, const T& value,
                              BinaryPredicate pred);

  template <class ForwardIterator, class Size, class T, class BinaryPredicate>
  inline ForwardIterator search_n (ForwardIterator first, ForwardIterator last,
                                   Size count, const T& value,
                                   BinaryPredicate pred)
  {
    if (count) 
      return  _RWsearch_n(first, last, _RWdistance_type(first), count,value, pred);
    else
      return first;
  }

//
// Modifying sequence operations.
//

  template <class InputIterator, class OutputIterator>
  OutputIterator copy (InputIterator first, InputIterator last,
                       OutputIterator result);

  template <class BidirectionalIterator1, class BidirectionalIterator2>
  BidirectionalIterator2 copy_backward (BidirectionalIterator1 first, 
                                        BidirectionalIterator1 last, 
                                        BidirectionalIterator2 result);

  template <class T>
  inline void swap (T& a, T& b)
  {
    T tmp = a;
    a = b;
    b = tmp;
  }

  template <class ForwardIterator1, class ForwardIterator2, class T>
  inline void _RWiter_swap (ForwardIterator1 a, ForwardIterator2 b, T*)
  {
    T tmp = *a;
    *a = *b;
    *b = tmp;
  }

  template <class ForwardIterator1, class ForwardIterator2>
  inline void iter_swap (ForwardIterator1 a, ForwardIterator2 b)
  {
    _RWiter_swap(a, b, _RWSTD_VALUE_TYPE(a));
  }

  template <class ForwardIterator1, class ForwardIterator2>
  ForwardIterator2 swap_ranges (ForwardIterator1 first1, ForwardIterator1 last1,
                                ForwardIterator2 first2);

  template <class InputIterator, class OutputIterator, class UnaryOperation>
  OutputIterator transform (InputIterator first, InputIterator last,
                            OutputIterator result, UnaryOperation op);

  template <class InputIterator1, class InputIterator2, class OutputIterator,
  class BinaryOperation>
  OutputIterator transform (InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, OutputIterator result,
                            BinaryOperation binary_op);

  template <class ForwardIterator, class T>
  void replace (ForwardIterator first, ForwardIterator last, const T& old_value,
                const T& new_value);

  template <class ForwardIterator, class Predicate, class T>
  void replace_if (ForwardIterator first, ForwardIterator last, Predicate pred,
                   const T& new_value);

  template <class InputIterator, class OutputIterator, class T>
  OutputIterator replace_copy (InputIterator first, InputIterator last,
                               OutputIterator result, const T& old_value,
                               const T& new_value);

  template <class Iterator, class OutputIterator, class Predicate, class T>
  OutputIterator replace_copy_if (Iterator first, Iterator last,
                                  OutputIterator result, Predicate pred,
                                  const T& new_value);

  template <class ForwardIterator, class T>
#ifdef _RWSTD_FILL_NAME_CLASH
  void std_fill (ForwardIterator first, ForwardIterator last, const T& value);
#else
  void fill (ForwardIterator first, ForwardIterator last, const T& value);
#endif

  template <class OutputIterator, class Size, class T>
  void fill_n (OutputIterator first, Size n, const T& value);

  template <class ForwardIterator, class Generator>
  void generate (ForwardIterator first, ForwardIterator last, Generator gen);

  template <class OutputIterator, class Size, class Generator>
  void generate_n (OutputIterator first, Size n, Generator gen);

  template <class InputIterator, class OutputIterator, class T>
  OutputIterator remove_copy (InputIterator first, InputIterator last,
                              OutputIterator result, const T& value);

  template <class InputIterator, class OutputIterator, class Predicate>
  OutputIterator remove_copy_if (InputIterator first, InputIterator last,
                                 OutputIterator result, Predicate pred);

  template <class ForwardIterator, class T>
  inline ForwardIterator remove (ForwardIterator first, ForwardIterator last,
                                 const T& value)
  {
    first = find(first, last, value);
    ForwardIterator next = first;
    return first == last ? first : remove_copy(++next, last, first, value);
  }

  template <class ForwardIterator, class Predicate>
  inline ForwardIterator remove_if (ForwardIterator first, ForwardIterator last,
                                    Predicate pred)
  {
    first = find_if(first, last, pred);
    ForwardIterator next = first;
    return first == last ? first : remove_copy_if(++next, last, first, pred);
  }

  template <class InputIterator, class ForwardIterator>
  ForwardIterator _RWunique_copy (InputIterator first, InputIterator last,
                                 ForwardIterator result, forward_iterator_tag);

  template <class InputIterator, class BidirectionalIterator>
  inline BidirectionalIterator _RWunique_copy (InputIterator first, 
                                              InputIterator last,
                                              BidirectionalIterator result, 
                                              bidirectional_iterator_tag)
  {
    return _RWunique_copy(first, last, result, forward_iterator_tag());
  }

  template <class InputIterator, class RandomAccessIterator>
  inline RandomAccessIterator _RWunique_copy (InputIterator first, 
                                             InputIterator last,
                                             RandomAccessIterator result, 
                                             random_access_iterator_tag)
  {
    return _RWunique_copy(first, last, result, forward_iterator_tag());
  }

  template <class InputIterator, class OutputIterator, class T>
  OutputIterator _RWunique_copy (InputIterator first, InputIterator last,
                                OutputIterator result, T*);

  template <class InputIterator, class OutputIterator>
  inline OutputIterator _RWunique_copy (InputIterator first, InputIterator last,
                                       OutputIterator result, 
                                       output_iterator_tag)
  {
    return _RWunique_copy(first, last, result, _RWSTD_VALUE_TYPE(first));
  }

  template <class InputIterator, class OutputIterator>
  inline OutputIterator unique_copy (InputIterator first, InputIterator last,
                                     OutputIterator result)
  {
    return first == last ? result :
#ifndef _RWSTD_NO_BASE_CLASS_MATCH
    _RWunique_copy(first, last, result, _RWiterator_category(result));
#else
    _RWunique_copy(first, last, result, output_iterator_tag());
#endif
  }

  template <class InputIterator, class ForwardIterator, class BinaryPredicate>
  ForwardIterator _RWunique_copy (InputIterator first, InputIterator last,
                                 ForwardIterator result, 
                                 BinaryPredicate binary_pred,
                                 forward_iterator_tag);
  template <class InputIterator, class BidirectionalIterator,
  class BinaryPredicate>
  inline BidirectionalIterator _RWunique_copy (InputIterator first, 
                                              InputIterator last,
                                              BidirectionalIterator result, 
                                              BinaryPredicate binary_pred,
                                              bidirectional_iterator_tag)
  {
    return _RWunique_copy(first, last, result, binary_pred,
                         forward_iterator_tag());
  }

  template <class InputIterator, class RandomAccessIterator,
  class BinaryPredicate>
  inline RandomAccessIterator _RWunique_copy (InputIterator first, 
                                             InputIterator last,
                                             RandomAccessIterator result, 
                                             BinaryPredicate binary_pred,
                                             random_access_iterator_tag)
  {
    return _RWunique_copy(first, last, result, binary_pred, 
                         forward_iterator_tag());
  }

  template <class InputIterator, class OutputIterator, class BinaryPredicate,
  class T>
  OutputIterator _RWunique_copy (InputIterator first, InputIterator last,
                                OutputIterator result,
                                BinaryPredicate binary_pred, T*);

  template <class InputIterator, class OutputIterator, class BinaryPredicate>
  inline OutputIterator _RWunique_copy (InputIterator first, InputIterator last,
                                       OutputIterator result,
                                       BinaryPredicate binary_pred,
                                       output_iterator_tag)
  {
    return _RWunique_copy(first, last, result, binary_pred,
                         _RWSTD_VALUE_TYPE(first));
  }

  template <class InputIterator, class OutputIterator, class BinaryPredicate>
  inline OutputIterator unique_copy (InputIterator first, InputIterator last,
                                     OutputIterator result,
                                     BinaryPredicate binary_pred)
  {
    return first == last ? result :
#ifndef _RWSTD_NO_BASE_CLASS_MATCH
    _RWunique_copy(first, last, result, binary_pred, _RWiterator_category(result));
#else
    _RWunique_copy(first, last, result, binary_pred, output_iterator_tag());
#endif
  }

  template <class ForwardIterator>
  inline ForwardIterator unique (ForwardIterator first, ForwardIterator last)
  {
    first = adjacent_find(first, last);
    return unique_copy(first, last, first);
  }

  template <class ForwardIterator, class BinaryPredicate>
  inline ForwardIterator unique (ForwardIterator first, ForwardIterator last,
                                 BinaryPredicate binary_pred)
  {
    first = adjacent_find(first, last, binary_pred);
    return unique_copy(first, last, first, binary_pred);
  }

  template <class BidirectionalIterator>
  void _RWreverse (BidirectionalIterator first, BidirectionalIterator last, 
                  bidirectional_iterator_tag);

  template <class RandomAccessIterator>
  void _RWreverse (RandomAccessIterator first, RandomAccessIterator last,
                  random_access_iterator_tag);

  template <class BidirectionalIterator>
  inline void reverse (BidirectionalIterator first, BidirectionalIterator last)
  {
#ifndef _RWSTD_NO_BASE_CLASS_MATCH
    _RWreverse(first, last, _RWiterator_category(first));
#else
    _RWreverse(first, last, bidirectional_iterator_tag());
#endif
  }

  template <class BidirectionalIterator, class OutputIterator>
  OutputIterator reverse_copy (BidirectionalIterator first,
                               BidirectionalIterator last,
                               OutputIterator result);

  template <class ForwardIterator, class Distance>
  void _RWrotate (ForwardIterator first, ForwardIterator middle,
                 ForwardIterator last, Distance*, forward_iterator_tag);

  template <class BidirectionalIterator, class Distance>
  inline void _RWrotate (BidirectionalIterator first, 
                        BidirectionalIterator middle,
                        BidirectionalIterator last, Distance*,
                        bidirectional_iterator_tag)
  {
    reverse(first, middle);
    reverse(middle, last);
    reverse(first, last);
  }

  template <class EuclideanRingElement>
  EuclideanRingElement _RWgcd (EuclideanRingElement m, EuclideanRingElement n);

  template <class RandomAccessIterator, class Distance, class T>
  void _RWrotate_cycle (RandomAccessIterator first, RandomAccessIterator last,
                       RandomAccessIterator initial, Distance shift, T*);

  template <class RandomAccessIterator, class Distance>
  void _RWrotate (RandomAccessIterator first, RandomAccessIterator middle,
                 RandomAccessIterator last, Distance*,
                 random_access_iterator_tag);

  template <class ForwardIterator>
  inline void rotate (ForwardIterator first, ForwardIterator middle,
                      ForwardIterator last)
  {
    if (!(first == middle || middle == last))
    {

#ifndef _RWSTD_NO_BASE_CLASS_MATCH
      _RWrotate(first, middle, last, _RWdistance_type(first), _RWiterator_category(first));
#else
      _RWrotate(first, middle, last, _RWdistance_type(first), forward_iterator_tag());
#endif
    }
  }

  template <class ForwardIterator, class OutputIterator>
  inline OutputIterator rotate_copy (ForwardIterator first,
                                     ForwardIterator middle,
                                     ForwardIterator last,
                                     OutputIterator result)
  {
    return copy(first, middle, copy(middle, last, result));
  }



  template <class RandomAccessIterator, class Distance>
  void _RWrandom_shuffle (RandomAccessIterator first, RandomAccessIterator last,
                         Distance*);

  template <class RandomAccessIterator>
  inline void random_shuffle (RandomAccessIterator first,
                              RandomAccessIterator last)
  {
    _RWrandom_shuffle(first, last, _RWdistance_type(first));
  }

  template <class RandomAccessIterator, class RandomNumberGenerator>
  void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,
                       RandomNumberGenerator& rand);

  template <class BidirectionalIterator, class Predicate>
  BidirectionalIterator partition (BidirectionalIterator first,
                                   BidirectionalIterator last, Predicate pred);

  template <class BidirectionalIterator, class Predicate, class Distance>
  BidirectionalIterator _RWinplace_stable_partition (BidirectionalIterator first,
                                                    BidirectionalIterator last,
                                                    Predicate pred,
                                                    Distance len);

  template <class BidirectionalIterator, class Pointer, class Predicate,
  class Distance, class T>
  BidirectionalIterator _RWstable_partition_adaptive (BidirectionalIterator first,
                                                     BidirectionalIterator last,
                                                     Predicate pred, Distance len,
                                                     Pointer buffer,
                                                     Distance buffer_size,
                                                     Distance& fill_pointer, T*);

  template <class BidirectionalIterator, class Predicate, class Pointer,
  class Distance>
  BidirectionalIterator _RWstable_partition (BidirectionalIterator first,
                                            BidirectionalIterator last,
                                            Predicate pred, Distance len,
#if defined(__DECCXX) && !defined(__DECFIXCXXL1194) 
                                            pair<Pointer, ptrdiff_t> p);
#else
                                            pair<Pointer, Distance> p);
#endif

  template <class BidirectionalIterator, class Predicate, class Distance>
  inline BidirectionalIterator _RWstable_partition_aux (BidirectionalIterator first,
                                                       BidirectionalIterator last, 
                                                       Predicate pred,
                                                       Distance*)
  {
    Distance len;
    _RWinitialize(len, Distance(0));
#if defined(__DECCXX) && !defined(__DECFIXCXXL542) && !defined(_RWSTD_NO_EXPLICIT_ARG)
   len = distance(first, last);
#else
    distance(first, last, len);
#endif

    return len == 0 ? last :
    _RWstable_partition(first, last, pred, len,
#ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
           get_temporary_buffer<_TYPENAME 
               iterator_traits<BidirectionalIterator>::value_type >(len));
#else
              get_temporary_buffer(len,_RWSTD_VALUE_TYPE(first)));
#endif
  }

  template <class BidirectionalIterator, class Predicate>
  inline BidirectionalIterator stable_partition (BidirectionalIterator first,
                                                 BidirectionalIterator last, 
                                                 Predicate pred)
  {
    return _RWstable_partition_aux(first, last, pred, _RWdistance_type(first));
  }

//
// Sorting and related operations.
//

  template <class T>
  inline const T& _RWmedian (const T& a, const T& b, const T& c)
  {
    if (a < b)
      if (b < c)
        return b;
      else if (a < c)
        return c;
      else
        return a;
    else if (a < c)
      return a;
    else if (b < c)
      return c;
    else
      return b;
  }

  template <class T, class Compare>
  inline const T& _RWmedian (const T& a, const T& b, const T& c, Compare comp)
  {
    if (comp(a, b))
      if (comp(b, c))
        return b;
      else if (comp(a, c))
        return c;
      else
        return a;
    else if (comp(a, c))
      return a;
    else if (comp(b, c))
      return c;
    else
      return b;
  }

  template <class RandomAccessIterator, class T>
  RandomAccessIterator _RWunguarded_partition (RandomAccessIterator first, 
                                              RandomAccessIterator last, 
                                              T pivot);

  template <class RandomAccessIterator, class T, class Compare>
  RandomAccessIterator _RWunguarded_partition (RandomAccessIterator first, 
                                              RandomAccessIterator last, 
                                              T pivot, Compare comp);

  template <class RandomAccessIterator, class T>
  void _RWquick_sort_loop_aux (RandomAccessIterator first,
                              RandomAccessIterator last, T*);

  template <class RandomAccessIterator>
  inline void _RWquick_sort_loop (RandomAccessIterator first,
                                 RandomAccessIterator last)
  {
    _RWquick_sort_loop_aux(first, last, _RWSTD_VALUE_TYPE(first));
  }

  template <class RandomAccessIterator, class T, class Compare>
  void _RWquick_sort_loop_aux (RandomAccessIterator first, 
                              RandomAccessIterator last, T*, Compare comp);

  template <class RandomAccessIterator, class Compare>
  inline void _RWquick_sort_loop (RandomAccessIterator first, 
                                 RandomAccessIterator last, Compare comp)
  {
    _RWquick_sort_loop_aux(first, last, _RWSTD_VALUE_TYPE(first), comp);
  }

  template <class RandomAccessIterator, class T>
  void _RWunguarded_linear_insert (RandomAccessIterator last, T value);

  template <class RandomAccessIterator, class T, class Compare>
  void _RWunguarded_linear_insert (RandomAccessIterator last,T value,Compare comp);

  template <class RandomAccessIterator, class T>
  inline void _RWlinear_insert (RandomAccessIterator first, 
                               RandomAccessIterator last, T*)
  {
    T value = *last;
    if (value < *first)
    {
      copy_backward(first, last, last + 1);
      *first = value;
    }
    else
      _RWunguarded_linear_insert(last, value);
  }

  template <class RandomAccessIterator, class T, class Compare>
  inline void _RWlinear_insert (RandomAccessIterator first, 
                               RandomAccessIterator last, T*, Compare comp)
  {
    T value = *last;
    if (comp(value, *first))
    {
      copy_backward(first, last, last + 1);
      *first = value;
    }
    else
      _RWunguarded_linear_insert(last, value, comp);
  }

  template <class RandomAccessIterator>
  void _RWinsertion_sort (RandomAccessIterator first, RandomAccessIterator last);

  template <class RandomAccessIterator, class Compare>
  void _RWinsertion_sort (RandomAccessIterator first,
                         RandomAccessIterator last, Compare comp);

  template <class RandomAccessIterator, class T>
  void _RWunguarded_insertion_sort_aux (RandomAccessIterator first, 
                                       RandomAccessIterator last, T*);

  template <class RandomAccessIterator>
  inline void _RWunguarded_insertion_sort(RandomAccessIterator first, 
                                         RandomAccessIterator last)
  {
    _RWunguarded_insertion_sort_aux(first, last, _RWSTD_VALUE_TYPE(first));
  }

  template <class RandomAccessIterator, class T, class Compare>
  void _RWunguarded_insertion_sort_aux (RandomAccessIterator first, 
                                       RandomAccessIterator last,
                                       T*, Compare comp);

  template <class RandomAccessIterator, class Compare>
  inline void _RWunguarded_insertion_sort (RandomAccessIterator first, 
                                          RandomAccessIterator last,
                                          Compare comp)
  {
    _RWunguarded_insertion_sort_aux(first, last, _RWSTD_VALUE_TYPE(first), comp);
  }

  template <class RandomAccessIterator>
  void _RWfinal_insertion_sort (RandomAccessIterator first, 
                               RandomAccessIterator last);

  template <class RandomAccessIterator, class Compare>
  void _RWfinal_insertion_sort (RandomAccessIterator first, 
                               RandomAccessIterator last, Compare comp);

  template <class RandomAccessIterator>
  inline void sort (RandomAccessIterator first, RandomAccessIterator last)
  {
    if (!(first == last))
    {
      _RWquick_sort_loop(first, last);
      _RWfinal_insertion_sort(first, last);
    }
  }

  template <class RandomAccessIterator, class Compare>
  inline void sort (RandomAccessIterator first, 
                    RandomAccessIterator last, Compare comp)
  {
    if (!(first == last))
    {
      _RWquick_sort_loop(first, last, comp);
      _RWfinal_insertion_sort(first, last, comp);
    }
  }

  template <class RandomAccessIterator>
  inline void _RWinplace_stable_sort (RandomAccessIterator first,
                                     RandomAccessIterator last)
  {
    if (last - first < 15)
      _RWinsertion_sort(first, last);
    else
    {
      RandomAccessIterator middle = first + (last - first) / 2;
      _RWinplace_stable_sort(first, middle);
      _RWinplace_stable_sort(middle, last);
      _RWmerge_without_buffer(first, middle, last, middle - first,
                             last - middle);
    }
  }

  template <class RandomAccessIterator, class Compare>
  inline void _RWinplace_stable_sort (RandomAccessIterator first,
                                     RandomAccessIterator last, Compare comp)
  {
    if (last - first < 15)
      _RWinsertion_sort(first, last, comp);
    else
    {
      RandomAccessIterator middle = first + (last - first) / 2;
      _RWinplace_stable_sort(first, middle, comp);
      _RWinplace_stable_sort(middle, last, comp);
      _RWmerge_without_buffer(first, middle, last, middle - first,
                             last - middle, comp);
    }
  }

  template <class RandomAccessIterator1, class RandomAccessIterator2,
  class Distance>
  void _RWmerge_sort_loop (RandomAccessIterator1 first,
                          RandomAccessIterator1 last, 
                          RandomAccessIterator2 result, Distance step_size);

  template <class RandomAccessIterator1, class RandomAccessIterator2,
  class Distance, class Compare>
  void _RWmerge_sort_loop (RandomAccessIterator1 first,
                          RandomAccessIterator1 last, 
                          RandomAccessIterator2 result, Distance step_size,
                          Compare comp);

  template <class RandomAccessIterator, class Distance>
  void _RWchunk_insertion_sort (RandomAccessIterator first, 
                               RandomAccessIterator last, Distance chunk_size);

  template <class RandomAccessIterator, class Distance, class Compare>
  void _RWchunk_insertion_sort (RandomAccessIterator first, 
                               RandomAccessIterator last,
                               Distance chunk_size, Compare comp);

  template <class RandomAccessIterator, class Pointer, class Distance, class T>
  void _RWmerge_sort_with_buffer (RandomAccessIterator first, 
                                 RandomAccessIterator last,
                                 Pointer buffer, Distance*, T*);

  template <class RandomAccessIterator, class Pointer, class Distance, class T,
  class Compare>
  void _RWmerge_sort_with_buffer (RandomAccessIterator first, 
                                 RandomAccessIterator last, Pointer buffer,
                                 Distance*, T*, Compare comp);

  template <class RandomAccessIterator, class Pointer, class Distance, class T>
  void _RWstable_sort_adaptive (RandomAccessIterator first, 
                               RandomAccessIterator last, Pointer buffer,
                               Distance buffer_size, T*);

  template <class RandomAccessIterator, class Pointer, class Distance, class T,
  class Compare>
  void _RWstable_sort_adaptive (RandomAccessIterator first, 
                               RandomAccessIterator last, Pointer buffer,
                               Distance buffer_size, T*, Compare comp);

  template <class RandomAccessIterator, class Pointer, class Distance, class T>
  inline void _RWstable_sort (RandomAccessIterator first,
                             RandomAccessIterator last,
                             pair<Pointer, Distance>& p, T*)
  {
    if (p.first == 0)
      _RWinplace_stable_sort(first, last);
    else
    {
      Distance len = min((int)p.second, (int)(last - first));
      copy(first, first + len, raw_storage_iterator<Pointer, T>(p.first));
      _RWstable_sort_adaptive(first, last, p.first, p.second, _RWSTD_STATIC_CAST(T*,0));
      __RWSTD::_RWdestroy(p.first, p.first + len);
      return_temporary_buffer(p.first);
    }
  }

  template <class RandomAccessIterator, class Pointer, class Distance, class T,
  class Compare>
  inline void _RWstable_sort (RandomAccessIterator first,
                             RandomAccessIterator last,
                             pair<Pointer, Distance>& p, T*, Compare comp)
  {
    if (p.first == 0)
      _RWinplace_stable_sort(first, last, comp);
    else
    {
      Distance len = min((int)p.second, (int)(last - first));
      copy(first, first + len, raw_storage_iterator<Pointer, T>(p.first));
      _RWstable_sort_adaptive(first, last, p.first, p.second, _RWSTD_STATIC_CAST(T*,0), comp);
      __RWSTD::_RWdestroy(p.first, p.first + len);
      return_temporary_buffer(p.first);
    }
  }

  template <class RandomAccessIterator, class T, class Distance>
  inline void _RWstable_sort_aux (RandomAccessIterator first,
                                 RandomAccessIterator last, T*, Distance*)
  {

    pair<T*, Distance> tmp = 
#ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
         get_temporary_buffer<T>(Distance(last-first));
#else
         get_temporary_buffer(Distance(last-first),_RWSTD_STATIC_CAST(T*,0));
#endif
    _RWstable_sort(first, last, tmp, _RWSTD_STATIC_CAST(T*,0));
  }

  template <class RandomAccessIterator, class T, class Distance, class Compare>
  inline void _RWstable_sort_aux (RandomAccessIterator first,
                                 RandomAccessIterator last, T*, Distance*,
                                 Compare comp)
  {
    pair<T*, Distance> tmp = 
#ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
        get_temporary_buffer<T>(Distance(last-first));
#else
        get_temporary_buffer(Distance(last-first),_RWSTD_STATIC_CAST(T*,0));
#endif
    _RWstable_sort(first, last, tmp, _RWSTD_STATIC_CAST(T*,0), comp);
  }

  template <class RandomAccessIterator>
  inline void stable_sort (RandomAccessIterator first,
                           RandomAccessIterator last)
  {
    if (!(first == last))
    {
      _RWstable_sort_aux(first, last, _RWSTD_VALUE_TYPE(first),
                        _RWdistance_type(first));
    }
  }

  template <class RandomAccessIterator, class Compare>
  inline void stable_sort (RandomAccessIterator first,
                           RandomAccessIterator last, Compare comp)
  {
    if (!(first == last))
    {
      _RWstable_sort_aux(first, last, _RWSTD_VALUE_TYPE(first),
                        _RWdistance_type(first), comp);
    }
  }

  template <class RandomAccessIterator, class T>
  void _RWpartial_sort (RandomAccessIterator first, RandomAccessIterator middle,
                       RandomAccessIterator last, T*);

  template <class RandomAccessIterator>
  inline void partial_sort (RandomAccessIterator first,
                            RandomAccessIterator middle,
                            RandomAccessIterator last)
  {
    if (!(first == middle))
      _RWpartial_sort(first, middle, last, _RWSTD_VALUE_TYPE(first));
  }

  template <class RandomAccessIterator, class T, class Compare>
  void _RWpartial_sort (RandomAccessIterator first, RandomAccessIterator middle,
                       RandomAccessIterator last, T*, Compare comp);

  template <class RandomAccessIterator, class Compare>
  inline void partial_sort (RandomAccessIterator first,
                            RandomAccessIterator middle,
                            RandomAccessIterator last, Compare comp)
  {
    if (!(first == middle))
      _RWpartial_sort(first, middle, last, _RWSTD_VALUE_TYPE(first), comp);
  }

  template <class InputIterator, class RandomAccessIterator, class Distance,
  class T>
  RandomAccessIterator _RWpartial_sort_copy (InputIterator first,
                                            InputIterator last,
                                            RandomAccessIterator result_first,
                                            RandomAccessIterator result_last, 
                                            Distance*, T*);

  template <class InputIterator, class RandomAccessIterator>
  inline RandomAccessIterator
  partial_sort_copy (InputIterator first, InputIterator last,
                     RandomAccessIterator result_first,
                     RandomAccessIterator result_last)
  {
    return first == last ? result_first :
    _RWpartial_sort_copy(first, last, result_first, result_last, 
                        _RWdistance_type(result_first),
                        _RWSTD_VALUE_TYPE(first));
  }

  template <class InputIterator, class RandomAccessIterator, class Compare,
  class Distance, class T>
  RandomAccessIterator _RWpartial_sort_copy (InputIterator first,
                                            InputIterator last,
                                            RandomAccessIterator result_first,
                                            RandomAccessIterator result_last,
                                            Compare comp, Distance*, T*);

  template <class InputIterator, class RandomAccessIterator, class Compare>
  inline RandomAccessIterator
  partial_sort_copy (InputIterator first, InputIterator last,
                     RandomAccessIterator result_first,
                     RandomAccessIterator result_last, Compare comp)
  {
    return first == last ? result_first :
    _RWpartial_sort_copy(first, last, result_first, result_last, comp,
                        _RWdistance_type(result_first),
                        _RWSTD_VALUE_TYPE(first));
  }

  template <class RandomAccessIterator, class T>
  void _RWnth_element (RandomAccessIterator first, RandomAccessIterator nth,
                      RandomAccessIterator last, T*);

  template <class RandomAccessIterator>
  inline void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
                           RandomAccessIterator last)
  {
    if (!(first == last))
      _RWnth_element(first, nth, last, _RWSTD_VALUE_TYPE(first));
  }

  template <class RandomAccessIterator, class T, class Compare>
  void _RWnth_element (RandomAccessIterator first, RandomAccessIterator nth,
                      RandomAccessIterator last, T*, Compare comp);

  template <class RandomAccessIterator, class Compare>
  inline void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
                           RandomAccessIterator last, Compare comp)
  {
    if (!(first == last))
      _RWnth_element(first, nth, last, _RWSTD_VALUE_TYPE(first), comp);
  }

//
// Binary search.
//

  template <class ForwardIterator, class T, class Distance>
  ForwardIterator _RWlower_bound (ForwardIterator first, ForwardIterator last,
                                 const T& value, Distance*,
                                 forward_iterator_tag);

  template <class ForwardIterator, class T, class Distance>
  inline ForwardIterator _RWlower_bound (ForwardIterator first,
                                        ForwardIterator last,
                                        const T& value, Distance*,
                                        bidirectional_iterator_tag)
  {
    return _RWlower_bound(first, last, value, _RWSTD_STATIC_CAST(Distance*,0),
                         forward_iterator_tag());
  }

  template <class RandomAccessIterator, class T, class Distance>
  RandomAccessIterator _RWlower_bound (RandomAccessIterator first,
                                      RandomAccessIterator last, const T& value,
                                      Distance*, random_access_iterator_tag);

  template <class ForwardIterator, class T>
  inline ForwardIterator lower_bound (ForwardIterator first,ForwardIterator last,
                                      const T& value)
  {

#ifndef _RWSTD_NO_BASE_CLASS_MATCH
    return _RWlower_bound(first, last, value, _RWdistance_type(first),                         _RWiterator_category(first));
#else
    return _RWlower_bound(first, last, value, _RWdistance_type(first), 
                         forward_iterator_tag());
#endif
  }

  template <class ForwardIterator, class T, class Compare, class Distance>
  ForwardIterator _RWlower_bound (ForwardIterator first, ForwardIterator last,
                                 const T& value, Compare comp, Distance*,
                                 forward_iterator_tag);

  template <class ForwardIterator, class T, class Compare, class Distance>
  inline ForwardIterator _RWlower_bound (ForwardIterator first,
                                        ForwardIterator last,
                                        const T& value, Compare comp, Distance*,
                                        bidirectional_iterator_tag)
  {
    return _RWlower_bound(first, last, value, comp,_RWSTD_STATIC_CAST(Distance*,0),
                         forward_iterator_tag());
  }

  template <class RandomAccessIterator, class T, class Compare, class Distance>
  RandomAccessIterator _RWlower_bound (RandomAccessIterator first,
                                      RandomAccessIterator last,
                                      const T& value, Compare comp, Distance*,
                                      random_access_iterator_tag);

  template <class ForwardIterator, class T, class Compare>
  inline ForwardIterator lower_bound (ForwardIterator first,ForwardIterator last,
                                      const T& value, Compare comp)
  {
#ifndef _RWSTD_NO_BASE_CLASS_MATCH
    return _RWlower_bound(first, last, value, comp, _RWdistance_type(first),
                         _RWiterator_category(first));
#else
    return _RWlower_bound(first, last, value, comp, _RWdistance_type(first),
                         forward_iterator_tag());
#endif
  }

  template <class ForwardIterator, class T, class Distance>
  ForwardIterator _RWupper_bound (ForwardIterator first, ForwardIterator last,
                                 const T& value, Distance*,
                                 forward_iterator_tag);

  template <class ForwardIterator, class T, class Distance>
  inline ForwardIterator _RWupper_bound (ForwardIterator first,
                                        ForwardIterator last,
                                        const T& value, Distance*,
                                        bidirectional_iterator_tag)
  {
    return _RWupper_bound(first, last, value, _RWSTD_STATIC_CAST(Distance*,0),
                         forward_iterator_tag());
  }

  template <class RandomAccessIterator, class T, class Distance>
  RandomAccessIterator _RWupper_bound (RandomAccessIterator first,
                                      RandomAccessIterator last, const T& value,
                                      Distance*, random_access_iterator_tag);

  template <class ForwardIterator, class T>
  inline ForwardIterator upper_bound (ForwardIterator first,ForwardIterator last,
                                      const T& value)
  {
#ifndef _RWSTD_NO_BASE_CLASS_MATCH
    return _RWupper_bound(first, last, value, _RWdistance_type(first),
                         _RWiterator_category(first));
#else
    return _RWupper_bound(first, last, value, _RWdistance_type(first),
                         forward_iterator_tag());
#endif
  }

  template <class ForwardIterator, class T, class Compare, class Distance>
  ForwardIterator _RWupper_bound (ForwardIterator first, ForwardIterator last,
                                 const T& value, Compare comp, Distance*,
                                 forward_iterator_tag);

  template <class ForwardIterator, class T, class Compare, class Distance>
  inline ForwardIterator _RWupper_bound (ForwardIterator first,
                                        ForwardIterator last,
                                        const T& value, Compare comp, Distance*,
                                        bidirectional_iterator_tag)
  {
    return _RWupper_bound(first, last, value, comp, _RWSTD_STATIC_CAST(Distance*,0),
                         forward_iterator_tag());
  }

  template <class RandomAccessIterator, class T, class Compare, class Distance>
  RandomAccessIterator _RWupper_bound (RandomAccessIterator first,
                                      RandomAccessIterator last,
                                      const T& value, Compare comp, Distance*,
                                      random_access_iterator_tag);

  template <class ForwardIterator, class T, class Compare>
  inline ForwardIterator upper_bound (ForwardIterator first,ForwardIterator last,
                                      const T& value, Compare comp)
  {
#ifndef _RWSTD_NO_BASE_CLASS_MATCH
    return _RWupper_bound(first, last, value, comp, _RWdistance_type(first),
                         _RWiterator_category(first));
#else
    return _RWupper_bound(first, last, value, comp, _RWdistance_type(first),
                         forward_iterator_tag());
#endif
  }

  template <class ForwardIterator, class T, class Distance>
  pair<ForwardIterator, ForwardIterator>
  _RWequal_range (ForwardIterator first, ForwardIterator last, const T& value,
                 Distance*, forward_iterator_tag);

  template <class ForwardIterator, class T, class Distance>
  inline pair<ForwardIterator, ForwardIterator>
  _RWequal_range (ForwardIterator first, ForwardIterator last, const T& value,
                 Distance*, bidirectional_iterator_tag)
  {
    return _RWequal_range(first, last, value, _RWSTD_STATIC_CAST(Distance*,0), 
                         forward_iterator_tag());
  }

  template <class RandomAccessIterator, class T, class Distance>
  pair<RandomAccessIterator, RandomAccessIterator>
  _RWequal_range (RandomAccessIterator first, RandomAccessIterator last,
                 const T& value, Distance*, random_access_iterator_tag);

  template <class ForwardIterator, class T>
  inline pair<ForwardIterator, ForwardIterator>
  equal_range (ForwardIterator first, ForwardIterator last, const T& value)
  {
#ifndef _RWSTD_NO_BASE_CLASS_MATCH
    return _RWequal_range(first, last, value, _RWdistance_type(first),
                         _RWiterator_category(first));
#else
    return _RWequal_range(first, last, value, _RWdistance_type(first),
                         forward_iterator_tag());
#endif
  }

  template <class ForwardIterator, class T, class Compare, class Distance>
  pair<ForwardIterator, ForwardIterator>
  _RWequal_range (ForwardIterator first, ForwardIterator last, const T& value,
                 Compare comp, Distance*, forward_iterator_tag);

  template <class ForwardIterator, class T, class Compare, class Distance>
  inline pair<ForwardIterator, ForwardIterator>
  _RWequal_range (ForwardIterator first, ForwardIterator last, const T& value,
                 Compare comp, Distance*, bidirectional_iterator_tag)
  {
    return _RWequal_range(first, last, value, comp, _RWSTD_STATIC_CAST(Distance*,0), 
                         forward_iterator_tag());
  }

  template <class RandomAccessIterator, class T, class Compare, class Distance>
  pair<RandomAccessIterator, RandomAccessIterator>
  _RWequal_range (RandomAccessIterator first, RandomAccessIterator last,
                 const T& value, Compare comp, Distance*,
                 random_access_iterator_tag);

  template <class ForwardIterator, class T, class Compare>
  inline pair<ForwardIterator, ForwardIterator>
  equal_range (ForwardIterator first, ForwardIterator last, const T& value,
               Compare comp)
  {
#ifndef _RWSTD_NO_BASE_CLASS_MATCH
    return _RWequal_range(first, last, value, comp, _RWdistance_type(first),
                         _RWiterator_category(first));
#else
    return _RWequal_range(first, last, value, comp, _RWdistance_type(first),
                         forward_iterator_tag());
#endif
  }    

  template <class ForwardIterator, class T>
  inline bool binary_search (ForwardIterator first, ForwardIterator last,
                             const T& value)
  {
    ForwardIterator i = lower_bound(first, last, value);
    return i != last && !(value < *i);
  }

  template <class ForwardIterator, class T, class Compare>
  inline bool binary_search (ForwardIterator first, ForwardIterator last,
                             const T& value, Compare comp)
  {
    ForwardIterator i = lower_bound(first, last, value, comp);
    return i != last && !comp(value, *i);
  }

//
// Merge
//

  template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result);

  template <class InputIterator1, class InputIterator2, class OutputIterator,
  class Compare>
  OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                        InputIterator2 first2, InputIterator2 last2,
                        OutputIterator result, Compare comp);

  template <class BidirectionalIterator, class Distance>
  void _RWmerge_without_buffer (BidirectionalIterator first,
                               BidirectionalIterator middle,
                               BidirectionalIterator last,
                               Distance len1, Distance len2);

  template <class BidirectionalIterator, class Distance, class Compare>
  void _RWmerge_without_buffer (BidirectionalIterator first,
                               BidirectionalIterator middle,
                               BidirectionalIterator last,
                               Distance len1, Distance len2, Compare comp);

  template <class BidirectionalIterator1, class BidirectionalIterator2,
  class Distance>
  BidirectionalIterator1 _RWrotate_adaptive (BidirectionalIterator1 first,
                                            BidirectionalIterator1 middle,
                                            BidirectionalIterator1 last,
                                            Distance len1, Distance len2,
                                            BidirectionalIterator2 buffer,
                                            Distance buffer_size);

  template <class BidirectionalIterator1, class BidirectionalIterator2,
  class BidirectionalIterator3>
  BidirectionalIterator3 _RWmerge_backward (BidirectionalIterator1 first1,
                                           BidirectionalIterator1 last1,
                                           BidirectionalIterator2 first2,
                                           BidirectionalIterator2 last2,
                                           BidirectionalIterator3 result);

  template <class BidirectionalIterator1, class BidirectionalIterator2,
  class BidirectionalIterator3, class Compare>
  BidirectionalIterator3 _RWmerge_backward (BidirectionalIterator1 first1,
                                           BidirectionalIterator1 last1,
                                           BidirectionalIterator2 first2,
                                           BidirectionalIterator2 last2,
                                           BidirectionalIterator3 result,
                                           Compare comp);

  template <class BidirectionalIterator, class Distance, class Pointer, class T>
  void _RWmerge_adaptive (BidirectionalIterator first,
                         BidirectionalIterator middle,
                         BidirectionalIterator last, Distance len1,Distance len2,
                         Pointer buffer, Distance buffer_size, T*);

  template <class BidirectionalIterator, class Distance, class Pointer, class T,
  class Compare>
  void _RWmerge_adaptive (BidirectionalIterator first,
                         BidirectionalIterator middle,
                         BidirectionalIterator last, Distance len1,Distance len2,
                         Pointer buffer, Distance buffer_size, T*, Compare comp);

  template <class BidirectionalIterator, class Distance, class Pointer, class T>
  void _RWinplace_merge (BidirectionalIterator first,
                        BidirectionalIterator middle, 
                        BidirectionalIterator last, Distance len1,
#if defined(__DECCXX) && !defined(__DECFIXCXXL1194) 
                        Distance len2, pair<Pointer, ptrdiff_t> p, T*);
#else
                        Distance len2, pair<Pointer, Distance> p, T*);
#endif

  template <class BidirectionalIterator, class Distance, class Pointer, class T,
  class Compare>
  void _RWinplace_merge (BidirectionalIterator first,
                        BidirectionalIterator middle,
                        BidirectionalIterator last, Distance len1,
#if defined(__DECCXX) && !defined(__DECFIXCXXL1194) 
                        Distance len2, pair<Pointer, ptrdiff_t> p, T*,
#else
                        Distance len2, pair<Pointer, Distance> p, T*,
#endif
                        Compare comp);

  template <class BidirectionalIterator, class T, class Distance>
  inline void _RWinplace_merge_aux (BidirectionalIterator first,
                                   BidirectionalIterator middle,
                                   BidirectionalIterator last, T*, Distance*)
  {
    Distance len1;
    _RWinitialize(len1, Distance(0));

#if defined(__DECCXX) && !defined(__DECFIXCXXL542) && !defined(_RWSTD_NO_EXPLICIT_ARG)
   len1 = distance(first, middle);
#else
    distance(first, middle, len1);
#endif

    Distance len2;
    _RWinitialize(len2, Distance(0));

#if defined(__DECCXX) && !defined(__DECFIXCXXL542) && !defined(_RWSTD_NO_EXPLICIT_ARG)
   len2 = distance(middle, last);
#else
    distance(middle, last, len2);
#endif

    _RWinplace_merge(first, middle, last, len1, len2, 
#ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
        get_temporary_buffer<T>(len1+len2),_RWSTD_STATIC_CAST(T*,0));
#else
        get_temporary_buffer(len1+len2,_RWSTD_STATIC_CAST(T*,0)),_RWSTD_STATIC_CAST(T*,0));
#endif

  }

  template <class BidirectionalIterator, class T, class Distance, class Compare>
  inline void _RWinplace_merge_aux (BidirectionalIterator first,
                                   BidirectionalIterator middle,
                                   BidirectionalIterator last, T*, Distance*,
                                   Compare comp)
  {
    Distance len1;
    _RWinitialize(len1, Distance(0));

#if defined(__DECCXX) && !defined(__DECFIXCXXL542) && !defined(_RWSTD_NO_EXPLICIT_ARG)
   len1 = distance(first, middle);
#else
    distance(first, middle, len1);
#endif

    Distance len2;
    _RWinitialize(len2, Distance(0));

#if defined(__DECCXX) && !defined(__DECFIXCXXL542) && !defined(_RWSTD_NO_EXPLICIT_ARG)
   len2 = distance(middle, last);
#else
    distance(middle, last, len2);
#endif


    _RWinplace_merge(first, middle, last, len1, len2, 
#ifndef _RWSTD_NO_TEMPLATE_ON_RETURN_TYPE
        get_temporary_buffer<T>(len1+len2), _RWSTD_STATIC_CAST(T*,0), comp);
#else
        get_temporary_buffer(len1 + len2, _RWSTD_STATIC_CAST(T*,0)), _RWSTD_STATIC_CAST(T*,0), comp);
#endif
  }

  template <class BidirectionalIterator>
  inline void inplace_merge (BidirectionalIterator first,
                             BidirectionalIterator middle,
                             BidirectionalIterator last)
  {
    if (!(first == middle || middle == last))
      _RWinplace_merge_aux(first, middle, last, _RWSTD_VALUE_TYPE(first),
                          _RWdistance_type(first));
  }

  template <class BidirectionalIterator, class Compare>
  inline void inplace_merge (BidirectionalIterator first,
                             BidirectionalIterator middle,
                             BidirectionalIterator last, Compare comp)
  {
    if (!(first == middle || middle == last))
      _RWinplace_merge_aux(first, middle, last, _RWSTD_VALUE_TYPE(first),
                          _RWdistance_type(first), comp);
  }

//
// Set operations.
//

  template <class InputIterator1, class InputIterator2>
  bool includes (InputIterator1 first1, InputIterator1 last1,
                 InputIterator2 first2, InputIterator2 last2);

  template <class InputIterator1, class InputIterator2, class Compare>
  bool includes (InputIterator1 first1, InputIterator1 last1,
                 InputIterator2 first2, InputIterator2 last2, 
                 Compare comp);

  template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, InputIterator2 last2,
                            OutputIterator result);

  template <class InputIterator1, class InputIterator2, class OutputIterator,
  class Compare>
  OutputIterator set_union (InputIterator1 first1, InputIterator1 last1,
                            InputIterator2 first2, InputIterator2 last2,
                            OutputIterator result, Compare comp);

  template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
                                   InputIterator2 first2, InputIterator2 last2,
                                   OutputIterator result);

  template <class InputIterator1, class InputIterator2, class OutputIterator,
  class Compare>
  OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
                                   InputIterator2 first2, InputIterator2 last2,
                                   OutputIterator result, Compare comp);

  template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,
                                 InputIterator2 first2, InputIterator2 last2,
                                 OutputIterator result);

  template <class InputIterator1, class InputIterator2, class OutputIterator, 
  class Compare>
  OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1,
                                 InputIterator2 first2, InputIterator2 last2, 
                                 OutputIterator result, Compare comp);

  template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_symmetric_difference (InputIterator1 first1,
                                           InputIterator1 last1,
                                           InputIterator2 first2,
                                           InputIterator2 last2,
                                           OutputIterator result);

  template <class InputIterator1, class InputIterator2, class OutputIterator,
  class Compare>
  OutputIterator set_symmetric_difference (InputIterator1 first1,
                                           InputIterator1 last1,
                                           InputIterator2 first2,
                                           InputIterator2 last2,
                                           OutputIterator result, 
                                           Compare comp);

//
// Heap operations.
//

  template <class RandomAccessIterator, class Distance, class T>
  void _RWpush_heap (RandomAccessIterator first, Distance holeIndex,
                    Distance topIndex, T value);

  template <class RandomAccessIterator, class Distance, class T>
  inline void _RWpush_heap_aux (RandomAccessIterator first,
                               RandomAccessIterator last, Distance*, T*)
  {
    _RWpush_heap(first, Distance((last-first)-1), Distance(0), T(*(last-1)));
  }

  template <class RandomAccessIterator>
  inline void push_heap (RandomAccessIterator first, RandomAccessIterator last)
  {
    if (!(first == last))
      _RWpush_heap_aux(first, last, _RWdistance_type(first),
                      _RWSTD_VALUE_TYPE(first));
  }

  template <class RandomAccessIterator, class Distance, class T, class Compare>
  void _RWpush_heap (RandomAccessIterator first, Distance holeIndex,
                    Distance topIndex, T value, Compare comp);

  template <class RandomAccessIterator, class Compare,  class Distance, class T>
  inline void _RWpush_heap_aux (RandomAccessIterator first,
                               RandomAccessIterator last, Compare comp,
                               Distance*, T*)
  {
    _RWpush_heap(first, Distance((last-first)-1), Distance(0),
                T(*(last - 1)), comp);
  }

  template <class RandomAccessIterator, class Compare>
  inline void push_heap (RandomAccessIterator first, RandomAccessIterator last,
                         Compare comp)
  {
    if (!(first == last))
      _RWpush_heap_aux(first, last, comp, _RWdistance_type(first),
                      _RWSTD_VALUE_TYPE(first));
  }

  template <class RandomAccessIterator, class Distance, class T>
  void _RWadjust_heap (RandomAccessIterator first, Distance holeIndex,
                      Distance len, T value);

  template <class RandomAccessIterator, class T, class Distance>
  inline void _RWpop_heap (RandomAccessIterator first, RandomAccessIterator last,
                          RandomAccessIterator result, T value, Distance*)
  {
    *result = *first;
    _RWadjust_heap(first, Distance(0), Distance(last - first), value);
  }

  template <class RandomAccessIterator, class T>
  inline void _RWpop_heap_aux (RandomAccessIterator first,
                              RandomAccessIterator last, T*)
  {
    _RWpop_heap(first, last-1, last-1, T(*(last-1)), _RWdistance_type(first));
  }

  template <class RandomAccessIterator>
  inline void pop_heap (RandomAccessIterator first, RandomAccessIterator last)
  {
    if (!(first == last))
      _RWpop_heap_aux(first, last, _RWSTD_VALUE_TYPE(first));
  }

  template <class RandomAccessIterator, class Distance, class T, class Compare>
  void _RWadjust_heap (RandomAccessIterator first, Distance holeIndex,
                      Distance len, T value, Compare comp);

  template <class RandomAccessIterator, class T, class Compare, class Distance>
  inline void _RWpop_heap (RandomAccessIterator first, RandomAccessIterator last,
                          RandomAccessIterator result, T value, Compare comp,
                          Distance*)
  {
    *result = *first;
    _RWadjust_heap(first, Distance(0), Distance(last - first), value, comp);
  }

  template <class RandomAccessIterator, class T, class Compare>
  inline void _RWpop_heap_aux (RandomAccessIterator first,
                              RandomAccessIterator last, T*, Compare comp)
  {
    _RWpop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,
               _RWdistance_type(first));
  }

  template <class RandomAccessIterator, class Compare>
  inline void pop_heap (RandomAccessIterator first, RandomAccessIterator last,
                        Compare comp)
  {
    if (!(first == last))
      _RWpop_heap_aux(first, last, _RWSTD_VALUE_TYPE(first), comp);
  }

  template <class RandomAccessIterator, class T, class Distance>
  void _RWmake_heap (RandomAccessIterator first, RandomAccessIterator last, T*,
                    Distance*);

  template <class RandomAccessIterator>
  inline void make_heap (RandomAccessIterator first, RandomAccessIterator last)
  {
    if (!(last - first < 2))
      _RWmake_heap(first, last, _RWSTD_VALUE_TYPE(first),
                  _RWdistance_type(first));
  }

  template <class RandomAccessIterator, class Compare, class T, class Distance>
  void _RWmake_heap (RandomAccessIterator first, RandomAccessIterator last,
                    Compare comp, T*, Distance*);

  template <class RandomAccessIterator, class Compare>
  inline void make_heap (RandomAccessIterator first, RandomAccessIterator last,
                         Compare comp)
  {
    if (!(last - first < 2))
      _RWmake_heap(first, last, comp, _RWSTD_VALUE_TYPE(first),
                  _RWdistance_type(first));
  }

  template <class RandomAccessIterator>
  void sort_heap (RandomAccessIterator first, RandomAccessIterator last);

  template <class RandomAccessIterator, class Compare>
  void sort_heap (RandomAccessIterator first, RandomAccessIterator last,
                  Compare comp);

//
// Minimum and maximum.
//

#if !defined(__MINMAX_DEFINED) 
  template <class T>
  inline const T& min (const T& a, const T& b)
  {
    return b < a ? b : a;
  }
#endif

  template <class T, class Compare>
  inline const T& min (const T& a, const T& b, Compare comp)
  {
    return comp(b, a) ? b : a;
  }

#if !defined(__MINMAX_DEFINED) 
  template <class T>
  inline const T& max (const T& a, const T& b)
  {
    return  a < b ? b : a;
  }
#endif

  template <class T, class Compare>
  inline const T& max (const T& a, const T& b, Compare comp)
  {
    return comp(a, b) ? b : a;
  }

  template <class ForwardIterator>
  ForwardIterator min_element (ForwardIterator first, ForwardIterator last);

  template <class ForwardIterator, class Compare>
  ForwardIterator min_element (ForwardIterator first, ForwardIterator last,
                               Compare comp);

  template <class ForwardIterator>
  ForwardIterator max_element (ForwardIterator first, ForwardIterator last);

  template <class ForwardIterator, class Compare>
  ForwardIterator max_element (ForwardIterator first, ForwardIterator last,
                               Compare comp);

  template <class InputIterator1, class InputIterator2>
  bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2);

  template <class InputIterator1, class InputIterator2, class Compare>
  bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
                               InputIterator2 first2, InputIterator2 last2,
                               Compare comp);

//
// Permutations.
//

  template <class BidirectionalIterator>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);

  template <class BidirectionalIterator, class Compare>
  bool next_permutation (BidirectionalIterator first, BidirectionalIterator last,
                         Compare comp);

  template <class BidirectionalIterator>
  bool prev_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);

  template <class BidirectionalIterator, class Compare>
  bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last,
                         Compare comp);

#ifndef _RWSTD_NO_NAMESPACE
}
#endif

#if defined(__VMS) && defined(__DECCXX) && !defined(__DECFIXCXXL1158)
#   pragma __extern_prefix __restore
#endif

#ifdef _RWSTD_COMPILE_INSTANTIATE
#include <algorithm.cc>
#endif

#if defined(__DECCXX)
#   ifdef __PRAGMA_ENVIRONMENT
#      pragma __environment __restore
#   endif
#endif

#endif /*__STD_ALGORITHM*/
