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 @a binary_op. The initial value is @a 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 @a 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 @a init, applies @a binary_op2 to 192 * successive elements from the two ranges and accumulates each result into 193 * the accumulated value using @a 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 the 228 * first value of the input, the second value in @p result is the sum of the 229 * 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 to write sums to. 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 @a result. Therefore, the first value in @p result is the 267 * first value of the input, the second value in @p result is the sum of the 268 * 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 to write sums to. 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 @a result. 307 * 308 * @param first Start of input range. 309 * @param last End of input range. 310 * @param result Output to write sums to. 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 @a binary_op and writes the 347 * result to @a result. 348 * 349 * @param first Start of input range. 350 * @param last End of input range. 351 * @param result Output to write sums to. 352 * @return Iterator pointing just beyond the values written to result. 353 * 354 * _GLIBCXX_RESOLVE_LIB_DEFECTS 355 * DR 539. partial_sum and adjacent_difference should mention requirements 356 */ 357 template<typename _InputIterator, typename _OutputIterator, 358 typename _BinaryOperation> 359 _OutputIterator 360 adjacent_difference(_InputIterator __first, _InputIterator __last, 361 _OutputIterator __result, _BinaryOperation __binary_op) 362 { 363 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 364 365 // concept requirements 366 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 367 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 368 _ValueType>) 369 __glibcxx_requires_valid_range(__first, __last); 370 371 if (__first == __last) 372 return __result; 373 _ValueType __value = *__first; 374 *__result = __value; 375 while (++__first != __last) 376 { 377 _ValueType __tmp = *__first; 378 *++__result = __binary_op(__tmp, __value); 379 __value = _GLIBCXX_MOVE(__tmp); 380 } 381 return ++__result; 382 } 383 384_GLIBCXX_END_NAMESPACE_ALGO 385} // namespace std 386 387#endif /* _STL_NUMERIC_H */ 388