1 // Numeric functions implementation -*- C++ -*- 2 3 // Copyright (C) 2001, 2004 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 2, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // You should have received a copy of the GNU General Public License along 17 // with this library; see the file COPYING. If not, write to the Free 18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19 // USA. 20 21 // As a special exception, you may use this file as part of a free software 22 // library without restriction. Specifically, if other files instantiate 23 // templates or use macros or inline functions from this file, or you compile 24 // this file and link it with other files to produce an executable, this 25 // file does not by itself cause the resulting executable to be covered by 26 // the GNU General Public License. This exception does not however 27 // invalidate any other reasons why the executable file might be covered by 28 // the GNU General Public License. 29 30 /* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1996,1997 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56 /** @file stl_numeric.h 57 * This is an internal header file, included by other library headers. 58 * You should not attempt to use it directly. 59 */ 60 61 #ifndef _STL_NUMERIC_H 62 #define _STL_NUMERIC_H 1 63 64 #include <debug/debug.h> 65 66 namespace std 67 { 68 69 /** 70 * @brief Accumulate values in a range. 71 * 72 * Accumulates the values in the range [first,last) using operator+(). The 73 * initial value is @a init. The values are processed in order. 74 * 75 * @param first Start of range. 76 * @param last End of range. 77 * @param init Starting value to add other values to. 78 * @return The final sum. 79 */ 80 template<typename _InputIterator, typename _Tp> 81 _Tp 82 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) 83 { 84 // concept requirements 85 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 86 __glibcxx_requires_valid_range(__first, __last); 87 88 for ( ; __first != __last; ++__first) 89 __init = __init + *__first; 90 return __init; 91 } 92 93 /** 94 * @brief Accumulate values in a range with operation. 95 * 96 * Accumulates the values in the range [first,last) using the function 97 * object @a binary_op. The initial value is @a init. The values are 98 * processed in order. 99 * 100 * @param first Start of range. 101 * @param last End of range. 102 * @param init Starting value to add other values to. 103 * @param binary_op Function object to accumulate with. 104 * @return The final sum. 105 */ 106 template<typename _InputIterator, typename _Tp, typename _BinaryOperation> 107 _Tp 108 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, 109 _BinaryOperation __binary_op) 110 { 111 // concept requirements 112 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 113 __glibcxx_requires_valid_range(__first, __last); 114 115 for ( ; __first != __last; ++__first) 116 __init = __binary_op(__init, *__first); 117 return __init; 118 } 119 120 /** 121 * @brief Compute inner product of two ranges. 122 * 123 * Starting with an initial value of @a init, multiplies successive 124 * elements from the two ranges and adds each product into the accumulated 125 * value using operator+(). The values in the ranges are processed in 126 * order. 127 * 128 * @param first1 Start of range 1. 129 * @param last1 End of range 1. 130 * @param first2 Start of range 2. 131 * @param init Starting value to add other values to. 132 * @return The final inner product. 133 */ 134 template<typename _InputIterator1, typename _InputIterator2, typename _Tp> 135 _Tp 136 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 137 _InputIterator2 __first2, _Tp __init) 138 { 139 // concept requirements 140 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 141 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 142 __glibcxx_requires_valid_range(__first1, __last1); 143 144 for ( ; __first1 != __last1; ++__first1, ++__first2) 145 __init = __init + (*__first1 * *__first2); 146 return __init; 147 } 148 149 /** 150 * @brief Compute inner product of two ranges. 151 * 152 * Starting with an initial value of @a init, applies @a binary_op2 to 153 * successive elements from the two ranges and accumulates each result into 154 * the accumulated value using @a binary_op1. The values in the ranges are 155 * processed in order. 156 * 157 * @param first1 Start of range 1. 158 * @param last1 End of range 1. 159 * @param first2 Start of range 2. 160 * @param init Starting value to add other values to. 161 * @param binary_op1 Function object to accumulate with. 162 * @param binary_op2 Function object to apply to pairs of input values. 163 * @return The final inner product. 164 */ 165 template<typename _InputIterator1, typename _InputIterator2, typename _Tp, 166 typename _BinaryOperation1, typename _BinaryOperation2> 167 _Tp 168 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 169 _InputIterator2 __first2, _Tp __init, 170 _BinaryOperation1 __binary_op1, 171 _BinaryOperation2 __binary_op2) 172 { 173 // concept requirements 174 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 175 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 176 __glibcxx_requires_valid_range(__first1, __last1); 177 178 for ( ; __first1 != __last1; ++__first1, ++__first2) 179 __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); 180 return __init; 181 } 182 183 /** 184 * @brief Return list of partial sums 185 * 186 * Accumulates the values in the range [first,last) using operator+(). 187 * As each successive input value is added into the total, that partial sum 188 * is written to @a result. Therefore, the first value in result is the 189 * first value of the input, the second value in result is the sum of the 190 * first and second input values, and so on. 191 * 192 * @param first Start of input range. 193 * @param last End of input range. 194 * @param result Output to write sums to. 195 * @return Iterator pointing just beyond the values written to result. 196 */ 197 template<typename _InputIterator, typename _OutputIterator> 198 _OutputIterator 199 partial_sum(_InputIterator __first, _InputIterator __last, 200 _OutputIterator __result) 201 { 202 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 203 204 // concept requirements 205 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 206 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _ValueType>) 207 __glibcxx_requires_valid_range(__first, __last); 208 209 if (__first == __last) return __result; 210 *__result = *__first; 211 _ValueType __value = *__first; 212 while (++__first != __last) { 213 __value = __value + *__first; 214 *++__result = __value; 215 } 216 return ++__result; 217 } 218 219 /** 220 * @brief Return list of partial sums 221 * 222 * Accumulates the values in the range [first,last) using operator+(). 223 * As each successive input value is added into the total, that partial sum 224 * is written to @a result. Therefore, the first value in result is the 225 * first value of the input, the second value in result is the sum of the 226 * first and second input values, and so on. 227 * 228 * @param first Start of input range. 229 * @param last End of input range. 230 * @param result Output to write sums to. 231 * @return Iterator pointing just beyond the values written to result. 232 */ 233 template<typename _InputIterator, typename _OutputIterator, typename _BinaryOperation> 234 _OutputIterator 235 partial_sum(_InputIterator __first, _InputIterator __last, 236 _OutputIterator __result, _BinaryOperation __binary_op) 237 { 238 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 239 240 // concept requirements 241 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 242 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _ValueType>) 243 __glibcxx_requires_valid_range(__first, __last); 244 245 if (__first == __last) return __result; 246 *__result = *__first; 247 _ValueType __value = *__first; 248 while (++__first != __last) { 249 __value = __binary_op(__value, *__first); 250 *++__result = __value; 251 } 252 return ++__result; 253 } 254 255 /** 256 * @brief Return differences between adjacent values. 257 * 258 * Computes the difference between adjacent values in the range 259 * [first,last) using operator-() and writes the result to @a result. 260 * 261 * @param first Start of input range. 262 * @param last End of input range. 263 * @param result Output to write sums to. 264 * @return Iterator pointing just beyond the values written to result. 265 */ 266 template<typename _InputIterator, typename _OutputIterator> 267 _OutputIterator 268 adjacent_difference(_InputIterator __first, 269 _InputIterator __last, _OutputIterator __result) 270 { 271 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 272 273 // concept requirements 274 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 275 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _ValueType>) 276 __glibcxx_requires_valid_range(__first, __last); 277 278 if (__first == __last) return __result; 279 *__result = *__first; 280 _ValueType __value = *__first; 281 while (++__first != __last) { 282 _ValueType __tmp = *__first; 283 *++__result = __tmp - __value; 284 __value = __tmp; 285 } 286 return ++__result; 287 } 288 289 /** 290 * @brief Return differences between adjacent values. 291 * 292 * Computes the difference between adjacent values in the range 293 * [first,last) using the function object @a binary_op and writes the 294 * result to @a result. 295 * 296 * @param first Start of input range. 297 * @param last End of input range. 298 * @param result Output to write sums to. 299 * @return Iterator pointing just beyond the values written to result. 300 */ 301 template<typename _InputIterator, typename _OutputIterator, typename _BinaryOperation> 302 _OutputIterator 303 adjacent_difference(_InputIterator __first, _InputIterator __last, 304 _OutputIterator __result, _BinaryOperation __binary_op) 305 { 306 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 307 308 // concept requirements 309 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 310 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _ValueType>) 311 __glibcxx_requires_valid_range(__first, __last); 312 313 if (__first == __last) return __result; 314 *__result = *__first; 315 _ValueType __value = *__first; 316 while (++__first != __last) { 317 _ValueType __tmp = *__first; 318 *++__result = __binary_op(__tmp, __value); 319 __value = __tmp; 320 } 321 return ++__result; 322 } 323 324 } // namespace std 325 326 #endif /* _STL_NUMERIC_H */ 327