// -*- C++ -*-
/***************************************************************************
 *
 * algorithm - declarations and inline definitions of the C++ Standard
 *             Library algorithms
 *
 * $Id$
 *
 ***************************************************************************
 *
 * 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.
 *
 ***************************************************************************
 *
 * Copyright (c) 1994-2005 Quovadx,  Inc., acting through its  Rogue Wave
 * Software division. Licensed under the Apache License, Version 2.0 (the
 * "License");  you may  not use this file except  in compliance with the
 * License.    You    may   obtain   a   copy   of    the   License    at
 * http://www.apache.org/licenses/LICENSE-2.0.    Unless   required    by
 * applicable law  or agreed to  in writing,  software  distributed under
 * the License is distributed on an "AS IS" BASIS,  WITHOUT WARRANTIES OR
 * CONDITIONS OF  ANY KIND, either  express or implied.  See  the License
 * for the specific language governing permissions  and limitations under
 * the License.
 * 
 **************************************************************************/

#ifndef _RWSTD_ALGORITHM_INCLUDED
#define _RWSTD_ALGORITHM_INCLUDED

#include <rw/_algobase.h>
#include <rw/_iterbase.h>
#include <rw/_heap.h>
#include <rw/_pair.h>
#include <rw/_rawiter.h>
#include <rw/_defs.h>


#ifdef _INLINE_RECURSIVE
#  define _INLINE inline
#else
#  define _INLINE
#endif


_RWSTD_NAMESPACE (__rw) {

_RWSTD_EXPORT _RWSTD_SIZE_T __rw_rand (_RWSTD_SIZE_T);

}   // namespace __rw


_RWSTD_NAMESPACE (std) { 


// 25.1 - Non-modifying sequence operations [lib.alg.nonmodifying]

// 25.1.1 - For Each [lib.alg.foreach]
template <class _InputIter, class _Function>
inline _Function
for_each (_InputIter __first, _InputIter __last, _Function __fun)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for ( ; !(__first == __last); ++__first)
        __fun (*__first);

    return __fun;
}


// 25.1.2 - Find [lib.alg.find]

template <class _InputIter, class _TypeT>
inline _InputIter
find (_InputIter __first, _InputIter __last, const _TypeT &__val)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (; !(__first == __last) && !(*__first == __val); ++__first);

    return __first;
}


template <class _InputIter, class _Predicate>
inline _InputIter
find_if (_InputIter __first, _InputIter __last, _Predicate __pred)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (; !(__first == __last) && __pred (*__first) == false; ++__first);

    return __first;
}


// helpers to work around the lack of iterator_traits
_EXPORT
template <class _FwdIter1, class _FwdIter2, class _Dist>
_FwdIter1 __find_end (_FwdIter1, _FwdIter1, _FwdIter2, _FwdIter2, _Dist*);

_EXPORT
template <class _FwdIter1, class _FwdIter2, 
          class _BinaryPredicate, class _Dist>
_FwdIter1 __find_end (_FwdIter1, _FwdIter1, _FwdIter2, _FwdIter2,
                      _BinaryPredicate, _Dist*);


// 25.1.3 - Find End [lib.alg.find.end]

template <class _FwdIter1, class _FwdIter2>
inline _FwdIter1 find_end (_FwdIter1 __first1, _FwdIter1 __last1,
                           _FwdIter2 __first2, _FwdIter2 __last2)
{
    _RWSTD_ASSERT_RANGE (__first1, __last1);
    _RWSTD_ASSERT_RANGE (__first2, __last2);

    return __find_end (__first1, __last1, __first2, __last2,
                       _RWSTD_DIFFERENCE_TYPE (_FwdIter1));
}


template <class _FwdIter1, class _FwdIter2, class _BinaryPredicate>
inline _FwdIter1 find_end (_FwdIter1 __first1, _FwdIter1 __last1,
                           _FwdIter2 __first2, _FwdIter2 __last2,
                           _BinaryPredicate __pred)
{
    _RWSTD_ASSERT_RANGE (__first1, __last1);
    _RWSTD_ASSERT_RANGE (__first2, __last2);

    return __find_end (__first1, __last1, __first2, __last2,
                       __pred, _RWSTD_DIFFERENCE_TYPE (_FwdIter1));
}

// 25.1.4 - Find First [lib.alg.find.first.of]

_EXPORT
template <class _FwdIter1, class _FwdIter2>
_FwdIter1 find_first_of (_FwdIter1, _FwdIter1, _FwdIter2, _FwdIter2);

_EXPORT
template <class _FwdIter1, class _FwdIter2, class _BinaryPred>
_FwdIter1 find_first_of (_FwdIter1,_FwdIter1, _FwdIter2, _FwdIter2,
                         _BinaryPred);


// 25.1.5 - Adjacent Find [lib.alg.adjacent.find]

_EXPORT
template <class _FwdIter>
_FwdIter adjacent_find (_FwdIter, _FwdIter);

_EXPORT
template <class _FwdIter, class _BinaryPredicate>
_FwdIter adjacent_find (_FwdIter, _FwdIter, _BinaryPredicate);


#ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC

// 25.1.6 - Count [lib.alg.count]

