algorithm.cc

realview22.rar

/***************************************************************************
 *
 * algorithm.cc - Non-inline definitions for the Standard Library algorithms
 *
 * $Id: algorithm.cc,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.
 *
 **************************************************************************/

#include <rw/_random.h>
#include <rw/_defs.h>


_RWSTD_NAMESPACE_BEGIN (std)


template <class _FwdIter1, class _FwdIter2, class _Distance>
_FwdIter1 __find_end (_FwdIter1 __first1, _FwdIter1 __last1,
                      _FwdIter2 __first2, _FwdIter2 __last2,
                      _Distance*)
{
    _RWSTD_ASSERT_RANGE (__first1, __last1);
    _RWSTD_ASSERT_RANGE (__first2, __last2);

    _Distance __dist1 = _DISTANCE (__first2, __last2, _Distance);

    if (!__dist1)
        return __last1;

    _Distance __dist2 = _DISTANCE (__first1, __last1, _Distance);

    _FwdIter1 __res = __last1;

    while (__dist2 >= __dist1) {
        if (equal (__first2, __last2, __first1))
            __res  = __first1;

        __dist2 = _DISTANCE (++__first1, __last1, _Distance);
    }
    return __res;
}



template <class _FwdIter1, class _FwdIter2,
    class _BinaryPredicate, class _Distance>
_FwdIter1 __find_end (_FwdIter1 __first1, _FwdIter1 __last1,
                      _FwdIter2 __first2, _FwdIter2 __last2,
                      _BinaryPredicate __pred, _Distance*)
{
    _RWSTD_ASSERT_RANGE (__first1, __last1);
    _RWSTD_ASSERT_RANGE (__first2, __last2);

    _Distance __dist1 = _DISTANCE (__first2, __last2, _Distance);

    if (!__dist1)
        return __last1;

    _Distance __dist2 = _DISTANCE (__first1, __last1, _Distance);

    _FwdIter1 __save = __last1;

    while (__dist2 >= __dist1)
    {
        if (_STD::equal (__first2, __last2, __first1, __pred))
            __save = __first1;
        __dist2 = _DISTANCE (++__first1, __last1, _Distance);
    }
    return __save;
}


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

    if (__first2 == __last2)
        return __last1;
    _FwdIter1 __next = __first1;
    while (__next != __last1)
    {
        if (_STD::find (__first2, __last2, *__next) != __last2)
            return __next;
        ++__next;
    }
    return __last1;
}


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

    if (__first2 == __last2)
        return __last1;

    for (_FwdIter1 __next = __first1; __next != __last1; ++__next)
        for (_FwdIter2 __iter = __first2; __iter != __last2; ++__iter)
            if (__pred (*__next, *__iter))
                return __next;
    return __last1;
}


template <class _FwdIter>
_FwdIter adjacent_find (_FwdIter __first, _FwdIter __last)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (__first == __last) return __last;
    _FwdIter __next = __first;
    while (++__next != __last)
    {
        if (*__first == *__next) return __first;
        __first = __next;
    }
    return __last;
}


template <class _FwdIter, class _BinaryPredicate>
_FwdIter adjacent_find (_FwdIter __first, _FwdIter __last,
                        _BinaryPredicate __pred)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    if (__first == __last) return __last;
    _FwdIter __next = __first;
    while (++__next != __last) {
        if (__pred (*__first, *__next))
            return __first;
        __first = __next;
    }
    return __last;
}



template <class _FwdIter1, class _FwdIter2,
    class _Distance1, class _Distance2>
_FwdIter1 __search (_FwdIter1 __first1, _FwdIter1 __last1,
                    _FwdIter2 __first2, _FwdIter2 __last2,
                    _Distance1*, _Distance2*)
{
    _RWSTD_ASSERT_RANGE (__first1, __last1);
    _RWSTD_ASSERT_RANGE (__first2, __last2);

    _Distance1 __dist1 = _DISTANCE (__first1, __last1, _Distance1);
    _Distance2 __dist2 = _DISTANCE (__first2, __last2, _Distance2);

    if (__dist1 < __dist2) return __last1;

    _FwdIter1 __cur1 = __first1;
    _FwdIter2 __cur2 = __first2;

    while (__cur2 != __last2) {
        if (!(*__cur1 == *__cur2)) {
            ++__cur1;
            ++__cur2;
            if (__dist1-- == __dist2)
                return __last1;
            else {
                __cur1 = ++__first1;
                __cur2 = __first2;
            }
        }
        else {
            ++__cur1;
            ++__cur2;
        }
    }

    return (__cur2 == __last2) ? __first1 : __last1;
}

template <class _FwdIter1, class _FwdIter2,
    class _BinaryPredicate, class _Distance1, class _Distance2>
