Implement LCM and GCD for C++17. Same code as for Library Fundamentals TS.
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@276751 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/algorithm b/include/algorithm
index 25e95ac..cf03d66 100644
--- a/include/algorithm
+++ b/include/algorithm
@@ -2431,7 +2431,7 @@
template<typename _Integral>
inline _LIBCPP_INLINE_VISIBILITY
_Integral
-__gcd(_Integral __x, _Integral __y)
+__algo_gcd(_Integral __x, _Integral __y)
{
do
{
@@ -2456,7 +2456,7 @@
_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/include/numeric b/include/numeric
index 21c3781..1643d64 100644
--- a/include/numeric
+++ b/include/numeric
@@ -53,6 +53,12 @@
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 @@
*__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