mstl_algorithm.hpp

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

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

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.
*/

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * 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.
 */

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

/*
基础算法: min, max, swap, *gcd, *median

复制算法: copy  *copy_n  copy_backward  *copy_backward_n  *copy_if  *copy_range

比较算法: equal  lexicographical_compare  mismatch  *matching

填充算法: fill, fill_n

线性查找算法: find, find_if, adjacent_find, find_first_of,
              *find_all, *find_all_if

子序列匹配算法: search, find_end, search_n

计算元素个数算法: count, count_if

最大值与最小值算法: min_element, max_element

互换算法: iter_swap, swap_ranges

遍历区间算法: for_each, generate, generate_n, transform

替换元素算法: replace, replace_if, replace_copy, replace_copy_if

移除元素算法: remove, remove_if, remove_copy, remove_copy_if,
              unique, unique_copy

排列算法: reverse, reverse_copy, rotate, rotate_copy,
          prev_permutation, next_permutation

分割算法: partition, stable_partition

随机重排与抽样算法: random_shuffle, *random_sample, *random_sample_n

二分查找算法: lower_bound, upper_bound, equal_range, binary_search

区间合并算法: merge, *merge_backward, inplace_merge

区间集合算法: includes, set_union, set_intersection, set_difference,
              set_symmetric_difference

排序算法: *is_sorted, sort, stable_sort, partial_sort, partial_sort_copy,
          nth_element

堆算法: push_heap, pop_heap, make_heap, sort_heap, *is_heap
*/

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_MINI_STL_ALGORITHM_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_ALGORITHM_HEADER_FILE__
//-----------------------------------------------------------------------------
#include <cstdlib>  //rand()函数
#include "mstl_temp_buffer.hpp"
#include "algorithm/mstl_algorithm_base.hpp"
#include "algorithm/mstl_algorithm_compare.hpp"
#include "algorithm/mstl_algorithm_copy.hpp"
#include "algorithm/mstl_algorithm_fill.hpp"
#include "algorithm/mstl_algorithm_heap.hpp"
#include "algorithm/mstl_algorithm_lower_bound.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

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 comp )
{
    if( comp(a, b) )
    {
        if( comp(b, c) )
            return b;
        else if( comp(a, c) )
            return c;
        else
            return a;
    }
    else if( comp(a, c) )
        return a;
    else if( comp(b, c) )
        return c;
    else
        return b;
}

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

//*****************************************************************************
//*****************************************************************************
//                            线性查找算法
//
//     find  find_if  adjacent_find  find_first_of  find_all  find_all_if
//*****************************************************************************
//*****************************************************************************

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

template< typename InputIterator, typename T >
inline InputIterator find( InputIterator first, InputIterator last,
                           const T& value )
{
    typedef  typename iterator_traits<InputIterator>::iterator_category  cate;
    return  find_aux( first, last, value, cate() );
}

template< typename InputIterator, typename T >
InputIterator find_aux( InputIterator first, InputIterator last,
                        const T& value, input_iterator_tag )
{
    while( first != last && *first != value )
        ++first;
    return first;
}

template< typename InputIterator, typename T >
InputIterator find_aux( InputIterator first, InputIterator last,
                        const T& value, random_access_iterator_tag )
{
    typedef  typename iterator_traits<InputIterator>::difference_type  diff_t;

    diff_t n = last - first;
    while( n > 0 && *first != value )
    {
        --n;
        ++first;
    }
    return first;
}

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

template< typename InputIterator, typename UnaryPredicate >
inline InputIterator find_if( InputIterator first, InputIterator last,
                              UnaryPredicate pred )
{
    typedef  typename iterator_traits<InputIterator>::iterator_category  cate;
    return  find_aux( first, last, pred, cate() );
}