template <class _InputIter, class _TypeT>
inline _TYPENAME iterator_traits<_InputIter>::difference_type
count (_InputIter __first, _InputIter __last, const _TypeT &__val)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _TYPENAME iterator_traits<_InputIter>::difference_type __n = 0;
    for ( ; !(__first == __last); ++__first)
        if (*__first == __val)
            ++__n;
    return __n;
}


template <class _InputIter, class _Predicate>
inline _TYPENAME iterator_traits<_InputIter>::difference_type
count_if (_InputIter __first, _InputIter __last, _Predicate __pred)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _TYPENAME iterator_traits<_InputIter>::difference_type __n = 0;
    for ( ; !(__first == __last); ++__first)
        if (!(__pred (*__first) == false))
            ++__n;
    return __n;
}

#endif   // _RWSTD_NO_CLASS_PARTIAL_SPEC


// provided as a backward-compatibility extension (or as a workaround)
#if    !defined (_RWSTD_NO_EXT_VOID_COUNT)    \
    || defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)

template <class _InputIter, class _TypeT, class _Size>
inline void count (_InputIter __first, _InputIter __last,
                   const _TypeT &__val, _Size& __n)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for ( ; !(__first == __last); ++__first) 
        if (*__first == __val)
            ++__n;
}


template <class _InputIter, class _Predicate, class _Size>
inline void count_if (_InputIter __first, _InputIter __last,
                      _Predicate __pred, _Size& __n)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for ( ; !(__first == __last); ++__first)
        if (!(__pred (*__first) == false))
            ++__n;
}

#endif   // !_RWSTD_NO_EXT_VOID_COUNT || _RWSTD_NO_CLASS_PARTIAL_SPEC


// 25.1.7 - Mismatch [lib.mismatch]
// 25.1.8 - Equal [lib.alg.equal]
// defined in <rw/_algobase.h>


// helpers to work around the lack of iterator_traits
_EXPORT
template <class _FwdIter1, class _FwdIter2, class _Dist1, class _Dist2>
_FwdIter1 __search (_FwdIter1, _FwdIter1, _FwdIter2, _FwdIter2,
                    _Dist1*, _Dist2*);

_EXPORT
template <class _FwdIter1, class _FwdIter2,
          class _BinaryPredicate, class Distance1, class Distance2>
_FwdIter1 __search (_FwdIter1, _FwdIter1, _FwdIter2, _FwdIter2,
                    _BinaryPredicate, Distance1*, Distance2*);

// 25.1.9 - Search [lib.alg.search]

// 25.1.9, p1
template <class _FwdIter1, class _FwdIter2>
inline _FwdIter1 search (_FwdIter1 __first1, _FwdIter1 __last1,
                         _FwdIter2 __first2, _FwdIter2 __last2)
{
    return __search (__first1, __last1, __first2, __last2,
                     _RWSTD_DIFFERENCE_TYPE (_FwdIter1),
                     _RWSTD_DIFFERENCE_TYPE (_FwdIter2));
}


template <class _FwdIter1, class _FwdIter2, class _BinaryPredicate>
inline _FwdIter1 search (_FwdIter1 __first1,_FwdIter1 __last1,
                         _FwdIter2 __first2,_FwdIter2 __last2,
                         _BinaryPredicate __pred)
{
    return __search (__first1, __last1, __first2, __last2, __pred,
                     _RWSTD_DIFFERENCE_TYPE (_FwdIter1),
                     _RWSTD_DIFFERENCE_TYPE (_FwdIter2));
}


// helper to work around the lack of iterator_traits
_EXPORT
template <class _FwdIter, class _Dist, class _Size, class _TypeT>
_FwdIter __search_n (_FwdIter, _FwdIter, _Dist*, _Size, const _TypeT&);
 
_EXPORT
template <class _FwdIter, class _Dist, class _Size, class _TypeT,
          class _BinaryPredicate>
_FwdIter __search_n (_FwdIter, _FwdIter, _Dist*, _Size,
                     const _TypeT&, _BinaryPredicate);

// 25.1.9, p4
template <class _FwdIter, class _Size, class _TypeT>
inline _FwdIter search_n (_FwdIter __first, _FwdIter __last,
                          _Size __count, const _TypeT &__val)
{
    if (__count) 
        return __search_n (__first, __last, _RWSTD_DIFFERENCE_TYPE (_FwdIter),
                           __count, __val);
    return __first;
}


template <class _FwdIter, class _Size, class _TypeT, class _BinaryPredicate>
inline _FwdIter search_n (_FwdIter __first, _FwdIter __last,
                          _Size __count, const _TypeT &__val,
                          _BinaryPredicate __pred)
{
    if (__count) 
        return __search_n (__first, __last,
                           _RWSTD_DIFFERENCE_TYPE (_FwdIter),
                           __count, __val, __pred);
    return __first;
}


// 25.2 - Mutating sequence operations [lib.alg.modifying,operations]

// 25.2.1 - Copy [lib.alg.copy]
// 25.2.2, p1 swap
// defined in <rw/_algobase.h>

