algorithms.hpp

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

template <ss_typename_param_k R>
inline ss_ptrdiff_t r_distance_1_impl(R r, iterable_range_tag const &)
{
    return std::distance(r.begin(), r.end());
}

template <ss_typename_param_k R>
inline ss_ptrdiff_t r_distance_1_impl(R r, indirect_range_tag const &)
{
    return r.distance();
}

template <ss_typename_param_k R>
inline ss_ptrdiff_t r_distance_1_impl(R r, basic_indirect_range_tag const &)
{
    return indirect_range_adaptor<R>(r).distance();
}

/// Counts the number of instances in the range
///
/// \param r The range
/// \retval The number of elements in the range
///
/// \note: Supports Notional, Iterable and Indirect Range types
template <ss_typename_param_k R>
inline ss_ptrdiff_t r_distance(R r)
{
    return r_distance_1_impl(r, r);
}

/* *********************************************************
 * equal (2)
 */

template<   ss_typename_param_k R1
        ,   ss_typename_param_k R2
        >
inline ss_bool_t r_equal_1_impl(R1 r1, R2 r2, notional_range_tag const &, notional_range_tag const &)
{
    for(; r1 && r2; ++r1, ++r2)
    {
        if(*r1 != *r2)
        {
            return false;
        }
    }

    return true;
}

template<   ss_typename_param_k R1
        ,   ss_typename_param_k R2
        >
inline ss_bool_t r_equal_1_impl(R1 r1, R2 r2, iterable_range_tag const &, iterable_range_tag const &)
{
    return std::equal(r1.begin(), r1.end(), r2.begin());
}

/// Determines whether two ranges are equal
///
/// \param r1 The first range to compare
/// \param r2 The second range to compare
/// \retval true if the first N elements in the second range match the N elements in the first range.
///
/// \note: Supports Notional and Iterable Range types
template<   ss_typename_param_k R1
        ,   ss_typename_param_k R2
        >
inline ss_bool_t r_equal(R1 r1, R2 r2)
{
    STLSOFT_ASSERT(r_distance(r1) <= r_distance(r2));

    return r_equal_1_impl(r1, r2, r1, r2);
}

/* *********************************************************
 * equal (3)
 */

template<   ss_typename_param_k R1
        ,   ss_typename_param_k R2
        ,   ss_typename_param_k P
        >
inline ss_bool_t r_equal_1_impl(R1 r1, R2 r2, P pred, notional_range_tag const &, notional_range_tag const &)
{
    for(; r1 && r2; ++r1, ++r2)
    {
        if(!pred(*r1, *r2))
        {
            return false;
        }
    }

    return true;
}

template<   ss_typename_param_k R1
        ,   ss_typename_param_k R2
        ,   ss_typename_param_k P
        >
inline ss_bool_t r_equal_1_impl(R1 r1, R2 r2, P pred, iterable_range_tag const &, iterable_range_tag const &)
{
    return std::equal(r1.begin(), r1.end(), r2.begin(), pred);
}

/// Determines whether two ranges are equal, as defined by a predicate
///
/// \param r1 The first range to compare
/// \param r2 The second range to compare
/// \param pred The predicate which evaluates matches between elements of the two ranges
/// \retval true if the first N elements in the second range match the N elements in the first range.
///
/// \note: Supports Notional and Iterable Range types
template<   ss_typename_param_k R1
        ,   ss_typename_param_k R2
        ,   ss_typename_param_k P
        >
inline ss_bool_t r_equal(R1 r1, R2 r2, P pred)
{
    STLSOFT_ASSERT(r_distance(r1) <= r_distance(r2));

    return r_equal_1_impl(r1, r2, pred, r1, r2);
}

