// -*- C++ -*-
/***************************************************************************
 *
 * algorithm - declarations and inline definitions of the Standard
 *              Library algorithms
 *
 * $Id: algorithm,v 1.1.1.1 2002/01/10 17:38:29 vkorstan Exp $
 *
 ***************************************************************************
 *
 * 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-2001 Rogue Wave Software, Inc.  All Rights Reserved.
 *
 * This computer software is owned by Rogue Wave Software, Inc. and is
 * protected by U.S. copyright laws and other laws and by international
 * treaties.  This computer software is furnished by Rogue Wave Software,
 * Inc. 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
 * computer software or any other copies thereof may not be provided or
 * otherwise made available to any other person.
 *
 * U.S. Government Restricted Rights.  This computer software is provided
 * with Restricted Rights.  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 or subparagraphs (c) (1) and (2) of the
 * Commercial Computer Software--Restricted Rights at 48 CFR 52.227-19,
 * as applicable.  Manufacturer is Rogue Wave Software, Inc., 5500
 * Flatiron Parkway, Boulder, Colorado 80301 USA.
 *
 **************************************************************************/

#ifndef _RWSTD_ALGORITHM_INCLUDED
#define _RWSTD_ALGORITHM_INCLUDED

#include <memory>
#include <utility>

#include <rw/_iterbase.h>
#include <rw/_algobase.h>
#include <rw/_defs.h>

#include _RWSTD_CSTDLIB


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


_RWSTD_NAMESPACE_BEGIN (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 __f)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

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


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

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

    while (!(__first == __last) && !(*__first == __value)) 
        ++__first;
    return __first;
}


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

    while (__first != __last && !__pred (*__first))
        ++__first;
    return __first;
}


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

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


// 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>
_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]

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

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]

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

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& __value)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _TYPENAME iterator_traits<_InputIter>::difference_type __n = 0;
    for (; __first != __last; ++__first)
        if (*__first == __value)
            ++__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))
            ++__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& __value, _Size& __n)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (;__first != __last;++__first) 
        if (*__first == __value)
            ++__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))
            ++__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
template <class _FwdIter1, class _FwdIter2, class _Distance1, class _Distance2>
_FwdIter1 __search (_FwdIter1, _FwdIter1, _FwdIter2, _FwdIter2,
                    _Distance1*, _Distance2*);

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
template <class _FwdIter, class _Distance, class _Size, class _TypeT>
_FwdIter __search_n (_FwdIter, _FwdIter, _Distance*, _Size, const _TypeT&);
 
template <class _FwdIter, class _Distance, class _Size, class _TypeT,
          class _BinaryPredicate>
_FwdIter __search_n (_FwdIter, _FwdIter, _Distance*, _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& __value)
{
    if (__count) 
        return __search_n (__first, __last, _RWSTD_DIFFERENCE_TYPE (_FwdIter),
                           __count, __value);
    return __first;
}


template <class _FwdIter, class _Size, class _TypeT, class _BinaryPredicate>
inline _FwdIter search_n (_FwdIter __first, _FwdIter __last,
                          _Size __count, const _TypeT& __value,
                          _BinaryPredicate __pred)
{
    if (__count) 
        return __search_n (__first, __last,
                           _RWSTD_DIFFERENCE_TYPE (_FwdIter),
                           __count,__value, __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>
_FwdIter2 swap_ranges (_FwdIter1, _FwdIter1, _FwdIter2);

// 25.2.3 - Transform [lib.alg.transform]
template <class _InputIter, class _OutputIter, class _UnaryOperation>
_OutputIter transform (_InputIter, _InputIter, _OutputIter, _UnaryOperation);

template <class _InputIter1, class _InputIter2, class _OutputIter,
          class _BinaryOperation>
_OutputIter transform (_InputIter1, _InputIter1, _InputIter2, _OutputIter,
                       _BinaryOperation);

// 25.2.4 - Replace [lib.alg.replace]
template <class _FwdIter, class _TypeT>
void replace (_FwdIter, _FwdIter, const _TypeT&, const _TypeT&);

template <class _FwdIter, class _Predicate, class _TypeT>
void replace_if (_FwdIter, _FwdIter, _Predicate, const _TypeT&);

template <class _InputIter, class _OutputIter, class _TypeT>
_OutputIter replace_copy (_InputIter, _InputIter, _OutputIter,
                          const _TypeT&, const _TypeT&);

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>
void generate (_FwdIter, _FwdIter, _Generator);

template <class _OutputIter, class _Size, class _Generator>
void generate_n (_OutputIter, _Size, _Generator);

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

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& __value)
{
    __first = _STD::find (__first, __last, __value);
    _FwdIter __next = __first;
    return __first == __last ?
        __first : _STD::remove_copy (++__next, __last, __first, __value);
}


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 ?