197403Sobrien// Numeric functions implementation -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2004, 2005 Free Software Foundation, Inc. 497403Sobrien// 597403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 697403Sobrien// software; you can redistribute it and/or modify it under the 797403Sobrien// terms of the GNU General Public License as published by the 897403Sobrien// Free Software Foundation; either version 2, or (at your option) 997403Sobrien// any later version. 1097403Sobrien 1197403Sobrien// This library is distributed in the hope that it will be useful, 1297403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1497403Sobrien// GNU General Public License for more details. 1597403Sobrien 1697403Sobrien// You should have received a copy of the GNU General Public License along 1797403Sobrien// with this library; see the file COPYING. If not, write to the Free 18169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 1997403Sobrien// USA. 2097403Sobrien 2197403Sobrien// As a special exception, you may use this file as part of a free software 2297403Sobrien// library without restriction. Specifically, if other files instantiate 2397403Sobrien// templates or use macros or inline functions from this file, or you compile 2497403Sobrien// this file and link it with other files to produce an executable, this 2597403Sobrien// file does not by itself cause the resulting executable to be covered by 2697403Sobrien// the GNU General Public License. This exception does not however 2797403Sobrien// invalidate any other reasons why the executable file might be covered by 2897403Sobrien// the GNU General Public License. 2997403Sobrien 3097403Sobrien/* 3197403Sobrien * 3297403Sobrien * Copyright (c) 1994 3397403Sobrien * Hewlett-Packard Company 3497403Sobrien * 3597403Sobrien * Permission to use, copy, modify, distribute and sell this software 3697403Sobrien * and its documentation for any purpose is hereby granted without fee, 3797403Sobrien * provided that the above copyright notice appear in all copies and 3897403Sobrien * that both that copyright notice and this permission notice appear 3997403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4097403Sobrien * representations about the suitability of this software for any 4197403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4297403Sobrien * 4397403Sobrien * 4497403Sobrien * Copyright (c) 1996,1997 4597403Sobrien * Silicon Graphics Computer Systems, Inc. 4697403Sobrien * 4797403Sobrien * Permission to use, copy, modify, distribute and sell this software 4897403Sobrien * and its documentation for any purpose is hereby granted without fee, 4997403Sobrien * provided that the above copyright notice appear in all copies and 5097403Sobrien * that both that copyright notice and this permission notice appear 5197403Sobrien * in supporting documentation. Silicon Graphics makes no 5297403Sobrien * representations about the suitability of this software for any 5397403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5497403Sobrien */ 5597403Sobrien 5697403Sobrien/** @file stl_numeric.h 5797403Sobrien * This is an internal header file, included by other library headers. 5897403Sobrien * You should not attempt to use it directly. 5997403Sobrien */ 6097403Sobrien 61132720Skan#ifndef _STL_NUMERIC_H 62132720Skan#define _STL_NUMERIC_H 1 6397403Sobrien 64132720Skan#include <debug/debug.h> 65132720Skan 66169691Skan_GLIBCXX_BEGIN_NAMESPACE(std) 6797403Sobrien 68132720Skan /** 69132720Skan * @brief Accumulate values in a range. 70132720Skan * 71132720Skan * Accumulates the values in the range [first,last) using operator+(). The 72132720Skan * initial value is @a init. The values are processed in order. 73132720Skan * 74132720Skan * @param first Start of range. 75132720Skan * @param last End of range. 76132720Skan * @param init Starting value to add other values to. 77132720Skan * @return The final sum. 78132720Skan */ 7997403Sobrien template<typename _InputIterator, typename _Tp> 8097403Sobrien _Tp 8197403Sobrien accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) 8297403Sobrien { 8397403Sobrien // concept requirements 84132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 85132720Skan __glibcxx_requires_valid_range(__first, __last); 8697403Sobrien 87169691Skan for (; __first != __last; ++__first) 8897403Sobrien __init = __init + *__first; 8997403Sobrien return __init; 9097403Sobrien } 9197403Sobrien 92132720Skan /** 93132720Skan * @brief Accumulate values in a range with operation. 94132720Skan * 95132720Skan * Accumulates the values in the range [first,last) using the function 96132720Skan * object @a binary_op. The initial value is @a init. The values are 97132720Skan * processed in order. 98132720Skan * 99132720Skan * @param first Start of range. 100132720Skan * @param last End of range. 101132720Skan * @param init Starting value to add other values to. 102132720Skan * @param binary_op Function object to accumulate with. 103132720Skan * @return The final sum. 104132720Skan */ 10597403Sobrien template<typename _InputIterator, typename _Tp, typename _BinaryOperation> 10697403Sobrien _Tp 10797403Sobrien accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, 10897403Sobrien _BinaryOperation __binary_op) 10997403Sobrien { 11097403Sobrien // concept requirements 111132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 112132720Skan __glibcxx_requires_valid_range(__first, __last); 11397403Sobrien 114169691Skan for (; __first != __last; ++__first) 11597403Sobrien __init = __binary_op(__init, *__first); 11697403Sobrien return __init; 11797403Sobrien } 11897403Sobrien 119132720Skan /** 120132720Skan * @brief Compute inner product of two ranges. 121132720Skan * 122132720Skan * Starting with an initial value of @a init, multiplies successive 123132720Skan * elements from the two ranges and adds each product into the accumulated 124132720Skan * value using operator+(). The values in the ranges are processed in 125132720Skan * order. 126132720Skan * 127132720Skan * @param first1 Start of range 1. 128132720Skan * @param last1 End of range 1. 129132720Skan * @param first2 Start of range 2. 130132720Skan * @param init Starting value to add other values to. 131132720Skan * @return The final inner product. 132132720Skan */ 13397403Sobrien template<typename _InputIterator1, typename _InputIterator2, typename _Tp> 13497403Sobrien _Tp 13597403Sobrien inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 13697403Sobrien _InputIterator2 __first2, _Tp __init) 13797403Sobrien { 13897403Sobrien // concept requirements 139132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 140132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 141132720Skan __glibcxx_requires_valid_range(__first1, __last1); 14297403Sobrien 143169691Skan for (; __first1 != __last1; ++__first1, ++__first2) 14497403Sobrien __init = __init + (*__first1 * *__first2); 14597403Sobrien return __init; 14697403Sobrien } 14797403Sobrien 148132720Skan /** 149132720Skan * @brief Compute inner product of two ranges. 150132720Skan * 151132720Skan * Starting with an initial value of @a init, applies @a binary_op2 to 152132720Skan * successive elements from the two ranges and accumulates each result into 153132720Skan * the accumulated value using @a binary_op1. The values in the ranges are 154132720Skan * processed in order. 155132720Skan * 156132720Skan * @param first1 Start of range 1. 157132720Skan * @param last1 End of range 1. 158132720Skan * @param first2 Start of range 2. 159132720Skan * @param init Starting value to add other values to. 160132720Skan * @param binary_op1 Function object to accumulate with. 161132720Skan * @param binary_op2 Function object to apply to pairs of input values. 162132720Skan * @return The final inner product. 163132720Skan */ 16497403Sobrien template<typename _InputIterator1, typename _InputIterator2, typename _Tp, 16597403Sobrien typename _BinaryOperation1, typename _BinaryOperation2> 16697403Sobrien _Tp 16797403Sobrien inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 168132720Skan _InputIterator2 __first2, _Tp __init, 16997403Sobrien _BinaryOperation1 __binary_op1, 17097403Sobrien _BinaryOperation2 __binary_op2) 17197403Sobrien { 17297403Sobrien // concept requirements 173132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 174132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 175132720Skan __glibcxx_requires_valid_range(__first1, __last1); 17697403Sobrien 177169691Skan for (; __first1 != __last1; ++__first1, ++__first2) 17897403Sobrien __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); 17997403Sobrien return __init; 18097403Sobrien } 18197403Sobrien 182132720Skan /** 183132720Skan * @brief Return list of partial sums 184132720Skan * 185132720Skan * Accumulates the values in the range [first,last) using operator+(). 186132720Skan * As each successive input value is added into the total, that partial sum 187132720Skan * is written to @a result. Therefore, the first value in result is the 188132720Skan * first value of the input, the second value in result is the sum of the 189132720Skan * first and second input values, and so on. 190132720Skan * 191132720Skan * @param first Start of input range. 192132720Skan * @param last End of input range. 193132720Skan * @param result Output to write sums to. 194132720Skan * @return Iterator pointing just beyond the values written to result. 195132720Skan */ 19697403Sobrien template<typename _InputIterator, typename _OutputIterator> 197132720Skan _OutputIterator 19897403Sobrien partial_sum(_InputIterator __first, _InputIterator __last, 19997403Sobrien _OutputIterator __result) 20097403Sobrien { 20197403Sobrien typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 20297403Sobrien 20397403Sobrien // concept requirements 204132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 205169691Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 206169691Skan _ValueType>) 207132720Skan __glibcxx_requires_valid_range(__first, __last); 20897403Sobrien 209169691Skan if (__first == __last) 210169691Skan return __result; 21197403Sobrien _ValueType __value = *__first; 212169691Skan *__result = __value; 213169691Skan while (++__first != __last) 214169691Skan { 215169691Skan __value = __value + *__first; 216169691Skan *++__result = __value; 217169691Skan } 21897403Sobrien return ++__result; 21997403Sobrien } 22097403Sobrien 221132720Skan /** 222132720Skan * @brief Return list of partial sums 223132720Skan * 224132720Skan * Accumulates the values in the range [first,last) using operator+(). 225132720Skan * As each successive input value is added into the total, that partial sum 226132720Skan * is written to @a result. Therefore, the first value in result is the 227132720Skan * first value of the input, the second value in result is the sum of the 228132720Skan * first and second input values, and so on. 229132720Skan * 230132720Skan * @param first Start of input range. 231132720Skan * @param last End of input range. 232132720Skan * @param result Output to write sums to. 233132720Skan * @return Iterator pointing just beyond the values written to result. 234132720Skan */ 235169691Skan template<typename _InputIterator, typename _OutputIterator, 236169691Skan typename _BinaryOperation> 237132720Skan _OutputIterator 23897403Sobrien partial_sum(_InputIterator __first, _InputIterator __last, 23997403Sobrien _OutputIterator __result, _BinaryOperation __binary_op) 24097403Sobrien { 24197403Sobrien typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 24297403Sobrien 24397403Sobrien // concept requirements 244132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 245169691Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 246169691Skan _ValueType>) 247132720Skan __glibcxx_requires_valid_range(__first, __last); 24897403Sobrien 249169691Skan if (__first == __last) 250169691Skan return __result; 25197403Sobrien _ValueType __value = *__first; 252169691Skan *__result = __value; 253169691Skan while (++__first != __last) 254169691Skan { 255169691Skan __value = __binary_op(__value, *__first); 256169691Skan *++__result = __value; 257169691Skan } 25897403Sobrien return ++__result; 25997403Sobrien } 26097403Sobrien 261132720Skan /** 262132720Skan * @brief Return differences between adjacent values. 263132720Skan * 264132720Skan * Computes the difference between adjacent values in the range 265132720Skan * [first,last) using operator-() and writes the result to @a result. 266132720Skan * 267132720Skan * @param first Start of input range. 268132720Skan * @param last End of input range. 269132720Skan * @param result Output to write sums to. 270132720Skan * @return Iterator pointing just beyond the values written to result. 271132720Skan */ 27297403Sobrien template<typename _InputIterator, typename _OutputIterator> 27397403Sobrien _OutputIterator 27497403Sobrien adjacent_difference(_InputIterator __first, 27597403Sobrien _InputIterator __last, _OutputIterator __result) 27697403Sobrien { 27797403Sobrien typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 27897403Sobrien 27997403Sobrien // concept requirements 280132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 281169691Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 282169691Skan _ValueType>) 283132720Skan __glibcxx_requires_valid_range(__first, __last); 28497403Sobrien 285169691Skan if (__first == __last) 286169691Skan return __result; 28797403Sobrien _ValueType __value = *__first; 288169691Skan *__result = __value; 289169691Skan while (++__first != __last) 290169691Skan { 291169691Skan _ValueType __tmp = *__first; 292169691Skan *++__result = __tmp - __value; 293169691Skan __value = __tmp; 294169691Skan } 29597403Sobrien return ++__result; 29697403Sobrien } 29797403Sobrien 298132720Skan /** 299132720Skan * @brief Return differences between adjacent values. 300132720Skan * 301132720Skan * Computes the difference between adjacent values in the range 302132720Skan * [first,last) using the function object @a binary_op and writes the 303132720Skan * result to @a result. 304132720Skan * 305132720Skan * @param first Start of input range. 306132720Skan * @param last End of input range. 307132720Skan * @param result Output to write sums to. 308132720Skan * @return Iterator pointing just beyond the values written to result. 309132720Skan */ 310169691Skan template<typename _InputIterator, typename _OutputIterator, 311169691Skan typename _BinaryOperation> 312132720Skan _OutputIterator 31397403Sobrien adjacent_difference(_InputIterator __first, _InputIterator __last, 31497403Sobrien _OutputIterator __result, _BinaryOperation __binary_op) 31597403Sobrien { 31697403Sobrien typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 31797403Sobrien 31897403Sobrien // concept requirements 319132720Skan __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 320169691Skan __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 321169691Skan _ValueType>) 322132720Skan __glibcxx_requires_valid_range(__first, __last); 32397403Sobrien 324169691Skan if (__first == __last) 325169691Skan return __result; 32697403Sobrien _ValueType __value = *__first; 327169691Skan *__result = __value; 328169691Skan while (++__first != __last) 329169691Skan { 330169691Skan _ValueType __tmp = *__first; 331169691Skan *++__result = __binary_op(__tmp, __value); 332169691Skan __value = __tmp; 333169691Skan } 33497403Sobrien return ++__result; 33597403Sobrien } 33697403Sobrien 337169691Skan_GLIBCXX_END_NAMESPACE 33897403Sobrien 339132720Skan#endif /* _STL_NUMERIC_H */ 340