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 InputIterator1, class InputIterator2, class T> 29 T 30 inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); 31 32 template <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 37 template <class InputIterator, class OutputIterator> 38 OutputIterator 39 partial_sum(InputIterator first, InputIterator last, OutputIterator result); 40 41 template <class InputIterator, class OutputIterator, class BinaryOperation> 42 OutputIterator 43 partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); 44 45 template <class InputIterator, class OutputIterator> 46 OutputIterator 47 adjacent_difference(InputIterator first, InputIterator last, OutputIterator result); 48 49 template <class InputIterator, class OutputIterator, class BinaryOperation> 50 OutputIterator 51 adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); 52 53 template <class ForwardIterator, class T> 54 void iota(ForwardIterator first, ForwardIterator last, T value); 55 56 template <class M, class N> 57 constexpr common_type_t<M,N> gcd(M m, N n); // C++17 58 59 template <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 76 template <class _InputIterator, class _Tp> 77 inline _LIBCPP_INLINE_VISIBILITY 78 _Tp 79 accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) 80 { 81 for (; __first != __last; ++__first) 82 __init = __init + *__first; 83 return __init; 84 } 85 86 template <class _InputIterator, class _Tp, class _BinaryOperation> 87 inline _LIBCPP_INLINE_VISIBILITY 88 _Tp 89 accumulate(_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 96 template <class _InputIterator1, class _InputIterator2, class _Tp> 97 inline _LIBCPP_INLINE_VISIBILITY 98 _Tp 99 inner_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 106 template <class _InputIterator1, class _InputIterator2, class _Tp, class _BinaryOperation1, class _BinaryOperation2> 107 inline _LIBCPP_INLINE_VISIBILITY 108 _Tp 109 inner_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 117 template <class _InputIterator, class _OutputIterator> 118 inline _LIBCPP_INLINE_VISIBILITY 119 _OutputIterator 120 partial_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 135 template <class _InputIterator, class _OutputIterator, class _BinaryOperation> 136 inline _LIBCPP_INLINE_VISIBILITY 137 _OutputIterator 138 partial_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 154 template <class _InputIterator, class _OutputIterator> 155 inline _LIBCPP_INLINE_VISIBILITY 156 _OutputIterator 157 adjacent_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 173 template <class _InputIterator, class _OutputIterator, class _BinaryOperation> 174 inline _LIBCPP_INLINE_VISIBILITY 175 _OutputIterator 176 adjacent_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 193 template <class _ForwardIterator, class _Tp> 194 inline _LIBCPP_INLINE_VISIBILITY 195 void 196 iota(_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 204 template <typename _Result, typename _Source, bool _IsSigned = is_signed<_Source>::value> struct __abs; 205 206 template <typename _Result, typename _Source> 207 struct __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 217 template <typename _Result, typename _Source> 218 struct __abs<_Result, _Source, false> { 219 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 220 _Result operator()(_Source __t) const noexcept { return __t; } 221 }; 222 223 224 template<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 233 template<class _Tp, class _Up> 234 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 235 common_type_t<_Tp,_Up> 236 gcd(_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 247 template<class _Tp, class _Up> 248 _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY 249 common_type_t<_Tp,_Up> 250 lcm(_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
