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