// 25.2.2, p3
template <class _FwdIter1, class _FwdIter2>
inline _FwdIter2
swap_ranges (_FwdIter1 __first1, _FwdIter1 __last1, _FwdIter2 __first2)
{
    _RWSTD_ASSERT_RANGE (__first1, __last1);

    for (; !(__first1 == __last1); ++__first1, ++__first2)
        _STD::iter_swap (__first1, __first2);
    return __first2;
}


// 25.2.3 - Transform [lib.alg.transform]

template <class _InputIter, class _OutputIter, class _UnaryOperation>
inline _OutputIter
transform (_InputIter __first, _InputIter __last, _OutputIter __res,
           _UnaryOperation __unary_op)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (; !(__first == __last); ++__res, ++__first)
        *__res = __unary_op (*__first);
    return __res;
}


template <class _InputIter1, class _InputIter2,
          class _OutputIter, class _BinaryOperation>
inline _OutputIter
transform (_InputIter1 __first1, _InputIter1 __last1,
           _InputIter2 __first2, _OutputIter __res,
           _BinaryOperation __binary_op)
{
    _RWSTD_ASSERT_RANGE (__first1, __last1);

    for (; !(__first1 == __last1); ++__res, ++__first1, ++__first2)
        *__res = __binary_op (*__first1, *__first2);
    return __res;
}


// 25.2.4 - Replace [lib.alg.replace]

template <class _FwdIter, class _TypeT>
inline void replace (_FwdIter __first, _FwdIter __last,
                     const _TypeT& __old_value, const _TypeT& __new_value)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (; !(__first == __last); ++__first) 
        if (*__first == __old_value)
            *__first = __new_value;
}


template <class _FwdIter, class _Predicate, class _TypeT>
inline void replace_if (_FwdIter __first, _FwdIter __last,
                        _Predicate __pred, const _TypeT& __new_value)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (; !(__first == __last); ++__first)
        if (!(__pred (*__first) == false))
            *__first = __new_value;
}


template <class _InputIter, class _OutputIter, class _TypeT>
inline _OutputIter
replace_copy (_InputIter __first, _InputIter __last, _OutputIter __res,
              const _TypeT& __old_value, const _TypeT& __new_value)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (; !(__first == __last); ++__first, ++__res)
        *__res = *__first == __old_value ? __new_value : *__first;
    return __res;
}

_EXPORT
template <class _Iter, class _OutputIter, class _Predicate, class _TypeT>
_OutputIter replace_copy_if (_Iter, _Iter, _OutputIter, _Predicate,
                             const _TypeT&);

// 25.2.5 - Fill [lib.alg.fill]
// defined in <rw/_algobase.h>

// 25.2.6 - Generate [lib.alg.generate]

template <class _FwdIter, class _Generator>
inline void generate (_FwdIter __first, _FwdIter __last, _Generator __gen)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (; !(__first == __last); ++__first)
        *__first = __gen ();
}


template <class _OutputIter, class _Size, class _Generator>
inline void generate_n (_OutputIter __first, _Size __n, _Generator __gen)
{
    // Size must be convertible to integral type but need not itself be one
    // Complexity:
    // Exactly n if n is positive, or 0 otherwise, assignments.
    // (see lwg issue 426 for the complexity when n is not positive)
    for (_RWSTD_PTRDIFF_T __inx = __n; 0 < __inx; --__inx, ++__first)
        *__first = __gen ();
}


// 25.2.7 - Remove [lib.alg.remove]
_EXPORT
template <class _InputIter, class _OutputIter, class _TypeT>
_OutputIter remove_copy (_InputIter, _InputIter, _OutputIter,
                         const _TypeT&);

_EXPORT
template <class _InputIter, class _OutputIter, class _Predicate>
_OutputIter remove_copy_if (_InputIter, _InputIter, _OutputIter, _Predicate);


template <class _FwdIter, class _TypeT>
inline _FwdIter
remove (_FwdIter __first, _FwdIter __last, const _TypeT &__val)
{
    __first = _STD::find (__first, __last, __val);
    _FwdIter __next = __first;
    return __first == __last ?
        __first : _STD::remove_copy (++__next, __last, __first, __val);
}


template <class _FwdIter, class _Predicate>
inline _FwdIter remove_if (_FwdIter __first, _FwdIter __last, _Predicate __pred)
{
    __first = _STD::find_if (__first, __last, __pred);
    _FwdIter __next = __first;
    return __first == __last ?
        __first : _STD::remove_copy_if (++__next, __last, __first, __pred);
}


_EXPORT
template <class _InputIter, class _FwdIter>
_FwdIter __unique_copy (_InputIter, _InputIter, _FwdIter, forward_iterator_tag);


template <class _InputIter, class _BidirIter>
inline _BidirIter
__unique_copy (_InputIter __first, _InputIter __last, _BidirIter __res, 
               bidirectional_iterator_tag)
{
    return __unique_copy (__first, __last, __res, forward_iterator_tag ());
}


template <class _InputIter, class _RandomAccessIter>
inline _RandomAccessIter
__unique_copy (_InputIter __first, _InputIter __last,
               _RandomAccessIter __res, random_access_iterator_tag)
{
    return __unique_copy (__first, __last, __res, forward_iterator_tag ());
}

