X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Finclude%2Fbits%2Fstl_numeric.h;h=82bee216d102d137fe5ea0d606fd97bfa53d4027;hb=1069247db128b23a7b0c830626c61a51ca10649a;hp=0b1742bc9d9f4be687c7d5ea30b0cb3c37ec81bf;hpb=1d487acac02f71846ad17cadad3e4cb1cca9f799;p=pf3gnuchains%2Fgcc-fork.git diff --git a/libstdc++-v3/include/bits/stl_numeric.h b/libstdc++-v3/include/bits/stl_numeric.h index 0b1742bc9d9..82bee216d10 100644 --- a/libstdc++-v3/include/bits/stl_numeric.h +++ b/libstdc++-v3/include/bits/stl_numeric.h @@ -1,3 +1,32 @@ +// Numeric functions implementation -*- C++ -*- + +// Copyright (C) 2001, 2004, 2005 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + /* * * Copyright (c) 1994 @@ -24,232 +53,287 @@ * purpose. It is provided "as is" without express or implied warranty. */ -/* NOTE: This is an internal header file, included by other STL headers. - * You should not attempt to use it directly. +/** @file stl_numeric.h + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. */ +#ifndef _STL_NUMERIC_H +#define _STL_NUMERIC_H 1 -#ifndef _CPP_BITS_STL_NUMERIC_H -#define _CPP_BITS_STL_NUMERIC_H 1 - -__STL_BEGIN_NAMESPACE - -template -_Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) -{ - __STL_REQUIRES(_InputIterator, _InputIterator); - for ( ; __first != __last; ++__first) - __init = __init + *__first; - return __init; -} - -template -_Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, - _BinaryOperation __binary_op) -{ - __STL_REQUIRES(_InputIterator, _InputIterator); - for ( ; __first != __last; ++__first) - __init = __binary_op(__init, *__first); - return __init; -} - -template -_Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _Tp __init) -{ - __STL_REQUIRES(_InputIterator2, _InputIterator); - __STL_REQUIRES(_InputIterator2, _InputIterator); - for ( ; __first1 != __last1; ++__first1, ++__first2) - __init = __init + (*__first1 * *__first2); - return __init; -} - -template -_Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _Tp __init, - _BinaryOperation1 __binary_op1, - _BinaryOperation2 __binary_op2) -{ - __STL_REQUIRES(_InputIterator2, _InputIterator); - __STL_REQUIRES(_InputIterator2, _InputIterator); - for ( ; __first1 != __last1; ++__first1, ++__first2) - __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); - return __init; -} - -template -_OutputIterator -__partial_sum(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, _Tp*) -{ - _Tp __value = *__first; - while (++__first != __last) { - __value = __value + *__first; - *++__result = __value; - } - return ++__result; -} - -template -_OutputIterator -partial_sum(_InputIterator __first, _InputIterator __last, - _OutputIterator __result) -{ - __STL_REQUIRES(_InputIterator, _InputIterator); - __STL_REQUIRES(_OutputIterator, _OutputIterator); - if (__first == __last) return __result; - *__result = *__first; - return __partial_sum(__first, __last, __result, __VALUE_TYPE(__first)); -} - -template -_OutputIterator -__partial_sum(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, _Tp*, _BinaryOperation __binary_op) -{ - _Tp __value = *__first; - while (++__first != __last) { - __value = __binary_op(__value, *__first); - *++__result = __value; - } - return ++__result; -} - -template -_OutputIterator -partial_sum(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, _BinaryOperation __binary_op) -{ - __STL_REQUIRES(_InputIterator, _InputIterator); - __STL_REQUIRES(_OutputIterator, _OutputIterator); - if (__first == __last) return __result; - *__result = *__first; - return __partial_sum(__first, __last, __result, __VALUE_TYPE(__first), - __binary_op); -} - -template -_OutputIterator -__adjacent_difference(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, _Tp*) -{ - _Tp __value = *__first; - while (++__first != __last) { - _Tp __tmp = *__first; - *++__result = __tmp - __value; - __value = __tmp; - } - return ++__result; -} - -template -_OutputIterator -adjacent_difference(_InputIterator __first, - _InputIterator __last, _OutputIterator __result) -{ - __STL_REQUIRES(_InputIterator, _InputIterator); - __STL_REQUIRES(_OutputIterator, _OutputIterator); - if (__first == __last) return __result; - *__result = *__first; - return __adjacent_difference(__first, __last, __result, - __VALUE_TYPE(__first)); -} - -template -_OutputIterator -__adjacent_difference(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, _Tp*, - _BinaryOperation __binary_op) { - _Tp __value = *__first; - while (++__first != __last) { - _Tp __tmp = *__first; - *++__result = __binary_op(__tmp, __value); - __value = __tmp; - } - return ++__result; -} - -template -_OutputIterator -adjacent_difference(_InputIterator __first, _InputIterator __last, - _OutputIterator __result, _BinaryOperation __binary_op) -{ - __STL_REQUIRES(_InputIterator, _InputIterator); - __STL_REQUIRES(_OutputIterator, _OutputIterator); - if (__first == __last) return __result; - *__result = *__first; - return __adjacent_difference(__first, __last, __result, - __VALUE_TYPE(__first), - __binary_op); -} - -// Returns __x ** __n, where __n >= 0. _Note that "multiplication" -// is required to be associative, but not necessarily commutative. - - -template -_Tp __power(_Tp __x, _Integer __n, _MonoidOperation __monoid_op) -{ - if (__n == 0) - return identity_element(__monoid_op); - else { - while ((__n & 1) == 0) { - __n >>= 1; - __x = __monoid_op(__x, __x); +#include + +_GLIBCXX_BEGIN_NAMESPACE(std) + + /** + * @brief Accumulate values in a range. + * + * Accumulates the values in the range [first,last) using operator+(). The + * initial value is @a init. The values are processed in order. + * + * @param first Start of range. + * @param last End of range. + * @param init Starting value to add other values to. + * @return The final sum. + */ + template + _Tp + accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_requires_valid_range(__first, __last); + + for (; __first != __last; ++__first) + __init = __init + *__first; + return __init; } - _Tp __result = __x; - __n >>= 1; - while (__n != 0) { - __x = __monoid_op(__x, __x); - if ((__n & 1) != 0) - __result = __monoid_op(__result, __x); - __n >>= 1; + /** + * @brief Accumulate values in a range with operation. + * + * Accumulates the values in the range [first,last) using the function + * object @a binary_op. The initial value is @a init. The values are + * processed in order. + * + * @param first Start of range. + * @param last End of range. + * @param init Starting value to add other values to. + * @param binary_op Function object to accumulate with. + * @return The final sum. + */ + template + _Tp + accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, + _BinaryOperation __binary_op) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_requires_valid_range(__first, __last); + + for (; __first != __last; ++__first) + __init = __binary_op(__init, *__first); + return __init; } - return __result; - } -} - -template -inline _Tp __power(_Tp __x, _Integer __n) -{ - return __power(__x, __n, multiplies<_Tp>()); -} - -// Alias for the internal name __power. Note that power is an extension, -// not part of the C++ standard. - -template -inline _Tp power(_Tp __x, _Integer __n, _MonoidOperation __monoid_op) -{ - return __power(__x, __n, __monoid_op); -} - -template -inline _Tp power(_Tp __x, _Integer __n) -{ - return __power(__x, __n); -} - -// iota is not part of the C++ standard. It is an extension. - -template -void -iota(_ForwardIter __first, _ForwardIter __last, _Tp __value) -{ - __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator); - __STL_CONVERTIBLE(_Tp, typename iterator_traits<_ForwardIter>::value_type); - while (__first != __last) - *__first++ = __value++; -} - -__STL_END_NAMESPACE - -#endif /* _CPP_BITS_STL_NUMERIC_H */ - -// Local Variables: -// mode:C++ -// End: + + /** + * @brief Compute inner product of two ranges. + * + * Starting with an initial value of @a init, multiplies successive + * elements from the two ranges and adds each product into the accumulated + * value using operator+(). The values in the ranges are processed in + * order. + * + * @param first1 Start of range 1. + * @param last1 End of range 1. + * @param first2 Start of range 2. + * @param init Starting value to add other values to. + * @return The final inner product. + */ + template + _Tp + inner_product(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _Tp __init) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_requires_valid_range(__first1, __last1); + + for (; __first1 != __last1; ++__first1, ++__first2) + __init = __init + (*__first1 * *__first2); + return __init; + } + + /** + * @brief Compute inner product of two ranges. + * + * Starting with an initial value of @a init, applies @a binary_op2 to + * successive elements from the two ranges and accumulates each result into + * the accumulated value using @a binary_op1. The values in the ranges are + * processed in order. + * + * @param first1 Start of range 1. + * @param last1 End of range 1. + * @param first2 Start of range 2. + * @param init Starting value to add other values to. + * @param binary_op1 Function object to accumulate with. + * @param binary_op2 Function object to apply to pairs of input values. + * @return The final inner product. + */ + template + _Tp + inner_product(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _Tp __init, + _BinaryOperation1 __binary_op1, + _BinaryOperation2 __binary_op2) + { + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_requires_valid_range(__first1, __last1); + + for (; __first1 != __last1; ++__first1, ++__first2) + __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); + return __init; + } + + /** + * @brief Return list of partial sums + * + * Accumulates the values in the range [first,last) using operator+(). + * As each successive input value is added into the total, that partial sum + * is written to @a result. Therefore, the first value in result is the + * first value of the input, the second value in result is the sum of the + * first and second input values, and so on. + * + * @param first Start of input range. + * @param last End of input range. + * @param result Output to write sums to. + * @return Iterator pointing just beyond the values written to result. + */ + template + _OutputIterator + partial_sum(_InputIterator __first, _InputIterator __last, + _OutputIterator __result) + { + typedef typename iterator_traits<_InputIterator>::value_type _ValueType; + + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return __result; + _ValueType __value = *__first; + *__result = __value; + while (++__first != __last) + { + __value = __value + *__first; + *++__result = __value; + } + return ++__result; + } + + /** + * @brief Return list of partial sums + * + * Accumulates the values in the range [first,last) using operator+(). + * As each successive input value is added into the total, that partial sum + * is written to @a result. Therefore, the first value in result is the + * first value of the input, the second value in result is the sum of the + * first and second input values, and so on. + * + * @param first Start of input range. + * @param last End of input range. + * @param result Output to write sums to. + * @return Iterator pointing just beyond the values written to result. + */ + template + _OutputIterator + partial_sum(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _BinaryOperation __binary_op) + { + typedef typename iterator_traits<_InputIterator>::value_type _ValueType; + + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return __result; + _ValueType __value = *__first; + *__result = __value; + while (++__first != __last) + { + __value = __binary_op(__value, *__first); + *++__result = __value; + } + return ++__result; + } + + /** + * @brief Return differences between adjacent values. + * + * Computes the difference between adjacent values in the range + * [first,last) using operator-() and writes the result to @a result. + * + * @param first Start of input range. + * @param last End of input range. + * @param result Output to write sums to. + * @return Iterator pointing just beyond the values written to result. + */ + template + _OutputIterator + adjacent_difference(_InputIterator __first, + _InputIterator __last, _OutputIterator __result) + { + typedef typename iterator_traits<_InputIterator>::value_type _ValueType; + + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return __result; + _ValueType __value = *__first; + *__result = __value; + while (++__first != __last) + { + _ValueType __tmp = *__first; + *++__result = __tmp - __value; + __value = __tmp; + } + return ++__result; + } + + /** + * @brief Return differences between adjacent values. + * + * Computes the difference between adjacent values in the range + * [first,last) using the function object @a binary_op and writes the + * result to @a result. + * + * @param first Start of input range. + * @param last End of input range. + * @param result Output to write sums to. + * @return Iterator pointing just beyond the values written to result. + */ + template + _OutputIterator + adjacent_difference(_InputIterator __first, _InputIterator __last, + _OutputIterator __result, _BinaryOperation __binary_op) + { + typedef typename iterator_traits<_InputIterator>::value_type _ValueType; + + // concept requirements + __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) + __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, + _ValueType>) + __glibcxx_requires_valid_range(__first, __last); + + if (__first == __last) + return __result; + _ValueType __value = *__first; + *__result = __value; + while (++__first != __last) + { + _ValueType __tmp = *__first; + *++__result = __binary_op(__tmp, __value); + __value = __tmp; + } + return ++__result; + } + +_GLIBCXX_END_NAMESPACE + +#endif /* _STL_NUMERIC_H */