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