algorithms.hpp

来自「用STL的方式封装了WindowsAPI、COM调用、ACE、ATL、MFC、W」· HPP 代码 · 共 1,555 行 · 第 1/3 页

/* /////////////////////////////////////////////////////////////////////////
 * File:        rangelib/algorithms.hpp
 *
 * Purpose:     Range algorithms.
 *
 * Created:     4th November 2003
 * Updated:     10th June 2006
 *
 * Thanks to:   Pablo Aguilar for requesting r_copy_if(); to Luoyi, for pointing
 *              out some gaps in the compatibility with the sequence_range.
 *
 * Home:        http://stlsoft.org/
 *
 * Copyright (c) 2003-2006, Matthew Wilson and Synesis Software
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * - Redistributions of source code must retain the above copyright notice, this
 *   list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimer in the documentation
 *   and/or other materials provided with the distribution.
 * - Neither the name(s) of Matthew Wilson and Synesis Software nor the names of
 *   any contributors may be used to endorse or promote products derived from
 *   this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 * ////////////////////////////////////////////////////////////////////// */


/** \file rangelib/algorithms.hpp Range algorithms
 *
 * This file includes the definition of the following algorithms:
 *
 * - r_accumulate()
 * - r_accumulate()
 * - r_copy()
 * - r_copy_if()
 * - r_count()
 * - r_count_if()
 * - r_distance()
 * - r_equal()
 * - r_exists()
 * - r_exists_if()
 * - r_fill()
 * - r_fill_n()
 * - r_find()
 * - r_find_if()
 * - r_for_each()
 * - r_generate()
 * - r_max_element()
 * - r_min_element()
 * - r_replace()
 * - r_replace_copy()
 * - r_replace_if()
 * - r_replace_copy_if()
 */

#ifndef RANGELIB_INCL_RANGELIB_HPP_ALGORITHMS
#define RANGELIB_INCL_RANGELIB_HPP_ALGORITHMS

#ifndef STLSOFT_DOCUMENTATION_SKIP_SECTION
# define RANGELIB_VER_RANGELIB_HPP_ALGORITHMS_MAJOR    2
# define RANGELIB_VER_RANGELIB_HPP_ALGORITHMS_MINOR    2
# define RANGELIB_VER_RANGELIB_HPP_ALGORITHMS_REVISION 2
# define RANGELIB_VER_RANGELIB_HPP_ALGORITHMS_EDIT     35
#endif /* !STLSOFT_DOCUMENTATION_SKIP_SECTION */

/* /////////////////////////////////////////////////////////////////////////
 * Auto-generation and compatibility
 */

/*
[Incompatibilies-start]
STLSOFT_COMPILER_IS_MSVC:     _MSC_VER < 1200
STLSOFT_COMPILER_IS_MWERKS:   (__MWERKS__ & 0xFF00) < 0x3000
[Incompatibilies-end]
 */

/* /////////////////////////////////////////////////////////////////////////
 * Includes
 */

#ifndef RANGELIB_INCL_RANGELIB_HPP_RANGELIB
# include <rangelib/rangelib.hpp>
#endif /* !RANGELIB_INCL_RANGELIB_HPP_RANGELIB */
#ifndef RANGELIB_INCL_RANGELIB_HPP_RANGE_CATEGORIES
# include <rangelib/range_categories.hpp>
#endif /* !RANGELIB_INCL_RANGELIB_HPP_RANGE_CATEGORIES */
#ifndef RANGELIB_INCL_RANGELIB_HPP_EXCEPTIONS
# include <rangelib/exceptions.hpp>
#endif /* !RANGELIB_INCL_RANGELIB_HPP_EXCEPTIONS */
#ifndef RANGELIB_INCL_RANGELIB_HPP_BASIC_INDIRECT_RANGE_ADAPTOR
# include <rangelib/basic_indirect_range_adaptor.hpp>
#endif /* !RANGELIB_INCL_RANGELIB_HPP_BASIC_INDIRECT_RANGE_ADAPTOR */
#include <algorithm>
#include <numeric>

