ycpp_algorithm.hpp

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
 * The young Library
 * Copyright (c) 2005 by Yang Huan(杨桓)

 * Permission to use, copy, modify, distribute and sell this software 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.
 * The author make no representations about the suitability of this software
 * for any purpose. It is provided "as is" without express or implied warranty.
 */

/*
 * 以下为新增的算法
 * 基础算法: *gcd, *median
 * 比较算法: *matching
 * 复制算法: *copy_n, *copy_backward_n, *copy_if, *copy_range
 * 线性查找算法: *find_all, *find_all_if
 * 区间合并算法: *merge_backward
 * 随机重排与抽样算法: *random_sample, *random_sample_n
 * 排序算法: *is_sorted
 * 堆算法: *is_heap
 */

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_ALGORITHM_HEADER_FILE__
#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_ALGORITHM_HEADER_FILE__
//------------------------------------------------------------------------------
#include <cstring>
#include <iterator>
#include <algorithm>
#include "ycpp_traits.hpp"
//------------------------------------------------------------------------------
namespace std {
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

template< typename T >
T gcd( T m, T n )  //求最大公因数
{
    while( n != 0 )
    {
        T x = m % n;
        m = n;
        n = x;
    }
    return m;
}

//------------------------------------------------------------------------------

template< typename T >
const T& median( const T& a, const T& b, const T& c )  //求中间值
{
    if( a < b )
    {
        if( b < c )  //a < b < c
            return b;
        else if( a < c )  //a < b && c <= b
            return c;
        else
            return a;
    }
    else if( a < c )  //a >= b
        return a;
    else if( b < c )  //a >=b && a >=c
        return c;
    else
        return b;
}



template< typename T, typename StrictWeakOrdering >
const T& median( const T& a, const T& b, const T& c, StrictWeakOrdering cmp )
{
    if( cmp(a, b) )
    {
        if( cmp(b, c) )
            return b;
        else if( cmp(a, c) )
            return c;
        else
            return a;
    }
    else if( cmp(a, c) )
        return a;
    else if( cmp(b, c) )
        return c;
    else
        return b;
}

//------------------------------------------------------------------------------

template< typename InputIterator1, typename InputIterator2 >
inline bool matching( InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2 )
{
    typedef  typename iterator_traits<InputIterator1>::iterator_category  cate1;
    typedef  typename iterator_traits<InputIterator2>::iterator_category  cate2;
    return match_aux( first1, last1, first2, last2, cate1(), cate2() );
}

template< typename InputIterator1, typename InputIterator2 >
bool match_aux( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2,
                input_iterator_tag, input_iterator_tag )
{
    for( ; (first1 != last1) && (first2 != last2); ++first1,++first2 )
    {
        if( !(*first1 == *first2) )
            return false;
    }

    return first1 == last1 && first2 == last2;
}

template< typename InputIterator1, typename InputIterator2 >
bool match_aux( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2,
                random_access_iterator_tag, random_access_iterator_tag )
{
    typedef  typename iterator_traits<InputIterator1>::difference_type  diff_t1;
    typedef  typename iterator_traits<InputIterator2>::difference_type  diff_t2;

    diff_t1 len1 = last1 - first1;
    diff_t2 len2 = last2 - first2;

    if( len1 != len2 )
        return false;

    for( ; len1 > 0; --len1,++first1,++first2 )
    {
        if( !(*first1 == *first2) )
            return false;
    }

    return true;
}



template< typename InputIterator1, typename InputIterator2,
          typename BinaryPredicate >
inline bool matching( InputIterator1 first1, InputIterator1 last1,
                      InputIterator2 first2, InputIterator2 last2,
                      BinaryPredicate bin_pred )
{
    typedef  typename iterator_traits<InputIterator1>::iterator_category  cate1;
    typedef  typename iterator_traits<InputIterator2>::iterator_category  cate2;
    return match_aux( first1, last1, first2, last2, bin_pred, cate1(), cate2() );
}

template< typename InputIterator1, typename InputIterator2,
          typename BinaryPredicate >
bool match_aux( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2,
                BinaryPredicate bin_pred,
                input_iterator_tag, input_iterator_tag )
{
    for( ; (first1 != last1) && (first2 != last2); ++first1,++first2 )
    {
        if( !bin_pred(*first1, *first2) )
            return false;
    }

    return first1 == last1 && first2 == last2;
}

template< typename InputIterator1, typename InputIterator2,
          typename BinaryPredicate >
bool match_aux( InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2,
                BinaryPredicate bin_pred,
                random_access_iterator_tag, random_access_iterator_tag )
{
    typedef  typename iterator_traits<InputIterator1>::difference_type  diff_t1;
    typedef  typename iterator_traits<InputIterator2>::difference_type  diff_t2;

    diff_t1 len1 = last1 - first1;
    diff_t2 len2 = last2 - first2;

    if( len1 != len2 )
        return false;

    for( ; len1 > 0; --len1,++first1,++first2 )
    {
        if( !bin_pred(*first1, *first2) )
            return false;
    }

    return true;
}



inline bool matching( const char* first1, const char* last1,
                      const char* first2, const char* last2 )
{
    size_t len1 = last1 - first1;
    size_t len2 = last2 - first2;
    return len1 == len2 && memcmp(first1, first2, len1) == 0;
}

inline bool matching( const unsigned char* first1, const unsigned char* last1,
                      const unsigned char* first2, const unsigned char* last2 )
{
    size_t len1 = last1 - first1;
    size_t len2 = last2 - first2;
    return len1 == len2 && memcmp(first1, first2, len1) == 0;
}

//------------------------------------------------------------------------------

template< typename InputIterator, typename Integer, typename OutputIterator >
inline OutputIterator copy_n( InputIterator first, Integer count,
                              OutputIterator result )
{
    return copy_n_aux( first, count, result );
}

template< typename InputIterator, typename Integer, typename OutputIterator >
OutputIterator copy_n_aux( InputIterator first, Integer count,
                           OutputIterator result )
{
    typedef  typename youngcpp::primal_traits<Integer>::primal_t  primal_int;

    for( primal_int i = 0; i < count; ++i,++first,++result )
        *result = *first;
    return result;
}



template< typename T1, typename Integer, typename T2 >
inline T2* copy_n( T1* first, Integer count, T2* result )
{
    typedef  typename youngcpp::primal_traits<T1>::primal_t  primal_t1;
    typedef  typename youngcpp::primal_traits<T2>::primal_t  primal_t2;
    typedef  typename youngcpp::matching_traits<primal_t1, primal_t2>::matching
             matching;
    typedef  typename youngcpp::property_traits<primal_t2>::has_trivial_assign
             assign;

    return ptr_copy_n( first, count, result, matching(), assign() );
}

template< typename T1, typename Integer, typename T2 >
inline T2* ptr_copy_n( T1* first, Integer count, T2* result,
                       youngcpp::same_type, youngcpp::true_type )
{
    memmove( result, first, count * sizeof(T2) );
    return result + count;
}

template< typename T1, typename Integer, typename T2 >
inline T2* ptr_copy_n( T1* first, Integer count, T2* result,
                       youngcpp::same_type, youngcpp::false_type )
{
    return copy_n_aux( first, count, result );
}

template< typename T1, typename Integer, typename T2 >
inline T2* ptr_copy_n( T1* first, Integer count, T2* result,
                       youngcpp::different_type, youngcpp::true_type )
{
    return copy_n_aux( first, count, result );
}

template< typename T1, typename Integer, typename T2 >
inline T2* ptr_copy_n( T1* first, Integer count, T2* result,
                       youngcpp::different_type, youngcpp::false_type )
{
    return copy_n_aux( first, count, result );
}

//------------------------------------------------------------------------------

template< typename BidirectionalIterator1, typename Integer,
          typename BidirectionalIterator2 >
inline
BidirectionalIterator2 copy_backward_n( BidirectionalIterator1 last,
                                        Integer count,
                                        BidirectionalIterator2 result_last )
{
    return copy_b_n_aux( last, count, result_last );
}

template< typename BidirectionalIterator1, typename Integer,
          typename BidirectionalIterator2 >
BidirectionalIterator2 copy_b_n_aux( BidirectionalIterator1 last,
                                     Integer count,
                                     BidirectionalIterator2 result_last )
{
    typedef  typename youngcpp::primal_traits<Integer>::primal_t  primal_int;

    for( primal_int i = 0; i < count; ++i )
        *(--result_last) = *(--last);
    return result_last;
}



template< typename T1, typename Integer, typename T2 >
inline T2* copy_backward_n( T1* last, Integer count, T2* result_last )
{
    typedef  typename youngcpp::primal_traits<T1>::primal_t  primal_t1;
    typedef  typename youngcpp::primal_traits<T2>::primal_t  primal_t2;
    typedef  typename youngcpp::matching_traits<primal_t1, primal_t2>::matching
             matching;
    typedef  typename youngcpp::property_traits<primal_t2>::has_trivial_assign
             assign;

    return ptr_copy_b_n( last - count, count, result_last - count,
                         matching(), assign() );
}

template< typename T1, typename Integer, typename T2 >
inline T2* ptr_copy_b_n( T1* last, Integer count, T2* result_last,
                         youngcpp::same_type, youngcpp::true_type )
{
    memmove( result_last - count, last - count, sizeof(T2) * count );
    return result_last - count;
}

template< typename T1, typename Integer, typename T2 >
inline T2* ptr_copy_b_n( T1* last, Integer count, T2* result_last,
                         youngcpp::same_type, youngcpp::false_type )
{
    return copy_b_n_aux( last, count, result_last );
}

template< typename T1, typename Integer, typename T2 >
inline T2* ptr_copy_b_n( T1* last, Integer count, T2* result_last,
                         youngcpp::different_type, youngcpp::true_type )
{
    return copy_b_n_aux( last, count, result_last );
}

template< typename T1, typename Integer, typename T2 >
inline T2* ptr_copy_b_n( T1* last, Integer count, T2* result_last,
                         youngcpp::different_type, youngcpp::false_type )
{
    return copy_b_n_aux( last, count, result_last );
}

//------------------------------------------------------------------------------

template< typename InputIterator, typename UnaryPredicate,
          typename OutputIterator >
inline OutputIterator copy_if( InputIterator first, InputIterator last,
                               OutputIterator result, UnaryPredicate pred )
{
    typedef  typename iterator_traits<InputIterator>::iterator_category  cate;

    if( first == last )
        return result;
    else
        return copy_if_aux( first, last, result, cate() );
}

template< typename InputIterator, typename UnaryPredicate,
          typename OutputIterator >
OutputIterator copy_if_aux( InputIterator first, InputIterator last,
                            OutputIterator result, UnaryPredicate pred,
                            input_iterator_tag )
{
    for( ; first != last; ++first )
    {
        if( pred(*first) )
        {
            *result = *first;
            ++result;
        }
    }

    return result;
}

template< typename InputIterator, typename UnaryPredicate,
          typename OutputIterator >
OutputIterator copy_if_aux( InputIterator first, InputIterator last,
                            OutputIterator result, UnaryPredicate pred,
                            random_access_iterator_tag )
{
    typedef  typename iterator_traits<InputIterator>::difference_type  diff_t;

    for( diff_t n = last - first; n > 0; --n,++first )
    {
        if( pred(*first) )
        {
            *result = *first;
            ++result;