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 operator+(). 226 * As each successive input value is added into the total, that partial sum 227 * is written to @a result. Therefore, the first value in result is the 228 * first value of the input, the second value in 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 operator+(). 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 result is the 267 * first value of the input, the second value in 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 * @return Iterator pointing just beyond the values written to result. 274 */ 275 template<typename _InputIterator, typename _OutputIterator, 276 typename _BinaryOperation> 277 _OutputIterator 278 partial_sum(_InputIterator __first, _InputIterator __last, 279 _OutputIterator __result, _BinaryOperation __binary_op) 280 { 281 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 282 283 // concept requirements 284 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 285 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 286 _ValueType>) 287 __glibcxx_requires_valid_range(__first, __last); 288 289 if (__first == __last) 290 return __result; 291 _ValueType __value = *__first; 292 *__result = __value; 293 while (++__first != __last) 294 { 295 __value = __binary_op(__value, *__first); 296 *++__result = __value; 297 } 298 return ++__result; 299 } 300 301 /** 302 * @brief Return differences between adjacent values. 303 * 304 * Computes the difference between adjacent values in the range 305 * [first,last) using operator-() and writes the result to @a result. 306 * 307 * @param first Start of input range. 308 * @param last End of input range. 309 * @param result Output to write sums to. 310 * @return Iterator pointing just beyond the values written to result. 311 * 312 * _GLIBCXX_RESOLVE_LIB_DEFECTS 313 * DR 539. partial_sum and adjacent_difference should mention requirements 314 */ 315 template<typename _InputIterator, typename _OutputIterator> 316 _OutputIterator 317 adjacent_difference(_InputIterator __first, 318 _InputIterator __last, _OutputIterator __result) 319 { 320 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 321 322 // concept requirements 323 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 324 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 325 _ValueType>) 326 __glibcxx_requires_valid_range(__first, __last); 327 328 if (__first == __last) 329 return __result; 330 _ValueType __value = *__first; 331 *__result = __value; 332 while (++__first != __last) 333 { 334 _ValueType __tmp = *__first; 335 *++__result = __tmp - __value; 336 __value = _GLIBCXX_MOVE(__tmp); 337 } 338 return ++__result; 339 } 340 341 /** 342 * @brief Return differences between adjacent values. 343 * 344 * Computes the difference between adjacent values in the range 345 * [first,last) using the function object @a binary_op and writes the 346 * result to @a result. 347 * 348 * @param first Start of input range. 349 * @param last End of input range. 350 * @param result Output to write sums to. 351 * @return Iterator pointing just beyond the values written to result. 352 * 353 * _GLIBCXX_RESOLVE_LIB_DEFECTS 354 * DR 539. partial_sum and adjacent_difference should mention requirements 355 */ 356 template<typename _InputIterator, typename _OutputIterator, 357 typename _BinaryOperation> 358 _OutputIterator 359 adjacent_difference(_InputIterator __first, _InputIterator __last, 360 _OutputIterator __result, _BinaryOperation __binary_op) 361 { 362 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 363 364 // concept requirements 365 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 366 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 367 _ValueType>) 368 __glibcxx_requires_valid_range(__first, __last); 369 370 if (__first == __last) 371 return __result; 372 _ValueType __value = *__first; 373 *__result = __value; 374 while (++__first != __last) 375 { 376 _ValueType __tmp = *__first; 377 *++__result = __binary_op(__tmp, __value); 378 __value = _GLIBCXX_MOVE(__tmp); 379 } 380 return ++__result; 381 } 382 383_GLIBCXX_END_NAMESPACE_ALGO 384} // namespace std 385 386#endif /* _STL_NUMERIC_H */ 387