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>
     85     OutputIterator
     86     inclusive_scan(InputIterator first, InputIterator last, OutputIterator result);  // C++17
     87 
     88 template<class InputIterator, class OutputIterator, class BinaryOperation>
     89     OutputIterator
     90     inclusive_scan(InputIterator first, InputIterator last,
     91                    OutputIterator result, BinaryOperation binary_op);  // C++17
     92 
     93 template<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 
     98 template<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 
    105 template<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                                           
    112 template<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 
    120 template <class InputIterator, class OutputIterator>
    121     OutputIterator
    122     adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);
    123 
    124 template <class InputIterator, class OutputIterator, class BinaryOperation>
    125     OutputIterator
    126     adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);
    127 
    128 template <class ForwardIterator, class T>
    129     void iota(ForwardIterator first, ForwardIterator last, T value);
    130 
    131 template <class M, class N>
    132     constexpr common_type_t<M,N> gcd(M m, N n);    // C++17
    133 
    134 template <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 
    146 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
    147 #pragma GCC system_header
    148 #endif
    149 
    150 _LIBCPP_PUSH_MACROS
    151 #include <__undef_macros>
    152 
    153 _LIBCPP_BEGIN_NAMESPACE_STD
    154 
    155 template <class _InputIterator, class _Tp>
    156 inline _LIBCPP_INLINE_VISIBILITY
    157 _Tp
    158 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
    159 {
    160     for (; __first != __last; ++__first)
    161         __init = __init + *__first;
    162     return __init;
    163 }
    164 
    165 template <class _InputIterator, class _Tp, class _BinaryOperation>
    166 inline _LIBCPP_INLINE_VISIBILITY
    167 _Tp
    168 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOperation __binary_op)
    169 {
    170     for (; __first != __last; ++__first)
    171         __init = __binary_op(__init, *__first);
    172     return __init;
    173 }
    174 
    175 #if _LIBCPP_STD_VER > 14
    176 template <class _InputIterator, class _Tp, class _BinaryOp>
    177 inline _LIBCPP_INLINE_VISIBILITY
    178 _Tp
    179 reduce(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOp __b)
    180 {
    181     for (; __first != __last; ++__first)
    182         __init = __b(__init, *__first);
    183     return __init;
    184 }
    185 
    186 template <class _InputIterator, class _Tp>
    187 inline _LIBCPP_INLINE_VISIBILITY
    188 _Tp
    189 reduce(_InputIterator __first, _InputIterator __last, _Tp __init)
    190 {
    191     return _VSTD::reduce(__first, __last, __init, _VSTD::plus<>());
    192 }
    193 
    194 template <class _InputIterator>
    195 inline _LIBCPP_INLINE_VISIBILITY
    196 typename iterator_traits<_InputIterator>::value_type
    197 reduce(_InputIterator __first, _InputIterator __last)
    198 {
    199     return _VSTD::reduce(__first, __last, 
    200        typename iterator_traits<_InputIterator>::value_type{});
    201 }
    202 #endif
    203 
    204 template <class _InputIterator1, class _InputIterator2, class _Tp>
    205 inline _LIBCPP_INLINE_VISIBILITY
    206 _Tp
    207 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init)
    208 {
    209     for (; __first1 != __last1; ++__first1, (void) ++__first2)
    210         __init = __init + *__first1 * *__first2;
    211     return __init;
    212 }
    213 
    214 template <class _InputIterator1, class _InputIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2>
    215 inline _LIBCPP_INLINE_VISIBILITY
    216 _Tp
    217 inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
    218               _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2)
    219 {
    220     for (; __first1 != __last1; ++__first1, (void) ++__first2)
    221         __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
    222     return __init;
    223 }
    224 
    225 #if _LIBCPP_STD_VER > 14
    226 template <class _InputIterator, class _Tp, class _BinaryOp, class _UnaryOp>
    227 inline _LIBCPP_INLINE_VISIBILITY
    228 _Tp
    229 transform_reduce(_InputIterator __first, _InputIterator __last, 
    230            _Tp __init,  _BinaryOp __b, _UnaryOp __u)
    231 {
    232     for (; __first != __last; ++__first)
    233         __init = __b(__init, __u(*__first));
    234     return __init;
    235 }
    236 
    237 template <class _InputIterator1, class _InputIterator2, 
    238           class _Tp, class _BinaryOp1, class _BinaryOp2>
    239 inline _LIBCPP_INLINE_VISIBILITY
    240 _Tp
    241 transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1,
    242                  _InputIterator2 __first2, _Tp __init,  _BinaryOp1 __b1, _BinaryOp2 __b2)
    243 {
    244     for (; __first1 != __last1; ++__first1, (void) ++__first2)
    245         __init = __b1(__init, __b2(*__first1, *__first2));
    246     return __init;
    247 }
    248 
    249 template <class _InputIterator1, class _InputIterator2, class _Tp>
    250 inline _LIBCPP_INLINE_VISIBILITY
    251 _Tp
    252 transform_reduce(_InputIterator1 __first1, _InputIterator1 __last1, 
    253                  _InputIterator2 __first2, _Tp __init)
    254 {
    255     return _VSTD::transform_reduce(__first1, __last1, __first2, __init, 
    256                                    _VSTD::plus<>(), _VSTD::multiplies<>());
    257 }
    258 #endif
    259 
    260 template <class _InputIterator, class _OutputIterator>
    261 inline _LIBCPP_INLINE_VISIBILITY
    262 _OutputIterator
    263 partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
    264 {
    265     if (__first != __last)
    266     {
    267         typename iterator_traits<_InputIterator>::value_type __t(*__first);
    268         *__result = __t;
    269         for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)
    270         {
    271             __t = __t + *__first;
    272             *__result = __t;
    273         }
    274     }
    275     return __result;
    276 }
    277 
    278 template <class _InputIterator, class _OutputIterator, class _BinaryOperation>
    279 inline _LIBCPP_INLINE_VISIBILITY
    280 _OutputIterator
    281 partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
    282               _BinaryOperation __binary_op)
    283 {
    284     if (__first != __last)
    285     {
    286         typename iterator_traits<_InputIterator>::value_type __t(*__first);
    287         *__result = __t;
    288         for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)
    289         {
    290             __t = __binary_op(__t, *__first);
    291             *__result = __t;
    292         }
    293     }
    294     return __result;
    295 }
    296 
    297 #if _LIBCPP_STD_VER > 14
    298 template <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp>
    299 inline _LIBCPP_INLINE_VISIBILITY
    300 _OutputIterator
    301 exclusive_scan(_InputIterator __first, _InputIterator __last, 
    302                _OutputIterator __result, _Tp __init, _BinaryOp __b)
    303 {
    304     if (__first != __last)
    305     {
    306         _Tp __saved = __init;
    307         do
    308         {
    309             __init = __b(__init, *__first);
    310             *__result = __saved;
    311             __saved = __init;
    312             ++__result;
    313         } while (++__first != __last);
    314     }
    315     return __result;
    316 }
    317 
    318 template <class _InputIterator, class _OutputIterator, class _Tp>
    319 inline _LIBCPP_INLINE_VISIBILITY
    320 _OutputIterator
    321 exclusive_scan(_InputIterator __first, _InputIterator __last, 
    322                _OutputIterator __result, _Tp __init)
    323 {
    324     return _VSTD::exclusive_scan(__first, __last, __result, __init, _VSTD::plus<>());
    325 }
    326 
    327 template <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp>
    328 _OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, 
    329                                _OutputIterator __result, _BinaryOp __b,  _Tp __init)
    330 {
    331     for (; __first != __last; ++__first, (void) ++__result) {
    332         __init = __b(__init, *__first);
    333         *__result = __init;
    334         }
    335     return __result;
    336 }
    337 
    338 template <class _InputIterator, class _OutputIterator, class _BinaryOp>
    339 _OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, 
    340                                _OutputIterator __result, _BinaryOp __b)
    341 {
    342     if (__first != __last) {
    343         typename std::iterator_traits<_InputIterator>::value_type __init = *__first;
    344         *__result++ = __init;
    345         if (++__first != __last)
    346             return _VSTD::inclusive_scan(__first, __last, __result, __b, __init);
    347         }
    348 
    349     return __result;
    350 }
    351 
    352 template <class _InputIterator, class _OutputIterator>
    353 _OutputIterator inclusive_scan(_InputIterator __first, _InputIterator __last, 
    354                                _OutputIterator __result)
    355 {
    356     return _VSTD::inclusive_scan(__first, __last, __result, std::plus<>());
    357 }
    358 
    359 template <class _InputIterator, class _OutputIterator, class _Tp, 
    360           class _BinaryOp, class _UnaryOp>
    361 inline _LIBCPP_INLINE_VISIBILITY
    362 _OutputIterator
    363 transform_exclusive_scan(_InputIterator __first, _InputIterator __last, 
    364                            _OutputIterator __result, _Tp __init,
    365                            _BinaryOp __b, _UnaryOp __u)
    366 {
    367     if (__first != __last)
    368     {
    369         _Tp __saved = __init;
    370         do
    371         {
    372             __init = __b(__init, __u(*__first));
    373             *__result = __saved;
    374             __saved = __init;
    375             ++__result;
    376         } while (++__first != __last);
    377     }
    378     return __result;
    379 }
    380 
    381 template <class _InputIterator, class _OutputIterator, class _Tp, class _BinaryOp, class _UnaryOp>
    382 _OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last, 
    383                            _OutputIterator __result, _BinaryOp __b, _UnaryOp __u, _Tp __init)
    384 {
    385     for (; __first != __last; ++__first, (void) ++__result) {
    386         __init = __b(__init, __u(*__first));
    387         *__result = __init;
    388         }
    389 
    390     return __result;
    391 }
    392 
    393 template <class _InputIterator, class _OutputIterator, class _BinaryOp, class _UnaryOp>
    394 _OutputIterator transform_inclusive_scan(_InputIterator __first, _InputIterator __last, 
    395                                _OutputIterator __result, _BinaryOp __b, _UnaryOp __u)
    396 {
    397     if (__first != __last) {
    398         typename std::iterator_traits<_InputIterator>::value_type __init = __u(*__first);
    399         *__result++ = __init;
    400         if (++__first != __last)
    401             return _VSTD::transform_inclusive_scan(__first, __last, __result, __b, __u, __init);
    402         }
    403     
    404     return __result;
    405 }
    406 #endif
    407 
    408 template <class _InputIterator, class _OutputIterator>
    409 inline _LIBCPP_INLINE_VISIBILITY
    410 _OutputIterator
    411 adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result)
    412 {
    413     if (__first != __last)
    414     {
    415         typename iterator_traits<_InputIterator>::value_type __t1(*__first);
    416         *__result = __t1;
    417         for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)
    418         {
    419             typename iterator_traits<_InputIterator>::value_type __t2(*__first);
    420             *__result = __t2 - __t1;
    421             __t1 = _VSTD::move(__t2);
    422         }
    423     }
    424     return __result;
    425 }
    426 
    427 template <class _InputIterator, class _OutputIterator, class _BinaryOperation>
    428 inline _LIBCPP_INLINE_VISIBILITY
    429 _OutputIterator
    430 adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result,
    431                       _BinaryOperation __binary_op)
    432 {
    433     if (__first != __last)
    434     {
    435         typename iterator_traits<_InputIterator>::value_type __t1(*__first);
    436         *__result = __t1;
    437         for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result)
    438         {
    439             typename iterator_traits<_InputIterator>::value_type __t2(*__first);
    440             *__result = __binary_op(__t2, __t1);
    441             __t1 = _VSTD::move(__t2);
    442         }
    443     }
    444     return __result;
    445 }
    446 
    447 template <class _ForwardIterator, class _Tp>
    448 inline _LIBCPP_INLINE_VISIBILITY
    449 void
    450 iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value_)
    451 {
    452     for (; __first != __last; ++__first, (void) ++__value_)
    453         *__first = __value_;
    454 }
    455 
    456 
    457 #if _LIBCPP_STD_VER > 14
    458 template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __abs;
    459 
    460 template <typename _Result, typename _Source>
    461 struct __abs<_Result, _Source, true> {
    462     _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
    463     _Result operator()(_Source __t) const noexcept
    464     {
    465     if (__t >= 0) return __t;
    466     if (__t == numeric_limits<_Source>::min()) return -static_cast<_Result>(__t);
    467     return -__t;
    468     }
    469 };
    470 
    471 template <typename _Result, typename _Source>
    472 struct __abs<_Result, _Source, false> {
    473     _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
    474     _Result operator()(_Source __t) const noexcept { return __t; }
    475 };
    476 
    477 
    478 template<class _Tp>
    479 _LIBCPP_CONSTEXPR _LIBCPP_HIDDEN
    480 _Tp __gcd(_Tp __m, _Tp __n)
    481 {
    482     static_assert((!is_signed<_Tp>::value), "");
    483     return __n == 0 ? __m : _VSTD::__gcd<_Tp>(__n, __m % __n);
    484 }
    485 
    486 
    487 template<class _Tp, class _Up>
    488 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
    489 common_type_t<_Tp,_Up>
    490 gcd(_Tp __m, _Up __n)
    491 {
    492     static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types");
    493     static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to gcd cannot be bool" );
    494     static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to gcd cannot be bool" );
    495     using _Rp = common_type_t<_Tp,_Up>;
    496     using _Wp = make_unsigned_t<_Rp>;
    497     return static_cast<_Rp>(_VSTD::__gcd(
    498         static_cast<_Wp>(__abs<_Rp, _Tp>()(__m)),
    499         static_cast<_Wp>(__abs<_Rp, _Up>()(__n))));
    500 }
    501 
    502 template<class _Tp, class _Up>
    503 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY
    504 common_type_t<_Tp,_Up>
    505 lcm(_Tp __m, _Up __n)
    506 {
    507     static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types");
    508     static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to lcm cannot be bool" );
    509     static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to lcm cannot be bool" );
    510     if (__m == 0 || __n == 0)
    511         return 0;
    512 
    513     using _Rp = common_type_t<_Tp,_Up>;
    514     _Rp __val1 = __abs<_Rp, _Tp>()(__m) / _VSTD::gcd(__m, __n);
    515     _Rp __val2 = __abs<_Rp, _Up>()(__n);
    516     _LIBCPP_ASSERT((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm");
    517     return __val1 * __val2;
    518 }
    519 
    520 #endif /* _LIBCPP_STD_VER > 14 */
    521 
    522 _LIBCPP_END_NAMESPACE_STD
    523 
    524 _LIBCPP_POP_MACROS
    525 
    526 #endif  // _LIBCPP_NUMERIC
    527