_EXPORT
template <class _InputIter, class _OutputIter, class _TypeT>
_OutputIter __unique_copy (_InputIter, _InputIter, _OutputIter, _TypeT*);


template <class _InputIter, class _OutputIter>
inline _OutputIter __unique_copy (_InputIter __first, _InputIter __last,
                                  _OutputIter __res, output_iterator_tag)
{
    return __unique_copy (__first, __last, __res,
                          _RWSTD_VALUE_TYPE (_InputIter));
}


_EXPORT
template <class _InputIter, class _FwdIter, class _BinaryPredicate>
_FwdIter __unique_copy (_InputIter, _InputIter, _FwdIter, _BinaryPredicate,
                        forward_iterator_tag);


template <class _InputIter, class _BidirIter, class _BinaryPredicate>
inline _BidirIter
__unique_copy (_InputIter __first, _InputIter __last, _BidirIter __res, 
               _BinaryPredicate __pred, bidirectional_iterator_tag)
{
    return __unique_copy (__first, __last, __res, __pred,
                          forward_iterator_tag ());
}


template <class _InputIter, class _RandomAccessIter, class _BinaryPredicate>
inline _RandomAccessIter
__unique_copy (_InputIter __first, _InputIter __last, _RandomAccessIter __res, 
               _BinaryPredicate __pred, random_access_iterator_tag)
{
    return __unique_copy (__first, __last, __res, __pred, 
                          forward_iterator_tag ());
}


_EXPORT
template <class _InputIter, class _OutputIter, class _BinaryPredicate,
          class _TypeT>
_OutputIter __unique_copy (_InputIter, _InputIter, _OutputIter,
                           _BinaryPredicate, _TypeT*);

template <class _InputIter, class _OutputIter, class _BinaryPredicate>
inline _OutputIter
__unique_copy (_InputIter __first, _InputIter __last, _OutputIter __res,
               _BinaryPredicate __pred, output_iterator_tag)
{
    return __unique_copy (__first, __last, __res, __pred,
                          _RWSTD_VALUE_TYPE (_InputIter));
}


// 25.2.8 - Unique   [lib.alg.unique]

_EXPORT
template <class _FwdIter>
_FwdIter
unique (_FwdIter, _FwdIter);


_EXPORT
template <class _FwdIter, class _BinaryPredicate>
_FwdIter
unique (_FwdIter, _FwdIter, _BinaryPredicate);


template <class _InputIter, class _OutputIter>
inline _OutputIter
unique_copy (_InputIter __first, _InputIter __last, _OutputIter __res)
{
    return  __unique_copy (__first, __last, __res,
                           _RWSTD_ITERATOR_CATEGORY (_OutputIter, __res));
}


template <class _InputIter, class _OutputIter, class _BinaryPredicate>
inline _OutputIter
unique_copy (_InputIter __first, _InputIter __last, _OutputIter __res,
             _BinaryPredicate __pred)
{
    return __unique_copy (__first, __last, __res, __pred,
                          _RWSTD_ITERATOR_CATEGORY (_OutputIter, __res));
}


template <class _BidirIter>
inline void
__reverse (_BidirIter __first, _BidirIter __last,
           bidirectional_iterator_tag)
{
    // 25.2.9, p2: Complexity: exactly (last - first) / 2 calls
    //             to std::iter_swap()
    for (; !(__first == __last) && !(__first == --__last); ++__first)
        _STD::iter_swap (__first, __last);
}


template <class _RandomAccessIter>
inline void
__reverse (_RandomAccessIter __first, _RandomAccessIter __last,
           random_access_iterator_tag)
{
    // 25.2.9, p2: Complexity: exactly (last - first) / 2 calls
    //             to std::iter_swap()
    if (!(__first == __last))
        for (; __first < --__last; ++__first)
            _STD::iter_swap (__first, __last);
}


template <class _BidirIter>
inline void
reverse (_BidirIter __first, _BidirIter __last)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    __reverse (__first, __last, _RWSTD_ITERATOR_CATEGORY (_BidirIter, __first));
}


template <class _BidirIter, class _OutputIter>
inline _OutputIter
reverse_copy (_BidirIter __first, _BidirIter __last, _OutputIter __res)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (; !(__first == __last); ++__res)
        *__res = *--__last;
    return __res;
}


_EXPORT
template <class _FwdIter, class _Dist>
void __rotate (_FwdIter, _FwdIter, _FwdIter, _Dist*, forward_iterator_tag);


template <class _BidirIter, class _Dist>
inline void
__rotate (_BidirIter __first, _BidirIter __middle, _BidirIter __last,
          _Dist*, bidirectional_iterator_tag)
{
    _STD::reverse (__first, __middle);
    _STD::reverse (__middle, __last);
    _STD::reverse (__first, __last);
}


_EXPORT
template <class _EuclideanRingElement>
_EuclideanRingElement
__gcd (_EuclideanRingElement, _EuclideanRingElement);


_EXPORT
template <class _RandomAccessIter, class _Dist, class _TypeT>
void __rotate_cycle (_RandomAccessIter, _RandomAccessIter, _RandomAccessIter,
                     _Dist, _TypeT*);


