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