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