_EXPORT
template <class _RandomAccessIter, class _Dist>
void __rotate (_RandomAccessIter, _RandomAccessIter, _RandomAccessIter,
               _Dist*, random_access_iterator_tag);


template <class _FwdIter>
inline void rotate (_FwdIter __first, _FwdIter __middle, _FwdIter __last)
{
    if (!(__first == __middle || __middle == __last))
        __rotate (__first, __middle, __last,
                  _RWSTD_DIFFERENCE_TYPE (_FwdIter),
                  _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first));
}


template <class _FwdIter, class _OutputIter>
inline _OutputIter
rotate_copy (_FwdIter __first, _FwdIter __middle, _FwdIter __last,
             _OutputIter __res)
{
    return _STD::copy (__first, __middle, _STD::copy (__middle, __last, __res));
}


_EXPORT
template <class _RandomAccessIter, class _RandomNumberGenerator>
void random_shuffle (_RandomAccessIter, _RandomAccessIter,
                     _RandomNumberGenerator&);


template <class _RandomAccessIter>
inline void
random_shuffle (_RandomAccessIter __first, _RandomAccessIter __last)
{
    _RWSTD_SIZE_T (*__rand) (_RWSTD_SIZE_T) = _RW::__rw_rand;
    
    _STD::random_shuffle (__first, __last, __rand);
}


_EXPORT
template <class _BidirIter, class _Predicate>
_BidirIter partition (_BidirIter, _BidirIter, _Predicate);


_EXPORT
template <class _BidirIter, class _Predicate, class _TypeT, class _Dist>
_BidirIter
__stable_partition (_BidirIter, _BidirIter, _Predicate, _TypeT*, _Dist*);

template <class _BidirIter, class _Predicate>
inline _BidirIter
stable_partition (_BidirIter __first, _BidirIter __last, _Predicate __pred)
{
    return __stable_partition (__first, __last, __pred,
                               _RWSTD_VALUE_TYPE (_BidirIter),
                               _RWSTD_DIFFERENCE_TYPE (_BidirIter));
}


// 25.3.1 - Sorting [lib.alg.sort]


_EXPORT
template <class _RandomAccessIter, class _TypeT, class _Compare>
void __unguarded_linear_insert (_RandomAccessIter, _TypeT, _Compare);


_EXPORT
template <class _RandomAccessIter, class _Compare>
void __insertion_sort (_RandomAccessIter, _RandomAccessIter, _Compare);

template <class _RandomAccessIter, class _Compare>
inline void
__unguarded_insertion_sort (_RandomAccessIter __first, _RandomAccessIter __last,
                            _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (_RandomAccessIter __i = __first; !(__i == __last); ++__i)
        __unguarded_linear_insert (__i, *__i, __comp);
}


_EXPORT
template <class _RandomAccessIter, class _Dist, class _Compare>
void __introsort_loop (_RandomAccessIter, _RandomAccessIter, _Dist, _Compare);

_EXPORT
template <class _RandomAccessIter, class _Compare>
void __final_insertion_sort (_RandomAccessIter, _RandomAccessIter, _Compare);


// 25.3.1.1
template <class _RandomAccessIter, class _Compare>
inline void
sort (_RandomAccessIter __first, _RandomAccessIter __last, _Compare __comp)
{
    if (!(__first == __last))  {
        // introsort guarantees O(N * log(N)) in the worst case
        __introsort_loop (__first, __last, __last - __first, __comp);
        __final_insertion_sort (__first, __last, __comp);
    }
}


template <class _RandomAccessIter>
inline void sort (_RandomAccessIter __first, _RandomAccessIter __last)
{
    _STD::sort (__first, __last, _RWSTD_LESS (_RandomAccessIter));
}


_EXPORT
template <class _BidirIter, class _Dist, class _Compare>
void __merge_without_buffer (_BidirIter, _BidirIter, _BidirIter,
                             _Dist, _Dist, _Compare);

template <class _RandomAccessIter, class _Compare>
_INLINE void
__inplace_stable_sort (_RandomAccessIter __first, _RandomAccessIter __last,
                       _Compare __comp)
{
    if (__last - __first < 15)
        __insertion_sort (__first, __last, __comp);
    else {
        _RandomAccessIter __middle = __first + (__last - __first) / 2;
        __inplace_stable_sort (__first, __middle, __comp);
        __inplace_stable_sort (__middle, __last, __comp);
        __merge_without_buffer (__first, __middle, __last,
                                __middle - __first, __last - __middle, __comp);
    }
}


_EXPORT
template <class _RandomAccessIter, class _TypeT, class _Dist, class _Compare>
void
__stable_sort (_RandomAccessIter, _RandomAccessIter, _TypeT*, _Dist*, _Compare);


// 25.3.1.2
template <class _RandomAccessIter, class _Compare>
inline void stable_sort (_RandomAccessIter __first, _RandomAccessIter __last,
                         _Compare __comp)
{
    if (!(__first == __last))
        __stable_sort (__first, __last,
                       _RWSTD_VALUE_TYPE (_RandomAccessIter),
                       _RWSTD_DIFFERENCE_TYPE (_RandomAccessIter), __comp);
}


