libstdc++-v3/include/std/numeric

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