123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703 |
- #ifndef _GLIBCXX_NUMERIC
- #define _GLIBCXX_NUMERIC 1
- #pragma GCC system_header
- #include <bits/c++config.h>
- #include <bits/stl_iterator_base_types.h>
- #include <bits/stl_numeric.h>
- #ifdef _GLIBCXX_PARALLEL
- # include <parallel/numeric>
- #endif
- #if __cplusplus >= 201402L
- #include <type_traits>
- namespace std _GLIBCXX_VISIBILITY(default)
- {
- _GLIBCXX_BEGIN_NAMESPACE_VERSION
- namespace __detail
- {
-
- template<typename _Tp>
- constexpr
- enable_if_t<__and_<is_integral<_Tp>, is_signed<_Tp>>::value, _Tp>
- __abs_integral(_Tp __val)
- { return __val < 0 ? -__val : __val; }
- template<typename _Tp>
- constexpr
- enable_if_t<__and_<is_integral<_Tp>, is_unsigned<_Tp>>::value, _Tp>
- __abs_integral(_Tp __val)
- { return __val; }
- void __abs_integral(bool) = delete;
- template<typename _Mn, typename _Nn>
- 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);
- }
-
- template<typename _Mn, typename _Nn>
- 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;
- }
- }
- #if __cplusplus >= 201703L
- #define __cpp_lib_gcd_lcm 201606
- #define __cpp_lib_gcd 201606
- #define __cpp_lib_lcm 201606
-
- template<typename _Mn, typename _Nn>
- 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<remove_cv_t<_Mn>, bool>,
- "gcd arguments are not bools");
- static_assert(!is_same_v<remove_cv_t<_Nn>, bool>,
- "gcd arguments are not bools");
- return __detail::__gcd(__m, __n);
- }
-
- template<typename _Mn, typename _Nn>
- 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<remove_cv_t<_Mn>, bool>,
- "lcm arguments are not bools");
- static_assert(!is_same_v<remove_cv_t<_Nn>, bool>,
- "lcm arguments are not bools");
- return __detail::__lcm(__m, __n);
- }
- #endif
- _GLIBCXX_END_NAMESPACE_VERSION
- }
- #endif
- #if __cplusplus > 201703L
- #include <limits>
- namespace std _GLIBCXX_VISIBILITY(default)
- {
- _GLIBCXX_BEGIN_NAMESPACE_VERSION
-
- # define __cpp_lib_interpolate 201902L
- template<typename _Tp>
- constexpr
- enable_if_t<__and_v<is_arithmetic<_Tp>, is_same<remove_cv_t<_Tp>, _Tp>,
- __not_<is_same<_Tp, bool>>>,
- _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
- {
- 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;
- if (__abs_a < __lo)
- return __a + __b/2;
- if (__abs_b < __lo)
- return __a/2 + __b;
- return __a/2 + __b/2;
- }
- }
- template<typename _Tp>
- constexpr
- enable_if_t<__and_v<is_object<_Tp>, bool_constant<sizeof(_Tp) != 0>>, _Tp*>
- midpoint(_Tp* __a, _Tp* __b) noexcept
- {
- return __a + (__b - __a) / 2;
- }
- _GLIBCXX_END_NAMESPACE_VERSION
- }
- #endif
- #if __cplusplus > 201402L
- #include <bits/stl_function.h>
- namespace std _GLIBCXX_VISIBILITY(default)
- {
- _GLIBCXX_BEGIN_NAMESPACE_VERSION
-
-
-
- template<typename _It, typename _Traits = iterator_traits<_It>,
- typename _Cat = typename _Traits::iterator_category>
- using __is_random_access_iter
- = is_base_of<random_access_iterator_tag, _Cat>;
-
-
- template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
- _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<value_type, _Tp>);
- 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;
- }
-
- template<typename _InputIterator, typename _Tp>
- inline _Tp
- reduce(_InputIterator __first, _InputIterator __last, _Tp __init)
- { return std::reduce(__first, __last, std::move(__init), plus<>()); }
-
- template<typename _InputIterator>
- 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<>());
- }
-
- template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
- typename _BinaryOperation1, typename _BinaryOperation2>
- _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;
- }
-
- template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
- inline _Tp
- transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1,
- _InputIterator2 __first2, _Tp __init)
- {
- return std::transform_reduce(__first1, __last1, __first2,
- std::move(__init),
- plus<>(), multiplies<>());
- }
-
- template<typename _InputIterator, typename _Tp,
- typename _BinaryOperation, typename _UnaryOperation>
- _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;
- }
-
- template<typename _InputIterator, typename _OutputIterator, typename _Tp,
- typename _BinaryOperation>
- _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;
- }
-
- template<typename _InputIterator, typename _OutputIterator, typename _Tp>
- inline _OutputIterator
- exclusive_scan(_InputIterator __first, _InputIterator __last,
- _OutputIterator __result, _Tp __init)
- {
- return std::exclusive_scan(__first, __last, __result, std::move(__init),
- plus<>());
- }
-
- template<typename _InputIterator, typename _OutputIterator,
- typename _BinaryOperation, typename _Tp>
- _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;
- }
-
- template<typename _InputIterator, typename _OutputIterator,
- typename _BinaryOperation>
- _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;
- }
-
- template<typename _InputIterator, typename _OutputIterator>
- inline _OutputIterator
- inclusive_scan(_InputIterator __first, _InputIterator __last,
- _OutputIterator __result)
- { return std::inclusive_scan(__first, __last, __result, plus<>()); }
-
- template<typename _InputIterator, typename _OutputIterator, typename _Tp,
- typename _BinaryOperation, typename _UnaryOperation>
- _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;
- }
-
- template<typename _InputIterator, typename _OutputIterator,
- typename _BinaryOperation, typename _UnaryOperation, typename _Tp>
- _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;
- }
-
- template<typename _InputIterator, typename _OutputIterator,
- typename _BinaryOperation, typename _UnaryOperation>
- _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;
- }
-
- _GLIBCXX_END_NAMESPACE_VERSION
- }
- # if __PSTL_EXECUTION_POLICIES_DEFINED
- # include <pstl/glue_numeric_impl.h>
- # else
- # include <pstl/glue_numeric_defs.h>
- # define __PSTL_NUMERIC_FORWARD_DECLARED 1
- # endif
- # define __cpp_lib_parallel_algorithm 201603L
- #endif
- #endif
|