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 InputIterator1, class InputIterator2, class T> 29 T 30 inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); 31 32template <class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2> 33 T 34 inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, 35 T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2); 36 37template <class InputIterator, class OutputIterator> 38 OutputIterator 39 partial_sum(InputIterator first, InputIterator last, OutputIterator result); 40 41template <class InputIterator, class OutputIterator, class BinaryOperation> 42 OutputIterator 43 partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); 44 45template <class InputIterator, class OutputIterator> 46 OutputIterator 47 adjacent_difference(InputIterator first, InputIterator last, OutputIterator result); 48 49template <class InputIterator, class OutputIterator, class BinaryOperation> 50 OutputIterator 51 adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); 52 53template <class ForwardIterator, class T> 54 void iota(ForwardIterator first, ForwardIterator last, T value); 55 56template <class M, class N> 57 constexpr common_type_t<M,N> gcd(M m, N n); // C++17 58 59template <class M, class N> 60 constexpr common_type_t<M,N> lcm(M m, N n); // C++17 61 62} // std 63 64*/ 65 66#include <__config> 67#include <iterator> 68#include <limits> // for numeric_limits 69 70#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 71#pragma GCC system_header 72#endif 73 74_LIBCPP_BEGIN_NAMESPACE_STD 75 76template <class _InputIterator, class _Tp> 77inline _LIBCPP_INLINE_VISIBILITY 78_Tp 79accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) 80{ 81 for (; __first != __last; ++__first) 82 __init = __init + *__first; 83 return __init; 84} 85 86template <class _InputIterator, class _Tp, class _BinaryOperation> 87inline _LIBCPP_INLINE_VISIBILITY 88_Tp 89accumulate(_InputIterator __first, _InputIterator __last, _Tp __init, _BinaryOperation __binary_op) 90{ 91 for (; __first != __last; ++__first) 92 __init = __binary_op(__init, *__first); 93 return __init; 94} 95 96template <class _InputIterator1, class _InputIterator2, class _Tp> 97inline _LIBCPP_INLINE_VISIBILITY 98_Tp 99inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _Tp __init) 100{ 101 for (; __first1 != __last1; ++__first1, (void) ++__first2) 102 __init = __init + *__first1 * *__first2; 103 return __init; 104} 105 106template <class _InputIterator1, class _InputIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2> 107inline _LIBCPP_INLINE_VISIBILITY 108_Tp 109inner_product(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, 110 _Tp __init, _BinaryOperation1 __binary_op1, _BinaryOperation2 __binary_op2) 111{ 112 for (; __first1 != __last1; ++__first1, (void) ++__first2) 113 __init = __binary_op1(__init, __binary_op2(*__first1, *__first2)); 114 return __init; 115} 116 117template <class _InputIterator, class _OutputIterator> 118inline _LIBCPP_INLINE_VISIBILITY 119_OutputIterator 120partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 121{ 122 if (__first != __last) 123 { 124 typename iterator_traits<_InputIterator>::value_type __t(*__first); 125 *__result = __t; 126 for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 127 { 128 __t = __t + *__first; 129 *__result = __t; 130 } 131 } 132 return __result; 133} 134 135template <class _InputIterator, class _OutputIterator, class _BinaryOperation> 136inline _LIBCPP_INLINE_VISIBILITY 137_OutputIterator 138partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result, 139 _BinaryOperation __binary_op) 140{ 141 if (__first != __last) 142 { 143 typename iterator_traits<_InputIterator>::value_type __t(*__first); 144 *__result = __t; 145 for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 146 { 147 __t = __binary_op(__t, *__first); 148 *__result = __t; 149 } 150 } 151 return __result; 152} 153 154template <class _InputIterator, class _OutputIterator> 155inline _LIBCPP_INLINE_VISIBILITY 156_OutputIterator 157adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result) 158{ 159 if (__first != __last) 160 { 161 typename iterator_traits<_InputIterator>::value_type __t1(*__first); 162 *__result = __t1; 163 for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 164 { 165 typename iterator_traits<_InputIterator>::value_type __t2(*__first); 166 *__result = __t2 - __t1; 167 __t1 = _VSTD::move(__t2); 168 } 169 } 170 return __result; 171} 172 173template <class _InputIterator, class _OutputIterator, class _BinaryOperation> 174inline _LIBCPP_INLINE_VISIBILITY 175_OutputIterator 176adjacent_difference(_InputIterator __first, _InputIterator __last, _OutputIterator __result, 177 _BinaryOperation __binary_op) 178{ 179 if (__first != __last) 180 { 181 typename iterator_traits<_InputIterator>::value_type __t1(*__first); 182 *__result = __t1; 183 for (++__first, (void) ++__result; __first != __last; ++__first, (void) ++__result) 184 { 185 typename iterator_traits<_InputIterator>::value_type __t2(*__first); 186 *__result = __binary_op(__t2, __t1); 187 __t1 = _VSTD::move(__t2); 188 } 189 } 190 return __result; 191} 192 193template <class _ForwardIterator, class _Tp> 194inline _LIBCPP_INLINE_VISIBILITY 195void 196iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value_) 197{ 198 for (; __first != __last; ++__first, (void) ++__value_) 199 *__first = __value_; 200} 201 202 203#if _LIBCPP_STD_VER > 14 204template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __abs; 205 206template <typename _Result, typename _Source> 207struct __abs<_Result, _Source, true> { 208 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 209 _Result operator()(_Source __t) const noexcept 210 { 211 if (__t >= 0) return __t; 212 if (__t == numeric_limits<_Source>::min()) return -static_cast<_Result>(__t); 213 return -__t; 214 } 215}; 216 217template <typename _Result, typename _Source> 218struct __abs<_Result, _Source, false> { 219 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 220 _Result operator()(_Source __t) const noexcept { return __t; } 221}; 222 223 224template<class _Tp> 225_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 226_Tp __gcd(_Tp __m, _Tp __n) 227{ 228 static_assert((!is_signed<_Tp>::value), ""); 229 return __n == 0 ? __m : __gcd<_Tp>(__n, __m % __n); 230} 231 232 233template<class _Tp, class _Up> 234_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 235common_type_t<_Tp,_Up> 236gcd(_Tp __m, _Up __n) 237{ 238 static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types"); 239 static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to gcd cannot be bool" ); 240 static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to gcd cannot be bool" ); 241 using _Rp = common_type_t<_Tp,_Up>; 242 using _Wp = make_unsigned_t<_Rp>; 243 return static_cast<_Rp>(__gcd(static_cast<_Wp>(__abs<_Rp, _Tp>()(__m)), 244 static_cast<_Wp>(__abs<_Rp, _Up>()(__n)))); 245} 246 247template<class _Tp, class _Up> 248_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 249common_type_t<_Tp,_Up> 250lcm(_Tp __m, _Up __n) 251{ 252 static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types"); 253 static_assert((!is_same<typename remove_cv<_Tp>::type, bool>::value), "First argument to lcm cannot be bool" ); 254 static_assert((!is_same<typename remove_cv<_Up>::type, bool>::value), "Second argument to lcm cannot be bool" ); 255 if (__m == 0 || __n == 0) 256 return 0; 257 258 using _Rp = common_type_t<_Tp,_Up>; 259 _Rp __val1 = __abs<_Rp, _Tp>()(__m) / gcd(__m, __n); 260 _Rp __val2 = __abs<_Rp, _Up>()(__n); 261 _LIBCPP_ASSERT((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm"); 262 return __val1 * __val2; 263} 264 265#endif /* _LIBCPP_STD_VER > 14 */ 266 267_LIBCPP_END_NAMESPACE_STD 268 269#endif // _LIBCPP_NUMERIC 270