// -*- C++ -*- // Copyright (C) 2001-2019 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 3, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // Under Section 7 of GPL version 3, you are granted additional // permissions described in the GCC Runtime Library Exception, version // 3.1, as published by the Free Software Foundation. // You should have received a copy of the GNU General Public License and // a copy of the GCC Runtime Library Exception along with this program; // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see // . /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * * Copyright (c) 1996,1997 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. */ /** @file include/numeric * This is a Standard C++ Library header. */ #ifndef _GLIBCXX_NUMERIC #define _GLIBCXX_NUMERIC 1 #pragma GCC system_header #include #include #include #ifdef _GLIBCXX_PARALLEL # include #endif /** * @defgroup numerics Numerics * * Components for performing numeric operations. Includes support for * complex number types, random number generation, numeric (n-at-a-time) * arrays, generalized numeric algorithms, and mathematical special functions. */ #if __cplusplus >= 201402L #include namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION namespace __detail { // std::abs is not constexpr and doesn't support unsigned integers. template constexpr enable_if_t<__and_, is_signed<_Tp>>::value, _Tp> __abs_integral(_Tp __val) { return __val < 0 ? -__val : __val; } template constexpr enable_if_t<__and_, is_unsigned<_Tp>>::value, _Tp> __abs_integral(_Tp __val) { return __val; } void __abs_integral(bool) = delete; template constexpr common_type_t<_Mn, _Nn> __gcd(_Mn __m, _Nn __n) { return __m == 0 ? __detail::__abs_integral(__n) : __n == 0 ? __detail::__abs_integral(__m) : __detail::__gcd(__n, __m % __n); } /// Least common multiple template constexpr common_type_t<_Mn, _Nn> __lcm(_Mn __m, _Nn __n) { return (__m != 0 && __n != 0) ? (__detail::__abs_integral(__m) / __detail::__gcd(__m, __n)) * __detail::__abs_integral(__n) : 0; } } // namespace __detail #if __cplusplus >= 201703L #define __cpp_lib_gcd_lcm 201606 // These were used in drafts of SD-6: #define __cpp_lib_gcd 201606 #define __cpp_lib_lcm 201606 /// Greatest common divisor template constexpr common_type_t<_Mn, _Nn> gcd(_Mn __m, _Nn __n) { static_assert(is_integral_v<_Mn>, "gcd arguments are integers"); static_assert(is_integral_v<_Nn>, "gcd arguments are integers"); static_assert(!is_same_v, bool>, "gcd arguments are not bools"); static_assert(!is_same_v, bool>, "gcd arguments are not bools"); return __detail::__gcd(__m, __n); } /// Least common multiple template constexpr common_type_t<_Mn, _Nn> lcm(_Mn __m, _Nn __n) { static_assert(is_integral_v<_Mn>, "lcm arguments are integers"); static_assert(is_integral_v<_Nn>, "lcm arguments are integers"); static_assert(!is_same_v, bool>, "lcm arguments are not bools"); static_assert(!is_same_v, bool>, "lcm arguments are not bools"); return __detail::__lcm(__m, __n); } #endif // C++17 _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // C++14 #if __cplusplus > 201703L #include namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION // midpoint # define __cpp_lib_interpolate 201902L template constexpr enable_if_t<__and_v, is_same, _Tp>, __not_>>, _Tp> midpoint(_Tp __a, _Tp __b) noexcept { if constexpr (is_integral_v<_Tp>) { using _Up = make_unsigned_t<_Tp>; int __k = 1; _Up __m = __a; _Up __M = __b; if (__a > __b) { __k = -1; __m = __b; __M = __a; } return __a + __k * _Tp(_Up(__M - __m) / 2); } else // is_floating { constexpr _Tp __lo = numeric_limits<_Tp>::min() * 2; constexpr _Tp __hi = numeric_limits<_Tp>::max() / 2; const _Tp __abs_a = __a < 0 ? -__a : __a; const _Tp __abs_b = __b < 0 ? -__b : __b; if (__abs_a <= __hi && __abs_b <= __hi) [[likely]] return (__a + __b) / 2; // always correctly rounded if (__abs_a < __lo) // not safe to halve __a return __a + __b/2; if (__abs_b < __lo) // not safe to halve __b return __a/2 + __b; return __a/2 + __b/2; // otherwise correctly rounded } } template constexpr enable_if_t<__and_v, bool_constant>, _Tp*> midpoint(_Tp* __a, _Tp* __b) noexcept { return __a + (__b - __a) / 2; } _GLIBCXX_END_NAMESPACE_VERSION } // namespace std #endif // C++20 #if __cplusplus > 201402L #include namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION /// @addtogroup numeric_ops /// @{ /// @cond undocumented template, typename _Cat = typename _Traits::iterator_category> using __is_random_access_iter = is_base_of; /// @endcond /** * @brief Calculate reduction of values in a range. * * @param __first Start of range. * @param __last End of range. * @param __init Starting value to add other values to. * @param __binary_op A binary function object. * @return The final sum. * * Reduce the values in the range `[first,last)` using a binary operation. * The initial value is `init`. The values are not necessarily processed * in order. * * This algorithm is similar to `std::accumulate` but is not required to * perform the operations in order from first to last. For operations * that are commutative and associative the result will be the same as * for `std::accumulate`, but for other operations (such as floating point * arithmetic) the result can be different. */ template _Tp reduce(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOperation __binary_op) { using value_type = typename iterator_traits<_InputIterator>::value_type; static_assert(is_invocable_r_v<_Tp, _BinaryOperation&, _Tp&, _Tp&>); static_assert(is_convertible_v); if constexpr (__is_random_access_iter<_InputIterator>::value) { while ((__last - __first) >= 4) { _Tp __v1 = __binary_op(__first[0], __first[1]); _Tp __v2 = __binary_op(__first[2], __first[3]); _Tp __v3 = __binary_op(__v1, __v2); __init = __binary_op(__init, __v3); __first += 4; } } for (; __first != __last; ++__first) __init = __binary_op(__init, *__first); return __init; } /** * @brief Calculate reduction of values in a range. * * @param __first Start of range. * @param __last End of range. * @param __init Starting value to add other values to. * @return The final sum. * * Reduce the values in the range `[first,last)` using addition. * Equivalent to calling `std::reduce(first, last, init, std::plus<>())`. */ template inline _Tp reduce(_InputIterator __first, _InputIterator __last, _Tp __init) { return std::reduce(__first, __last, std::move(__init), plus<>()); } /** * @brief Calculate reduction of values in a range. * * @param __first Start of range. * @param __last End of range. * @return The final sum. * * Reduce the values in the range `[first,last)` using addition, with * an initial value of `T{}`, where `T` is the iterator's value type. * Equivalent to calling `std::reduce(first, last, T{}, std::plus<>())`. */ template inline typename iterator_traits<_InputIterator>::value_type reduce(_InputIterator __first, _InputIterator __last) { using value_type = typename iterator_traits<_InputIterator>::value_type; return std::reduce(__first, __last, value_type{}, plus<>()); } /** * @brief Combine elements from two ranges and reduce * * @param __first1 Start of first range. * @param __last1 End of first range. * @param __first2 Start of second range. * @param __init Starting value to add other values to. * @param __binary_op1 The function used to perform reduction. * @param __binary_op2 The function used to combine values from the ranges. * @return The final sum. * * Call `binary_op2(first1[n],first2[n])` for each `n` in `[0,last1-first1)` * and then use `binary_op1` to reduce the values returned by `binary_op2` * to a single value of type `T`. * * The range beginning at `first2` must contain at least `last1-first1` * elements. */ template _Tp transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2) { if constexpr (__and_v<__is_random_access_iter<_InputIterator1>, __is_random_access_iter<_InputIterator2>>) { while ((__last1 - __first1) >= 4) { _Tp __v1 = __binary_op1(__binary_op2(__first1[0], __first2[0]), __binary_op2(__first1[1], __first2[1])); _Tp __v2 = __binary_op1(__binary_op2(__first1[2], __first2[2]), __binary_op2(__first1[3], __first2[3])); _Tp __v3 = __binary_op1(__v1, __v2); __init = __binary_op1(__init, __v3); __first1 += 4; __first2 += 4; } } for (; __first1 != __last1; ++__first1, (void) ++__first2) __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); return __init; } /** * @brief Combine elements from two ranges and reduce * * @param __first1 Start of first range. * @param __last1 End of first range. * @param __first2 Start of second range. * @param __init Starting value to add other values to. * @return The final sum. * * Call `first1[n]*first2[n]` for each `n` in `[0,last1-first1)` and then * use addition to sum those products to a single value of type `T`. * * The range beginning at `first2` must contain at least `last1-first1` * elements. */ template inline _Tp transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init) { return std::transform_reduce(__first1, __last1, __first2, std::move(__init), plus<>(), multiplies<>()); } /** * @brief Transform the elements of a range and reduce * * @param __first Start of range. * @param __last End of range. * @param __init Starting value to add other values to. * @param __binary_op The function used to perform reduction. * @param __unary_op The function used to transform values from the range. * @return The final sum. * * Call `unary_op(first[n])` for each `n` in `[0,last-first)` and then * use `binary_op` to reduce the values returned by `unary_op` * to a single value of type `T`. */ template _Tp transform_reduce(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __unary_op) { if constexpr (__is_random_access_iter<_InputIterator>::value) { while ((__last - __first) >= 4) { _Tp __v1 = __binary_op(__unary_op(__first[0]), __unary_op(__first[1])); _Tp __v2 = __binary_op(__unary_op(__first[2]), __unary_op(__first[3])); _Tp __v3 = __binary_op(__v1, __v2); __init = __binary_op(__init, __v3); __first += 4; } } for (; __first != __last; ++__first) __init = __binary_op(__init, __unary_op(*__first)); return __init; } /** @brief Output the cumulative sum of one range to a second range * * @param __first Start of input range. * @param __last End of input range. * @param __result Start of output range. * @param __init Initial value. * @param __binary_op Function to perform summation. * @return The end of the output range. * * Write the cumulative sum (aka prefix sum, aka scan) of the input range * to the output range. Each element of the output range contains the * running total of all earlier elements (and the initial value), * using `binary_op` for summation. * * This function generates an "exclusive" scan, meaning the Nth element * of the output range is the sum of the first N-1 input elements, * so the Nth input element is not included. */ template _OutputIterator exclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Tp __init, _BinaryOperation __binary_op) { while (__first != __last) { auto __v = __init; __init = __binary_op(__init, *__first); ++__first; *__result++ = std::move(__v); } return __result; } /** @brief Output the cumulative sum of one range to a second range * * @param __first Start of input range. * @param __last End of input range. * @param __result Start of output range. * @param __init Initial value. * @return The end of the output range. * * Write the cumulative sum (aka prefix sum, aka scan) of the input range * to the output range. Each element of the output range contains the * running total of all earlier elements (and the initial value), * using `std::plus<>` for summation. * * This function generates an "exclusive" scan, meaning the Nth element * of the output range is the sum of the first N-1 input elements, * so the Nth input element is not included. */ template inline _OutputIterator exclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Tp __init) { return std::exclusive_scan(__first, __last, __result, std::move(__init), plus<>()); } /** @brief Output the cumulative sum of one range to a second range * * @param __first Start of input range. * @param __last End of input range. * @param __result Start of output range. * @param __binary_op Function to perform summation. * @param __init Initial value. * @return The end of the output range. * * Write the cumulative sum (aka prefix sum, aka scan) of the input range * to the output range. Each element of the output range contains the * running total of all earlier elements (and the initial value), * using `binary_op` for summation. * * This function generates an "inclusive" scan, meaning the Nth element * of the output range is the sum of the first N input elements, * so the Nth input element is included. */ template _OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryOperation __binary_op, _Tp __init) { for (; __first != __last; ++__first) *__result++ = __init = __binary_op(__init, *__first); return __result; } /** @brief Output the cumulative sum of one range to a second range * * @param __first Start of input range. * @param __last End of input range. * @param __result Start of output range. * @param __binary_op Function to perform summation. * @return The end of the output range. * * Write the cumulative sum (aka prefix sum, aka scan) of the input range * to the output range. Each element of the output range contains the * running total of all earlier elements, using `binary_op` for summation. * * This function generates an "inclusive" scan, meaning the Nth element * of the output range is the sum of the first N input elements, * so the Nth input element is included. */ template _OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryOperation __binary_op) { if (__first != __last) { auto __init = *__first; *__result++ = __init; ++__first; if (__first != __last) __result = std::inclusive_scan(__first, __last, __result, __binary_op, std::move(__init)); } return __result; } /** @brief Output the cumulative sum of one range to a second range * * @param __first Start of input range. * @param __last End of input range. * @param __result Start of output range. * @return The end of the output range. * * Write the cumulative sum (aka prefix sum, aka scan) of the input range * to the output range. Each element of the output range contains the * running total of all earlier elements, using `std::plus<>` for summation. * * This function generates an "inclusive" scan, meaning the Nth element * of the output range is the sum of the first N input elements, * so the Nth input element is included. */ template inline _OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { return std::inclusive_scan(__first, __last, __result, plus<>()); } /** @brief Output the cumulative sum of one range to a second range * * @param __first Start of input range. * @param __last End of input range. * @param __result Start of output range. * @param __init Initial value. * @param __binary_op Function to perform summation. * @param __unary_op Function to transform elements of the input range. * @return The end of the output range. * * Write the cumulative sum (aka prefix sum, aka scan) of the input range * to the output range. Each element of the output range contains the * running total of all earlier elements (and the initial value), * using `__unary_op` to transform the input elements * and using `__binary_op` for summation. * * This function generates an "exclusive" scan, meaning the Nth element * of the output range is the sum of the first N-1 input elements, * so the Nth input element is not included. */ template _OutputIterator transform_exclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Tp __init, _BinaryOperation __binary_op, _UnaryOperation __unary_op) { while (__first != __last) { auto __v = __init; __init = __binary_op(__init, __unary_op(*__first)); ++__first; *__result++ = std::move(__v); } return __result; } /** @brief Output the cumulative sum of one range to a second range * * @param __first Start of input range. * @param __last End of input range. * @param __result Start of output range. * @param __binary_op Function to perform summation. * @param __unary_op Function to transform elements of the input range. * @param __init Initial value. * @return The end of the output range. * * Write the cumulative sum (aka prefix sum, aka scan) of the input range * to the output range. Each element of the output range contains the * running total of all earlier elements (and the initial value), * using `__unary_op` to transform the input elements * and using `__binary_op` for summation. * * This function generates an "inclusive" scan, meaning the Nth element * of the output range is the sum of the first N input elements, * so the Nth input element is included. */ template _OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryOperation __binary_op, _UnaryOperation __unary_op, _Tp __init) { for (; __first != __last; ++__first) *__result++ = __init = __binary_op(__init, __unary_op(*__first)); return __result; } /** @brief Output the cumulative sum of one range to a second range * * @param __first Start of input range. * @param __last End of input range. * @param __result Start of output range. * @param __binary_op Function to perform summation. * @param __unary_op Function to transform elements of the input range. * @return The end of the output range. * * Write the cumulative sum (aka prefix sum, aka scan) of the input range * to the output range. Each element of the output range contains the * running total of all earlier elements, * using `__unary_op` to transform the input elements * and using `__binary_op` for summation. * * This function generates an "inclusive" scan, meaning the Nth element * of the output range is the sum of the first N input elements, * so the Nth input element is included. */ template _OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryOperation __binary_op, _UnaryOperation __unary_op) { if (__first != __last) { auto __init = __unary_op(*__first); *__result++ = __init; ++__first; if (__first != __last) __result = std::transform_inclusive_scan(__first, __last, __result, __binary_op, __unary_op, std::move(__init)); } return __result; } // @} group numeric_ops _GLIBCXX_END_NAMESPACE_VERSION } // namespace std // Parallel STL algorithms # if __PSTL_EXECUTION_POLICIES_DEFINED // If has already been included, pull in implementations # include # else // Otherwise just pull in forward declarations # include # define __PSTL_NUMERIC_FORWARD_DECLARED 1 # endif // Feature test macro for parallel algorithms # define __cpp_lib_parallel_algorithm 201603L #endif // C++17 #endif /* _GLIBCXX_NUMERIC */