C++ young 程序库——y_numeric.hpp

文件位置：young/y_numeric.hpp

The young Library

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.

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

#ifndef __MACRO_CPLUSPLUS_YOUNG_LIBRARY_NUMERIC_HEADER_FILE__

#define __MACRO_CPLUSPLUS_YOUNG_LIBRARY_NUMERIC_HEADER_FILE__

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

#include "y_iterator.hpp"

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

__MACRO_CPLUSPLUS_YOUNG_LIBRARY_BEGIN_NAMESPACE__

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

template< typename InputIterator, typename T >

T accumulate( InputIterator first, InputIterator last, T init )

{

for( ; first != last; ++first )

init += *first;

return init;

}

template< typename InputIterator, typename T, typename BinaryOperation >

T accumulate( InputIterator first, InputIterator last, T init,

BinaryOperation bin_op )

{

for( ; first != last; ++first )

init = bin_op( init, *first );

return init;

}

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

template< typename InputIterator1, typename InputIterator2, typename T >

T inner_product( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, T init )

{

for( ; first1 != last1; ++first1,++first2 )

init += ( (*first1) * (*first2) );

return init;

}

template< typename InputIterator1, typename InputIterator2, typename T,

typename BinaryOperation1, typename BinaryOperation2 >

T inner_product( InputIterator1 first1, InputIterator1 last1,

InputIterator2 first2, T init,

BinaryOperation1 bin_op1, BinaryOperation2 bin_op2 )

{

for( ; first1 != last1; ++first1,++first2 )

init = bin_op1( init, bin_op2((*first1) * (*first2)) );

return init;

}

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

template< typename InputIterator, typename OutputIterator >

OutputIterator partial_sum( InputIterator first, InputIterator last,

OutputIterator result )

{

typedef typename iterator_traits<InputIterator>::value_type value_t;

if( first == last )

return result;

*result = *first;

value_t temp = *first;

while( first != last )

{

++first;

++result;

temp += *first;

*result = temp;

}

return ++result;

}

template< typename InputIterator, typename OutputIterator,

typename BinaryOperation >

OutputIterator partial_sum( InputIterator first, InputIterator last,

OutputIterator result, BinaryOperation bin_op )

{

typedef typename iterator_traits<InputIterator>::value_type value_t;

if( first == last )

return result;

*result = *first;

value_t temp = *first;

while( first != last )

{

++first;

++result;

temp = bin_op( temp, *first );

*result = temp;

}

return ++result;

}

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

template< typename InputIterator, typename OutputIterator >

OutputIterator adjacent_diffeence( InputIterator first, InputIterator last,

OutputIterator result )

{

typedef typename iterator_traits<InputIterator>::value_type value_t;

if( first == last )

return result;

*result = *first;

value_t temp = *first;

while( first != last )

{

++first;

++result;

*result = *first - temp;

temp = *first;

}

return ++result;

}

template< typename InputIterator, typename OutputIterator,

typename BinaryOperation >

OutputIterator adjacent_diffeence( InputIterator first, InputIterator last,

OutputIterator result,

BinaryOperation bin_op )

{

typedef typename iterator_traits<InputIterator>::value_type value_t;

if( first == last )

return result;

*result = *first;

value_t temp = *first;

while( first != last )

{

++first;

++result;

*result = bin_op( *first, temp );

temp = *first;

}

return ++result;

}

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

template< typename OutputIterator, typename T >

void increase_assign( OutputIterator first, OutputIterator last, T value )

{

for( ; first != last; ++first,++value )

*first = value;

}

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

template< typename OutputIterator, typename T >

void decrease_assign( OutputIterator first, OutputIterator last, T value )

{

for( ; first != last; ++first,--value )

*first = value;

}

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

//[first, last)为等差序列，采用高斯算法进行计算

template< typename InputIterator, typename T >

inline T quick_accumulate( InputIterator first, InputIterator last, T init )

{

typedef typename iterator_traits<InputIterator>::iterator_category cate;

if( first == last )

return init;

else

return quick_accumulate_aux( first, last, init, cate() );

}

template< typename InputIterator, typename T >

T quick_accumulate_aux( InputIterator first, InputIterator last, T init,

input_iterator_tag )

