1 | // <numeric> -*- 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 include/numeric |
52 | * This is a Standard C++ Library header. |
53 | */ |
54 | |
55 | #ifndef _GLIBCXX_NUMERIC |
56 | #define _GLIBCXX_NUMERIC 1 |
57 | |
58 | #pragma GCC system_header |
59 | |
60 | #include <bits/c++config.h> |
61 | #include <bits/stl_iterator_base_types.h> |
62 | #include <bits/stl_numeric.h> |
63 | #include <ext/numeric_traits.h> |
64 | |
65 | #ifdef _GLIBCXX_PARALLEL |
66 | # include <parallel/numeric> |
67 | #endif |
68 | |
69 | /** |
70 | * @defgroup numerics Numerics |
71 | * |
72 | * Components for performing numeric operations. Includes support for |
73 | * complex number types, random number generation, numeric (n-at-a-time) |
74 | * arrays, generalized numeric algorithms, and mathematical special functions. |
75 | */ |
76 | |
77 | #if __cplusplus >= 201402L |
78 | #include <type_traits> |
79 | |
80 | namespace std _GLIBCXX_VISIBILITY(default) |
81 | { |
82 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
83 | |
84 | namespace __detail |
85 | { |
86 | // std::abs is not constexpr, doesn't support unsigned integers, |
87 | // and std::abs(std::numeric_limits<T>::min()) is undefined. |
88 | template<typename _Up, typename _Tp> |
89 | constexpr _Up |
90 | __absu(_Tp __val) |
91 | { |
92 | static_assert(is_unsigned<_Up>::value, "result type must be unsigned" ); |
93 | static_assert(sizeof(_Up) >= sizeof(_Tp), |
94 | "result type must be at least as wide as the input type" ); |
95 | return __val < 0 ? -(_Up)__val : (_Up)__val; |
96 | } |
97 | |
98 | template<typename _Up> void __absu(bool) = delete; |
99 | |
100 | // GCD implementation |
101 | template<typename _Tp> |
102 | constexpr _Tp |
103 | __gcd(_Tp __m, _Tp __n) |
104 | { |
105 | static_assert(is_unsigned<_Tp>::value, "type must be unsigned" ); |
106 | return __m == 0 ? __n |
107 | : __n == 0 ? __m |
108 | : __detail::__gcd(__n, _Tp(__m % __n)); |
109 | } |
110 | |
111 | // LCM implementation |
112 | template<typename _Tp> |
113 | constexpr _Tp |
114 | __lcm(_Tp __m, _Tp __n) |
115 | { |
116 | return (__m != 0 && __n != 0) |
117 | ? (__m / __detail::__gcd(__m, __n)) * __n |
118 | : 0; |
119 | } |
120 | } // namespace __detail |
121 | |
122 | #if __cplusplus >= 201703L |
123 | |
124 | #define __cpp_lib_gcd_lcm 201606 |
125 | // These were used in drafts of SD-6: |
126 | #define __cpp_lib_gcd 201606 |
127 | #define __cpp_lib_lcm 201606 |
128 | |
129 | /// Greatest common divisor |
130 | template<typename _Mn, typename _Nn> |
131 | constexpr common_type_t<_Mn, _Nn> |
132 | gcd(_Mn __m, _Nn __n) noexcept |
133 | { |
134 | static_assert(is_integral_v<_Mn>, "std::gcd arguments must be integers" ); |
135 | static_assert(is_integral_v<_Nn>, "std::gcd arguments must be integers" ); |
136 | static_assert(_Mn(2) != _Mn(1), "std::gcd arguments must not be bool" ); |
137 | static_assert(_Nn(2) != _Nn(1), "std::gcd arguments must not be bool" ); |
138 | using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>; |
139 | return __detail::__gcd(__detail::__absu<_Up>(__m), |
140 | __detail::__absu<_Up>(__n)); |
141 | } |
142 | |
143 | /// Least common multiple |
144 | template<typename _Mn, typename _Nn> |
145 | constexpr common_type_t<_Mn, _Nn> |
146 | lcm(_Mn __m, _Nn __n) noexcept |
147 | { |
148 | static_assert(is_integral_v<_Mn>, "std::lcm arguments must be integers" ); |
149 | static_assert(is_integral_v<_Nn>, "std::lcm arguments must be integers" ); |
150 | static_assert(_Mn(2) == 2, "std::lcm arguments must not be bool" ); |
151 | static_assert(_Nn(2) == 2, "std::lcm arguments must not be bool" ); |
152 | using _Up = make_unsigned_t<common_type_t<_Mn, _Nn>>; |
153 | return __detail::__lcm(__detail::__absu<_Up>(__m), |
154 | __detail::__absu<_Up>(__n)); |
155 | } |
156 | |
157 | #endif // C++17 |
158 | |
159 | _GLIBCXX_END_NAMESPACE_VERSION |
160 | } // namespace std |
161 | |
162 | #endif // C++14 |
163 | |
164 | #if __cplusplus > 201703L |
165 | #include <limits> |
166 | |
167 | namespace std _GLIBCXX_VISIBILITY(default) |
168 | { |
169 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
170 | // midpoint |
171 | # define __cpp_lib_interpolate 201902L |
172 | |
173 | template<typename _Tp> |
174 | constexpr |
175 | enable_if_t<__and_v<is_arithmetic<_Tp>, is_same<remove_cv_t<_Tp>, _Tp>, |
176 | __not_<is_same<_Tp, bool>>>, |
177 | _Tp> |
178 | midpoint(_Tp __a, _Tp __b) noexcept |
179 | { |
180 | if constexpr (is_integral_v<_Tp>) |
181 | { |
182 | using _Up = make_unsigned_t<_Tp>; |
183 | |
184 | int __k = 1; |
185 | _Up __m = __a; |
186 | _Up __M = __b; |
187 | if (__a > __b) |
188 | { |
189 | __k = -1; |
190 | __m = __b; |
191 | __M = __a; |
192 | } |
193 | return __a + __k * _Tp(_Up(__M - __m) / 2); |
194 | } |
195 | else // is_floating |
196 | { |
197 | constexpr _Tp __lo = numeric_limits<_Tp>::min() * 2; |
198 | constexpr _Tp __hi = numeric_limits<_Tp>::max() / 2; |
199 | const _Tp __abs_a = __a < 0 ? -__a : __a; |
200 | const _Tp __abs_b = __b < 0 ? -__b : __b; |
201 | if (__abs_a <= __hi && __abs_b <= __hi) [[likely]] |
202 | return (__a + __b) / 2; // always correctly rounded |
203 | if (__abs_a < __lo) // not safe to halve __a |
204 | return __a + __b/2; |
205 | if (__abs_b < __lo) // not safe to halve __b |
206 | return __a/2 + __b; |
207 | return __a/2 + __b/2; // otherwise correctly rounded |
208 | } |
209 | } |
210 | |
211 | template<typename _Tp> |
212 | constexpr |
213 | enable_if_t<__and_v<is_object<_Tp>, bool_constant<sizeof(_Tp) != 0>>, _Tp*> |
214 | midpoint(_Tp* __a, _Tp* __b) noexcept |
215 | { |
216 | return __a + (__b - __a) / 2; |
217 | } |
218 | _GLIBCXX_END_NAMESPACE_VERSION |
219 | } // namespace std |
220 | |
221 | #endif // C++20 |
222 | |
223 | #if __cplusplus > 201402L |
224 | #include <bits/stl_function.h> |
225 | |
226 | namespace std _GLIBCXX_VISIBILITY(default) |
227 | { |
228 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
229 | |
230 | /// @addtogroup numeric_ops |
231 | /// @{ |
232 | |
233 | /// @cond undocumented |
234 | template<typename _It, typename _Traits = iterator_traits<_It>, |
235 | typename _Cat = typename _Traits::iterator_category> |
236 | using __is_random_access_iter |
237 | = is_base_of<random_access_iterator_tag, _Cat>; |
238 | /// @endcond |
239 | |
240 | /** |
241 | * @brief Calculate reduction of values in a range. |
242 | * |
243 | * @param __first Start of range. |
244 | * @param __last End of range. |
245 | * @param __init Starting value to add other values to. |
246 | * @param __binary_op A binary function object. |
247 | * @return The final sum. |
248 | * |
249 | * Reduce the values in the range `[first,last)` using a binary operation. |
250 | * The initial value is `init`. The values are not necessarily processed |
251 | * in order. |
252 | * |
253 | * This algorithm is similar to `std::accumulate` but is not required to |
254 | * perform the operations in order from first to last. For operations |
255 | * that are commutative and associative the result will be the same as |
256 | * for `std::accumulate`, but for other operations (such as floating point |
257 | * arithmetic) the result can be different. |
258 | */ |
259 | template<typename _InputIterator, typename _Tp, typename _BinaryOperation> |
260 | _Tp |
261 | reduce(_InputIterator __first, _InputIterator __last, _Tp __init, |
262 | _BinaryOperation __binary_op) |
263 | { |
264 | using value_type = typename iterator_traits<_InputIterator>::value_type; |
265 | static_assert(is_invocable_r_v<_Tp, _BinaryOperation&, _Tp&, _Tp&>); |
266 | static_assert(is_convertible_v<value_type, _Tp>); |
267 | if constexpr (__is_random_access_iter<_InputIterator>::value) |
268 | { |
269 | while ((__last - __first) >= 4) |
270 | { |
271 | _Tp __v1 = __binary_op(__first[0], __first[1]); |
272 | _Tp __v2 = __binary_op(__first[2], __first[3]); |
273 | _Tp __v3 = __binary_op(__v1, __v2); |
274 | __init = __binary_op(__init, __v3); |
275 | __first += 4; |
276 | } |
277 | } |
278 | for (; __first != __last; ++__first) |
279 | __init = __binary_op(__init, *__first); |
280 | return __init; |
281 | } |
282 | |
283 | /** |
284 | * @brief Calculate reduction of values in a range. |
285 | * |
286 | * @param __first Start of range. |
287 | * @param __last End of range. |
288 | * @param __init Starting value to add other values to. |
289 | * @return The final sum. |
290 | * |
291 | * Reduce the values in the range `[first,last)` using addition. |
292 | * Equivalent to calling `std::reduce(first, last, init, std::plus<>())`. |
293 | */ |
294 | template<typename _InputIterator, typename _Tp> |
295 | inline _Tp |
296 | reduce(_InputIterator __first, _InputIterator __last, _Tp __init) |
297 | { return std::reduce(__first, __last, std::move(__init), plus<>()); } |
298 | |
299 | /** |
300 | * @brief Calculate reduction of values in a range. |
301 | * |
302 | * @param __first Start of range. |
303 | * @param __last End of range. |
304 | * @return The final sum. |
305 | * |
306 | * Reduce the values in the range `[first,last)` using addition, with |
307 | * an initial value of `T{}`, where `T` is the iterator's value type. |
308 | * Equivalent to calling `std::reduce(first, last, T{}, std::plus<>())`. |
309 | */ |
310 | template<typename _InputIterator> |
311 | inline typename iterator_traits<_InputIterator>::value_type |
312 | reduce(_InputIterator __first, _InputIterator __last) |
313 | { |
314 | using value_type = typename iterator_traits<_InputIterator>::value_type; |
315 | return std::reduce(__first, __last, value_type{}, plus<>()); |
316 | } |
317 | |
318 | /** |
319 | * @brief Combine elements from two ranges and reduce |
320 | * |
321 | * @param __first1 Start of first range. |
322 | * @param __last1 End of first range. |
323 | * @param __first2 Start of second range. |
324 | * @param __init Starting value to add other values to. |
325 | * @param __binary_op1 The function used to perform reduction. |
326 | * @param __binary_op2 The function used to combine values from the ranges. |
327 | * @return The final sum. |
328 | * |
329 | * Call `binary_op2(first1[n],first2[n])` for each `n` in `[0,last1-first1)` |
330 | * and then use `binary_op1` to reduce the values returned by `binary_op2` |
331 | * to a single value of type `T`. |
332 | * |
333 | * The range beginning at `first2` must contain at least `last1-first1` |
334 | * elements. |
335 | */ |
336 | template<typename _InputIterator1, typename _InputIterator2, typename _Tp, |
337 | typename _BinaryOperation1, typename _BinaryOperation2> |
338 | _Tp |
339 | transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, |
340 | _InputIterator2 __first2, _Tp __init, |
341 | _BinaryOperation1 __binary_op1, |
342 | _BinaryOperation2 __binary_op2) |
343 | { |
344 | if constexpr (__and_v<__is_random_access_iter<_InputIterator1>, |
345 | __is_random_access_iter<_InputIterator2>>) |
346 | { |
347 | while ((__last1 - __first1) >= 4) |
348 | { |
349 | _Tp __v1 = __binary_op1(__binary_op2(__first1[0], __first2[0]), |
350 | __binary_op2(__first1[1], __first2[1])); |
351 | _Tp __v2 = __binary_op1(__binary_op2(__first1[2], __first2[2]), |
352 | __binary_op2(__first1[3], __first2[3])); |
353 | _Tp __v3 = __binary_op1(__v1, __v2); |
354 | __init = __binary_op1(__init, __v3); |
355 | __first1 += 4; |
356 | __first2 += 4; |
357 | } |
358 | } |
359 | for (; __first1 != __last1; ++__first1, (void) ++__first2) |
360 | __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); |
361 | return __init; |
362 | } |
363 | |
364 | /** |
365 | * @brief Combine elements from two ranges and reduce |
366 | * |
367 | * @param __first1 Start of first range. |
368 | * @param __last1 End of first range. |
369 | * @param __first2 Start of second range. |
370 | * @param __init Starting value to add other values to. |
371 | * @return The final sum. |
372 | * |
373 | * Call `first1[n]*first2[n]` for each `n` in `[0,last1-first1)` and then |
374 | * use addition to sum those products to a single value of type `T`. |
375 | * |
376 | * The range beginning at `first2` must contain at least `last1-first1` |
377 | * elements. |
378 | */ |
379 | template<typename _InputIterator1, typename _InputIterator2, typename _Tp> |
380 | inline _Tp |
381 | transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, |
382 | _InputIterator2 __first2, _Tp __init) |
383 | { |
384 | return std::transform_reduce(__first1, __last1, __first2, |
385 | std::move(__init), |
386 | plus<>(), multiplies<>()); |
387 | } |
388 | |
389 | /** |
390 | * @brief Transform the elements of a range and reduce |
391 | * |
392 | * @param __first Start of range. |
393 | * @param __last End of range. |
394 | * @param __init Starting value to add other values to. |
395 | * @param __binary_op The function used to perform reduction. |
396 | * @param __unary_op The function used to transform values from the range. |
397 | * @return The final sum. |
398 | * |
399 | * Call `unary_op(first[n])` for each `n` in `[0,last-first)` and then |
400 | * use `binary_op` to reduce the values returned by `unary_op` |
401 | * to a single value of type `T`. |
402 | */ |
403 | template<typename _InputIterator, typename _Tp, |
404 | typename _BinaryOperation, typename _UnaryOperation> |
405 | _Tp |
406 | transform_reduce(_InputIterator __first, _InputIterator __last, _Tp __init, |
407 | _BinaryOperation __binary_op, _UnaryOperation __unary_op) |
408 | { |
409 | if constexpr (__is_random_access_iter<_InputIterator>::value) |
410 | { |
411 | while ((__last - __first) >= 4) |
412 | { |
413 | _Tp __v1 = __binary_op(__unary_op(__first[0]), |
414 | __unary_op(__first[1])); |
415 | _Tp __v2 = __binary_op(__unary_op(__first[2]), |
416 | __unary_op(__first[3])); |
417 | _Tp __v3 = __binary_op(__v1, __v2); |
418 | __init = __binary_op(__init, __v3); |
419 | __first += 4; |
420 | } |
421 | } |
422 | for (; __first != __last; ++__first) |
423 | __init = __binary_op(__init, __unary_op(*__first)); |
424 | return __init; |
425 | } |
426 | |
427 | /** @brief Output the cumulative sum of one range to a second range |
428 | * |
429 | * @param __first Start of input range. |
430 | * @param __last End of input range. |
431 | * @param __result Start of output range. |
432 | * @param __init Initial value. |
433 | * @param __binary_op Function to perform summation. |
434 | * @return The end of the output range. |
435 | * |
436 | * Write the cumulative sum (aka prefix sum, aka scan) of the input range |
437 | * to the output range. Each element of the output range contains the |
438 | * running total of all earlier elements (and the initial value), |
439 | * using `binary_op` for summation. |
440 | * |
441 | * This function generates an "exclusive" scan, meaning the Nth element |
442 | * of the output range is the sum of the first N-1 input elements, |
443 | * so the Nth input element is not included. |
444 | */ |
445 | template<typename _InputIterator, typename _OutputIterator, typename _Tp, |
446 | typename _BinaryOperation> |
447 | _OutputIterator |
448 | exclusive_scan(_InputIterator __first, _InputIterator __last, |
449 | _OutputIterator __result, _Tp __init, |
450 | _BinaryOperation __binary_op) |
451 | { |
452 | while (__first != __last) |
453 | { |
454 | auto __v = __init; |
455 | __init = __binary_op(__init, *__first); |
456 | ++__first; |
457 | *__result++ = std::move(__v); |
458 | } |
459 | return __result; |
460 | } |
461 | |
462 | /** @brief Output the cumulative sum of one range to a second range |
463 | * |
464 | * @param __first Start of input range. |
465 | * @param __last End of input range. |
466 | * @param __result Start of output range. |
467 | * @param __init Initial value. |
468 | * @return The end of the output range. |
469 | * |
470 | * Write the cumulative sum (aka prefix sum, aka scan) of the input range |
471 | * to the output range. Each element of the output range contains the |
472 | * running total of all earlier elements (and the initial value), |
473 | * using `std::plus<>` for summation. |
474 | * |
475 | * This function generates an "exclusive" scan, meaning the Nth element |
476 | * of the output range is the sum of the first N-1 input elements, |
477 | * so the Nth input element is not included. |
478 | */ |
479 | template<typename _InputIterator, typename _OutputIterator, typename _Tp> |
480 | inline _OutputIterator |
481 | exclusive_scan(_InputIterator __first, _InputIterator __last, |
482 | _OutputIterator __result, _Tp __init) |
483 | { |
484 | return std::exclusive_scan(__first, __last, __result, std::move(__init), |
485 | plus<>()); |
486 | } |
487 | |
488 | /** @brief Output the cumulative sum of one range to a second range |
489 | * |
490 | * @param __first Start of input range. |
491 | * @param __last End of input range. |
492 | * @param __result Start of output range. |
493 | * @param __binary_op Function to perform summation. |
494 | * @param __init Initial value. |
495 | * @return The end of the output range. |
496 | * |
497 | * Write the cumulative sum (aka prefix sum, aka scan) of the input range |
498 | * to the output range. Each element of the output range contains the |
499 | * running total of all earlier elements (and the initial value), |
500 | * using `binary_op` for summation. |
501 | * |
502 | * This function generates an "inclusive" scan, meaning the Nth element |
503 | * of the output range is the sum of the first N input elements, |
504 | * so the Nth input element is included. |
505 | */ |
506 | template<typename _InputIterator, typename _OutputIterator, |
507 | typename _BinaryOperation, typename _Tp> |
508 | _OutputIterator |
509 | inclusive_scan(_InputIterator __first, _InputIterator __last, |
510 | _OutputIterator __result, _BinaryOperation __binary_op, |
511 | _Tp __init) |
512 | { |
513 | for (; __first != __last; ++__first) |
514 | *__result++ = __init = __binary_op(__init, *__first); |
515 | return __result; |
516 | } |
517 | |
518 | /** @brief Output the cumulative sum of one range to a second range |
519 | * |
520 | * @param __first Start of input range. |
521 | * @param __last End of input range. |
522 | * @param __result Start of output range. |
523 | * @param __binary_op Function to perform summation. |
524 | * @return The end of the output range. |
525 | * |
526 | * Write the cumulative sum (aka prefix sum, aka scan) of the input range |
527 | * to the output range. Each element of the output range contains the |
528 | * running total of all earlier elements, using `binary_op` for summation. |
529 | * |
530 | * This function generates an "inclusive" scan, meaning the Nth element |
531 | * of the output range is the sum of the first N input elements, |
532 | * so the Nth input element is included. |
533 | */ |
534 | template<typename _InputIterator, typename _OutputIterator, |
535 | typename _BinaryOperation> |
536 | _OutputIterator |
537 | inclusive_scan(_InputIterator __first, _InputIterator __last, |
538 | _OutputIterator __result, _BinaryOperation __binary_op) |
539 | { |
540 | if (__first != __last) |
541 | { |
542 | auto __init = *__first; |
543 | *__result++ = __init; |
544 | ++__first; |
545 | if (__first != __last) |
546 | __result = std::inclusive_scan(__first, __last, __result, |
547 | __binary_op, std::move(__init)); |
548 | } |
549 | return __result; |
550 | } |
551 | |
552 | /** @brief Output the cumulative sum of one range to a second range |
553 | * |
554 | * @param __first Start of input range. |
555 | * @param __last End of input range. |
556 | * @param __result Start of output range. |
557 | * @return The end of the output range. |
558 | * |
559 | * Write the cumulative sum (aka prefix sum, aka scan) of the input range |
560 | * to the output range. Each element of the output range contains the |
561 | * running total of all earlier elements, using `std::plus<>` for summation. |
562 | * |
563 | * This function generates an "inclusive" scan, meaning the Nth element |
564 | * of the output range is the sum of the first N input elements, |
565 | * so the Nth input element is included. |
566 | */ |
567 | template<typename _InputIterator, typename _OutputIterator> |
568 | inline _OutputIterator |
569 | inclusive_scan(_InputIterator __first, _InputIterator __last, |
570 | _OutputIterator __result) |
571 | { return std::inclusive_scan(__first, __last, __result, plus<>()); } |
572 | |
573 | /** @brief Output the cumulative sum of one range to a second range |
574 | * |
575 | * @param __first Start of input range. |
576 | * @param __last End of input range. |
577 | * @param __result Start of output range. |
578 | * @param __init Initial value. |
579 | * @param __binary_op Function to perform summation. |
580 | * @param __unary_op Function to transform elements of the input range. |
581 | * @return The end of the output range. |
582 | * |
583 | * Write the cumulative sum (aka prefix sum, aka scan) of the input range |
584 | * to the output range. Each element of the output range contains the |
585 | * running total of all earlier elements (and the initial value), |
586 | * using `__unary_op` to transform the input elements |
587 | * and using `__binary_op` for summation. |
588 | * |
589 | * This function generates an "exclusive" scan, meaning the Nth element |
590 | * of the output range is the sum of the first N-1 input elements, |
591 | * so the Nth input element is not included. |
592 | */ |
593 | template<typename _InputIterator, typename _OutputIterator, typename _Tp, |
594 | typename _BinaryOperation, typename _UnaryOperation> |
595 | _OutputIterator |
596 | transform_exclusive_scan(_InputIterator __first, _InputIterator __last, |
597 | _OutputIterator __result, _Tp __init, |
598 | _BinaryOperation __binary_op, |
599 | _UnaryOperation __unary_op) |
600 | { |
601 | while (__first != __last) |
602 | { |
603 | auto __v = __init; |
604 | __init = __binary_op(__init, __unary_op(*__first)); |
605 | ++__first; |
606 | *__result++ = std::move(__v); |
607 | } |
608 | return __result; |
609 | } |
610 | |
611 | /** @brief Output the cumulative sum of one range to a second range |
612 | * |
613 | * @param __first Start of input range. |
614 | * @param __last End of input range. |
615 | * @param __result Start of output range. |
616 | * @param __binary_op Function to perform summation. |
617 | * @param __unary_op Function to transform elements of the input range. |
618 | * @param __init Initial value. |
619 | * @return The end of the output range. |
620 | * |
621 | * Write the cumulative sum (aka prefix sum, aka scan) of the input range |
622 | * to the output range. Each element of the output range contains the |
623 | * running total of all earlier elements (and the initial value), |
624 | * using `__unary_op` to transform the input elements |
625 | * and using `__binary_op` for summation. |
626 | * |
627 | * This function generates an "inclusive" scan, meaning the Nth element |
628 | * of the output range is the sum of the first N input elements, |
629 | * so the Nth input element is included. |
630 | */ |
631 | template<typename _InputIterator, typename _OutputIterator, |
632 | typename _BinaryOperation, typename _UnaryOperation, typename _Tp> |
633 | _OutputIterator |
634 | transform_inclusive_scan(_InputIterator __first, _InputIterator __last, |
635 | _OutputIterator __result, |
636 | _BinaryOperation __binary_op, |
637 | _UnaryOperation __unary_op, |
638 | _Tp __init) |
639 | { |
640 | for (; __first != __last; ++__first) |
641 | *__result++ = __init = __binary_op(__init, __unary_op(*__first)); |
642 | return __result; |
643 | } |
644 | |
645 | /** @brief Output the cumulative sum of one range to a second range |
646 | * |
647 | * @param __first Start of input range. |
648 | * @param __last End of input range. |
649 | * @param __result Start of output range. |
650 | * @param __binary_op Function to perform summation. |
651 | * @param __unary_op Function to transform elements of the input range. |
652 | * @return The end of the output range. |
653 | * |
654 | * Write the cumulative sum (aka prefix sum, aka scan) of the input range |
655 | * to the output range. Each element of the output range contains the |
656 | * running total of all earlier elements, |
657 | * using `__unary_op` to transform the input elements |
658 | * and using `__binary_op` for summation. |
659 | * |
660 | * This function generates an "inclusive" scan, meaning the Nth element |
661 | * of the output range is the sum of the first N input elements, |
662 | * so the Nth input element is included. |
663 | */ |
664 | template<typename _InputIterator, typename _OutputIterator, |
665 | typename _BinaryOperation, typename _UnaryOperation> |
666 | _OutputIterator |
667 | transform_inclusive_scan(_InputIterator __first, _InputIterator __last, |
668 | _OutputIterator __result, |
669 | _BinaryOperation __binary_op, |
670 | _UnaryOperation __unary_op) |
671 | { |
672 | if (__first != __last) |
673 | { |
674 | auto __init = __unary_op(*__first); |
675 | *__result++ = __init; |
676 | ++__first; |
677 | if (__first != __last) |
678 | __result = std::transform_inclusive_scan(__first, __last, __result, |
679 | __binary_op, __unary_op, |
680 | std::move(__init)); |
681 | } |
682 | return __result; |
683 | } |
684 | |
685 | /// @} group numeric_ops |
686 | |
687 | _GLIBCXX_END_NAMESPACE_VERSION |
688 | } // namespace std |
689 | |
690 | // Parallel STL algorithms |
691 | # if __PSTL_EXECUTION_POLICIES_DEFINED |
692 | // If <execution> has already been included, pull in implementations |
693 | # include <pstl/glue_numeric_impl.h> |
694 | # else |
695 | // Otherwise just pull in forward declarations |
696 | # include <pstl/glue_numeric_defs.h> |
697 | # define __PSTL_NUMERIC_FORWARD_DECLARED 1 |
698 | # endif |
699 | |
700 | // Feature test macro for parallel algorithms |
701 | # define __cpp_lib_parallel_algorithm 201603L |
702 | #endif // C++17 |
703 | |
704 | #endif /* _GLIBCXX_NUMERIC */ |
705 | |