10b57cec5SDimitry Andric// -*- C++ -*- 20b57cec5SDimitry Andric//===---------------------------- numeric ---------------------------------===// 30b57cec5SDimitry Andric// 40b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 50b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information. 60b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 70b57cec5SDimitry Andric// 80b57cec5SDimitry Andric//===----------------------------------------------------------------------===// 90b57cec5SDimitry Andric 100b57cec5SDimitry Andric#ifndef _LIBCPP_NUMERIC 110b57cec5SDimitry Andric#define _LIBCPP_NUMERIC 120b57cec5SDimitry Andric 130b57cec5SDimitry Andric/* 140b57cec5SDimitry Andric numeric synopsis 150b57cec5SDimitry Andric 160b57cec5SDimitry Andricnamespace std 170b57cec5SDimitry Andric{ 180b57cec5SDimitry Andric 190b57cec5SDimitry Andrictemplate <class InputIterator, class T> 200b57cec5SDimitry Andric T 210b57cec5SDimitry Andric accumulate(InputIterator first, InputIterator last, T init); 220b57cec5SDimitry Andric 230b57cec5SDimitry Andrictemplate <class InputIterator, class T, class BinaryOperation> 240b57cec5SDimitry Andric T 250b57cec5SDimitry Andric accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op); 260b57cec5SDimitry Andric 270b57cec5SDimitry Andrictemplate<class InputIterator> 280b57cec5SDimitry Andric typename iterator_traits<InputIterator>::value_type 290b57cec5SDimitry Andric reduce(InputIterator first, InputIterator last); // C++17 300b57cec5SDimitry Andric 310b57cec5SDimitry Andrictemplate<class InputIterator, class T> 320b57cec5SDimitry Andric T 330b57cec5SDimitry Andric reduce(InputIterator first, InputIterator last, T init); // C++17 340b57cec5SDimitry Andric 350b57cec5SDimitry Andrictemplate<class InputIterator, class T, class BinaryOperation> 360b57cec5SDimitry Andric T 370b57cec5SDimitry Andric reduce(InputIterator first, InputIterator last, T init, BinaryOperation binary_op); // C++17 380b57cec5SDimitry Andric 390b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class T> 400b57cec5SDimitry Andric T 410b57cec5SDimitry Andric inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); 420b57cec5SDimitry Andric 430b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2> 440b57cec5SDimitry Andric T 450b57cec5SDimitry Andric inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, 460b57cec5SDimitry Andric T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2); 470b57cec5SDimitry Andric 480b57cec5SDimitry Andric 490b57cec5SDimitry Andrictemplate<class InputIterator1, class InputIterator2, class T> 500b57cec5SDimitry Andric T 510b57cec5SDimitry Andric transform_reduce(InputIterator1 first1, InputIterator1 last1, 520b57cec5SDimitry Andric InputIterator2 first2, T init); // C++17 530b57cec5SDimitry Andric 540b57cec5SDimitry Andrictemplate<class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2> 550b57cec5SDimitry Andric T 560b57cec5SDimitry Andric transform_reduce(InputIterator1 first1, InputIterator1 last1, 570b57cec5SDimitry Andric InputIterator2 first2, T init, 580b57cec5SDimitry Andric BinaryOperation1 binary_op1, BinaryOperation2 binary_op2); // C++17 590b57cec5SDimitry Andric 600b57cec5SDimitry Andrictemplate<class InputIterator, class T, class BinaryOperation, class UnaryOperation> 610b57cec5SDimitry Andric T 620b57cec5SDimitry Andric transform_reduce(InputIterator first, InputIterator last, T init, 630b57cec5SDimitry Andric BinaryOperation binary_op, UnaryOperation unary_op); // C++17 640b57cec5SDimitry Andric 650b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator> 660b57cec5SDimitry Andric OutputIterator 670b57cec5SDimitry Andric partial_sum(InputIterator first, InputIterator last, OutputIterator result); 680b57cec5SDimitry Andric 690b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator, class BinaryOperation> 700b57cec5SDimitry Andric OutputIterator 710b57cec5SDimitry Andric partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); 720b57cec5SDimitry Andric 730b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, class T> 740b57cec5SDimitry Andric OutputIterator 750b57cec5SDimitry Andric exclusive_scan(InputIterator first, InputIterator last, 760b57cec5SDimitry Andric OutputIterator result, T init); // C++17 770b57cec5SDimitry Andric 780b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, class T, class BinaryOperation> 790b57cec5SDimitry Andric OutputIterator 800b57cec5SDimitry Andric exclusive_scan(InputIterator first, InputIterator last, 810b57cec5SDimitry Andric OutputIterator result, T init, BinaryOperation binary_op); // C++17 820b57cec5SDimitry Andric 830b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator> 840b57cec5SDimitry Andric OutputIterator 850b57cec5SDimitry Andric inclusive_scan(InputIterator first, InputIterator last, OutputIterator result); // C++17 860b57cec5SDimitry Andric 870b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, class BinaryOperation> 880b57cec5SDimitry Andric OutputIterator 890b57cec5SDimitry Andric inclusive_scan(InputIterator first, InputIterator last, 900b57cec5SDimitry Andric OutputIterator result, BinaryOperation binary_op); // C++17 910b57cec5SDimitry Andric 920b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, class BinaryOperation, class T> 930b57cec5SDimitry Andric OutputIterator 940b57cec5SDimitry Andric inclusive_scan(InputIterator first, InputIterator last, 950b57cec5SDimitry Andric OutputIterator result, BinaryOperation binary_op, T init); // C++17 960b57cec5SDimitry Andric 970b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, class T, 980b57cec5SDimitry Andric class BinaryOperation, class UnaryOperation> 990b57cec5SDimitry Andric OutputIterator 1000b57cec5SDimitry Andric transform_exclusive_scan(InputIterator first, InputIterator last, 1010b57cec5SDimitry Andric OutputIterator result, T init, 1020b57cec5SDimitry Andric BinaryOperation binary_op, UnaryOperation unary_op); // C++17 1030b57cec5SDimitry Andric 1040b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, 1050b57cec5SDimitry Andric class BinaryOperation, class UnaryOperation> 1060b57cec5SDimitry Andric OutputIterator 1070b57cec5SDimitry Andric transform_inclusive_scan(InputIterator first, InputIterator last, 1080b57cec5SDimitry Andric OutputIterator result, 1090b57cec5SDimitry Andric BinaryOperation binary_op, UnaryOperation unary_op); // C++17 1100b57cec5SDimitry Andric 1110b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, 1120b57cec5SDimitry Andric class BinaryOperation, class UnaryOperation, class T> 1130b57cec5SDimitry Andric OutputIterator 1140b57cec5SDimitry Andric transform_inclusive_scan(InputIterator first, InputIterator last, 1150b57cec5SDimitry Andric OutputIterator result, 1160b57cec5SDimitry Andric BinaryOperation binary_op, UnaryOperation unary_op, 1170b57cec5SDimitry Andric T init); // C++17 1180b57cec5SDimitry Andric 1190b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator> 1200b57cec5SDimitry Andric OutputIterator 1210b57cec5SDimitry Andric adjacent_difference(InputIterator first, InputIterator last, OutputIterator result); 1220b57cec5SDimitry Andric 1230b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator, class BinaryOperation> 1240b57cec5SDimitry Andric OutputIterator 1250b57cec5SDimitry Andric adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); 1260b57cec5SDimitry Andric 1270b57cec5SDimitry Andrictemplate <class ForwardIterator, class T> 1280b57cec5SDimitry Andric void iota(ForwardIterator first, ForwardIterator last, T value); 1290b57cec5SDimitry Andric 1300b57cec5SDimitry Andrictemplate <class M, class N> 1310b57cec5SDimitry Andric constexpr common_type_t<M,N> gcd(M m, N n); // C++17 1320b57cec5SDimitry Andric 1330b57cec5SDimitry Andrictemplate <class M, class N> 1340b57cec5SDimitry Andric constexpr common_type_t<M,N> lcm(M m, N n); // C++17 1350b57cec5SDimitry Andric 1360b57cec5SDimitry Andricinteger midpoint(integer a, integer b); // C++20 1370b57cec5SDimitry Andricpointer midpoint(pointer a, pointer b); // C++20 1380b57cec5SDimitry Andricfloating_point midpoint(floating_point a, floating_point b); // C++20 1390b57cec5SDimitry Andric 1400b57cec5SDimitry Andric} // std 1410b57cec5SDimitry Andric 1420b57cec5SDimitry Andric*/ 1430b57cec5SDimitry Andric 1440b57cec5SDimitry Andric#include <__config> 1450b57cec5SDimitry Andric#include <iterator> 1460b57cec5SDimitry Andric#include <limits> // for numeric_limits 1470b57cec5SDimitry Andric#include <functional> 1480b57cec5SDimitry Andric#include <cmath> // for isnormal 1490b57cec5SDimitry Andric#include <version> 1500b57cec5SDimitry Andric 1510b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 1520b57cec5SDimitry Andric#pragma GCC system_header 1530b57cec5SDimitry Andric#endif 1540b57cec5SDimitry Andric 1550b57cec5SDimitry Andric_LIBCPP_PUSH_MACROS 1560b57cec5SDimitry Andric#include <__undef_macros> 1570b57cec5SDimitry Andric 1580b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 1590b57cec5SDimitry Andric 1600b57cec5SDimitry Andrictemplate <class _InputIterator, class _Tp> 1610b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 1620b57cec5SDimitry Andric_Tp 1630b57cec5SDimitry Andricaccumulate(_InputIterator __first, _InputIterator __last, _Tp __init) 1640b57cec5SDimitry Andric{ 1650b57cec5SDimitry Andric for (; __first != __last; ++__first) 1660b57cec5SDimitry Andric __init = __init + *__first; 1670b57cec5SDimitry Andric return __init; 1680b57cec5SDimitry Andric} 1690b57cec5SDimitry Andric 1700b57cec5SDimitry Andrictemplate <class _InputIterator, class _Tp, class _BinaryOperation> 1710b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 1720b57cec5SDimitry Andric_Tp 1730b57cec5SDimitry Andricaccumulate(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOperation __binary_op) 1740b57cec5SDimitry Andric{ 1750b57cec5SDimitry Andric for (; __first != __last; ++__first) 1760b57cec5SDimitry Andric __init = __binary_op(__init, *__first); 1770b57cec5SDimitry Andric return __init; 1780b57cec5SDimitry Andric} 1790b57cec5SDimitry Andric 1800b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 1810b57cec5SDimitry Andrictemplate <class _InputIterator, class _Tp, class _BinaryOp> 1820b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 1830b57cec5SDimitry Andric_Tp 1840b57cec5SDimitry Andricreduce(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOp __b) 1850b57cec5SDimitry Andric{ 1860b57cec5SDimitry Andric for (; __first != __last; ++__first) 1870b57cec5SDimitry Andric __init = __b(__init, *__first); 1880b57cec5SDimitry Andric return __init; 1890b57cec5SDimitry Andric} 1900b57cec5SDimitry Andric 1910b57cec5SDimitry Andrictemplate <class _InputIterator, class _Tp> 1920b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 1930b57cec5SDimitry Andric_Tp 1940b57cec5SDimitry Andricreduce(_InputIterator __first, _InputIterator __last, _Tp __init) 1950b57cec5SDimitry Andric{ 1960b57cec5SDimitry Andric return _VSTD::reduce(__first, __last, __init, _VSTD::plus<>()); 1970b57cec5SDimitry Andric} 1980b57cec5SDimitry Andric 1990b57cec5SDimitry Andrictemplate <class _InputIterator> 2000b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 2010b57cec5SDimitry Andrictypename iterator_traits<_InputIterator>::value_type 2020b57cec5SDimitry Andricreduce(_InputIterator __first, _InputIterator __last) 2030b57cec5SDimitry Andric{ 2040b57cec5SDimitry Andric return _VSTD::reduce(__first, __last, 2050b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type{}); 2060b57cec5SDimitry Andric} 2070b57cec5SDimitry Andric#endif 2080b57cec5SDimitry Andric 2090b57cec5SDimitry Andrictemplate <class _InputIterator1, class _InputIterator2, class _Tp> 2100b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 2110b57cec5SDimitry Andric_Tp 2120b57cec5SDimitry Andricinner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init) 2130b57cec5SDimitry Andric{ 2140b57cec5SDimitry Andric for (; __first1 != __last1; ++__first1, (void) ++__first2) 2150b57cec5SDimitry Andric __init = __init + *__first1 * *__first2; 2160b57cec5SDimitry Andric return __init; 2170b57cec5SDimitry Andric} 2180b57cec5SDimitry Andric 2190b57cec5SDimitry Andrictemplate <class _InputIterator1, class _InputIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2> 2200b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 2210b57cec5SDimitry Andric_Tp 2220b57cec5SDimitry Andricinner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, 2230b57cec5SDimitry Andric _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2) 2240b57cec5SDimitry Andric{ 2250b57cec5SDimitry Andric for (; __first1 != __last1; ++__first1, (void) ++__first2) 2260b57cec5SDimitry Andric __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); 2270b57cec5SDimitry Andric return __init; 2280b57cec5SDimitry Andric} 2290b57cec5SDimitry Andric 2300b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 2310b57cec5SDimitry Andrictemplate <class _InputIterator, class _Tp, class _BinaryOp, class _UnaryOp> 2320b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 2330b57cec5SDimitry Andric_Tp 2340b57cec5SDimitry Andrictransform_reduce(_InputIterator __first, _InputIterator __last, 2350b57cec5SDimitry Andric _Tp __init, _BinaryOp __b, _UnaryOp __u) 2360b57cec5SDimitry Andric{ 2370b57cec5SDimitry Andric for (; __first != __last; ++__first) 2380b57cec5SDimitry Andric __init = __b(__init, __u(*__first)); 2390b57cec5SDimitry Andric return __init; 2400b57cec5SDimitry Andric} 2410b57cec5SDimitry Andric 2420b57cec5SDimitry Andrictemplate <class _InputIterator1, class _InputIterator2, 2430b57cec5SDimitry Andric class _Tp, class _BinaryOp1, class _BinaryOp2> 2440b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 2450b57cec5SDimitry Andric_Tp 2460b57cec5SDimitry Andrictransform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, 2470b57cec5SDimitry Andric _InputIterator2 __first2, _Tp __init, _BinaryOp1 __b1, _BinaryOp2 __b2) 2480b57cec5SDimitry Andric{ 2490b57cec5SDimitry Andric for (; __first1 != __last1; ++__first1, (void) ++__first2) 2500b57cec5SDimitry Andric __init = __b1(__init, __b2(*__first1, *__first2)); 2510b57cec5SDimitry Andric return __init; 2520b57cec5SDimitry Andric} 2530b57cec5SDimitry Andric 2540b57cec5SDimitry Andrictemplate <class _InputIterator1, class _InputIterator2, class _Tp> 2550b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 2560b57cec5SDimitry Andric_Tp 2570b57cec5SDimitry Andrictransform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, 2580b57cec5SDimitry Andric _InputIterator2 __first2, _Tp __init) 2590b57cec5SDimitry Andric{ 2600b57cec5SDimitry Andric return _VSTD::transform_reduce(__first1, __last1, __first2, _VSTD::move(__init), 2610b57cec5SDimitry Andric _VSTD::plus<>(), _VSTD::multiplies<>()); 2620b57cec5SDimitry Andric} 2630b57cec5SDimitry Andric#endif 2640b57cec5SDimitry Andric 2650b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator> 2660b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 2670b57cec5SDimitry Andric_OutputIterator 2680b57cec5SDimitry Andricpartial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 2690b57cec5SDimitry Andric{ 2700b57cec5SDimitry Andric if (__first != __last) 2710b57cec5SDimitry Andric { 2720b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type __t(*__first); 2730b57cec5SDimitry Andric *__result = __t; 2740b57cec5SDimitry Andric for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 2750b57cec5SDimitry Andric { 2760b57cec5SDimitry Andric __t = __t + *__first; 2770b57cec5SDimitry Andric *__result = __t; 2780b57cec5SDimitry Andric } 2790b57cec5SDimitry Andric } 2800b57cec5SDimitry Andric return __result; 2810b57cec5SDimitry Andric} 2820b57cec5SDimitry Andric 2830b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _BinaryOperation> 2840b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 2850b57cec5SDimitry Andric_OutputIterator 2860b57cec5SDimitry Andricpartial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result, 2870b57cec5SDimitry Andric _BinaryOperation __binary_op) 2880b57cec5SDimitry Andric{ 2890b57cec5SDimitry Andric if (__first != __last) 2900b57cec5SDimitry Andric { 2910b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type __t(*__first); 2920b57cec5SDimitry Andric *__result = __t; 2930b57cec5SDimitry Andric for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 2940b57cec5SDimitry Andric { 2950b57cec5SDimitry Andric __t = __binary_op(__t, *__first); 2960b57cec5SDimitry Andric *__result = __t; 2970b57cec5SDimitry Andric } 2980b57cec5SDimitry Andric } 2990b57cec5SDimitry Andric return __result; 3000b57cec5SDimitry Andric} 3010b57cec5SDimitry Andric 3020b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 3030b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp> 3040b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 3050b57cec5SDimitry Andric_OutputIterator 3060b57cec5SDimitry Andricexclusive_scan(_InputIterator __first, _InputIterator __last, 3070b57cec5SDimitry Andric _OutputIterator __result, _Tp __init, _BinaryOp __b) 3080b57cec5SDimitry Andric{ 3090b57cec5SDimitry Andric if (__first != __last) 3100b57cec5SDimitry Andric { 3110b57cec5SDimitry Andric _Tp __saved = __init; 3120b57cec5SDimitry Andric do 3130b57cec5SDimitry Andric { 3140b57cec5SDimitry Andric __init = __b(__init, *__first); 3150b57cec5SDimitry Andric *__result = __saved; 3160b57cec5SDimitry Andric __saved = __init; 3170b57cec5SDimitry Andric ++__result; 3180b57cec5SDimitry Andric } while (++__first != __last); 3190b57cec5SDimitry Andric } 3200b57cec5SDimitry Andric return __result; 3210b57cec5SDimitry Andric} 3220b57cec5SDimitry Andric 3230b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _Tp> 3240b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 3250b57cec5SDimitry Andric_OutputIterator 3260b57cec5SDimitry Andricexclusive_scan(_InputIterator __first, _InputIterator __last, 3270b57cec5SDimitry Andric _OutputIterator __result, _Tp __init) 3280b57cec5SDimitry Andric{ 3290b57cec5SDimitry Andric return _VSTD::exclusive_scan(__first, __last, __result, __init, _VSTD::plus<>()); 3300b57cec5SDimitry Andric} 3310b57cec5SDimitry Andric 3320b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp> 3330b57cec5SDimitry Andric_OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, 3340b57cec5SDimitry Andric _OutputIterator __result, _BinaryOp __b, _Tp __init) 3350b57cec5SDimitry Andric{ 3360b57cec5SDimitry Andric for (; __first != __last; ++__first, (void) ++__result) { 3370b57cec5SDimitry Andric __init = __b(__init, *__first); 3380b57cec5SDimitry Andric *__result = __init; 3390b57cec5SDimitry Andric } 3400b57cec5SDimitry Andric return __result; 3410b57cec5SDimitry Andric} 3420b57cec5SDimitry Andric 3430b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _BinaryOp> 3440b57cec5SDimitry Andric_OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, 3450b57cec5SDimitry Andric _OutputIterator __result, _BinaryOp __b) 3460b57cec5SDimitry Andric{ 3470b57cec5SDimitry Andric if (__first != __last) { 3480b57cec5SDimitry Andric typename std::iterator_traits<_InputIterator>::value_type __init = *__first; 3490b57cec5SDimitry Andric *__result++ = __init; 3500b57cec5SDimitry Andric if (++__first != __last) 3510b57cec5SDimitry Andric return _VSTD::inclusive_scan(__first, __last, __result, __b, __init); 3520b57cec5SDimitry Andric } 3530b57cec5SDimitry Andric 3540b57cec5SDimitry Andric return __result; 3550b57cec5SDimitry Andric} 3560b57cec5SDimitry Andric 3570b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator> 3580b57cec5SDimitry Andric_OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, 3590b57cec5SDimitry Andric _OutputIterator __result) 3600b57cec5SDimitry Andric{ 3610b57cec5SDimitry Andric return _VSTD::inclusive_scan(__first, __last, __result, std::plus<>()); 3620b57cec5SDimitry Andric} 3630b57cec5SDimitry Andric 3640b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _Tp, 3650b57cec5SDimitry Andric class _BinaryOp, class _UnaryOp> 3660b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 3670b57cec5SDimitry Andric_OutputIterator 3680b57cec5SDimitry Andrictransform_exclusive_scan(_InputIterator __first, _InputIterator __last, 3690b57cec5SDimitry Andric _OutputIterator __result, _Tp __init, 3700b57cec5SDimitry Andric _BinaryOp __b, _UnaryOp __u) 3710b57cec5SDimitry Andric{ 3720b57cec5SDimitry Andric if (__first != __last) 3730b57cec5SDimitry Andric { 3740b57cec5SDimitry Andric _Tp __saved = __init; 3750b57cec5SDimitry Andric do 3760b57cec5SDimitry Andric { 3770b57cec5SDimitry Andric __init = __b(__init, __u(*__first)); 3780b57cec5SDimitry Andric *__result = __saved; 3790b57cec5SDimitry Andric __saved = __init; 3800b57cec5SDimitry Andric ++__result; 3810b57cec5SDimitry Andric } while (++__first != __last); 3820b57cec5SDimitry Andric } 3830b57cec5SDimitry Andric return __result; 3840b57cec5SDimitry Andric} 3850b57cec5SDimitry Andric 3860b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp, class _UnaryOp> 3870b57cec5SDimitry Andric_OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last, 3880b57cec5SDimitry Andric _OutputIterator __result, _BinaryOp __b, _UnaryOp __u, _Tp __init) 3890b57cec5SDimitry Andric{ 3900b57cec5SDimitry Andric for (; __first != __last; ++__first, (void) ++__result) { 3910b57cec5SDimitry Andric __init = __b(__init, __u(*__first)); 3920b57cec5SDimitry Andric *__result = __init; 3930b57cec5SDimitry Andric } 3940b57cec5SDimitry Andric 3950b57cec5SDimitry Andric return __result; 3960b57cec5SDimitry Andric} 3970b57cec5SDimitry Andric 3980b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _BinaryOp, class _UnaryOp> 3990b57cec5SDimitry Andric_OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last, 4000b57cec5SDimitry Andric _OutputIterator __result, _BinaryOp __b, _UnaryOp __u) 4010b57cec5SDimitry Andric{ 4020b57cec5SDimitry Andric if (__first != __last) { 4030b57cec5SDimitry Andric typename std::iterator_traits<_InputIterator>::value_type __init = __u(*__first); 4040b57cec5SDimitry Andric *__result++ = __init; 4050b57cec5SDimitry Andric if (++__first != __last) 4060b57cec5SDimitry Andric return _VSTD::transform_inclusive_scan(__first, __last, __result, __b, __u, __init); 4070b57cec5SDimitry Andric } 4080b57cec5SDimitry Andric 4090b57cec5SDimitry Andric return __result; 4100b57cec5SDimitry Andric} 4110b57cec5SDimitry Andric#endif 4120b57cec5SDimitry Andric 4130b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator> 4140b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 4150b57cec5SDimitry Andric_OutputIterator 4160b57cec5SDimitry Andricadjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 4170b57cec5SDimitry Andric{ 4180b57cec5SDimitry Andric if (__first != __last) 4190b57cec5SDimitry Andric { 4200b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type __t1(*__first); 4210b57cec5SDimitry Andric *__result = __t1; 4220b57cec5SDimitry Andric for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 4230b57cec5SDimitry Andric { 4240b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type __t2(*__first); 4250b57cec5SDimitry Andric *__result = __t2 - __t1; 4260b57cec5SDimitry Andric __t1 = _VSTD::move(__t2); 4270b57cec5SDimitry Andric } 4280b57cec5SDimitry Andric } 4290b57cec5SDimitry Andric return __result; 4300b57cec5SDimitry Andric} 4310b57cec5SDimitry Andric 4320b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _BinaryOperation> 4330b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 4340b57cec5SDimitry Andric_OutputIterator 4350b57cec5SDimitry Andricadjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result, 4360b57cec5SDimitry Andric _BinaryOperation __binary_op) 4370b57cec5SDimitry Andric{ 4380b57cec5SDimitry Andric if (__first != __last) 4390b57cec5SDimitry Andric { 4400b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type __t1(*__first); 4410b57cec5SDimitry Andric *__result = __t1; 4420b57cec5SDimitry Andric for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 4430b57cec5SDimitry Andric { 4440b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type __t2(*__first); 4450b57cec5SDimitry Andric *__result = __binary_op(__t2, __t1); 4460b57cec5SDimitry Andric __t1 = _VSTD::move(__t2); 4470b57cec5SDimitry Andric } 4480b57cec5SDimitry Andric } 4490b57cec5SDimitry Andric return __result; 4500b57cec5SDimitry Andric} 4510b57cec5SDimitry Andric 4520b57cec5SDimitry Andrictemplate <class _ForwardIterator, class _Tp> 4530b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 4540b57cec5SDimitry Andricvoid 4550b57cec5SDimitry Andriciota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value_) 4560b57cec5SDimitry Andric{ 4570b57cec5SDimitry Andric for (; __first != __last; ++__first, (void) ++__value_) 4580b57cec5SDimitry Andric *__first = __value_; 4590b57cec5SDimitry Andric} 4600b57cec5SDimitry Andric 4610b57cec5SDimitry Andric 4620b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 4630b57cec5SDimitry Andrictemplate <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __ct_abs; 4640b57cec5SDimitry Andric 4650b57cec5SDimitry Andrictemplate <typename _Result, typename _Source> 4660b57cec5SDimitry Andricstruct __ct_abs<_Result, _Source, true> { 4670b57cec5SDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 4680b57cec5SDimitry Andric _Result operator()(_Source __t) const noexcept 4690b57cec5SDimitry Andric { 4700b57cec5SDimitry Andric if (__t >= 0) return __t; 4710b57cec5SDimitry Andric if (__t == numeric_limits<_Source>::min()) return -static_cast<_Result>(__t); 4720b57cec5SDimitry Andric return -__t; 4730b57cec5SDimitry Andric } 4740b57cec5SDimitry Andric}; 4750b57cec5SDimitry Andric 4760b57cec5SDimitry Andrictemplate <typename _Result, typename _Source> 4770b57cec5SDimitry Andricstruct __ct_abs<_Result, _Source, false> { 4780b57cec5SDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 4790b57cec5SDimitry Andric _Result operator()(_Source __t) const noexcept { return __t; } 4800b57cec5SDimitry Andric}; 4810b57cec5SDimitry Andric 4820b57cec5SDimitry Andric 4830b57cec5SDimitry Andrictemplate<class _Tp> 4840b57cec5SDimitry Andric_LIBCPP_CONSTEXPR _LIBCPP_HIDDEN 4850b57cec5SDimitry Andric_Tp __gcd(_Tp __m, _Tp __n) 4860b57cec5SDimitry Andric{ 4870b57cec5SDimitry Andric static_assert((!is_signed<_Tp>::value), ""); 4880b57cec5SDimitry Andric return __n == 0 ? __m : _VSTD::__gcd<_Tp>(__n, __m % __n); 4890b57cec5SDimitry Andric} 4900b57cec5SDimitry Andric 4910b57cec5SDimitry Andric 4920b57cec5SDimitry Andrictemplate<class _Tp, class _Up> 4930b57cec5SDimitry Andric_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 4940b57cec5SDimitry Andriccommon_type_t<_Tp,_Up> 4950b57cec5SDimitry Andricgcd(_Tp __m, _Up __n) 4960b57cec5SDimitry Andric{ 4970b57cec5SDimitry Andric static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types"); 4980b57cec5SDimitry Andric static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to gcd cannot be bool" ); 4990b57cec5SDimitry Andric static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to gcd cannot be bool" ); 5000b57cec5SDimitry Andric using _Rp = common_type_t<_Tp,_Up>; 5010b57cec5SDimitry Andric using _Wp = make_unsigned_t<_Rp>; 5020b57cec5SDimitry Andric return static_cast<_Rp>(_VSTD::__gcd( 5030b57cec5SDimitry Andric static_cast<_Wp>(__ct_abs<_Rp, _Tp>()(__m)), 5040b57cec5SDimitry Andric static_cast<_Wp>(__ct_abs<_Rp, _Up>()(__n)))); 5050b57cec5SDimitry Andric} 5060b57cec5SDimitry Andric 5070b57cec5SDimitry Andrictemplate<class _Tp, class _Up> 5080b57cec5SDimitry Andric_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 5090b57cec5SDimitry Andriccommon_type_t<_Tp,_Up> 5100b57cec5SDimitry Andriclcm(_Tp __m, _Up __n) 5110b57cec5SDimitry Andric{ 5120b57cec5SDimitry Andric static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types"); 5130b57cec5SDimitry Andric static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to lcm cannot be bool" ); 5140b57cec5SDimitry Andric static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to lcm cannot be bool" ); 5150b57cec5SDimitry Andric if (__m == 0 || __n == 0) 5160b57cec5SDimitry Andric return 0; 5170b57cec5SDimitry Andric 5180b57cec5SDimitry Andric using _Rp = common_type_t<_Tp,_Up>; 5190b57cec5SDimitry Andric _Rp __val1 = __ct_abs<_Rp, _Tp>()(__m) / _VSTD::gcd(__m, __n); 5200b57cec5SDimitry Andric _Rp __val2 = __ct_abs<_Rp, _Up>()(__n); 5210b57cec5SDimitry Andric _LIBCPP_ASSERT((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm"); 5220b57cec5SDimitry Andric return __val1 * __val2; 5230b57cec5SDimitry Andric} 5240b57cec5SDimitry Andric 5250b57cec5SDimitry Andric#endif /* _LIBCPP_STD_VER > 14 */ 5260b57cec5SDimitry Andric 5270b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 17 5280b57cec5SDimitry Andrictemplate <class _Tp> 5290b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY constexpr 5300b57cec5SDimitry Andricenable_if_t<is_integral_v<_Tp> && !is_same_v<bool, _Tp> && !is_null_pointer_v<_Tp>, _Tp> 5310b57cec5SDimitry Andricmidpoint(_Tp __a, _Tp __b) noexcept 5320b57cec5SDimitry Andric_LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 5330b57cec5SDimitry Andric{ 5340b57cec5SDimitry Andric using _Up = std::make_unsigned_t<_Tp>; 5350b57cec5SDimitry Andric 5360b57cec5SDimitry Andric int __sign = 1; 5370b57cec5SDimitry Andric _Up __m = __a; 5380b57cec5SDimitry Andric _Up __M = __b; 5390b57cec5SDimitry Andric if (__a > __b) 5400b57cec5SDimitry Andric { 5410b57cec5SDimitry Andric __sign = -1; 5420b57cec5SDimitry Andric __m = __b; 5430b57cec5SDimitry Andric __M = __a; 5440b57cec5SDimitry Andric } 5450b57cec5SDimitry Andric return __a + __sign * _Tp(_Up(__M-__m) >> 1); 5460b57cec5SDimitry Andric} 5470b57cec5SDimitry Andric 5480b57cec5SDimitry Andric 5490b57cec5SDimitry Andrictemplate <class _TPtr> 5500b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY constexpr 5510b57cec5SDimitry Andricenable_if_t<is_pointer_v<_TPtr> 5520b57cec5SDimitry Andric && is_object_v<remove_pointer_t<_TPtr>> 5530b57cec5SDimitry Andric && ! is_void_v<remove_pointer_t<_TPtr>> 5540b57cec5SDimitry Andric && (sizeof(remove_pointer_t<_TPtr>) > 0), _TPtr> 5550b57cec5SDimitry Andricmidpoint(_TPtr __a, _TPtr __b) noexcept 5560b57cec5SDimitry Andric{ 5570b57cec5SDimitry Andric return __a + _VSTD::midpoint(ptrdiff_t(0), __b - __a); 5580b57cec5SDimitry Andric} 5590b57cec5SDimitry Andric 5600b57cec5SDimitry Andric 5610b57cec5SDimitry Andrictemplate <typename _Tp> 5620b57cec5SDimitry Andricconstexpr int __sign(_Tp __val) { 5630b57cec5SDimitry Andric return (_Tp(0) < __val) - (__val < _Tp(0)); 5640b57cec5SDimitry Andric} 5650b57cec5SDimitry Andric 5660b57cec5SDimitry Andrictemplate <typename _Fp> 5670b57cec5SDimitry Andricconstexpr _Fp __fp_abs(_Fp __f) { return __f >= 0 ? __f : -__f; } 5680b57cec5SDimitry Andric 5690b57cec5SDimitry Andrictemplate <class _Fp> 5700b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY constexpr 5710b57cec5SDimitry Andricenable_if_t<is_floating_point_v<_Fp>, _Fp> 5720b57cec5SDimitry Andricmidpoint(_Fp __a, _Fp __b) noexcept 5730b57cec5SDimitry Andric{ 5740b57cec5SDimitry Andric constexpr _Fp __lo = numeric_limits<_Fp>::min()*2; 5750b57cec5SDimitry Andric constexpr _Fp __hi = numeric_limits<_Fp>::max()/2; 5760b57cec5SDimitry Andric return __fp_abs(__a) <= __hi && __fp_abs(__b) <= __hi ? // typical case: overflow is impossible 5770b57cec5SDimitry Andric (__a + __b)/2 : // always correctly rounded 5780b57cec5SDimitry Andric __fp_abs(__a) < __lo ? __a + __b/2 : // not safe to halve a 5790b57cec5SDimitry Andric __fp_abs(__a) < __lo ? __a/2 + __b : // not safe to halve b 5800b57cec5SDimitry Andric __a/2 + __b/2; // otherwise correctly rounded 5810b57cec5SDimitry Andric} 5820b57cec5SDimitry Andric 5830b57cec5SDimitry Andric#endif // _LIBCPP_STD_VER > 17 5840b57cec5SDimitry Andric 5850b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 5860b57cec5SDimitry Andric 5870b57cec5SDimitry Andric_LIBCPP_POP_MACROS 5880b57cec5SDimitry Andric 589*e40139ffSDimitry Andric#if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17 590*e40139ffSDimitry Andric# include <__pstl_numeric> 591*e40139ffSDimitry Andric#endif 592*e40139ffSDimitry Andric 5930b57cec5SDimitry Andric#endif // _LIBCPP_NUMERIC 594