template <class _RandomAccessIter>
inline void stable_sort (_RandomAccessIter __first, _RandomAccessIter __last)
{
    _STD::stable_sort (__first, __last, _RWSTD_LESS (_RandomAccessIter));
}


// helper to work around the lack of iterator_traits
_EXPORT
template <class _RandomAccessIter, class _TypeT, class _Compare>
void __partial_sort (_RandomAccessIter, _RandomAccessIter,
                     _RandomAccessIter, _TypeT*, _Compare);

// 25.3.1.3
template <class _RandomAccessIter, class _Compare>
inline void partial_sort (_RandomAccessIter __first,
                          _RandomAccessIter __middle,
                          _RandomAccessIter __last, _Compare __comp)
{
    _RWSTD_ASSERT_RANGE (__first, __last);
    _RWSTD_ASSERT_RANGE (__first, __middle);

    if (!(__first == __middle))
        __partial_sort (__first, __middle, __last,
                        _RWSTD_VALUE_TYPE(_RandomAccessIter),
                        __comp);
}

template <class _RandomAccessIter>
inline void
partial_sort (_RandomAccessIter __first, _RandomAccessIter __middle,
              _RandomAccessIter __last)
{
    _STD::partial_sort (__first, __middle, __last,
                        _RWSTD_LESS (_RandomAccessIter));
}


// helper to work around the lack of iterator_traits
_EXPORT
template <class _InputIter, class _RandomAccessIter, class _Compare,
          class _Dist, class _TypeT>
_RandomAccessIter
__partial_sort_copy (_InputIter, _InputIter,
                     _RandomAccessIter, _RandomAccessIter,
                     _Compare, _Dist*, _TypeT*);


// 25.3.1.4
template <class _InputIter, class _RandomAccessIter, class _Compare>
inline _RandomAccessIter
partial_sort_copy (_InputIter __first, _InputIter __last,
                   _RandomAccessIter __res_first,
                   _RandomAccessIter __res_last, _Compare __comp)
{
    return __first == __last ? __res_first :
        __partial_sort_copy (__first, __last, __res_first, __res_last, __comp,
                             _RWSTD_DIFFERENCE_TYPE (_RandomAccessIter),
                             _RWSTD_VALUE_TYPE (_RandomAccessIter));
}


template <class _InputIter, class _RandomAccessIter>
inline _RandomAccessIter
partial_sort_copy (_InputIter __first1, _InputIter __last1,
                   _RandomAccessIter __first2, _RandomAccessIter __last2)
{
    return _STD::partial_sort_copy (__first1, __last1, __first2, __last2,
                                    _RWSTD_LESS (_InputIter));
}


_EXPORT
template <class _RandomAccessIter, class _TypeT, class _Compare>
void __nth_element (_RandomAccessIter, _RandomAccessIter,
                    _RandomAccessIter, _TypeT*, _Compare);

// 25.3.2 - Nth element [lib.alg.nth.element]

template <class _RandomAccessIter, class _Compare>
inline void nth_element (_RandomAccessIter __first, _RandomAccessIter __nth,
                         _RandomAccessIter __last, _Compare __comp)
{
    if (!(__first == __last))
        __nth_element (__first, __nth, __last,
                       _RWSTD_VALUE_TYPE (_RandomAccessIter), __comp);
}

template <class _RandomAccessIter>
inline void nth_element (_RandomAccessIter __first, _RandomAccessIter __nth,
                         _RandomAccessIter __last)
{
    _STD::nth_element (__first, __nth, __last, _RWSTD_LESS (_RandomAccessIter));
}


// 25.3.3 - Binary search [lib.alg.binary.search]

_EXPORT
template <class _FwdIter, class _TypeT, class _Compare, class _Dist>
_FwdIter __lower_bound (_FwdIter, _FwdIter, const _TypeT&, _Compare,
                        _Dist*, forward_iterator_tag);


template <class _FwdIter, class _TypeT, class _Compare, class _Dist>
inline _FwdIter
__lower_bound (_FwdIter __first, _FwdIter __last,
               const _TypeT &__val, _Compare __comp, _Dist*,
               bidirectional_iterator_tag)
{
    return __lower_bound (__first, __last, __val, __comp,
                          (_Dist*)0, forward_iterator_tag ());
}

_EXPORT
template <class _RandomAccessIter, class _TypeT, class _Compare, class _Dist>
_RandomAccessIter __lower_bound (_RandomAccessIter, _RandomAccessIter,
                                 const _TypeT&, _Compare, _Dist*,
                                 random_access_iterator_tag);

// 25.3.3.1
template <class _FwdIter, class _TypeT, class _Compare>
inline _FwdIter
lower_bound (_FwdIter __first,_FwdIter __last,
             const _TypeT &__val, _Compare __comp)
{
    return __lower_bound (__first, __last, __val, __comp,
                          _RWSTD_DIFFERENCE_TYPE (_FwdIter),
                          _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first));
}


template <class _FwdIter, class _TypeT>
inline _FwdIter
lower_bound (_FwdIter __first, _FwdIter __last, const _TypeT &__val)
{
    return _STD::lower_bound (__first, __last, __val,
                              _RWSTD_LESS (_FwdIter));
}


