Home | History | Annotate | Download | only in v1 
      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 
     17 namespace std
     18 {
     19 
     20 template <class InputIterator, class T>
     21     T
     22     accumulate(InputIterator first, InputIterator last, T init);
     23 
     24 template <class InputIterator, class T, class BinaryOperation>
     25     T
     26     accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);
     27 
     28 template<class InputIterator>
     29     typename iterator_traits<InputIterator>::value_type
     30     reduce(InputIterator first, InputIterator last);  // C++17
     31 
     32 template<class InputIterator, class T>
     33     T
     34     reduce(InputIterator first, InputIterator last, T init);  // C++17
     35 
     36 template<class InputIterator, class T, class BinaryOperation>
     37     T
     38     reduce(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);  // C++17
     39 
     40 template <class InputIterator1, class InputIterator2, class T>
     41     T
     42     inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init);
     43 
     44 template <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 
     50 template<class InputIterator1, class InputIterator2, class T>
     51     T
     52     transform_reduce(InputIterator1 first1, InputIterator1 last1,
     53                      InputIterator2 first2, T init);  // C++17
     54                      
     55 template<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 
     61 template<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 
     66 template <class InputIterator, class OutputIterator>
     67     OutputIterator
     68     partial_sum(InputIterator first, InputIterator last, OutputIterator result);
     69 
     70 template <class InputIterator, class OutputIterator, class BinaryOperation>
     71     OutputIterator
     72     partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);
     73 
     74 template<class InputIterator, class OutputIterator, class T>
     75     OutputIterator
     76     exclusive_scan(InputIterator first, InputIterator last,
     77                    OutputIterator result, T init); // C++17
     78                            
     79 template<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 
     84 template<class InputIterator, class OutputIterator, class T,
     85          class BinaryOperation, class UnaryOperation>
     86     OutputIterator
     87     transform_exclusive_scan(InputIterator first, InputIterator last,
     88                              OutputIterator result, T init,
     89                              BinaryOperation binary_op, UnaryOperation unary_op);  // C++17
     90 
     91 template <class InputIterator, class OutputIterator>
     92     OutputIterator
     93     adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);
     94 
     95 template <class InputIterator, class OutputIterator, class BinaryOperation>
     96     OutputIterator
     97     adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);
     98 
     99 template <class ForwardIterator, class T>
    100     void iota(ForwardIterator first, ForwardIterator last, T value);
    101 
    102 template <class M, class N>
    103     constexpr common_type_t<M,N> gcd(M m, N n);    // C++17
    104 
    105 template <class M, class N>
    106     constexpr common_type_t<M,N> lcm(M m, N n);    // C++17
    107 
    108 }  // std
    109 
    110 */
    111 
    112 #include <__config>
    113 #include <iterator>
    114 #include <limits> // for numeric_limits
    115 #include <functional>
    116 
    117 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
    118 #pragma GCC system_header
    119 #endif
    120 
    121 _LIBCPP_PUSH_MACROS
    122 #include <__undef_macros>
    123 
    124 _LIBCPP_BEGIN_NAMESPACE_STD
    125 
    126 template <class _InputIterator, class _Tp>
    127 inline _LIBCPP_INLINE_VISIBILITY
    128 _Tp
    129 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
    130 {
    131     for (; __first != __last; ++__first)
    132         __init = __init + *__first;
    133     return __init;
    134 }
    135 
    136 template <class _InputIterator, class _Tp, class _BinaryOperation>
    137 inline _LIBCPP_INLINE_VISIBILITY
    138 _Tp
    139 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOperation __binary_op)
    140 {
    141     for (; __first != __last; ++__first)
    142         __init = __binary_op(__init, *__first);
    143     return __init;
    144 }
    145 
    146 #if _LIBCPP_STD_VER > 14
    147 template <class _InputIterator, class _Tp, class _BinaryOp>
    148 inline _LIBCPP_INLINE_VISIBILITY
    149 _Tp
    150 reduce(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOp __b)
    151 {
    152     for (; __first != __last; ++__first)
    153         __init = __b(__init, *__first);
    154     return __init;
    155 }
    156 
    157 template <class _InputIterator, class _Tp>
    158 inline _LIBCPP_INLINE_VISIBILITY
    159 _Tp
    160 reduce(_InputIterator __first, _InputIterator __last, _Tp __init)
    161 {
    162     return _VSTD::reduce(__first, __last, __init, _VSTD::plus<>());
    163 }
    164 
    165 template <class _InputIterator>
    166 inline _LIBCPP_INLINE_VISIBILITY
    167 typename iterator_traits<_InputIterator>::value_type
    168 reduce(_InputIterator __first, _InputIterator __last)
    169 {
    170     return _VSTD::reduce(__first, __last, 
    171        typename iterator_traits<_InputIterator>::value_type{});
    172 }
    173 #endif
    174 
    175 template <class _InputIterator1, class _InputIterator2, class _Tp>
    176 inline _LIBCPP_INLINE_VISIBILITY
    177 _Tp
    178 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init)
    179 {
    180     for (; __first1 != __last1; ++__first1, (void) ++__first2)
    181         __init = __init + *__first1 * *__first2;
    182     return __init;
    183 }
    184 
    185 template <class _InputIterator1, class _InputIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2>
    186 inline _LIBCPP_INLINE_VISIBILITY
    187 _Tp
    188 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
    189               _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2)
    190 {
    191     for (; __first1 != __last1; ++__first1, (void) ++__first2)
    192         __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
    193     return __init;
    194 }
    195 
    196 #if _LIBCPP_STD_VER > 14
    197 template <class _InputIterator, class _Tp, class _BinaryOp, class _UnaryOp>
    198 inline _LIBCPP_INLINE_VISIBILITY
    199 _Tp
    200 transform_reduce(_InputIterator __first, _InputIterator __last, 
    201            _Tp __init,  _BinaryOp __b, _UnaryOp __u)
    202 {
    203     for (; __first != __last; ++__first)
    204         __init = __b(__init, __u(*__first));
    205     return __init;
    206 }
    207 
    208 template <class _InputIterator1, class _InputIterator2, 
    209           class _Tp, class _BinaryOp1, class _BinaryOp2>
    210 inline _LIBCPP_INLINE_VISIBILITY
    211 _Tp
    212 transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1,
    213                  _InputIterator2 __first2, _Tp __init,  _BinaryOp1 __b1, _BinaryOp2 __b2)
    214 {
    215     for (; __first1 != __last1; ++__first1, (void) ++__first2)
    216         __init = __b1(__init, __b2(*__first1, *__first2));
    217     return __init;
    218 }
    219 
    220 template <class _InputIterator1, class _InputIterator2, class _Tp>
    221 inline _LIBCPP_INLINE_VISIBILITY
    222 _Tp
    223 transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, 
    224                  _InputIterator2 __first2, _Tp __init)
    225 {
    226     return _VSTD::transform_reduce(__first1, __last1, __first2, __init, 
    227                                    _VSTD::plus<>(), _VSTD::multiplies<>());
    228 }
    229 #endif
    230 
    231 template <class _InputIterator, class _OutputIterator>
    232 inline _LIBCPP_INLINE_VISIBILITY
    233 _OutputIterator
    234 partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
    235 {
    236     if (__first != __last)
    237     {
    238         typename iterator_traits<_InputIterator>::value_type __t(*__first);
    239         *__result = __t;
    240         for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)
    241         {
    242             __t = __t + *__first;
    243             *__result = __t;
    244         }
    245     }
    246     return __result;
    247 }
    248 
    249 template <class _InputIterator, class _OutputIterator, class _BinaryOperation>
    250 inline _LIBCPP_INLINE_VISIBILITY
    251 _OutputIterator
    252 partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
    253               _BinaryOperation __binary_op)
    254 {
    255     if (__first != __last)
    256     {
    257         typename iterator_traits<_InputIterator>::value_type __t(*__first);
    258         *__result = __t;
    259         for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)
    260         {
    261             __t = __binary_op(__t, *__first);
    262             *__result = __t;
    263         }
    264     }
    265     return __result;
    266 }
    267 
    268 #if _LIBCPP_STD_VER > 14
    269 template <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp>
    270 inline _LIBCPP_INLINE_VISIBILITY
    271 _OutputIterator
    272 exclusive_scan(_InputIterator __first, _InputIterator __last, 
    273                _OutputIterator __result, _Tp __init, _BinaryOp __b)
    274 {
    275     if (__first != __last)
    276     {
    277         _Tp __saved = __init;
    278         do
    279         {
    280             __init = __b(__init, *__first);
    281             *__result = __saved;
    282             __saved = __init;
    283             ++__result;
    284         } while (++__first != __last);
    285     }
    286     return __result;
    287 }
    288 
    289 template <class _InputIterator, class _OutputIterator, class _Tp>
    290 inline _LIBCPP_INLINE_VISIBILITY
    291 _OutputIterator
    292 exclusive_scan(_InputIterator __first, _InputIterator __last, 
    293                _OutputIterator __result, _Tp __init)
    294 {
    295     return _VSTD::exclusive_scan(__first, __last, __result, __init, _VSTD::plus<>());
    296 }
    297 
    298 template <class _InputIterator, class _OutputIterator, class _Tp, 
    299           class _BinaryOp, class _UnaryOp>
    300 inline _LIBCPP_INLINE_VISIBILITY
    301 _OutputIterator
    302 transform_exclusive_scan(_InputIterator __first, _InputIterator __last, 
    303                            _OutputIterator __result, _Tp __init,
    304                            _BinaryOp __b, _UnaryOp __u)
    305 {
    306     if (__first != __last)
    307     {
    308         _Tp __saved = __init;
    309         do
    310         {
    311             __init = __b(__init, __u(*__first));
    312             *__result = __saved;
    313             __saved = __init;
    314             ++__result;
    315         } while (++__first != __last);
    316     }
    317     return __result;
    318 }
    319 #endif
    320 
    321 template <class _InputIterator, class _OutputIterator>
    322 inline _LIBCPP_INLINE_VISIBILITY
    323 _OutputIterator
    324 adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
    325 {
    326     if (__first != __last)
    327     {
    328         typename iterator_traits<_InputIterator>::value_type __t1(*__first);
    329         *__result = __t1;
    330         for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)
    331         {
    332             typename iterator_traits<_InputIterator>::value_type __t2(*__first);
    333             *__result = __t2 - __t1;
    334             __t1 = _VSTD::move(__t2);
    335         }
    336     }
    337     return __result;
    338 }
    339 
    340 template <class _InputIterator, class _OutputIterator, class _BinaryOperation>
    341 inline _LIBCPP_INLINE_VISIBILITY
    342 _OutputIterator
    343 adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
    344                       _BinaryOperation __binary_op)
    345 {
    346     if (__first != __last)
    347     {
    348         typename iterator_traits<_InputIterator>::value_type __t1(*__first);
    349         *__result = __t1;
    350         for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)
    351         {
    352             typename iterator_traits<_InputIterator>::value_type __t2(*__first);
    353             *__result = __binary_op(__t2, __t1);
    354             __t1 = _VSTD::move(__t2);
    355         }
    356     }
    357     return __result;
    358 }
    359 
    360 template <class _ForwardIterator, class _Tp>
    361 inline _LIBCPP_INLINE_VISIBILITY
    362 void
    363 iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value_)
    364 {
    365     for (; __first != __last; ++__first, (void) ++__value_)
    366         *__first = __value_;
    367 }
    368 
    369 
    370 #if _LIBCPP_STD_VER > 14
    371 template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __abs;
    372 
    373 template <typename _Result, typename _Source>
    374 struct __abs<_Result, _Source, true> {
    375     _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
    376     _Result operator()(_Source __t) const noexcept
    377     {
    378     if (__t >= 0) return __t;
    379     if (__t == numeric_limits<_Source>::min()) return -static_cast<_Result>(__t);
    380     return -__t;
    381     }
    382 };
    383 
    384 template <typename _Result, typename _Source>
    385 struct __abs<_Result, _Source, false> {
    386     _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
    387     _Result operator()(_Source __t) const noexcept { return __t; }
    388 };
    389 
    390 
    391 template<class _Tp>
    392 _LIBCPP_CONSTEXPR _LIBCPP_HIDDEN
    393 _Tp __gcd(_Tp __m, _Tp __n)
    394 {
    395     static_assert((!is_signed<_Tp>::value), "");
    396     return __n == 0 ? __m : _VSTD::__gcd<_Tp>(__n, __m % __n);
    397 }
    398 
    399 
    400 template<class _Tp, class _Up>
    401 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
    402 common_type_t<_Tp,_Up>
    403 gcd(_Tp __m, _Up __n)
    404 {
    405     static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types");
    406     static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to gcd cannot be bool" );
    407     static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to gcd cannot be bool" );
    408     using _Rp = common_type_t<_Tp,_Up>;
    409     using _Wp = make_unsigned_t<_Rp>;
    410     return static_cast<_Rp>(_VSTD::__gcd(
    411         static_cast<_Wp>(__abs<_Rp, _Tp>()(__m)),
    412         static_cast<_Wp>(__abs<_Rp, _Up>()(__n))));
    413 }
    414 
    415 template<class _Tp, class _Up>
    416 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
    417 common_type_t<_Tp,_Up>
    418 lcm(_Tp __m, _Up __n)
    419 {
    420     static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types");
    421     static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to lcm cannot be bool" );
    422     static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to lcm cannot be bool" );
    423     if (__m == 0 || __n == 0)
    424         return 0;
    425 
    426     using _Rp = common_type_t<_Tp,_Up>;
    427     _Rp __val1 = __abs<_Rp, _Tp>()(__m) / _VSTD::gcd(__m, __n);
    428     _Rp __val2 = __abs<_Rp, _Up>()(__n);
    429     _LIBCPP_ASSERT((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm");
    430     return __val1 * __val2;
    431 }
    432 
    433 #endif /* _LIBCPP_STD_VER > 14 */
    434 
    435 _LIBCPP_END_NAMESPACE_STD
    436 
    437 _LIBCPP_POP_MACROS
    438 
    439 #endif  // _LIBCPP_NUMERIC
    440