/* /////////////////////////////////////////////////////////////////////////
 * Namespace
 */

#ifndef RANGELIB_NO_NAMESPACE
# if defined(_STLSOFT_NO_NAMESPACE) || \
     defined(STLSOFT_DOCUMENTATION_SKIP_SECTION)
/* There is no stlsoft namespace, so must define ::rangelib */
namespace rangelib
{
# else
/* Define stlsoft::rangelib_project */

namespace stlsoft
{

namespace rangelib_project
{

# endif /* _STLSOFT_NO_NAMESPACE */
#endif /* !RANGELIB_NO_NAMESPACE */

/* /////////////////////////////////////////////////////////////////////////
 * Functions
 */

/* *********************************************************
 * accumulate (2)
 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline T r_accumulate_2_impl(R r, T val, notional_range_tag const &)
{
    for(; r; ++r)
    {
        val = val + *r;
    }

    return val;
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline T r_accumulate_2_impl(R r, T val, iterable_range_tag const &)
{
    return std::accumulate(r.begin(), r.end(), val);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline T r_accumulate_2_impl(R r, T val, basic_indirect_range_tag const &)
{
    return indirect_range_adaptor<R>(r).accumulate(val);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline T r_accumulate_2_impl(R r, T val, indirect_range_tag const &)
{
    return r.accumulate(val);
}

/// accumulate() for ranges
///
/// \param r The range
/// \param val The initial value
/// \retval The sum of the accumulate items and the initial value
///
/// \note: Supports Notional, Iterable and Indirect Range types
template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline T r_accumulate(R r, T val)
{
    return r_accumulate_2_impl(r, val, r);
}

/* *********************************************************
 * accumulate (3)
 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        ,   ss_typename_param_k P
        >
inline T r_accumulate_3_impl(R r, T val, P pred, notional_range_tag const &)
{
    for(; r; ++r)
    {
        val = pred(val, *r);
    }

    return val;
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        ,   ss_typename_param_k P
        >
inline T r_accumulate_3_impl(R r, T val, P pred, iterable_range_tag const &)
{
    return std::accumulate(r.begin(), r.end(), val, pred);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        ,   ss_typename_param_k P
        >
inline T r_accumulate_2_impl(R r, T val, P pred, basic_indirect_range_tag const &)
{
    return indirect_range_adaptor<R>(r).accumulate(val, pred);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        ,   ss_typename_param_k P
        >
inline T r_accumulate_3_impl(R r, T val, P pred, indirect_range_tag const &)
{
    return r.accumulate(val, pred);
}

/// accumulate() for ranges
///
/// \param r The range
/// \param val The initial value
/// \param pred The predicate applied to each entry
/// \retval The sum of the accumulate items and the initial value
///
/// \note: Supports Notional, Iterable and Indirect Range types
template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        ,   ss_typename_param_k P
        >
inline T r_accumulate(R r, T val, P pred)
{
    return r_accumulate_3_impl(r, val, pred, r);
}


/* *********************************************************
 * copy
 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k O
        >
inline O r_copy_impl(R r, O o, notional_range_tag const &)
{
    for(; r; ++r, ++o)
    {
        *o = *r;
    }

    return o;
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k O
        >
inline O r_copy_impl(R r, O o, iterable_range_tag const &)
{
    return std::copy(r.begin(), r.end(), o);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k O
        >
inline O r_copy_impl(R r, O o, indirect_range_tag const &)
{
    return r.copy(o);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k O
        >
inline O r_copy_impl(R r, O o, basic_indirect_range_tag const &)
{
    return indirect_range_adaptor<R>(r).copy(o);
}

/// Copies the contents of the range to the output iterator
///
/// \param r The range whose elements are to be copied
/// \param o The output iterator to receive the elements
///
/// \note: Supports Notional, Iterable and Indirect Range types
template<   ss_typename_param_k R
        ,   ss_typename_param_k O
        >
inline O r_copy(R r, O o)
{
    return r_copy_impl(r, o, r);
}


/* *********************************************************
 * copy_if
 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k O
        ,   ss_typename_param_k P
        >
inline O r_copy_if_impl(R r, O o, P pred, notional_range_tag const &)
{
    for(; r; ++r)
    {
        if(pred(*r))
        {
            *o = *r;

            ++o;
        }
    }

    return o;
}

#if 0 /* Not defined, since copy_if() is not in standard, so we reuse the Notional Range implementation */
template<   ss_typename_param_k R
        ,   ss_typename_param_k O
        ,   ss_typename_param_k P
        >
inline O r_copy_if_impl(R r, O o, P pred, iterable_range_tag const &)
{
    return std::copy_if(r.begin(), r.end(), o);
}
#endif /* 0 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k O
        ,   ss_typename_param_k P
        >
inline O r_copy_if_impl(R r, O o, P pred, indirect_range_tag const &)
{
    return r.copy_if(o);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k O
        ,   ss_typename_param_k P
        >
inline O r_copy_if_impl(R r, O o, P pred, basic_indirect_range_tag const &)
{
    return indirect_range_adaptor<R>(r).copy_if(o);
}

/// Copies the contents of the range to the output iterator
///
/// \param r The range whose elements are to be copied
/// \param o The output iterator to receive the elements
/// \param pred The predicate used to select the elements
///
/// \note: Supports Notional, Iterable and Indirect Range types
template<   ss_typename_param_k R
        ,   ss_typename_param_k O
        ,   ss_typename_param_k P
        >
inline O r_copy_if(R r, O o, P pred)
{
    return r_copy_if_impl(r, o, pred, r);
}


/* *********************************************************
 * count
 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline ss_size_t r_count_impl(R r, const T &val, notional_range_tag const &)
{
    ss_size_t n;

    for(n = 0; r; ++r)
    {
        if(val == *r)
        {
            ++n;
        }
    }

    return n;
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline ss_size_t r_count_impl(R r, const T &val, iterable_range_tag const &)
{
    return std::count(r.begin(), r.end(), val);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline ss_size_t r_count_impl(R r, const T &val, basic_indirect_range_tag const &)
{
    return indirect_range_adaptor<R>(r).count(val);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline ss_size_t r_count_impl(R r, const T &val, indirect_range_tag const &)
{
    return r.count(val);
}

/// Counts the number of instances of a given value in the range
///
/// \param r The range
/// \param val The value to search for
/// \retval The number of elements in the range matching \c val
///
/// \note: Supports Notional, Iterable and Indirect Range types
template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline ss_size_t r_count(R r, const T &val)
{
    return r_count_impl(r, val, r);
}


/* *********************************************************
 * count_if
 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        >
inline ss_size_t r_count_if_impl(R r, P pred, notional_range_tag const &)
{
    ss_size_t n;

    for(n = 0; r; ++r)
    {
        if(pred(*r))
        {
            ++n;
        }
    }

    return n;
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        >
inline ss_size_t r_count_if_impl(R r, P pred, iterable_range_tag const &)
{
    return std::count_if(r.begin(), r.end(), pred);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        >
inline ss_size_t r_count_if_impl(R r, P pred, basic_indirect_range_tag const &)
{
    return indirect_range_adaptor<R>(r).count_if(pred);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        >
inline ss_size_t r_count_if_impl(R r, P pred, indirect_range_tag const &)
{
    return r.count_if(pred);
}

/// Counts the number of instances matching the given predicate in the range
///
/// \param r The range
/// \param pred The predicate applied to each entry
/// \retval The number of elements in the range matching \c val
///
/// \note: Supports Notional, Iterable and Indirect Range types
template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        >
inline ss_size_t r_count_if(R r, P pred)
{
    return r_count_if_impl(r, pred, r);
}


/* *********************************************************
 * distance
 */

template <ss_typename_param_k R>
inline ss_ptrdiff_t r_distance_1_impl(R r, notional_range_tag const &)
{
    ss_ptrdiff_t    d = 0;

    for(; r; ++r, ++d)
    {}

    return d;
}