1// Numeric functions implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 4// 2011 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 bits/stl_numeric.h 53 * This is an internal header file, included by other library headers. 54 * Do not attempt to use it directly. @headername{numeric} 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 66namespace std _GLIBCXX_VISIBILITY(default) 67{ 68_GLIBCXX_BEGIN_NAMESPACE_VERSION 69 70 /** 71 * @brief Create a range of sequentially increasing values. 72 * 73 * For each element in the range @p [first,last) assigns @p value and 74 * increments @p value as if by @p ++value. 75 * 76 * @param __first Start of range. 77 * @param __last End of range. 78 * @param __value Starting value. 79 * @return Nothing. 80 */ 81 template<typename _ForwardIterator, typename _Tp> 82 void 83 iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value) 84 { 85 // concept requirements 86 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 87 _ForwardIterator>) 88 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 89 typename iterator_traits<_ForwardIterator>::value_type>) 90 __glibcxx_requires_valid_range(__first, __last); 91 92 for (; __first != __last; ++__first) 93 { 94 *__first = __value; 95 ++__value; 96 } 97 } 98 99_GLIBCXX_END_NAMESPACE_VERSION 100} // namespace std 101 102#endif 103 104namespace std _GLIBCXX_VISIBILITY(default) 105{ 106_GLIBCXX_BEGIN_NAMESPACE_ALGO 107 108 /** 109 * @brief Accumulate values in a range. 110 * 111 * Accumulates the values in the range [first,last) using operator+(). The 112 * initial value is @a init. The values are processed in order. 113 * 114 * @param __first Start of range. 115 * @param __last End of range. 116 * @param __init Starting value to add other values to. 117 * @return The final sum. 118 */ 119 template<typename _InputIterator, typename _Tp> 120 inline _Tp 121 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) 122 { 123 // concept requirements 124 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 125 __glibcxx_requires_valid_range(__first, __last); 126 127 for (; __first != __last; ++__first) 128 __init = __init + *__first; 129 return __init; 130 } 131 132 /** 133 * @brief Accumulate values in a range with operation. 134 * 135 * Accumulates the values in the range [first,last) using the function 136 * object @p __binary_op. The initial value is @p __init. The values are 137 * processed in order. 138 * 139 * @param __first Start of range. 140 * @param __last End of range. 141 * @param __init Starting value to add other values to. 142 * @param __binary_op Function object to accumulate with. 143 * @return The final sum. 144 */ 145 template<typename _InputIterator, typename _Tp, typename _BinaryOperation> 146 inline _Tp 147 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, 148 _BinaryOperation __binary_op) 149 { 150 // concept requirements 151 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 152 __glibcxx_requires_valid_range(__first, __last); 153 154 for (; __first != __last; ++__first) 155 __init = __binary_op(__init, *__first); 156 return __init; 157 } 158 159 /** 160 * @brief Compute inner product of two ranges. 161 * 162 * Starting with an initial value of @p __init, multiplies successive 163 * elements from the two ranges and adds each product into the accumulated 164 * value using operator+(). The values in the ranges are processed in 165 * order. 166 * 167 * @param __first1 Start of range 1. 168 * @param __last1 End of range 1. 169 * @param __first2 Start of range 2. 170 * @param __init Starting value to add other values to. 171 * @return The final inner product. 172 */ 173 template<typename _InputIterator1, typename _InputIterator2, typename _Tp> 174 inline _Tp 175 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 176 _InputIterator2 __first2, _Tp __init) 177 { 178 // concept requirements 179 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 180 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 181 __glibcxx_requires_valid_range(__first1, __last1); 182 183 for (; __first1 != __last1; ++__first1, ++__first2) 184 __init = __init + (*__first1 * *__first2); 185 return __init; 186 } 187 188 /** 189 * @brief Compute inner product of two ranges. 190 * 191 * Starting with an initial value of @p __init, applies @p __binary_op2 to 192 * successive elements from the two ranges and accumulates each result into 193 * the accumulated value using @p __binary_op1. The values in the ranges are 194 * processed in order. 195 * 196 * @param __first1 Start of range 1. 197 * @param __last1 End of range 1. 198 * @param __first2 Start of range 2. 199 * @param __init Starting value to add other values to. 200 * @param __binary_op1 Function object to accumulate with. 201 * @param __binary_op2 Function object to apply to pairs of input values. 202 * @return The final inner product. 203 */ 204 template<typename _InputIterator1, typename _InputIterator2, typename _Tp, 205 typename _BinaryOperation1, typename _BinaryOperation2> 206 inline _Tp 207 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 208 _InputIterator2 __first2, _Tp __init, 209 _BinaryOperation1 __binary_op1, 210 _BinaryOperation2 __binary_op2) 211 { 212 // concept requirements 213 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 214 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 215 __glibcxx_requires_valid_range(__first1, __last1); 216 217 for (; __first1 != __last1; ++__first1, ++__first2) 218 __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); 219 return __init; 220 } 221 222 /** 223 * @brief Return list of partial sums 224 * 225 * Accumulates the values in the range [first,last) using the @c + operator. 226 * As each successive input value is added into the total, that partial sum 227 * is written to @p __result. Therefore, the first value in @p __result is 228 * the first value of the input, the second value in @p __result is the sum 229 * of the first and second input values, and so on. 230 * 231 * @param __first Start of input range. 232 * @param __last End of input range. 233 * @param __result Output sum. 234 * @return Iterator pointing just beyond the values written to __result. 235 */ 236 template<typename _InputIterator, typename _OutputIterator> 237 _OutputIterator 238 partial_sum(_InputIterator __first, _InputIterator __last, 239 _OutputIterator __result) 240 { 241 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 242 243 // concept requirements 244 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 245 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 246 _ValueType>) 247 __glibcxx_requires_valid_range(__first, __last); 248 249 if (__first == __last) 250 return __result; 251 _ValueType __value = *__first; 252 *__result = __value; 253 while (++__first != __last) 254 { 255 __value = __value + *__first; 256 *++__result = __value; 257 } 258 return ++__result; 259 } 260 261 /** 262 * @brief Return list of partial sums 263 * 264 * Accumulates the values in the range [first,last) using @p __binary_op. 265 * As each successive input value is added into the total, that partial sum 266 * is written to @p __result. Therefore, the first value in @p __result is 267 * the first value of the input, the second value in @p __result is the sum 268 * of the first and second input values, and so on. 269 * 270 * @param __first Start of input range. 271 * @param __last End of input range. 272 * @param __result Output sum. 273 * @param __binary_op Function object. 274 * @return Iterator pointing just beyond the values written to __result. 275 */ 276 template<typename _InputIterator, typename _OutputIterator, 277 typename _BinaryOperation> 278 _OutputIterator 279 partial_sum(_InputIterator __first, _InputIterator __last, 280 _OutputIterator __result, _BinaryOperation __binary_op) 281 { 282 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 283 284 // concept requirements 285 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 286 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 287 _ValueType>) 288 __glibcxx_requires_valid_range(__first, __last); 289 290 if (__first == __last) 291 return __result; 292 _ValueType __value = *__first; 293 *__result = __value; 294 while (++__first != __last) 295 { 296 __value = __binary_op(__value, *__first); 297 *++__result = __value; 298 } 299 return ++__result; 300 } 301 302 /** 303 * @brief Return differences between adjacent values. 304 * 305 * Computes the difference between adjacent values in the range 306 * [first,last) using operator-() and writes the result to @p __result. 307 * 308 * @param __first Start of input range. 309 * @param __last End of input range. 310 * @param __result Output sums. 311 * @return Iterator pointing just beyond the values written to result. 312 * 313 * _GLIBCXX_RESOLVE_LIB_DEFECTS 314 * DR 539. partial_sum and adjacent_difference should mention requirements 315 */ 316 template<typename _InputIterator, typename _OutputIterator> 317 _OutputIterator 318 adjacent_difference(_InputIterator __first, 319 _InputIterator __last, _OutputIterator __result) 320 { 321 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 322 323 // concept requirements 324 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 325 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 326 _ValueType>) 327 __glibcxx_requires_valid_range(__first, __last); 328 329 if (__first == __last) 330 return __result; 331 _ValueType __value = *__first; 332 *__result = __value; 333 while (++__first != __last) 334 { 335 _ValueType __tmp = *__first; 336 *++__result = __tmp - __value; 337 __value = _GLIBCXX_MOVE(__tmp); 338 } 339 return ++__result; 340 } 341 342 /** 343 * @brief Return differences between adjacent values. 344 * 345 * Computes the difference between adjacent values in the range 346 * [__first,__last) using the function object @p __binary_op and writes the 347 * result to @p __result. 348 * 349 * @param __first Start of input range. 350 * @param __last End of input range. 351 * @param __result Output sum. 352 * @param __binary_op Function object. 353 * @return Iterator pointing just beyond the values written to result. 354 * 355 * _GLIBCXX_RESOLVE_LIB_DEFECTS 356 * DR 539. partial_sum and adjacent_difference should mention requirements 357 */ 358 template<typename _InputIterator, typename _OutputIterator, 359 typename _BinaryOperation> 360 _OutputIterator 361 adjacent_difference(_InputIterator __first, _InputIterator __last, 362 _OutputIterator __result, _BinaryOperation __binary_op) 363 { 364 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 365 366 // concept requirements 367 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 368 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 369 _ValueType>) 370 __glibcxx_requires_valid_range(__first, __last); 371 372 if (__first == __last) 373 return __result; 374 _ValueType __value = *__first; 375 *__result = __value; 376 while (++__first != __last) 377 { 378 _ValueType __tmp = *__first; 379 *++__result = __binary_op(__tmp, __value); 380 __value = _GLIBCXX_MOVE(__tmp); 381 } 382 return ++__result; 383 } 384 385_GLIBCXX_END_NAMESPACE_ALGO 386} // namespace std 387 388#endif /* _STL_NUMERIC_H */ 389