ycpp_algorithm.hpp

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

        }
    }

    return result;
}

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

template< typename InputIterator, typename OutputIterator >
OutputIterator copy_range( InputIterator first,
                           InputIterator last,
                           OutputIterator result_first,
                           OutputIterator result_last )
{
    while( first != last && result_first != result_last )
    {
        *result_first = *first;
        ++first;
        ++result_first;
    }
    return result_first;
}



template< typename T1, typename T2 >
inline T2* copy_range( T1* first, T1* last, T2* result_first, 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;

    ptrdiff_t len1 = last - first;
    ptrdiff_t len2 = result_last - result_first;
    ptrdiff_t len = len1 < len2 ? len1 : len2;

    ptr_copy_b_n( first + len, len, result_first + len, matching(), assign() );

    return result_first + len;
}

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

template< typename InputIterator, typename T, typename OutputIterator >
OutputIterator find_all( InputIterator first,
                         InputIterator last,
                         OutputIterator result_first,
                         OutputIterator result_last,
                         const T& value )
{
    for( ; first != last && result_first != result_last; ++first )
    {
        if( *first == value )
        {
            *result_first = first;
            ++result_first;
        }
    }

    return result_first;
}



template< typename InputIterator, typename IteratorContainer, typename T >
void find_all( InputIterator first, InputIterator last,
               IteratorContainer& result, const T& value )
{
    for( ; first != last; ++first )
    {
        if( *first == value )
            result.push_back( first );
    }
}

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

template< typename InputIterator, typename OutputIterator,
          typename UnaryPredicate >
OutputIterator find_all_if( InputIterator first,
                            InputIterator last,
                            OutputIterator result_first,
                            OutputIterator result_last,
                            UnaryPredicate pred )
{
    for( ; first != last && result_first != result_last; ++first )
    {
        if( pred(*first) )
        {
            *result_first = first;
            ++result_first;
        }
    }

    return result_first;
}



template< typename InputIterator, typename IteratorContainer,
          typename UnaryPredicate >
void find_all_if( InputIterator first, InputIterator last,
                  IteratorContainer& result, UnaryPredicate pred )
{
    for( ; first != last; ++first )
    {
        if( pred(*first) )
            result.push_back( first );
    }
}

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

template< typename BidirectionalIterator1, typename BidirectionalIterator2,
          typename BidirectionalIterator3 >
BidirectionalIterator3 merge_backward( BidirectionalIterator1 first1,
                                       BidirectionalIterator1 last1,
                                       BidirectionalIterator2 first2,
                                       BidirectionalIterator2 last2,
                                       BidirectionalIterator3 result_last )
{
    if( first1 == last1 )
        return copy_backward( first2, last2, result_last );
    if( first2 == last2 )
        return copy_backward( first1, last1, result_last );

    --last1;
    --last2;
    while( 1 )
    {
        if( *last2 < *last1 )
        {
            *--result_last = *last1;
            if( first1 == last1 )
                return copy_backward( first2, ++last2, result_last );
            --last1;
        }
        else
        {
            *--result_last = *last2;
            if( first2 == last2 )
                return copy_backward( first1, ++last1, result_last );
            --last2;
        }
    }
}



template< typename BidirectionalIterator1, typename BidirectionalIterator2,
          typename BidirectionalIterator3, typename StrictWeakOrdering >
BidirectionalIterator3 merge_backward( BidirectionalIterator1 first1,
                                       BidirectionalIterator1 last1,
                                       BidirectionalIterator2 first2,
                                       BidirectionalIterator2 last2,
                                       BidirectionalIterator3 result_last,
                                       StrictWeakOrdering cmp )
{
    if( first1 == last1 )
        return copy_backward( first2, last2, result_last );
    if( first2 == last2 )
        return copy_backward( first1, last1, result_last );

    --last1;
    --last2;
    while( 1 )
    {
        if( cmp(*last2, *last1) )
        {
            *--result_last = *last1;
            if( first1 == last1 )
                return copy_backward( first2, ++last2, result_last );
            --last1;
        }
        else
        {
            *--result_last = *last2;
            if( first2 == last2 )
                return copy_backward( first1, ++last1, result_last );
            --last2;
        }
    }
}

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