{

typedef typename iterator_traits<InputIterator>::difference_type diff_t;

typedef typename iterator_traits<InputIterator>::value_type value_t;

//由于必须获得最后一个有效迭代器和区间长度，使用一般方法要遍历两次，

//而使用 pair_iter_len 则只需遍历一次，可提高程序效率

pair<InputIterator, diff_t> iter_len = pair_iter_len( first, last );

InputIterator prev_last = iter_len.first;

diff_t len = iter_len.second;

diff_t half = len / 2;

value_t sum = *first + *prev_last;

if( len % 2 == 0 ) //区间长度为偶数

init = init + sum * half;

else //区间长度为奇数

{

InputIterator temp = first;

++temp;

value_t half_value = *first + (*temp - *first) * half;

init = init + sum * half + half_value;

}

return init;

}

template< typename InputIterator, typename T >

T quick_accumulate_aux( InputIterator first, InputIterator last, T init,

bidirectional_iterator_tag )

{

typedef typename iterator_traits<InputIterator>::difference_type diff_t;

typedef typename iterator_traits<InputIterator>::value_type value_t;

diff_t len = distance( first, last );

diff_t half = len / 2;

InputIterator prev_last = last;

--prev_last;

value_t sum = *first + *prev_last;

if( len % 2 == 0 )

init = init + sum * half;

else

{

InputIterator temp = first;

++temp;

value_t half_value = *first + (*temp - *first) * half;

init = init + sum * half + half_value;

}

return init;

}

template< typename InputIterator, typename T >

T quick_accumulate_aux( InputIterator first, InputIterator last, T init,

random_access_iterator_tag )

{

typedef typename iterator_traits<InputIterator>::difference_type diff_t;

typedef typename iterator_traits<InputIterator>::value_type value_t;

diff_t len = last - first;

diff_t half = len / 2;

value_t sum = *first + *(last - 1);

if( len % 2 == 0 )

init = init + sum * half;

else

init = init + sum * half + *(first + half);

return init;

}

template< typename InputIterator, typename T, typename BinaryOperation >

inline T quick_accumulate( InputIterator first, InputIterator last, T init,

BinaryOperation bin_op )

{

typedef typename iterator_traits<InputIterator>::iterator_category cate;

if( first == last )

return init;

else

return quick_accumulate_aux( first, last, init, bin_op, cate() );

}

template< typename InputIterator, typename T, typename BinaryOperation >

T quick_accumulate_aux( InputIterator first, InputIterator last, T init,

BinaryOperation bin_op, input_iterator_tag )

{

typedef typename iterator_traits<InputIterator>::difference_type diff_t;

typedef typename iterator_traits<InputIterator>::value_type value_t;

pair<InputIterator, diff_t> iter_len = pair_iter_len( first, last );

InputIterator prev_last = iter_len.first;

diff_t len = iter_len.second;

diff_t half = len / 2;

value_t sum = bin_op( *first, *prev_last );

if( len % 2 == 0 )

init = bin_op( init, sum * half );

else

{

InputIterator temp = first;

advance( temp, half );

init = bin_op( init, sum * half );

init = bin_op( init, *temp );

}

return init;

}

template< typename InputIterator, typename T, typename BinaryOperation >

T quick_accumulate_aux( InputIterator first, InputIterator last, T init,

BinaryOperation bin_op, bidirectional_iterator_tag )

{

typedef typename iterator_traits<InputIterator>::difference_type diff_t;

typedef typename iterator_traits<InputIterator>::value_type value_t;

diff_t len = distance( first, last );

diff_t half = len / 2;

InputIterator prev_last = last;

--prev_last;

value_t sum = bin_op( *first, *prev_last );

if( len % 2 == 0 )

init = bin_op( init, sum * half );

else

{

InputIterator temp = first;

advance( temp, half );

init = bin_op( init, sum * half );

init = bin_op( init, *temp );

}

return init;

}

template< typename InputIterator, typename T, typename BinaryOperation >

T quick_accumulate_aux( InputIterator first, InputIterator last, T init,

BinaryOperation bin_op, random_access_iterator_tag )

{

typedef typename iterator_traits<InputIterator>::difference_type diff_t;

typedef typename iterator_traits<InputIterator>::value_type value_t;

diff_t len = last - first;

diff_t half = len / 2;

value_t sum = bin_op( *first, *(last - 1) );

if( len % 2 == 0 )

init = bin_op( init, sum * half );

else

{

init = bin_op( init, sum * half );

init = bin_op( init, *(first + half) );

}

return init;

}

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

__MACRO_CPLUSPLUS_YOUNG_LIBRARY_END_NAMESPACE__

#endif

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