_EXPORT
template <class _FwdIter, class _TypeT, class _Compare, class _Dist>
_FwdIter __upper_bound (_FwdIter, _FwdIter, const _TypeT&, _Compare,
                        _Dist*, forward_iterator_tag);


template <class _FwdIter, class _TypeT, class _Compare, class _Dist>
inline _FwdIter
__upper_bound (_FwdIter __first, _FwdIter __last, const _TypeT &__val,
               _Compare __comp, _Dist*, bidirectional_iterator_tag)
{
    return __upper_bound (__first, __last, __val, __comp,
                          (_Dist*)0, forward_iterator_tag ());
}


_EXPORT
template <class _RandomAccessIter, class _TypeT, class _Compare,
          class _Dist>
_RandomAccessIter __upper_bound (_RandomAccessIter, _RandomAccessIter,
                                 const _TypeT&, _Compare, _Dist*,
                                 random_access_iterator_tag);

// 25.3.3.2
template <class _FwdIter, class _TypeT, class _Compare>
inline _FwdIter
upper_bound (_FwdIter __first,_FwdIter __last,
             const _TypeT &__val, _Compare __comp)
{
    return __upper_bound (__first, __last, __val, __comp,
                          _RWSTD_DIFFERENCE_TYPE (_FwdIter),
                          _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first));
}


template <class _FwdIter, class _TypeT>
inline _FwdIter
upper_bound (_FwdIter __first, _FwdIter __last, const _TypeT &__val)
{
    return _STD::upper_bound (__first, __last, __val,
                              _RWSTD_LESS (_FwdIter));
}


_EXPORT
template <class _FwdIter, class _TypeT, class _Compare, class _Dist>
pair<_FwdIter, _FwdIter>
__equal_range (_FwdIter, _FwdIter, const _TypeT&,
               _Compare, _Dist*, forward_iterator_tag);


template <class _FwdIter, class _TypeT, class _Compare, class _Dist>
inline pair<_FwdIter, _FwdIter>
__equal_range (_FwdIter __first, _FwdIter __last, const _TypeT &__val,
               _Compare __comp, _Dist*, bidirectional_iterator_tag)
{
    return __equal_range (__first, __last, __val, __comp,
                          (_Dist*)0, forward_iterator_tag());
}


_EXPORT
template <class _RandomAccessIter, class _TypeT, class _Compare, class _Dist>
pair<_RandomAccessIter, _RandomAccessIter>
__equal_range (_RandomAccessIter, _RandomAccessIter,
               const _TypeT&, _Compare, _Dist*, random_access_iterator_tag);


// 25.3.3.3
template <class _FwdIter, class _TypeT, class _Compare>
inline pair<_FwdIter, _FwdIter>
equal_range (_FwdIter __first, _FwdIter __last,
             const _TypeT &__val, _Compare __comp)
{
    return __equal_range (__first, __last, __val, __comp,
                          _RWSTD_DIFFERENCE_TYPE (_FwdIter),
                          _RWSTD_ITERATOR_CATEGORY (_FwdIter, __first));
}

template <class _FwdIter, class _TypeT>
inline pair<_FwdIter, _FwdIter>
equal_range (_FwdIter __first, _FwdIter __last, const _TypeT &__val)
{
    return _STD::equal_range (__first, __last, __val, _RWSTD_LESS (_FwdIter));
}


// 25.3.3.4
template <class _FwdIter, class _TypeT, class _Compare>
inline bool binary_search (_FwdIter __first, _FwdIter __last,
                           const _TypeT &__val, _Compare __comp)
{
    _FwdIter __i = _STD::lower_bound (__first, __last, __val, __comp);
    return !(__i == __last) && !__comp(__val, *__i);
}


template <class _FwdIter, class _TypeT>
inline bool
binary_search (_FwdIter __first, _FwdIter __last, const _TypeT &__val)
{
    return _STD::binary_search (__first, __last, __val, _RWSTD_LESS (_FwdIter));
}


// 25.3.4 - Merge [lib.alg.merge]

_EXPORT
template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter merge (_InputIter1 __first1, _InputIter1 __last1,
                   _InputIter2 __first2, _InputIter2 __last2,
                   _OutputIter __res, _Compare __comp);

template <class _InputIter1, class _InputIter2, class _OutputIter>
inline _OutputIter merge (_InputIter1 __first1, _InputIter1 __last1,
                          _InputIter2 __first2, _InputIter2 __last2,
                          _OutputIter __res)
{
    return _STD::merge (__first1, __last1, __first2, __last2, __res,
                        _RWSTD_LESS (_InputIter1));
}


_EXPORT
template <class _BidirIter, class _Dist, class _TypeT, class _Compare>
void __inplace_merge (_BidirIter, _BidirIter, _BidirIter,
                      _Dist*, _TypeT*, _Compare);

// 25.3.4, p6
template <class _BidirIter, class _Compare>
inline void
inplace_merge (_BidirIter __first, _BidirIter __middle, _BidirIter __last,
               _Compare __comp)
{
    if (!(__first == __middle || __middle == __last))
        __inplace_merge (__first, __middle, __last,
                         _RWSTD_DIFFERENCE_TYPE (_BidirIter),
                         _RWSTD_VALUE_TYPE (_BidirIter), __comp);
}



