numeric 24 KB

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