_FwdIter1 __search (_FwdIter1 __first1, _FwdIter1 __last1,
                    _FwdIter2 __first2, _FwdIter2 __last2,
                    _BinaryPredicate __pred, _Distance1*, _Distance2*)
{
    _RWSTD_ASSERT_RANGE (__first1, __last1);
    _RWSTD_ASSERT_RANGE (__first2, __last2);

    _Distance1 __dist1 = _DISTANCE (__first1, __last1, _Distance1);
    _Distance2 __dist2 = _DISTANCE (__first2, __last2, _Distance2);

    if (__dist1 < __dist2) return __last1;

    _FwdIter1 __cur1 = __first1;
    _FwdIter2 __cur2 = __first2;

    while (__cur2 != __last2) {
        if (!__pred (*__cur1, *__cur2)) {
            ++__cur1;
            ++__cur2;
            if (__dist1-- == __dist2)
                return __last1;
            else {
                __cur1 = ++__first1;
                __cur2 = __first2;
            }
        }
        else {
            ++__cur1;
            ++__cur2;
        }
    }

    return (__cur2 == __last2) ? __first1 : __last1;
}

template <class _FwdIter, class _Distance, class _Size, class _TypeT>
_FwdIter __search_n (_FwdIter __first, _FwdIter __last,
                     _Distance*, _Size __count, const _TypeT& __val)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _Distance __dist = _DISTANCE (__first, __last, _Distance);

    if (__dist < __count || __count <= 0) return __last;

    _Distance        __span    = __dist - __count;
    _Size            __matches = 0;
    _FwdIter         __current = __first;

    while (__current != __last) {
        if (!(*__current == __val)) {
            if (__span < __matches + 1)
                return __last;
            __span   -= __matches + 1;
            __matches = 0;
            __first   = ++__current;
        }
        else {
            if (++__matches == __count)
                return __first;
            ++__current;
        }
    }

    return __last;
}

template <class _FwdIter, class _Distance, class _Size, class _TypeT,
    class _BinaryPredicate>
_FwdIter __search_n (_FwdIter __first, _FwdIter __last,
                     _Distance*, _Size __count, const _TypeT& __val,
                     _BinaryPredicate __pred)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _Distance __dist = _DISTANCE (__first, __last, _Distance);

    if (__dist < __count || __count <= 0) return __last;

    _Distance        __span    = __dist - __count;
    _Size            __matches = 0;
    _FwdIter __current = __first;

    while (__current != __last) {
        if (!__pred (*__current, __val)) {
            if (__span < __matches + 1)
                return __last;
            __span   -= __matches + 1;
            __matches = 0;
            __first   = ++__current;
        }
        else {
            if (++__matches == __count)
                return __first;
            ++__current;
        }
    }

    return __last;
}

//
// Modifying sequence operations.
//

template <class _Iter, class _OutputIter, class _Predicate, class _TypeT>
_OutputIter replace_copy_if (_Iter __first, _Iter __last,
                             _OutputIter __res, _Predicate __pred,
                             const _TypeT& __new_value)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (; __first != __last; ++__res, ++__first)
        if (__pred (*__first))
            *__res = __new_value;
        else
            *__res = *__first;
    return __res;
}

template <class _InputIter, class _OutputIter, class _TypeT>
_OutputIter remove_copy (_InputIter __first, _InputIter __last,
                         _OutputIter __res, const _TypeT& __val)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (; __first != __last; ++__first)
        if (!(*__first == __val)) {
            *__res = *__first;
            ++__res;
        }
    return __res;
}

template <class _InputIter, class _OutputIter, class _Predicate>
_OutputIter remove_copy_if (_InputIter __first, _InputIter __last,
                            _OutputIter __res, _Predicate __pred)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    for (; __first != __last; ++__first)
        if (!__pred (*__first)) {
            *__res = *__first;
            ++__res;
        }
    return __res;
}

template <class _InputIter, class _FwdIter>
_FwdIter __unique_copy (_InputIter __first, _InputIter __last,
                        _FwdIter __res, forward_iterator_tag)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    *__res = *__first;
    while (++__first != __last)
        if (!(*__res == *__first))
            *++__res = *__first;
    return ++__res;
}

template <class _InputIter, class _OutputIter, class _TypeT>
_OutputIter __unique_copy (_InputIter __first, _InputIter __last,
                           _OutputIter __res, _TypeT*)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _TypeT __val = *__first;
    *__res = __val;
    while (++__first != __last) {
        if (!(__val == *__first)) {
            __val = *__first;
            *++__res = __val;
        }
    }
    return ++__res;
}

template <class _InputIter, class _FwdIter, class _BinaryPredicate>
_FwdIter __unique_copy (_InputIter __first, _InputIter __last,
                        _FwdIter __res,
                        _BinaryPredicate __pred,
                        forward_iterator_tag)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    *__res = *__first;
    while (++__first != __last)
        if (!__pred (*__res, *__first))
            *++__res = *__first;
    return ++__res;
}


template <class _InputIter, class _OutputIter, class _BinaryPredicate,
    class _TypeT>
_OutputIter __unique_copy (_InputIter __first, _InputIter __last,
                           _OutputIter __res,
                           _BinaryPredicate __pred, _TypeT*)
{
    _RWSTD_ASSERT_RANGE (__first, __last);

    _TypeT __val = *__first;
    *__res = __val;
    while (++__first != __last)  {
        if (!__pred (__val, *__first))   {
            __val = *__first;
            *++__res = __val;
        }
    }
    return ++__res;
}


template <class _FwdIter, class _Distance>
void __rotate (_FwdIter __first, _FwdIter __middle,
               _FwdIter __last, _Distance*, forward_iterator_tag)
{
    _RWSTD_ASSERT_IN_RANGE (__middle, __first, __last); 

    _FwdIter __i = __middle;
    for (; ; )