template< typename InputIterator, typename RandomAccessIterator >
RandomAccessIterator random_sample( InputIterator first,
                                    InputIterator last,
                                    RandomAccessIterator result_first,
                                    RandomAccessIterator result_last )
{
    typedef  typename iterator_traits<RandomAccessIterator>::difference_type
             diff_t;

    diff_t len = result_last - result_first;
    diff_t m = 0, n = len;

    for( ; first != last && m < len; ++first,++m )
        *(result_first + m) = *first;

    while( first != last )
    {
        ++n;
        diff_t num = rand() % n;
        if( num < len )
            *(result_first + num) = *first;
        ++first;
    }

    return ( result_first + m );
}



template< typename InputIterator, typename RandomAccessIterator,
          typename RandomNumberGenerator >
RandomAccessIterator random_sample( InputIterator first,
                                    InputIterator last,
                                    RandomAccessIterator result_first,
                                    RandomAccessIterator result_last,
                                    RandomNumberGenerator& rand )
{
    typedef  typename iterator_traits<RandomAccessIterator>::difference_type
             diff_t;

    diff_t len = result_last - result_first;
    diff_t m = 0, n = len;

    for( ; first != last && m < len; ++first,++m )
        *(result_first + m) = *first;

    while( first != last )
    {
        ++n;
        diff_t num = rand( n );
        if( num < len )
            *(result_first + num) = *first;
        ++first;
    }

    return ( result_first + m );
}

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

template< typename ForwardIterator, typename OutputIterator, typename Integer >
OutputIterator random_sample_n( ForwardIterator first, ForwardIterator last,
                                OutputIterator result, Integer count )
{
    Integer len = distance( first, last );
    Integer n = min( count, len );

    while( n > 0 )
    {
        if( rand() % len < n )
        {
            *result = *first;
            ++result;
            --n;
        }
        --len;
        ++first;
    }

    return result;
}



template< typename ForwardIterator, typename OutputIterator, typename Integer,
          typename RandomNumberGenerator >
OutputIterator random_sample_n( ForwardIterator first, ForwardIterator last,
                                OutputIterator result, Integer count,
                                RandomNumberGenerator& rand )
{
    Integer len = distance( first, last );
    Integer n = min( count, len );

    while( n > 0 )
    {
        if( rand(len) < n )
        {
            *result = *first;
            ++result;
            --n;
        }
        --len;
        ++first;
    }

    return result;
}

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

template< typename RandomAccessIterator >
bool is_heap( RandomAccessIterator first, RandomAccessIterator last )
{
    typedef  typename iterator_traits<RandomAccessIterator>::difference_type
             diff_t;

    diff_t len = last - first;

    if( len < 2 )
        return true;

    diff_t parent = 0;
    for( diff_t child = 1; child < len; ++child )
    {
        if( *(first + parent) < *(first + child) )
            return false;
        if( child % 2 == 0 )
            ++parent;
    }

    return true;
}



template< typename RandomAccessIterator, typename StrictWeakOrdering >
bool is_heap( RandomAccessIterator first, RandomAccessIterator last,
              StrictWeakOrdering cmp )
{
    typedef  typename iterator_traits<RandomAccessIterator>::difference_type
             diff_t;

    diff_t len = last - first;

    if( len < 2 )
        return true;

    diff_t parent = 0;
    for( diff_t child = 1; child < len; ++child )
    {
        if( cmp(*(first + parent), *(first + child)) )
            return false;
        if( child % 2 == 0 )
            ++parent;
    }

    return true;
}

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

template< typename ForwardIterator >
bool is_sorted( ForwardIterator first, ForwardIterator last )
{
    if( first != last )
    {
        ForwardIterator next = first;
        for( ++next; next != last; ++next )
        {
            if( *next < *first )
                return false;
            first = next;
        }
    }

    return true;
}



template< typename ForwardIterator, typename StrictWeakOrdering >
bool is_sorted( ForwardIterator first, ForwardIterator last,
                StrictWeakOrdering cmp )
{
    if( first != last )
    {
        ForwardIterator next = first;
        for( ++next; next != last; ++next )
        {
            if( cmp(*next, *first) )
                return false;
            first = next;
        }
    }

    return true;
}

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
}  //end namespace
#endif
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------