/* *********************************************************
 * exists
 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline ss_bool_t r_exists_impl(R r, T const &val, notional_range_tag const &)
{
    for(; r; ++r)
    {
        if(val == *r)
        {
            return true;
        }
    }

    return false;
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline ss_bool_t r_exists_impl(R r, T const &val, iterable_range_tag const &)
{
    return std::find(r.begin(), r.end(), val) != r.end();
}

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

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

/// Determines whether the given value exists in the range
///
/// \param r The range
/// \param val The value to search for
///
/// \note: Supports Notional, Iterable and Indirect Range types
template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline ss_bool_t r_exists(R r, T const &val)
{
    return r_exists_impl(r, val, r);
}

/* *********************************************************
 * exists_if (1)
 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        >
inline ss_bool_t r_exists_if_1_impl(R r, P pred, notional_range_tag const &)
{
    for(; r; ++r)
    {
        if(pred(*r))
        {
            return true;
        }
    }

    return false;
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        >
inline ss_bool_t r_exists_if_1_impl(R r, P pred, iterable_range_tag const &)
{
    return std::find(r.begin(), r.end(), pred) != r.end();
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        >
inline ss_bool_t r_exists_if_1_impl(R r, P pred, basic_indirect_range_tag const &)
{
    return indirect_range_adaptor<R>(r).exists_if(pred);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        >
inline ss_bool_t r_exists_if_1_impl(R r, P pred, indirect_range_tag const &)
{
    return r.exists_if(pred);
}

/// Determines whether a value matching the given predicate exists in the range
///
/// \param r The range
/// \param pred The predicate used to match the items
///
/// \note: Supports Notional, Iterable and Indirect Range types
template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        >
inline ss_bool_t r_exists_if(R r, P pred)
{
    return r_exists_if_1_impl(r, pred, r);
}

/* *********************************************************
 * exists_if (2)
 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        ,   ss_typename_param_k T
        >
inline ss_bool_t r_exists_if_2_impl(R r, P pred, T &result, notional_range_tag const &)
{
    for(; r; ++r)
    {
        if(pred(*r))
        {
            result = *r;

            return true;
        }
    }

    return false;
}

template<   ss_typename_param_k I
        ,   ss_typename_param_k V
        >
inline ss_bool_t r_exists_if_2_impl_helper_(I from, I to, V &val)
{
    if(from == to)
    {
        return false;
    }
    else
    {
        val = *from;

        return true;
    }
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        ,   ss_typename_param_k T
        >
inline ss_bool_t r_exists_if_2_impl(R r, P pred, T &result, iterable_range_tag const &)
{
    return r_exists_if_2_impl_helper_(std::find(r.begin(), r.end(), pred), r.end());
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        ,   ss_typename_param_k T
        >
inline ss_bool_t r_exists_if_2_impl(R r, P pred, T &result, basic_indirect_range_tag const &)
{
    return indirect_range_adaptor<R>(r).exists_if(pred, result);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        ,   ss_typename_param_k T
        >
inline ss_bool_t r_exists_if_2_impl(R r, P pred, T &result, indirect_range_tag const &)
{
    return r.exists_if(pred, result);
}

/// Determines whether a value matching the given predicate exists in the range
///
/// \param r The range
/// \param pred The predicate used to match the items
/// \param result The returned result
///
/// \note: Supports Notional, Iterable and Indirect Range types
template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        ,   ss_typename_param_k T
        >
inline R r_exists_if(R r, P pred, T &result)
{
    return r_exists_if_2_impl(r, pred, result, r);
}

/* *********************************************************
 * fill
 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline void r_fill_impl(R r, T const &val, iterable_range_tag const &)
{
    std::fill(r.begin(), r.end(), val);
}

/// Sets the elements in the range to the given value
///
/// \param r The range
/// \param val The value to assign to all elements in the range
///
/// \note: Supports Iterable Range type
template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline void r_fill(R r, const T &val)
{
    r_fill_impl(r, val, r);
}

/* *********************************************************
 * fill_n
 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k S
        ,   ss_typename_param_k T
        >
inline void r_fill_n_impl(R r, S n, T const &val, iterable_range_tag const &)
{
    std::fill(r.begin(), n, val);
}

/// Sets the first \c n elements in the range to the given value
///
/// \param r The range
/// \param n The number of elements to set. This must be <code><= r_distance(r)</code>
/// \param val The value to assign to all elements in the range
///
/// \note: Supports Iterable Range type
template<   ss_typename_param_k R
        ,   ss_typename_param_k S
        ,   ss_typename_param_k T
        >
inline void r_fill_n(R r, S n, T const &val)
{
    STLSOFT_ASSERT(n <= r_distance(r));

    r_fill_1_impl(r, n, val, r);
}

/* *********************************************************
 * find
 */

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

    return r;
}

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

/// Finds the first instance of the given value in the range
///
/// \param r The range
/// \param val The value to find
///
/// \note: Supports Notional and Iterable Range types
template<   ss_typename_param_k R
        ,   ss_typename_param_k T
        >
inline R r_find(R r, T const &val)
{
    return r_find_impl(r, val, r);
}

/* *********************************************************
 * find_if
 */

// find_if

template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        >
inline R r_find_if_impl(R r, P pred, notional_range_tag const &)
{
    for(; r; ++r)
    {
        if(pred(*r))
        {
            break;
        }
    }

    return r;
}

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

/// Finds the first instance of a value in the range matching the given predicate
///
/// \param r The range
/// \param pred The value to find
///
/// \note: Supports Notional and Iterable Range types
template<   ss_typename_param_k R
        ,   ss_typename_param_k P
        >
inline R r_find_if(R r, P pred)
{
    return r_find_if_impl(r, pred, r);
}

/* *********************************************************
 * for_each
 */

template<   ss_typename_param_k R
        ,   ss_typename_param_k F
        >
inline F r_for_each_impl(R r, F f, notional_range_tag const &)
{
    for(; r; ++r)
    {
        f(*r);
    }

    return f;
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k F
        >
inline F r_for_each_impl(R r, F f, iterable_range_tag const &)
{
    return std::for_each(r.begin(), r.end(), f);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k F
        >
inline F r_for_each_impl(R r, F f, basic_indirect_range_tag const &)
{
    return indirect_range_adaptor<R>(r).for_each(f);
}

template<   ss_typename_param_k R
        ,   ss_typename_param_k F
        >
inline F r_for_each_impl(R r, F f, indirect_range_tag const &)
{
    return r.for_each(f);
}

/// Applies the given function to every element in the range
///
/// \param r The range
/// \param f The function to apply
///
/// \note: Supports Notional, Iterable and Indirect Range types
template<   ss_typename_param_k R
        ,   ss_typename_param_k F
        >
inline F r_for_each(R r, F f)
{