template< typename InputIterator, typename UnaryPredicate >
InputIterator find_if_aux( InputIterator first, InputIterator last,
                           UnaryPredicate pred, input_iterator_tag )
{
    while( first != last && !pred(*first) )
        ++first;
    return first;
}

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

    diff_t n = last - first;
    while( n > 0 && !pred(*first) )
    {
        --n;
        ++first;
    }
    return first;
}

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

//寻找[first, last)中第一次出现相邻值相等的位置
template< typename ForwardIterator >
inline
ForwardIterator adjacent_find( ForwardIterator first, ForwardIterator last )
{
    typedef  typename iterator_traits<ForwardIterator>::iterator_category  cate;

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

template< typename ForwardIterator >
ForwardIterator ad_find_aux( ForwardIterator first, ForwardIterator last,
                             forward_iterator_tag )
{
    ForwardIterator next = first;
    ++next;
    for( ; next != last; ++next )
    {
        if( *first == *next )
            return first;
        else
            first = next;
    }
    return last;
}

template< typename ForwardIterator >
ForwardIterator ad_find_aux( ForwardIterator first, ForwardIterator last,
                             random_access_iterator_tag )
{
    typedef  typename iterator_traits<ForwardIterator>::difference_type  diff_t;

    ForwardIterator next = first;
    ++next;
    for( diff_t n = last - first; n > 0; --n,++next )
    {
        if( *first == *next )
            return first;
        else
            first = next;
    }
    return last;
}



template< typename ForwardIterator, typename BinaryPredicate >
inline
ForwardIterator adjacent_find( ForwardIterator first, ForwardIterator last,
                               BinaryPredicate bin_pred )
{
    typedef  typename iterator_traits<ForwardIterator>::iterator_category  cate;

    if( first == last )
        return last;
    else
        return ad_find_aux( first, last, bin_pred, cate() );
}

template< typename ForwardIterator, typename BinaryPredicate >
ForwardIterator ad_find_aux( ForwardIterator first, ForwardIterator last,
                             BinaryPredicate bin_pred,
                             forward_iterator_tag )
{
    ForwardIterator next = first;
    ++next;
    for( ; next != last; ++next )
    {
        if( bin_pred(*first, *next) )
            return first;
        else
            first = next;
    }
    return last;
}

template< typename ForwardIterator, typename BinaryPredicate >
ForwardIterator ad_find_aux( ForwardIterator first, ForwardIterator last,
                             BinaryPredicate bin_pred,
                             random_access_iterator_tag )
{
    typedef  typename iterator_traits<ForwardIterator>::difference_type  diff_t;

    ForwardIterator next = first;
    ++next;
    for( diff_t n = last - first; n > 0; --n,++next )
    {
        if( bin_pred(*first, *next) )
            return first;
        else
            first = next;
    }
    return last;
}

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

template< typename InputIterator, typename ForwardIterator >
InputIterator find_first_of( InputIterator first1, InputIterator last1,
                             ForwardIterator first2, ForwardIterator last2 )
{
    for( ; first1 != last1; ++first1 )
    {
        for( ForwardIterator temp = first2; temp != last2; ++temp )
        {
            if( *first1 == *temp )
                return first1;
        }
    }
    return last1;
}



template< typename InputIterator, typename ForwardIterator,
          typename BinaryPredicate >
InputIterator find_first_of( InputIterator first1, InputIterator last1,
                             ForwardIterator first2, ForwardIterator last2,
                             BinaryPredicate bin_pred )
{
    for( ; first1 != last1; ++first1 )
    {
        for( ForwardIterator temp = first2; temp != last2; ++temp )
        {
            if( bin_pred(*first1, *temp) )
                return first1;
        }
    }
    return last1;
}

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

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 Container, typename T >
void find_all( InputIterator first, InputIterator last, Container& result,
               const T& value )
{
    typename Container::iterator  itr1 = result.begin();
    typename Container::iterator  itr2 = result.end();

    for( ; first != last; ++first )
    {
    	if( *first == value )
    	{
    	    if( itr1 != itr2 )