diff options
Diffstat (limited to 'libcxx/include')
| -rw-r--r-- | libcxx/include/algorithm | 4 | ||||
| -rw-r--r-- | libcxx/include/numeric | 62 |
2 files changed, 64 insertions, 2 deletions
diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm index 25e95ac443a..cf03d66d542 100644 --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -2431,7 +2431,7 @@ __rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIt template<typename _Integral> inline _LIBCPP_INLINE_VISIBILITY _Integral -__gcd(_Integral __x, _Integral __y) +__algo_gcd(_Integral __x, _Integral __y) { do { @@ -2456,7 +2456,7 @@ __rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Ran _VSTD::swap_ranges(__first, __middle, __middle); return __middle; } - const difference_type __g = _VSTD::__gcd(__m1, __m2); + const difference_type __g = _VSTD::__algo_gcd(__m1, __m2); for (_RandomAccessIterator __p = __first + __g; __p != __first;) { value_type __t(_VSTD::move(*--__p)); diff --git a/libcxx/include/numeric b/libcxx/include/numeric index 21c3781ab6a..1643d6400d1 100644 --- a/libcxx/include/numeric +++ b/libcxx/include/numeric @@ -53,6 +53,12 @@ template <class InputIterator, class OutputIterator, class BinaryOperation> template <class ForwardIterator, class T> void iota(ForwardIterator first, ForwardIterator last, T value); +template <class M, class N> + constexpr common_type_t<M,N> gcd(M m, N n); // C++17 + +template <class M, class N> + constexpr common_type_t<M,N> lcm(M m, N n); // C++17 + } // std */ @@ -192,6 +198,62 @@ iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value_) *__first = __value_; } + +#if _LIBCPP_STD_VER > 14 +template <typename _Tp, bool _IsSigned = is_signed<_Tp>::value> struct __abs; + +template <typename _Tp> +struct __abs<_Tp, true> { + _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY + _Tp operator()(_Tp __t) const noexcept { return __t >= 0 ? __t : -__t; } +}; + +template <typename _Tp> +struct __abs<_Tp, false> { + _LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY + _Tp operator()(_Tp __t) const noexcept { return __t; } +}; + + +template<class _Tp> +_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY +_Tp __gcd(_Tp __m, _Tp __n) +{ + static_assert((!is_signed<_Tp>::value), "" ); + return __n == 0 ? __m : __gcd<_Tp>(__n, __m % __n); +} + + +template<class _Tp, class _Up> +_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY +common_type_t<_Tp,_Up> +gcd(_Tp __m, _Up __n) +{ + static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to gcd must be integer types"); + using _Rp = common_type_t<_Tp,_Up>; + using _Wp = make_unsigned_t<_Rp>; + return static_cast<_Rp>(__gcd(static_cast<_Wp>(__abs<_Tp>()(__m)), + static_cast<_Wp>(__abs<_Up>()(__n)))); +} + +template<class _Tp, class _Up> +_LIBCPP_CONSTEXPR _LIBCPP_INLINE_VISIBILITY +common_type_t<_Tp,_Up> +lcm(_Tp __m, _Up __n) +{ + static_assert((is_integral<_Tp>::value && is_integral<_Up>::value), "Arguments to lcm must be integer types"); + if (__m == 0 || __n == 0) + return 0; + + using _Rp = common_type_t<_Tp,_Up>; + _Rp __val1 = __abs<_Tp>()(__m) / gcd(__m,__n); + _Up __val2 = __abs<_Up>()(__n); + _LIBCPP_ASSERT((numeric_limits<_Rp>::max() / __val1 > __val2), "Overflow in lcm"); + return __val1 * __val2; +} + +#endif /* _LIBCPP_STD_VER > 14 */ + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP_NUMERIC |
