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, _VSTD::move(__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
