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