// 25.3.4, p6
template <class _BidirIter>
inline void
inplace_merge (_BidirIter __first, _BidirIter __middle, _BidirIter __last)
{
    _STD::inplace_merge (__first, __middle, __last, _RWSTD_LESS (_BidirIter));
}

// 25.3.5 - Set operations on sorted structures

// 25.3.5.1
_EXPORT
template <class _InputIter1, class _InputIter2, class _Compare>
bool includes (_InputIter1, _InputIter1, _InputIter2, _InputIter2, _Compare);

template <class _InputIter1, class _InputIter2>
inline bool includes (_InputIter1 __first1, _InputIter1 __last1,
                      _InputIter2 __first2, _InputIter2 __last2)
{
    return _STD::includes (__first1, __last1, __first2, __last2,
                           _RWSTD_LESS (_InputIter1));
}


// 25.3.5.2
_EXPORT
template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter
set_union (_InputIter1, _InputIter1, _InputIter2, _InputIter2,
           _OutputIter, _Compare);

template <class _InputIter1, class _InputIter2, class _OutputIter>
inline _OutputIter
set_union (_InputIter1 __first1, _InputIter1 __last1,
           _InputIter2 __first2, _InputIter2 __last2, _OutputIter __res)
{
    return _STD::set_union (__first1, __last1, __first2, __last2, __res,
                            _RWSTD_LESS (_InputIter1));
}


// 25.3.5.3
_EXPORT
template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter
set_intersection (_InputIter1, _InputIter1, _InputIter2, _InputIter2,
                  _OutputIter, _Compare);

template <class _InputIter1, class _InputIter2, class _OutputIter>
inline _OutputIter
set_intersection (_InputIter1 __first1, _InputIter1 __last1,
                  _InputIter2 __first2, _InputIter2 __last2, _OutputIter __res)
{
    return _STD::set_intersection (__first1, __last1, __first2, __last2,
                                   __res, _RWSTD_LESS (_InputIter1));
}


// 25.3.5.4
_EXPORT
template <class _InputIter1, class _InputIter2, class _OutputIter, 
          class _Compare>
_OutputIter
set_difference (_InputIter1, _InputIter1, _InputIter2, _InputIter2, 
                _OutputIter, _Compare);

template <class _InputIter1, class _InputIter2, class _OutputIter>
inline _OutputIter
set_difference (_InputIter1 __first1, _InputIter1 __last1,
                _InputIter2 __first2, _InputIter2 __last2, _OutputIter __res)
{
    return _STD::set_difference (__first1, __last1, __first2, __last2,
                                 __res, _RWSTD_LESS (_InputIter1));
}


// 25.3.5.5
_EXPORT
template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _Compare>
_OutputIter
set_symmetric_difference (_InputIter1, _InputIter1, _InputIter2, _InputIter2,
                          _OutputIter, _Compare);

template <class _InputIter1, class _InputIter2, class _OutputIter>
inline _OutputIter
set_symmetric_difference (_InputIter1 __first1, _InputIter1 __last1,
                          _InputIter2 __first2, _InputIter2 __last2,
                          _OutputIter __res)
{
    return _STD::set_symmetric_difference (__first1, __last1,
                                           __first2, __last2,
                                           __res, _RWSTD_LESS (_InputIter1));
}


// 25.3.6 - Heap operations
// defined in <rw/_heap.h>

// 25.3.7 - Minimum and maximum

// 25.3.7, p7
_EXPORT
template <class _FwdIter, class _Compare>
_FwdIter min_element (_FwdIter, _FwdIter, _Compare);

template <class _FwdIter>
inline _FwdIter min_element (_FwdIter __first, _FwdIter __last)
{
    return _STD::min_element (__first, __last, _RWSTD_LESS (_FwdIter));
}


// 25.3.7, p9
_EXPORT
template <class _FwdIter, class _Compare>
_FwdIter max_element (_FwdIter, _FwdIter, _Compare);


template <class _FwdIter>
inline _FwdIter max_element (_FwdIter __first, _FwdIter __last)
{
    return _STD::max_element (__first, __last, _RWSTD_LESS (_FwdIter));
}


// 25.3.9 - Permutation generators [lib.alg.permutation.generators]

// 25.3.9, p1
_EXPORT
template <class _BidirIter, class _Compare>
bool next_permutation (_BidirIter, _BidirIter, _Compare);

template <class _BidirIter>
inline bool next_permutation (_BidirIter __first, _BidirIter __last)
{
    return _STD::next_permutation (__first, __last, _RWSTD_LESS (_BidirIter));
}


// 25.3.9, p3
_EXPORT
template <class _BidirIter, class _Compare>
bool prev_permutation (_BidirIter, _BidirIter, _Compare);

template <class _BidirIter>
inline bool prev_permutation (_BidirIter __first, _BidirIter __last)
{
    return _STD::prev_permutation (__first, __last, _RWSTD_LESS (_BidirIter));
}


}   // namespace std


#undef _INLINE


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


#endif   // _RWSTD_ALGORITHM_INCLUDED