1*0b57cec5SDimitry Andric// -*- C++ -*- 2*0b57cec5SDimitry Andric//===---------------------------- numeric ---------------------------------===// 3*0b57cec5SDimitry Andric// 4*0b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5*0b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information. 6*0b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7*0b57cec5SDimitry Andric// 8*0b57cec5SDimitry Andric//===----------------------------------------------------------------------===// 9*0b57cec5SDimitry Andric 10*0b57cec5SDimitry Andric#ifndef _LIBCPP_NUMERIC 11*0b57cec5SDimitry Andric#define _LIBCPP_NUMERIC 12*0b57cec5SDimitry Andric 13*0b57cec5SDimitry Andric/* 14*0b57cec5SDimitry Andric numeric synopsis 15*0b57cec5SDimitry Andric 16*0b57cec5SDimitry Andricnamespace std 17*0b57cec5SDimitry Andric{ 18*0b57cec5SDimitry Andric 19*0b57cec5SDimitry Andrictemplate <class InputIterator, class T> 20*0b57cec5SDimitry Andric T 21*0b57cec5SDimitry Andric accumulate(InputIterator first, InputIterator last, T init); 22*0b57cec5SDimitry Andric 23*0b57cec5SDimitry Andrictemplate <class InputIterator, class T, class BinaryOperation> 24*0b57cec5SDimitry Andric T 25*0b57cec5SDimitry Andric accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op); 26*0b57cec5SDimitry Andric 27*0b57cec5SDimitry Andrictemplate<class InputIterator> 28*0b57cec5SDimitry Andric typename iterator_traits<InputIterator>::value_type 29*0b57cec5SDimitry Andric reduce(InputIterator first, InputIterator last); // C++17 30*0b57cec5SDimitry Andric 31*0b57cec5SDimitry Andrictemplate<class InputIterator, class T> 32*0b57cec5SDimitry Andric T 33*0b57cec5SDimitry Andric reduce(InputIterator first, InputIterator last, T init); // C++17 34*0b57cec5SDimitry Andric 35*0b57cec5SDimitry Andrictemplate<class InputIterator, class T, class BinaryOperation> 36*0b57cec5SDimitry Andric T 37*0b57cec5SDimitry Andric reduce(InputIterator first, InputIterator last, T init, BinaryOperation binary_op); // C++17 38*0b57cec5SDimitry Andric 39*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class T> 40*0b57cec5SDimitry Andric T 41*0b57cec5SDimitry Andric inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); 42*0b57cec5SDimitry Andric 43*0b57cec5SDimitry Andrictemplate <class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2> 44*0b57cec5SDimitry Andric T 45*0b57cec5SDimitry Andric inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, 46*0b57cec5SDimitry Andric T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2); 47*0b57cec5SDimitry Andric 48*0b57cec5SDimitry Andric 49*0b57cec5SDimitry Andrictemplate<class InputIterator1, class InputIterator2, class T> 50*0b57cec5SDimitry Andric T 51*0b57cec5SDimitry Andric transform_reduce(InputIterator1 first1, InputIterator1 last1, 52*0b57cec5SDimitry Andric InputIterator2 first2, T init); // C++17 53*0b57cec5SDimitry Andric 54*0b57cec5SDimitry Andrictemplate<class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2> 55*0b57cec5SDimitry Andric T 56*0b57cec5SDimitry Andric transform_reduce(InputIterator1 first1, InputIterator1 last1, 57*0b57cec5SDimitry Andric InputIterator2 first2, T init, 58*0b57cec5SDimitry Andric BinaryOperation1 binary_op1, BinaryOperation2 binary_op2); // C++17 59*0b57cec5SDimitry Andric 60*0b57cec5SDimitry Andrictemplate<class InputIterator, class T, class BinaryOperation, class UnaryOperation> 61*0b57cec5SDimitry Andric T 62*0b57cec5SDimitry Andric transform_reduce(InputIterator first, InputIterator last, T init, 63*0b57cec5SDimitry Andric BinaryOperation binary_op, UnaryOperation unary_op); // C++17 64*0b57cec5SDimitry Andric 65*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator> 66*0b57cec5SDimitry Andric OutputIterator 67*0b57cec5SDimitry Andric partial_sum(InputIterator first, InputIterator last, OutputIterator result); 68*0b57cec5SDimitry Andric 69*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator, class BinaryOperation> 70*0b57cec5SDimitry Andric OutputIterator 71*0b57cec5SDimitry Andric partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); 72*0b57cec5SDimitry Andric 73*0b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, class T> 74*0b57cec5SDimitry Andric OutputIterator 75*0b57cec5SDimitry Andric exclusive_scan(InputIterator first, InputIterator last, 76*0b57cec5SDimitry Andric OutputIterator result, T init); // C++17 77*0b57cec5SDimitry Andric 78*0b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, class T, class BinaryOperation> 79*0b57cec5SDimitry Andric OutputIterator 80*0b57cec5SDimitry Andric exclusive_scan(InputIterator first, InputIterator last, 81*0b57cec5SDimitry Andric OutputIterator result, T init, BinaryOperation binary_op); // C++17 82*0b57cec5SDimitry Andric 83*0b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator> 84*0b57cec5SDimitry Andric OutputIterator 85*0b57cec5SDimitry Andric inclusive_scan(InputIterator first, InputIterator last, OutputIterator result); // C++17 86*0b57cec5SDimitry Andric 87*0b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, class BinaryOperation> 88*0b57cec5SDimitry Andric OutputIterator 89*0b57cec5SDimitry Andric inclusive_scan(InputIterator first, InputIterator last, 90*0b57cec5SDimitry Andric OutputIterator result, BinaryOperation binary_op); // C++17 91*0b57cec5SDimitry Andric 92*0b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, class BinaryOperation, class T> 93*0b57cec5SDimitry Andric OutputIterator 94*0b57cec5SDimitry Andric inclusive_scan(InputIterator first, InputIterator last, 95*0b57cec5SDimitry Andric OutputIterator result, BinaryOperation binary_op, T init); // C++17 96*0b57cec5SDimitry Andric 97*0b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, class T, 98*0b57cec5SDimitry Andric class BinaryOperation, class UnaryOperation> 99*0b57cec5SDimitry Andric OutputIterator 100*0b57cec5SDimitry Andric transform_exclusive_scan(InputIterator first, InputIterator last, 101*0b57cec5SDimitry Andric OutputIterator result, T init, 102*0b57cec5SDimitry Andric BinaryOperation binary_op, UnaryOperation unary_op); // C++17 103*0b57cec5SDimitry Andric 104*0b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, 105*0b57cec5SDimitry Andric class BinaryOperation, class UnaryOperation> 106*0b57cec5SDimitry Andric OutputIterator 107*0b57cec5SDimitry Andric transform_inclusive_scan(InputIterator first, InputIterator last, 108*0b57cec5SDimitry Andric OutputIterator result, 109*0b57cec5SDimitry Andric BinaryOperation binary_op, UnaryOperation unary_op); // C++17 110*0b57cec5SDimitry Andric 111*0b57cec5SDimitry Andrictemplate<class InputIterator, class OutputIterator, 112*0b57cec5SDimitry Andric class BinaryOperation, class UnaryOperation, class T> 113*0b57cec5SDimitry Andric OutputIterator 114*0b57cec5SDimitry Andric transform_inclusive_scan(InputIterator first, InputIterator last, 115*0b57cec5SDimitry Andric OutputIterator result, 116*0b57cec5SDimitry Andric BinaryOperation binary_op, UnaryOperation unary_op, 117*0b57cec5SDimitry Andric T init); // C++17 118*0b57cec5SDimitry Andric 119*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator> 120*0b57cec5SDimitry Andric OutputIterator 121*0b57cec5SDimitry Andric adjacent_difference(InputIterator first, InputIterator last, OutputIterator result); 122*0b57cec5SDimitry Andric 123*0b57cec5SDimitry Andrictemplate <class InputIterator, class OutputIterator, class BinaryOperation> 124*0b57cec5SDimitry Andric OutputIterator 125*0b57cec5SDimitry Andric adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); 126*0b57cec5SDimitry Andric 127*0b57cec5SDimitry Andrictemplate <class ForwardIterator, class T> 128*0b57cec5SDimitry Andric void iota(ForwardIterator first, ForwardIterator last, T value); 129*0b57cec5SDimitry Andric 130*0b57cec5SDimitry Andrictemplate <class M, class N> 131*0b57cec5SDimitry Andric constexpr common_type_t<M,N> gcd(M m, N n); // C++17 132*0b57cec5SDimitry Andric 133*0b57cec5SDimitry Andrictemplate <class M, class N> 134*0b57cec5SDimitry Andric constexpr common_type_t<M,N> lcm(M m, N n); // C++17 135*0b57cec5SDimitry Andric 136*0b57cec5SDimitry Andricinteger midpoint(integer a, integer b); // C++20 137*0b57cec5SDimitry Andricpointer midpoint(pointer a, pointer b); // C++20 138*0b57cec5SDimitry Andricfloating_point midpoint(floating_point a, floating_point b); // C++20 139*0b57cec5SDimitry Andric 140*0b57cec5SDimitry Andric} // std 141*0b57cec5SDimitry Andric 142*0b57cec5SDimitry Andric*/ 143*0b57cec5SDimitry Andric 144*0b57cec5SDimitry Andric#include <__config> 145*0b57cec5SDimitry Andric#include <iterator> 146*0b57cec5SDimitry Andric#include <limits> // for numeric_limits 147*0b57cec5SDimitry Andric#include <functional> 148*0b57cec5SDimitry Andric#include <cmath> // for isnormal 149*0b57cec5SDimitry Andric#include <version> 150*0b57cec5SDimitry Andric 151*0b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 152*0b57cec5SDimitry Andric#pragma GCC system_header 153*0b57cec5SDimitry Andric#endif 154*0b57cec5SDimitry Andric 155*0b57cec5SDimitry Andric_LIBCPP_PUSH_MACROS 156*0b57cec5SDimitry Andric#include <__undef_macros> 157*0b57cec5SDimitry Andric 158*0b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 159*0b57cec5SDimitry Andric 160*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _Tp> 161*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 162*0b57cec5SDimitry Andric_Tp 163*0b57cec5SDimitry Andricaccumulate(_InputIterator __first, _InputIterator __last, _Tp __init) 164*0b57cec5SDimitry Andric{ 165*0b57cec5SDimitry Andric for (; __first != __last; ++__first) 166*0b57cec5SDimitry Andric __init = __init + *__first; 167*0b57cec5SDimitry Andric return __init; 168*0b57cec5SDimitry Andric} 169*0b57cec5SDimitry Andric 170*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _Tp, class _BinaryOperation> 171*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 172*0b57cec5SDimitry Andric_Tp 173*0b57cec5SDimitry Andricaccumulate(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOperation __binary_op) 174*0b57cec5SDimitry Andric{ 175*0b57cec5SDimitry Andric for (; __first != __last; ++__first) 176*0b57cec5SDimitry Andric __init = __binary_op(__init, *__first); 177*0b57cec5SDimitry Andric return __init; 178*0b57cec5SDimitry Andric} 179*0b57cec5SDimitry Andric 180*0b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 181*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _Tp, class _BinaryOp> 182*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 183*0b57cec5SDimitry Andric_Tp 184*0b57cec5SDimitry Andricreduce(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOp __b) 185*0b57cec5SDimitry Andric{ 186*0b57cec5SDimitry Andric for (; __first != __last; ++__first) 187*0b57cec5SDimitry Andric __init = __b(__init, *__first); 188*0b57cec5SDimitry Andric return __init; 189*0b57cec5SDimitry Andric} 190*0b57cec5SDimitry Andric 191*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _Tp> 192*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 193*0b57cec5SDimitry Andric_Tp 194*0b57cec5SDimitry Andricreduce(_InputIterator __first, _InputIterator __last, _Tp __init) 195*0b57cec5SDimitry Andric{ 196*0b57cec5SDimitry Andric return _VSTD::reduce(__first, __last, __init, _VSTD::plus<>()); 197*0b57cec5SDimitry Andric} 198*0b57cec5SDimitry Andric 199*0b57cec5SDimitry Andrictemplate <class _InputIterator> 200*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 201*0b57cec5SDimitry Andrictypename iterator_traits<_InputIterator>::value_type 202*0b57cec5SDimitry Andricreduce(_InputIterator __first, _InputIterator __last) 203*0b57cec5SDimitry Andric{ 204*0b57cec5SDimitry Andric return _VSTD::reduce(__first, __last, 205*0b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type{}); 206*0b57cec5SDimitry Andric} 207*0b57cec5SDimitry Andric#endif 208*0b57cec5SDimitry Andric 209*0b57cec5SDimitry Andrictemplate <class _InputIterator1, class _InputIterator2, class _Tp> 210*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 211*0b57cec5SDimitry Andric_Tp 212*0b57cec5SDimitry Andricinner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init) 213*0b57cec5SDimitry Andric{ 214*0b57cec5SDimitry Andric for (; __first1 != __last1; ++__first1, (void) ++__first2) 215*0b57cec5SDimitry Andric __init = __init + *__first1 * *__first2; 216*0b57cec5SDimitry Andric return __init; 217*0b57cec5SDimitry Andric} 218*0b57cec5SDimitry Andric 219*0b57cec5SDimitry Andrictemplate <class _InputIterator1, class _InputIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2> 220*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 221*0b57cec5SDimitry Andric_Tp 222*0b57cec5SDimitry Andricinner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, 223*0b57cec5SDimitry Andric _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2) 224*0b57cec5SDimitry Andric{ 225*0b57cec5SDimitry Andric for (; __first1 != __last1; ++__first1, (void) ++__first2) 226*0b57cec5SDimitry Andric __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); 227*0b57cec5SDimitry Andric return __init; 228*0b57cec5SDimitry Andric} 229*0b57cec5SDimitry Andric 230*0b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 231*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _Tp, class _BinaryOp, class _UnaryOp> 232*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 233*0b57cec5SDimitry Andric_Tp 234*0b57cec5SDimitry Andrictransform_reduce(_InputIterator __first, _InputIterator __last, 235*0b57cec5SDimitry Andric _Tp __init, _BinaryOp __b, _UnaryOp __u) 236*0b57cec5SDimitry Andric{ 237*0b57cec5SDimitry Andric for (; __first != __last; ++__first) 238*0b57cec5SDimitry Andric __init = __b(__init, __u(*__first)); 239*0b57cec5SDimitry Andric return __init; 240*0b57cec5SDimitry Andric} 241*0b57cec5SDimitry Andric 242*0b57cec5SDimitry Andrictemplate <class _InputIterator1, class _InputIterator2, 243*0b57cec5SDimitry Andric class _Tp, class _BinaryOp1, class _BinaryOp2> 244*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 245*0b57cec5SDimitry Andric_Tp 246*0b57cec5SDimitry Andrictransform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, 247*0b57cec5SDimitry Andric _InputIterator2 __first2, _Tp __init, _BinaryOp1 __b1, _BinaryOp2 __b2) 248*0b57cec5SDimitry Andric{ 249*0b57cec5SDimitry Andric for (; __first1 != __last1; ++__first1, (void) ++__first2) 250*0b57cec5SDimitry Andric __init = __b1(__init, __b2(*__first1, *__first2)); 251*0b57cec5SDimitry Andric return __init; 252*0b57cec5SDimitry Andric} 253*0b57cec5SDimitry Andric 254*0b57cec5SDimitry Andrictemplate <class _InputIterator1, class _InputIterator2, class _Tp> 255*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 256*0b57cec5SDimitry Andric_Tp 257*0b57cec5SDimitry Andrictransform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, 258*0b57cec5SDimitry Andric _InputIterator2 __first2, _Tp __init) 259*0b57cec5SDimitry Andric{ 260*0b57cec5SDimitry Andric return _VSTD::transform_reduce(__first1, __last1, __first2, _VSTD::move(__init), 261*0b57cec5SDimitry Andric _VSTD::plus<>(), _VSTD::multiplies<>()); 262*0b57cec5SDimitry Andric} 263*0b57cec5SDimitry Andric#endif 264*0b57cec5SDimitry Andric 265*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator> 266*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 267*0b57cec5SDimitry Andric_OutputIterator 268*0b57cec5SDimitry Andricpartial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 269*0b57cec5SDimitry Andric{ 270*0b57cec5SDimitry Andric if (__first != __last) 271*0b57cec5SDimitry Andric { 272*0b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type __t(*__first); 273*0b57cec5SDimitry Andric *__result = __t; 274*0b57cec5SDimitry Andric for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 275*0b57cec5SDimitry Andric { 276*0b57cec5SDimitry Andric __t = __t + *__first; 277*0b57cec5SDimitry Andric *__result = __t; 278*0b57cec5SDimitry Andric } 279*0b57cec5SDimitry Andric } 280*0b57cec5SDimitry Andric return __result; 281*0b57cec5SDimitry Andric} 282*0b57cec5SDimitry Andric 283*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _BinaryOperation> 284*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 285*0b57cec5SDimitry Andric_OutputIterator 286*0b57cec5SDimitry Andricpartial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result, 287*0b57cec5SDimitry Andric _BinaryOperation __binary_op) 288*0b57cec5SDimitry Andric{ 289*0b57cec5SDimitry Andric if (__first != __last) 290*0b57cec5SDimitry Andric { 291*0b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type __t(*__first); 292*0b57cec5SDimitry Andric *__result = __t; 293*0b57cec5SDimitry Andric for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 294*0b57cec5SDimitry Andric { 295*0b57cec5SDimitry Andric __t = __binary_op(__t, *__first); 296*0b57cec5SDimitry Andric *__result = __t; 297*0b57cec5SDimitry Andric } 298*0b57cec5SDimitry Andric } 299*0b57cec5SDimitry Andric return __result; 300*0b57cec5SDimitry Andric} 301*0b57cec5SDimitry Andric 302*0b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 303*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp> 304*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 305*0b57cec5SDimitry Andric_OutputIterator 306*0b57cec5SDimitry Andricexclusive_scan(_InputIterator __first, _InputIterator __last, 307*0b57cec5SDimitry Andric _OutputIterator __result, _Tp __init, _BinaryOp __b) 308*0b57cec5SDimitry Andric{ 309*0b57cec5SDimitry Andric if (__first != __last) 310*0b57cec5SDimitry Andric { 311*0b57cec5SDimitry Andric _Tp __saved = __init; 312*0b57cec5SDimitry Andric do 313*0b57cec5SDimitry Andric { 314*0b57cec5SDimitry Andric __init = __b(__init, *__first); 315*0b57cec5SDimitry Andric *__result = __saved; 316*0b57cec5SDimitry Andric __saved = __init; 317*0b57cec5SDimitry Andric ++__result; 318*0b57cec5SDimitry Andric } while (++__first != __last); 319*0b57cec5SDimitry Andric } 320*0b57cec5SDimitry Andric return __result; 321*0b57cec5SDimitry Andric} 322*0b57cec5SDimitry Andric 323*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _Tp> 324*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 325*0b57cec5SDimitry Andric_OutputIterator 326*0b57cec5SDimitry Andricexclusive_scan(_InputIterator __first, _InputIterator __last, 327*0b57cec5SDimitry Andric _OutputIterator __result, _Tp __init) 328*0b57cec5SDimitry Andric{ 329*0b57cec5SDimitry Andric return _VSTD::exclusive_scan(__first, __last, __result, __init, _VSTD::plus<>()); 330*0b57cec5SDimitry Andric} 331*0b57cec5SDimitry Andric 332*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp> 333*0b57cec5SDimitry Andric_OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, 334*0b57cec5SDimitry Andric _OutputIterator __result, _BinaryOp __b, _Tp __init) 335*0b57cec5SDimitry Andric{ 336*0b57cec5SDimitry Andric for (; __first != __last; ++__first, (void) ++__result) { 337*0b57cec5SDimitry Andric __init = __b(__init, *__first); 338*0b57cec5SDimitry Andric *__result = __init; 339*0b57cec5SDimitry Andric } 340*0b57cec5SDimitry Andric return __result; 341*0b57cec5SDimitry Andric} 342*0b57cec5SDimitry Andric 343*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _BinaryOp> 344*0b57cec5SDimitry Andric_OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, 345*0b57cec5SDimitry Andric _OutputIterator __result, _BinaryOp __b) 346*0b57cec5SDimitry Andric{ 347*0b57cec5SDimitry Andric if (__first != __last) { 348*0b57cec5SDimitry Andric typename std::iterator_traits<_InputIterator>::value_type __init = *__first; 349*0b57cec5SDimitry Andric *__result++ = __init; 350*0b57cec5SDimitry Andric if (++__first != __last) 351*0b57cec5SDimitry Andric return _VSTD::inclusive_scan(__first, __last, __result, __b, __init); 352*0b57cec5SDimitry Andric } 353*0b57cec5SDimitry Andric 354*0b57cec5SDimitry Andric return __result; 355*0b57cec5SDimitry Andric} 356*0b57cec5SDimitry Andric 357*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator> 358*0b57cec5SDimitry Andric_OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, 359*0b57cec5SDimitry Andric _OutputIterator __result) 360*0b57cec5SDimitry Andric{ 361*0b57cec5SDimitry Andric return _VSTD::inclusive_scan(__first, __last, __result, std::plus<>()); 362*0b57cec5SDimitry Andric} 363*0b57cec5SDimitry Andric 364*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _Tp, 365*0b57cec5SDimitry Andric class _BinaryOp, class _UnaryOp> 366*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 367*0b57cec5SDimitry Andric_OutputIterator 368*0b57cec5SDimitry Andrictransform_exclusive_scan(_InputIterator __first, _InputIterator __last, 369*0b57cec5SDimitry Andric _OutputIterator __result, _Tp __init, 370*0b57cec5SDimitry Andric _BinaryOp __b, _UnaryOp __u) 371*0b57cec5SDimitry Andric{ 372*0b57cec5SDimitry Andric if (__first != __last) 373*0b57cec5SDimitry Andric { 374*0b57cec5SDimitry Andric _Tp __saved = __init; 375*0b57cec5SDimitry Andric do 376*0b57cec5SDimitry Andric { 377*0b57cec5SDimitry Andric __init = __b(__init, __u(*__first)); 378*0b57cec5SDimitry Andric *__result = __saved; 379*0b57cec5SDimitry Andric __saved = __init; 380*0b57cec5SDimitry Andric ++__result; 381*0b57cec5SDimitry Andric } while (++__first != __last); 382*0b57cec5SDimitry Andric } 383*0b57cec5SDimitry Andric return __result; 384*0b57cec5SDimitry Andric} 385*0b57cec5SDimitry Andric 386*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp, class _UnaryOp> 387*0b57cec5SDimitry Andric_OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last, 388*0b57cec5SDimitry Andric _OutputIterator __result, _BinaryOp __b, _UnaryOp __u, _Tp __init) 389*0b57cec5SDimitry Andric{ 390*0b57cec5SDimitry Andric for (; __first != __last; ++__first, (void) ++__result) { 391*0b57cec5SDimitry Andric __init = __b(__init, __u(*__first)); 392*0b57cec5SDimitry Andric *__result = __init; 393*0b57cec5SDimitry Andric } 394*0b57cec5SDimitry Andric 395*0b57cec5SDimitry Andric return __result; 396*0b57cec5SDimitry Andric} 397*0b57cec5SDimitry Andric 398*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _BinaryOp, class _UnaryOp> 399*0b57cec5SDimitry Andric_OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last, 400*0b57cec5SDimitry Andric _OutputIterator __result, _BinaryOp __b, _UnaryOp __u) 401*0b57cec5SDimitry Andric{ 402*0b57cec5SDimitry Andric if (__first != __last) { 403*0b57cec5SDimitry Andric typename std::iterator_traits<_InputIterator>::value_type __init = __u(*__first); 404*0b57cec5SDimitry Andric *__result++ = __init; 405*0b57cec5SDimitry Andric if (++__first != __last) 406*0b57cec5SDimitry Andric return _VSTD::transform_inclusive_scan(__first, __last, __result, __b, __u, __init); 407*0b57cec5SDimitry Andric } 408*0b57cec5SDimitry Andric 409*0b57cec5SDimitry Andric return __result; 410*0b57cec5SDimitry Andric} 411*0b57cec5SDimitry Andric#endif 412*0b57cec5SDimitry Andric 413*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator> 414*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 415*0b57cec5SDimitry Andric_OutputIterator 416*0b57cec5SDimitry Andricadjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 417*0b57cec5SDimitry Andric{ 418*0b57cec5SDimitry Andric if (__first != __last) 419*0b57cec5SDimitry Andric { 420*0b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type __t1(*__first); 421*0b57cec5SDimitry Andric *__result = __t1; 422*0b57cec5SDimitry Andric for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 423*0b57cec5SDimitry Andric { 424*0b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type __t2(*__first); 425*0b57cec5SDimitry Andric *__result = __t2 - __t1; 426*0b57cec5SDimitry Andric __t1 = _VSTD::move(__t2); 427*0b57cec5SDimitry Andric } 428*0b57cec5SDimitry Andric } 429*0b57cec5SDimitry Andric return __result; 430*0b57cec5SDimitry Andric} 431*0b57cec5SDimitry Andric 432*0b57cec5SDimitry Andrictemplate <class _InputIterator, class _OutputIterator, class _BinaryOperation> 433*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 434*0b57cec5SDimitry Andric_OutputIterator 435*0b57cec5SDimitry Andricadjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result, 436*0b57cec5SDimitry Andric _BinaryOperation __binary_op) 437*0b57cec5SDimitry Andric{ 438*0b57cec5SDimitry Andric if (__first != __last) 439*0b57cec5SDimitry Andric { 440*0b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type __t1(*__first); 441*0b57cec5SDimitry Andric *__result = __t1; 442*0b57cec5SDimitry Andric for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 443*0b57cec5SDimitry Andric { 444*0b57cec5SDimitry Andric typename iterator_traits<_InputIterator>::value_type __t2(*__first); 445*0b57cec5SDimitry Andric *__result = __binary_op(__t2, __t1); 446*0b57cec5SDimitry Andric __t1 = _VSTD::move(__t2); 447*0b57cec5SDimitry Andric } 448*0b57cec5SDimitry Andric } 449*0b57cec5SDimitry Andric return __result; 450*0b57cec5SDimitry Andric} 451*0b57cec5SDimitry Andric 452*0b57cec5SDimitry Andrictemplate <class _ForwardIterator, class _Tp> 453*0b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 454*0b57cec5SDimitry Andricvoid 455*0b57cec5SDimitry Andriciota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value_) 456*0b57cec5SDimitry Andric{ 457*0b57cec5SDimitry Andric for (; __first != __last; ++__first, (void) ++__value_) 458*0b57cec5SDimitry Andric *__first = __value_; 459*0b57cec5SDimitry Andric} 460*0b57cec5SDimitry Andric 461*0b57cec5SDimitry Andric 462*0b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 463*0b57cec5SDimitry Andrictemplate <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __ct_abs; 464*0b57cec5SDimitry Andric 465*0b57cec5SDimitry Andrictemplate <typename _Result, typename _Source> 466*0b57cec5SDimitry Andricstruct __ct_abs<_Result, _Source, true> { 467*0b57cec5SDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 468*0b57cec5SDimitry Andric _Result operator()(_Source __t) const noexcept 469*0b57cec5SDimitry Andric { 470*0b57cec5SDimitry Andric if (__t >= 0) return __t; 471*0b57cec5SDimitry Andric if (__t == numeric_limits<_Source>::min()) return -static_cast<_Result>(__t); 472*0b57cec5SDimitry Andric return -__t; 473*0b57cec5SDimitry Andric } 474*0b57cec5SDimitry Andric}; 475*0b57cec5SDimitry Andric 476*0b57cec5SDimitry Andrictemplate <typename _Result, typename _Source> 477*0b57cec5SDimitry Andricstruct __ct_abs<_Result, _Source, false> { 478*0b57cec5SDimitry Andric _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 479*0b57cec5SDimitry Andric _Result operator()(_Source __t) const noexcept { return __t; } 480*0b57cec5SDimitry Andric}; 481*0b57cec5SDimitry Andric 482*0b57cec5SDimitry Andric 483*0b57cec5SDimitry Andrictemplate<class _Tp> 484*0b57cec5SDimitry Andric_LIBCPP_CONSTEXPR _LIBCPP_HIDDEN 485*0b57cec5SDimitry Andric_Tp __gcd(_Tp __m, _Tp __n) 486*0b57cec5SDimitry Andric{ 487*0b57cec5SDimitry Andric static_assert((!is_signed<_Tp>::value), ""); 488*0b57cec5SDimitry Andric return __n == 0 ? __m : _VSTD::__gcd<_Tp>(__n, __m % __n); 489*0b57cec5SDimitry Andric} 490*0b57cec5SDimitry Andric 491*0b57cec5SDimitry Andric 492*0b57cec5SDimitry Andrictemplate<class _Tp, class _Up> 493*0b57cec5SDimitry Andric_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 494*0b57cec5SDimitry Andriccommon_type_t<_Tp,_Up> 495*0b57cec5SDimitry Andricgcd(_Tp __m, _Up __n) 496*0b57cec5SDimitry Andric{ 497*0b57cec5SDimitry Andric static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types"); 498*0b57cec5SDimitry Andric static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to gcd cannot be bool" ); 499*0b57cec5SDimitry Andric static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to gcd cannot be bool" ); 500*0b57cec5SDimitry Andric using _Rp = common_type_t<_Tp,_Up>; 501*0b57cec5SDimitry Andric using _Wp = make_unsigned_t<_Rp>; 502*0b57cec5SDimitry Andric return static_cast<_Rp>(_VSTD::__gcd( 503*0b57cec5SDimitry Andric static_cast<_Wp>(__ct_abs<_Rp, _Tp>()(__m)), 504*0b57cec5SDimitry Andric static_cast<_Wp>(__ct_abs<_Rp, _Up>()(__n)))); 505*0b57cec5SDimitry Andric} 506*0b57cec5SDimitry Andric 507*0b57cec5SDimitry Andrictemplate<class _Tp, class _Up> 508*0b57cec5SDimitry Andric_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 509*0b57cec5SDimitry Andriccommon_type_t<_Tp,_Up> 510*0b57cec5SDimitry Andriclcm(_Tp __m, _Up __n) 511*0b57cec5SDimitry Andric{ 512*0b57cec5SDimitry Andric static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types"); 513*0b57cec5SDimitry Andric static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to lcm cannot be bool" ); 514*0b57cec5SDimitry Andric static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to lcm cannot be bool" ); 515*0b57cec5SDimitry Andric if (__m == 0 || __n == 0) 516*0b57cec5SDimitry Andric return 0; 517*0b57cec5SDimitry Andric 518*0b57cec5SDimitry Andric using _Rp = common_type_t<_Tp,_Up>; 519*0b57cec5SDimitry Andric _Rp __val1 = __ct_abs<_Rp, _Tp>()(__m) / _VSTD::gcd(__m, __n); 520*0b57cec5SDimitry Andric _Rp __val2 = __ct_abs<_Rp, _Up>()(__n); 521*0b57cec5SDimitry Andric _LIBCPP_ASSERT((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm"); 522*0b57cec5SDimitry Andric return __val1 * __val2; 523*0b57cec5SDimitry Andric} 524*0b57cec5SDimitry Andric 525*0b57cec5SDimitry Andric#endif /* _LIBCPP_STD_VER > 14 */ 526*0b57cec5SDimitry Andric 527*0b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 17 528*0b57cec5SDimitry Andrictemplate <class _Tp> 529*0b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY constexpr 530*0b57cec5SDimitry Andricenable_if_t<is_integral_v<_Tp> && !is_same_v<bool, _Tp> && !is_null_pointer_v<_Tp>, _Tp> 531*0b57cec5SDimitry Andricmidpoint(_Tp __a, _Tp __b) noexcept 532*0b57cec5SDimitry Andric_LIBCPP_DISABLE_UBSAN_UNSIGNED_INTEGER_CHECK 533*0b57cec5SDimitry Andric{ 534*0b57cec5SDimitry Andric using _Up = std::make_unsigned_t<_Tp>; 535*0b57cec5SDimitry Andric 536*0b57cec5SDimitry Andric int __sign = 1; 537*0b57cec5SDimitry Andric _Up __m = __a; 538*0b57cec5SDimitry Andric _Up __M = __b; 539*0b57cec5SDimitry Andric if (__a > __b) 540*0b57cec5SDimitry Andric { 541*0b57cec5SDimitry Andric __sign = -1; 542*0b57cec5SDimitry Andric __m = __b; 543*0b57cec5SDimitry Andric __M = __a; 544*0b57cec5SDimitry Andric } 545*0b57cec5SDimitry Andric return __a + __sign * _Tp(_Up(__M-__m) >> 1); 546*0b57cec5SDimitry Andric} 547*0b57cec5SDimitry Andric 548*0b57cec5SDimitry Andric 549*0b57cec5SDimitry Andrictemplate <class _TPtr> 550*0b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY constexpr 551*0b57cec5SDimitry Andricenable_if_t<is_pointer_v<_TPtr> 552*0b57cec5SDimitry Andric && is_object_v<remove_pointer_t<_TPtr>> 553*0b57cec5SDimitry Andric && ! is_void_v<remove_pointer_t<_TPtr>> 554*0b57cec5SDimitry Andric && (sizeof(remove_pointer_t<_TPtr>) > 0), _TPtr> 555*0b57cec5SDimitry Andricmidpoint(_TPtr __a, _TPtr __b) noexcept 556*0b57cec5SDimitry Andric{ 557*0b57cec5SDimitry Andric return __a + _VSTD::midpoint(ptrdiff_t(0), __b - __a); 558*0b57cec5SDimitry Andric} 559*0b57cec5SDimitry Andric 560*0b57cec5SDimitry Andric 561*0b57cec5SDimitry Andrictemplate <typename _Tp> 562*0b57cec5SDimitry Andricconstexpr int __sign(_Tp __val) { 563*0b57cec5SDimitry Andric return (_Tp(0) < __val) - (__val < _Tp(0)); 564*0b57cec5SDimitry Andric} 565*0b57cec5SDimitry Andric 566*0b57cec5SDimitry Andrictemplate <typename _Fp> 567*0b57cec5SDimitry Andricconstexpr _Fp __fp_abs(_Fp __f) { return __f >= 0 ? __f : -__f; } 568*0b57cec5SDimitry Andric 569*0b57cec5SDimitry Andrictemplate <class _Fp> 570*0b57cec5SDimitry Andric_LIBCPP_INLINE_VISIBILITY constexpr 571*0b57cec5SDimitry Andricenable_if_t<is_floating_point_v<_Fp>, _Fp> 572*0b57cec5SDimitry Andricmidpoint(_Fp __a, _Fp __b) noexcept 573*0b57cec5SDimitry Andric{ 574*0b57cec5SDimitry Andric constexpr _Fp __lo = numeric_limits<_Fp>::min()*2; 575*0b57cec5SDimitry Andric constexpr _Fp __hi = numeric_limits<_Fp>::max()/2; 576*0b57cec5SDimitry Andric return __fp_abs(__a) <= __hi && __fp_abs(__b) <= __hi ? // typical case: overflow is impossible 577*0b57cec5SDimitry Andric (__a + __b)/2 : // always correctly rounded 578*0b57cec5SDimitry Andric __fp_abs(__a) < __lo ? __a + __b/2 : // not safe to halve a 579*0b57cec5SDimitry Andric __fp_abs(__a) < __lo ? __a/2 + __b : // not safe to halve b 580*0b57cec5SDimitry Andric __a/2 + __b/2; // otherwise correctly rounded 581*0b57cec5SDimitry Andric} 582*0b57cec5SDimitry Andric 583*0b57cec5SDimitry Andric#endif // _LIBCPP_STD_VER > 17 584*0b57cec5SDimitry Andric 585*0b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 586*0b57cec5SDimitry Andric 587*0b57cec5SDimitry Andric_LIBCPP_POP_MACROS 588*0b57cec5SDimitry Andric 589*0b57cec5SDimitry Andric#endif // _LIBCPP_NUMERIC 590