1// Numeric functions implementation -*- C++ -*- 2 3// Copyright (C) 2001-2013 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 3, 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// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996,1997 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51/** @file bits/stl_numeric.h 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{numeric} 54 */ 55 56#ifndef _STL_NUMERIC_H 57#define _STL_NUMERIC_H 1 58 59#include <bits/concept_check.h> 60#include <debug/debug.h> 61#include <bits/move.h> // For _GLIBCXX_MOVE 62 63#if __cplusplus >= 201103L 64 65namespace std _GLIBCXX_VISIBILITY(default) 66{ 67_GLIBCXX_BEGIN_NAMESPACE_VERSION 68 69 /** 70 * @brief Create a range of sequentially increasing values. 71 * 72 * For each element in the range @p [first,last) assigns @p value and 73 * increments @p value as if by @p ++value. 74 * 75 * @param __first Start of range. 76 * @param __last End of range. 77 * @param __value Starting value. 78 * @return Nothing. 79 */ 80 template<typename _ForwardIterator, typename _Tp> 81 void 82 iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value) 83 { 84 // concept requirements 85 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept< 86 _ForwardIterator>) 87 __glibcxx_function_requires(_ConvertibleConcept<_Tp, 88 typename iterator_traits<_ForwardIterator>::value_type>) 89 __glibcxx_requires_valid_range(__first, __last); 90 91 for (; __first != __last; ++__first) 92 { 93 *__first = __value; 94 ++__value; 95 } 96 } 97 98_GLIBCXX_END_NAMESPACE_VERSION 99} // namespace std 100 101#endif 102 103namespace std _GLIBCXX_VISIBILITY(default) 104{ 105_GLIBCXX_BEGIN_NAMESPACE_ALGO 106 107 /** 108 * @brief Accumulate values in a range. 109 * 110 * Accumulates the values in the range [first,last) using operator+(). The 111 * initial value is @a init. The values are processed in order. 112 * 113 * @param __first Start of range. 114 * @param __last End of range. 115 * @param __init Starting value to add other values to. 116 * @return The final sum. 117 */ 118 template<typename _InputIterator, typename _Tp> 119 inline _Tp 120 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) 121 { 122 // concept requirements 123 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 124 __glibcxx_requires_valid_range(__first, __last); 125 126 for (; __first != __last; ++__first) 127 __init = __init + *__first; 128 return __init; 129 } 130 131 /** 132 * @brief Accumulate values in a range with operation. 133 * 134 * Accumulates the values in the range [first,last) using the function 135 * object @p __binary_op. The initial value is @p __init. The values are 136 * processed in order. 137 * 138 * @param __first Start of range. 139 * @param __last End of range. 140 * @param __init Starting value to add other values to. 141 * @param __binary_op Function object to accumulate with. 142 * @return The final sum. 143 */ 144 template<typename _InputIterator, typename _Tp, typename _BinaryOperation> 145 inline _Tp 146 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, 147 _BinaryOperation __binary_op) 148 { 149 // concept requirements 150 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 151 __glibcxx_requires_valid_range(__first, __last); 152 153 for (; __first != __last; ++__first) 154 __init = __binary_op(__init, *__first); 155 return __init; 156 } 157 158 /** 159 * @brief Compute inner product of two ranges. 160 * 161 * Starting with an initial value of @p __init, multiplies successive 162 * elements from the two ranges and adds each product into the accumulated 163 * value using operator+(). The values in the ranges are processed in 164 * order. 165 * 166 * @param __first1 Start of range 1. 167 * @param __last1 End of range 1. 168 * @param __first2 Start of range 2. 169 * @param __init Starting value to add other values to. 170 * @return The final inner product. 171 */ 172 template<typename _InputIterator1, typename _InputIterator2, typename _Tp> 173 inline _Tp 174 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 175 _InputIterator2 __first2, _Tp __init) 176 { 177 // concept requirements 178 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 179 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 180 __glibcxx_requires_valid_range(__first1, __last1); 181 182 for (; __first1 != __last1; ++__first1, ++__first2) 183 __init = __init + (*__first1 * *__first2); 184 return __init; 185 } 186 187 /** 188 * @brief Compute inner product of two ranges. 189 * 190 * Starting with an initial value of @p __init, applies @p __binary_op2 to 191 * successive elements from the two ranges and accumulates each result into 192 * the accumulated value using @p __binary_op1. The values in the ranges are 193 * processed in order. 194 * 195 * @param __first1 Start of range 1. 196 * @param __last1 End of range 1. 197 * @param __first2 Start of range 2. 198 * @param __init Starting value to add other values to. 199 * @param __binary_op1 Function object to accumulate with. 200 * @param __binary_op2 Function object to apply to pairs of input values. 201 * @return The final inner product. 202 */ 203 template<typename _InputIterator1, typename _InputIterator2, typename _Tp, 204 typename _BinaryOperation1, typename _BinaryOperation2> 205 inline _Tp 206 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, 207 _InputIterator2 __first2, _Tp __init, 208 _BinaryOperation1 __binary_op1, 209 _BinaryOperation2 __binary_op2) 210 { 211 // concept requirements 212 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) 213 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) 214 __glibcxx_requires_valid_range(__first1, __last1); 215 216 for (; __first1 != __last1; ++__first1, ++__first2) 217 __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); 218 return __init; 219 } 220 221 /** 222 * @brief Return list of partial sums 223 * 224 * Accumulates the values in the range [first,last) using the @c + operator. 225 * As each successive input value is added into the total, that partial sum 226 * is written to @p __result. Therefore, the first value in @p __result is 227 * the first value of the input, the second value in @p __result is the sum 228 * of the first and second input values, and so on. 229 * 230 * @param __first Start of input range. 231 * @param __last End of input range. 232 * @param __result Output sum. 233 * @return Iterator pointing just beyond the values written to __result. 234 */ 235 template<typename _InputIterator, typename _OutputIterator> 236 _OutputIterator 237 partial_sum(_InputIterator __first, _InputIterator __last, 238 _OutputIterator __result) 239 { 240 typedef typename iterator_traits<_InputIterator>::value_type _ValueType; 241 242 // concept requirements 243 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) 244 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, 245 _ValueType>) 246 __glibcxx_requires_valid_range(__first, __last); 247 248 if (__first == __last) 249 return __result; 250 _ValueType __value = *__first; 251 *__result = __value; 252 while (++__first != __last) 253 { 254 __value = __value + *__first; 255 *++__result = __value; 256 } 257 return ++__result; 258 } 259 260 /** 261 * @brief Return list of partial sums 262 * 263 * Accumulates the values in the range [first,last) using @p __binary_op. 264 * As each successive input value is added into the total, that partial sum 265 * is written to @p __result. Therefore, the first value in @p __result is 266 * the first value of the input, the second value in @p __result is the sum 267 * of the first and second input values, and so on. 268 * 269 * @param __first Start of input range. 270 * @param __last End of input range. 271 * @param __result Output sum. 272 * @param __binary_op Function object. 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 @p __result. 306 * 307 * @param __first Start of input range. 308 * @param __last End of input range. 309 * @param __result Output sums. 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 @p __binary_op and writes the 346 * result to @p __result. 347 * 348 * @param __first Start of input range. 349 * @param __last End of input range. 350 * @param __result Output sum. 351 * @param __binary_op Function object. 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