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