1// Numeric functions implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009 4// Free Software Foundation, Inc. 5// 6// This file is part of the GNU ISO C++ Library. This library is free 7// software; you can redistribute it and/or modify it under the 8// terms of the GNU General Public License as published by the 9// Free Software Foundation; either version 3, or (at your option) 10// any later version. 11 12// This library is distributed in the hope that it will be useful, 13// but WITHOUT ANY WARRANTY; without even the implied warranty of 14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15// GNU General Public License for more details. 16 17// Under Section 7 of GPL version 3, you are granted additional 18// permissions described in the GCC Runtime Library Exception, version 19// 3.1, as published by the Free Software Foundation. 20 21// You should have received a copy of the GNU General Public License and 22// a copy of the GCC Runtime Library Exception along with this program; 23// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24// <http://www.gnu.org/licenses/>. 25 26/* 27 * 28 * Copyright (c) 1994 29 * Hewlett-Packard Company 30 * 31 * Permission to use, copy, modify, distribute and sell this software 32 * and its documentation for any purpose is hereby granted without fee, 33 * provided that the above copyright notice appear in all copies and 34 * that both that copyright notice and this permission notice appear 35 * in supporting documentation. Hewlett-Packard Company makes no 36 * representations about the suitability of this software for any 37 * purpose. It is provided "as is" without express or implied warranty. 38 * 39 * 40 * Copyright (c) 1996,1997 41 * Silicon Graphics Computer Systems, Inc. 42 * 43 * Permission to use, copy, modify, distribute and sell this software 44 * and its documentation for any purpose is hereby granted without fee, 45 * provided that the above copyright notice appear in all copies and 46 * that both that copyright notice and this permission notice appear 47 * in supporting documentation. Silicon Graphics makes no 48 * representations about the suitability of this software for any 49 * purpose. It is provided "as is" without express or implied warranty. 50 */ 51 52/** @file stl_numeric.h 53 * This is an internal header file, included by other library headers. 54 * You should not attempt to use it directly. 55 */ 56 57#ifndef _STL_NUMERIC_H 58#define _STL_NUMERIC_H 1 59 60#include <bits/concept_check.h> 61#include <debug/debug.h> 62#include <bits/move.h> // For _GLIBCXX_MOVE 63 64#ifdef __GXX_EXPERIMENTAL_CXX0X__ 65 66_GLIBCXX_BEGIN_NAMESPACE(std) 67 68 /** 69 * @brief Create a range of sequentially increasing values. 70 * 71 * For each element in the range @p [first,last) assigns @p value and 72 * increments @p value as if by @p ++value. 73 * 74 * @param first Start of range. 75 * @param last End of range. 76 * @param value Starting value. 77 * @return Nothing. 78 */ 79 template<typename _ForwardIterator, typename _Tp> 80 void 81 iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value) 82 { 83 // concept requirements 84 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 85 _ForwardIterator>) 86 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 87 typename iterator_traits<_ForwardIterator>::value_type>) 88 __glibcxx_requires_valid_range(__first, __last); 89 90 for (; __first != __last; ++__first) 91 { 92 *__first = __value; 93 ++__value; 94 } 95 } 96 97_GLIBCXX_END_NAMESPACE 98 99#endif 100 101_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P) 102 103 /** 104 * @brief Accumulate values in a range. 105 * 106 * Accumulates the values in the range [first,last) using operator+(). The 107 * initial value is @a init. The values are processed in order. 108 * 109 * @param first Start of range. 110 * @param last End of range. 111 * @param init Starting value to add other values to. 112 * @return The final sum. 113 */ 114 template<typename _InputIterator, typename _Tp> 115 inline _Tp 116 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) 117 { 118 // concept requirements 119 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 120 __glibcxx_requires_valid_range(__first, __last); 121 122 for (; __first != __last; ++__first) 123 __init = __init + *__first; 124 return __init; 125 } 126 127 /** 128 * @brief Accumulate values in a range with operation. 129 * 130 * Accumulates the values in the range [first,last) using the function 131 * object @a binary_op. The initial value is @a init. The values are 132 * processed in order. 133 * 134 * @param first Start of range. 135 * @param last End of range. 136 * @param init Starting value to add other values to. 137 * @param binary_op Function object to accumulate with. 138 * @return The final sum. 139 */ 140 template<typename _InputIterator, typename _Tp, typename _BinaryOperation> 141 inline _Tp 142 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, 143 _BinaryOperation __binary_op) 144 { 145 // concept requirements 146 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 147 __glibcxx_requires_valid_range(__first, __last); 148 149 for (; __first != __last; ++__first) 150 __init = __binary_op(__init, *__first); 151 return __init; 152 } 153 154 /** 155 * @brief Compute inner product of two ranges. 156 * 157 * Starting with an initial value of @a init, multiplies successive 158 * elements from the two ranges and adds each product into the accumulated 159 * value using operator+(). The values in the ranges are processed in 160 * order. 161 * 162 * @param first1 Start of range 1. 163 * @param last1 End of range 1. 164 * @param first2 Start of range 2. 165 * @param init Starting value to add other values to. 166 * @return The final inner product. 167 */ 168 template<typename _InputIterator1, typename _InputIterator2, typename _Tp> 169 inline _Tp 170 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 171 _InputIterator2 __first2, _Tp __init) 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 = __init + (*__first1 * *__first2); 180 return __init; 181 } 182 183 /** 184 * @brief Compute inner product of two ranges. 185 * 186 * Starting with an initial value of @a init, applies @a binary_op2 to 187 * successive elements from the two ranges and accumulates each result into 188 * the accumulated value using @a binary_op1. The values in the ranges are 189 * processed in order. 190 * 191 * @param first1 Start of range 1. 192 * @param last1 End of range 1. 193 * @param first2 Start of range 2. 194 * @param init Starting value to add other values to. 195 * @param binary_op1 Function object to accumulate with. 196 * @param binary_op2 Function object to apply to pairs of input values. 197 * @return The final inner product. 198 */ 199 template<typename _InputIterator1, typename _InputIterator2, typename _Tp, 200 typename _BinaryOperation1, typename _BinaryOperation2> 201 inline _Tp 202 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 203 _InputIterator2 __first2, _Tp __init, 204 _BinaryOperation1 __binary_op1, 205 _BinaryOperation2 __binary_op2) 206 { 207 // concept requirements 208 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 209 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 210 __glibcxx_requires_valid_range(__first1, __last1); 211 212 for (; __first1 != __last1; ++__first1, ++__first2) 213 __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); 214 return __init; 215 } 216 217 /** 218 * @brief Return list of partial sums 219 * 220 * Accumulates the values in the range [first,last) using operator+(). 221 * As each successive input value is added into the total, that partial sum 222 * is written to @a result. Therefore, the first value in result is the 223 * first value of the input, the second value in result is the sum of the 224 * first and second input values, and so on. 225 * 226 * @param first Start of input range. 227 * @param last End of input range. 228 * @param result Output to write sums to. 229 * @return Iterator pointing just beyond the values written to result. 230 */ 231 template<typename _InputIterator, typename _OutputIterator> 232 _OutputIterator 233 partial_sum(_InputIterator __first, _InputIterator __last, 234 _OutputIterator __result) 235 { 236 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 237 238 // concept requirements 239 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 240 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 241 _ValueType>) 242 __glibcxx_requires_valid_range(__first, __last); 243 244 if (__first == __last) 245 return __result; 246 _ValueType __value = *__first; 247 *__result = __value; 248 while (++__first != __last) 249 { 250 __value = __value + *__first; 251 *++__result = __value; 252 } 253 return ++__result; 254 } 255 256 /** 257 * @brief Return list of partial sums 258 * 259 * Accumulates the values in the range [first,last) using operator+(). 260 * As each successive input value is added into the total, that partial sum 261 * is written to @a result. Therefore, the first value in result is the 262 * first value of the input, the second value in result is the sum of the 263 * first and second input values, and so on. 264 * 265 * @param first Start of input range. 266 * @param last End of input range. 267 * @param result Output to write sums to. 268 * @return Iterator pointing just beyond the values written to result. 269 */ 270 template<typename _InputIterator, typename _OutputIterator, 271 typename _BinaryOperation> 272 _OutputIterator 273 partial_sum(_InputIterator __first, _InputIterator __last, 274 _OutputIterator __result, _BinaryOperation __binary_op) 275 { 276 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 277 278 // concept requirements 279 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 280 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 281 _ValueType>) 282 __glibcxx_requires_valid_range(__first, __last); 283 284 if (__first == __last) 285 return __result; 286 _ValueType __value = *__first; 287 *__result = __value; 288 while (++__first != __last) 289 { 290 __value = __binary_op(__value, *__first); 291 *++__result = __value; 292 } 293 return ++__result; 294 } 295 296 /** 297 * @brief Return differences between adjacent values. 298 * 299 * Computes the difference between adjacent values in the range 300 * [first,last) using operator-() and writes the result to @a result. 301 * 302 * @param first Start of input range. 303 * @param last End of input range. 304 * @param result Output to write sums to. 305 * @return Iterator pointing just beyond the values written to result. 306 * 307 * _GLIBCXX_RESOLVE_LIB_DEFECTS 308 * DR 539. partial_sum and adjacent_difference should mention requirements 309 */ 310 template<typename _InputIterator, typename _OutputIterator> 311 _OutputIterator 312 adjacent_difference(_InputIterator __first, 313 _InputIterator __last, _OutputIterator __result) 314 { 315 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 316 317 // concept requirements 318 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 319 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 320 _ValueType>) 321 __glibcxx_requires_valid_range(__first, __last); 322 323 if (__first == __last) 324 return __result; 325 _ValueType __value = *__first; 326 *__result = __value; 327 while (++__first != __last) 328 { 329 _ValueType __tmp = *__first; 330 *++__result = __tmp - __value; 331 __value = _GLIBCXX_MOVE(__tmp); 332 } 333 return ++__result; 334 } 335 336 /** 337 * @brief Return differences between adjacent values. 338 * 339 * Computes the difference between adjacent values in the range 340 * [first,last) using the function object @a binary_op and writes the 341 * result to @a result. 342 * 343 * @param first Start of input range. 344 * @param last End of input range. 345 * @param result Output to write sums to. 346 * @return Iterator pointing just beyond the values written to result. 347 * 348 * _GLIBCXX_RESOLVE_LIB_DEFECTS 349 * DR 539. partial_sum and adjacent_difference should mention requirements 350 */ 351 template<typename _InputIterator, typename _OutputIterator, 352 typename _BinaryOperation> 353 _OutputIterator 354 adjacent_difference(_InputIterator __first, _InputIterator __last, 355 _OutputIterator __result, _BinaryOperation __binary_op) 356 { 357 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 358 359 // concept requirements 360 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 361 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 362 _ValueType>) 363 __glibcxx_requires_valid_range(__first, __last); 364 365 if (__first == __last) 366 return __result; 367 _ValueType __value = *__first; 368 *__result = __value; 369 while (++__first != __last) 370 { 371 _ValueType __tmp = *__first; 372 *++__result = __binary_op(__tmp, __value); 373 __value = _GLIBCXX_MOVE(__tmp); 374 } 375 return ++__result; 376 } 377 378_GLIBCXX_END_NESTED_NAMESPACE 379 380#endif /* _STL_NUMERIC_H */ 381