diff options
author | Dimitry Andric <dim@FreeBSD.org> | 2022-07-03 14:10:23 +0000 |
---|---|---|
committer | Dimitry Andric <dim@FreeBSD.org> | 2022-07-03 14:10:23 +0000 |
commit | 145449b1e420787bb99721a429341fa6be3adfb6 (patch) | |
tree | 1d56ae694a6de602e348dd80165cf881a36600ed /libcxx/include/__algorithm | |
parent | ecbca9f5fb7d7613d2b94982c4825eb0d33d6842 (diff) |
Diffstat (limited to 'libcxx/include/__algorithm')
144 files changed, 4660 insertions, 890 deletions
diff --git a/libcxx/include/__algorithm/adjacent_find.h b/libcxx/include/__algorithm/adjacent_find.h index 29ad83f96810..83d8c260f27a 100644 --- a/libcxx/include/__algorithm/adjacent_find.h +++ b/libcxx/include/__algorithm/adjacent_find.h @@ -15,7 +15,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/all_of.h b/libcxx/include/__algorithm/all_of.h index 817a4bc89ca0..3af32a577504 100644 --- a/libcxx/include/__algorithm/all_of.h +++ b/libcxx/include/__algorithm/all_of.h @@ -13,7 +13,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/any_of.h b/libcxx/include/__algorithm/any_of.h index f4116d913059..6fe6a0b6b3c4 100644 --- a/libcxx/include/__algorithm/any_of.h +++ b/libcxx/include/__algorithm/any_of.h @@ -13,7 +13,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/binary_search.h b/libcxx/include/__algorithm/binary_search.h index 2558dd0b27b9..121a741d070b 100644 --- a/libcxx/include/__algorithm/binary_search.h +++ b/libcxx/include/__algorithm/binary_search.h @@ -16,28 +16,20 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD -template <class _Compare, class _ForwardIterator, class _Tp> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) -{ - __first = _VSTD::__lower_bound<_Compare>(__first, __last, __value_, __comp); - return __first != __last && !__comp(__value_, *__first); -} - template <class _ForwardIterator, class _Tp, class _Compare> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__binary_search<_Comp_ref>(__first, __last, __value_, __comp); + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + __first = std::lower_bound<_ForwardIterator, _Tp, _Comp_ref>(__first, __last, __value_, __comp); + return __first != __last && !__comp(__value_, *__first); } template <class _ForwardIterator, class _Tp> @@ -46,8 +38,8 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) { - return _VSTD::binary_search(__first, __last, __value_, - __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); + return std::binary_search(__first, __last, __value_, + __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/clamp.h b/libcxx/include/__algorithm/clamp.h index a51c1015be3f..b3762b85a0bc 100644 --- a/libcxx/include/__algorithm/clamp.h +++ b/libcxx/include/__algorithm/clamp.h @@ -10,11 +10,11 @@ #define _LIBCPP___ALGORITHM_CLAMP_H #include <__algorithm/comp.h> +#include <__assert> #include <__config> -#include <__debug> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/comp.h b/libcxx/include/__algorithm/comp.h index b3f971e4f052..62c06ae57f23 100644 --- a/libcxx/include/__algorithm/comp.h +++ b/libcxx/include/__algorithm/comp.h @@ -12,7 +12,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/comp_ref_type.h b/libcxx/include/__algorithm/comp_ref_type.h index 6cc6405686f5..4719871461cf 100644 --- a/libcxx/include/__algorithm/comp_ref_type.h +++ b/libcxx/include/__algorithm/comp_ref_type.h @@ -10,29 +10,24 @@ #define _LIBCPP___ALGORITHM_COMP_REF_TYPE_H #include <__config> - -#ifdef _LIBCPP_DEBUG -# include <__debug> -# include <__utility/declval.h> -#endif +#include <__debug> +#include <__utility/declval.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD -#ifdef _LIBCPP_DEBUG - template <class _Compare> struct __debug_less { _Compare &__comp_; - _LIBCPP_CONSTEXPR_AFTER_CXX17 + _LIBCPP_CONSTEXPR_AFTER_CXX11 __debug_less(_Compare& __c) : __comp_(__c) {} template <class _Tp, class _Up> - _LIBCPP_CONSTEXPR_AFTER_CXX17 + _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _Tp& __x, const _Up& __y) { bool __r = __comp_(__x, __y); @@ -42,7 +37,7 @@ struct __debug_less } template <class _Tp, class _Up> - _LIBCPP_CONSTEXPR_AFTER_CXX17 + _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(_Tp& __x, _Up& __y) { bool __r = __comp_(__x, __y); @@ -52,31 +47,31 @@ struct __debug_less } template <class _LHS, class _RHS> - _LIBCPP_CONSTEXPR_AFTER_CXX17 + _LIBCPP_CONSTEXPR_AFTER_CXX11 inline _LIBCPP_INLINE_VISIBILITY decltype((void)declval<_Compare&>()( declval<_LHS &>(), declval<_RHS &>())) __do_compare_assert(int, _LHS & __l, _RHS & __r) { - _LIBCPP_ASSERT(!__comp_(__l, __r), + _LIBCPP_DEBUG_ASSERT(!__comp_(__l, __r), "Comparator does not induce a strict weak ordering"); + (void)__l; + (void)__r; } template <class _LHS, class _RHS> - _LIBCPP_CONSTEXPR_AFTER_CXX17 + _LIBCPP_CONSTEXPR_AFTER_CXX11 inline _LIBCPP_INLINE_VISIBILITY void __do_compare_assert(long, _LHS &, _RHS &) {} }; -#endif // _LIBCPP_DEBUG - template <class _Comp> struct __comp_ref_type { // Pass the comparator by lvalue reference. Or in debug mode, using a // debugging wrapper that stores a reference. -#ifndef _LIBCPP_DEBUG - typedef _Comp& type; -#else +#ifdef _LIBCPP_ENABLE_DEBUG_MODE typedef __debug_less<_Comp> type; +#else + typedef _Comp& type; #endif }; diff --git a/libcxx/include/__algorithm/copy.h b/libcxx/include/__algorithm/copy.h index 65f0e0b0ef7d..886a1ac6ce3e 100644 --- a/libcxx/include/__algorithm/copy.h +++ b/libcxx/include/__algorithm/copy.h @@ -12,64 +12,93 @@ #include <__algorithm/unwrap_iter.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__iterator/reverse_iterator.h> +#include <__utility/move.h> +#include <__utility/pair.h> #include <cstring> #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD // copy -template <class _InputIterator, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -__copy_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - for (; __first != __last; ++__first, (void) ++__result) - *__result = *__first; - return __result; +template <class _InIter, class _Sent, class _OutIter> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_InIter, _OutIter> __copy_impl(_InIter __first, _Sent __last, _OutIter __result) { + while (__first != __last) { + *__result = *__first; + ++__first; + ++__result; + } + return pair<_InIter, _OutIter>(std::move(__first), std::move(__result)); } -template <class _InputIterator, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY -_OutputIterator -__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - return _VSTD::__copy_constexpr(__first, __last, __result); +template <class _InValueT, + class _OutValueT, + class = __enable_if_t<is_same<typename remove_const<_InValueT>::type, _OutValueT>::value + && is_trivially_copy_assignable<_OutValueT>::value> > +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_InValueT*, _OutValueT*> __copy_impl(_InValueT* __first, _InValueT* __last, _OutValueT* __result) { + if (__libcpp_is_constant_evaluated() +// TODO: Remove this once GCC supports __builtin_memmove during constant evaluation +#ifndef _LIBCPP_COMPILER_GCC + && !is_trivially_copyable<_InValueT>::value +#endif + ) + return std::__copy_impl<_InValueT*, _InValueT*, _OutValueT*>(__first, __last, __result); + const size_t __n = static_cast<size_t>(__last - __first); + if (__n > 0) + ::__builtin_memmove(__result, __first, __n * sizeof(_OutValueT)); + return std::make_pair(__first + __n, __result + __n); +} + +template <class _InIter, class _OutIter, + __enable_if_t<is_same<typename remove_const<__iter_value_type<_InIter> >::type, __iter_value_type<_OutIter> >::value + && __is_cpp17_contiguous_iterator<_InIter>::value + && __is_cpp17_contiguous_iterator<_OutIter>::value + && is_trivially_copy_assignable<__iter_value_type<_OutIter> >::value, int> = 0> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<reverse_iterator<_InIter>, reverse_iterator<_OutIter> > +__copy_impl(reverse_iterator<_InIter> __first, + reverse_iterator<_InIter> __last, + reverse_iterator<_OutIter> __result) { + auto __first_base = std::__unwrap_iter(__first.base()); + auto __last_base = std::__unwrap_iter(__last.base()); + auto __result_base = std::__unwrap_iter(__result.base()); + auto __result_first = __result_base - (__first_base - __last_base); + std::__copy_impl(__last_base, __first_base, __result_first); + return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first))); +} + +template <class _InIter, class _Sent, class _OutIter, + __enable_if_t<!(is_copy_constructible<_InIter>::value + && is_copy_constructible<_Sent>::value + && is_copy_constructible<_OutIter>::value), int> = 0 > +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_InIter, _OutIter> __copy(_InIter __first, _Sent __last, _OutIter __result) { + return std::__copy_impl(std::move(__first), std::move(__last), std::move(__result)); } -template <class _Tp, class _Up> -inline _LIBCPP_INLINE_VISIBILITY -typename enable_if -< - is_same<typename remove_const<_Tp>::type, _Up>::value && - is_trivially_copy_assignable<_Up>::value, - _Up* ->::type -__copy(_Tp* __first, _Tp* __last, _Up* __result) -{ - const size_t __n = static_cast<size_t>(__last - __first); - if (__n > 0) - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); - return __result + __n; +template <class _InIter, class _Sent, class _OutIter, + __enable_if_t<is_copy_constructible<_InIter>::value + && is_copy_constructible<_Sent>::value + && is_copy_constructible<_OutIter>::value, int> = 0> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_InIter, _OutIter> +__copy(_InIter __first, _Sent __last, _OutIter __result) { + auto __ret = std::__copy_impl(std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__result)); + return std::make_pair(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second)); } template <class _InputIterator, class _OutputIterator> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - if (__libcpp_is_constant_evaluated()) { - return _VSTD::__copy_constexpr(__first, __last, __result); - } else { - return _VSTD::__rewrap_iter(__result, - _VSTD::__copy(_VSTD::__unwrap_iter(__first), - _VSTD::__unwrap_iter(__last), - _VSTD::__unwrap_iter(__result))); - } +copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { + return std::__copy(__first, __last, __result).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/copy_backward.h b/libcxx/include/__algorithm/copy_backward.h index ac733290abe4..dd43a91ffa87 100644 --- a/libcxx/include/__algorithm/copy_backward.h +++ b/libcxx/include/__algorithm/copy_backward.h @@ -9,69 +9,43 @@ #ifndef _LIBCPP___ALGORITHM_COPY_BACKWARD_H #define _LIBCPP___ALGORITHM_COPY_BACKWARD_H +#include <__algorithm/copy.h> #include <__algorithm/unwrap_iter.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__iterator/reverse_iterator.h> #include <cstring> #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD -template <class _BidirectionalIterator, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -__copy_backward_constexpr(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result) -{ - while (__first != __last) - *--__result = *--__last; - return __result; +template <class _Iter1, class _Sent1, class _Iter2> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter2> __copy_backward_impl(_Iter1 __first, _Sent1 __last, _Iter2 __result) { + auto __ret = std::__copy(reverse_iterator<_Iter1>(__last), + reverse_iterator<_Sent1>(__first), + reverse_iterator<_Iter2>(__result)); + return pair<_Iter1, _Iter2>(__ret.first.base(), __ret.second.base()); } -template <class _BidirectionalIterator, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY -_OutputIterator -__copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result) -{ - return _VSTD::__copy_backward_constexpr(__first, __last, __result); -} - -template <class _Tp, class _Up> -inline _LIBCPP_INLINE_VISIBILITY -typename enable_if -< - is_same<typename remove_const<_Tp>::type, _Up>::value && - is_trivially_copy_assignable<_Up>::value, - _Up* ->::type -__copy_backward(_Tp* __first, _Tp* __last, _Up* __result) -{ - const size_t __n = static_cast<size_t>(__last - __first); - if (__n > 0) - { - __result -= __n; - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); - } - return __result; +template <class _Iter1, class _Sent1, class _Iter2> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter2> __copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result) { + auto __ret = std::__copy_backward_impl(std::__unwrap_iter(__first), + std::__unwrap_iter(__last), + std::__unwrap_iter(__result)); + return pair<_Iter1, _Iter2>(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second)); } template <class _BidirectionalIterator1, class _BidirectionalIterator2> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator2 -copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, - _BidirectionalIterator2 __result) -{ - if (__libcpp_is_constant_evaluated()) { - return _VSTD::__copy_backward_constexpr(__first, __last, __result); - } else { - return _VSTD::__rewrap_iter(__result, - _VSTD::__copy_backward(_VSTD::__unwrap_iter(__first), - _VSTD::__unwrap_iter(__last), - _VSTD::__unwrap_iter(__result))); - } +copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result) { + return std::__copy_backward(__first, __last, __result).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/copy_if.h b/libcxx/include/__algorithm/copy_if.h index d32514d999b5..9c3cd29e2413 100644 --- a/libcxx/include/__algorithm/copy_if.h +++ b/libcxx/include/__algorithm/copy_if.h @@ -12,7 +12,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/copy_n.h b/libcxx/include/__algorithm/copy_n.h index cdcc0d50dbf1..8b915af63c0d 100644 --- a/libcxx/include/__algorithm/copy_n.h +++ b/libcxx/include/__algorithm/copy_n.h @@ -15,7 +15,7 @@ #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/count.h b/libcxx/include/__algorithm/count.h index 81a2c186f83b..e18128cae8a8 100644 --- a/libcxx/include/__algorithm/count.h +++ b/libcxx/include/__algorithm/count.h @@ -14,7 +14,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/count_if.h b/libcxx/include/__algorithm/count_if.h index 00f5d671da57..1ec2d83394e1 100644 --- a/libcxx/include/__algorithm/count_if.h +++ b/libcxx/include/__algorithm/count_if.h @@ -14,7 +14,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/equal.h b/libcxx/include/__algorithm/equal.h index 4c9ad05ad6b8..ca1bc6bc5665 100644 --- a/libcxx/include/__algorithm/equal.h +++ b/libcxx/include/__algorithm/equal.h @@ -16,7 +16,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/equal_range.h b/libcxx/include/__algorithm/equal_range.h index e13f0bdd9695..2a07364bb66f 100644 --- a/libcxx/include/__algorithm/equal_range.h +++ b/libcxx/include/__algorithm/equal_range.h @@ -12,13 +12,18 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> #include <__algorithm/half_positive.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/lower_bound.h> #include <__algorithm/upper_bound.h> #include <__config> -#include <iterator> +#include <__functional/identity.h> +#include <__iterator/advance.h> +#include <__iterator/distance.h> +#include <__iterator/iterator_traits.h> +#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD @@ -46,10 +51,11 @@ __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va } else { + auto __proj = std::__identity(); _ForwardIterator __mp1 = __m; return pair<_ForwardIterator, _ForwardIterator> ( - _VSTD::__lower_bound<_Compare>(__first, __m, __value_, __comp), + _VSTD::__lower_bound_impl<_StdIterOps>(__first, __m, __value_, __comp, __proj), _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value_, __comp) ); } diff --git a/libcxx/include/__algorithm/fill.h b/libcxx/include/__algorithm/fill.h index 0cb36b02c831..be5b4740a52a 100644 --- a/libcxx/include/__algorithm/fill.h +++ b/libcxx/include/__algorithm/fill.h @@ -15,7 +15,7 @@ #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/fill_n.h b/libcxx/include/__algorithm/fill_n.h index 857ac1415731..590c8f38f3fd 100644 --- a/libcxx/include/__algorithm/fill_n.h +++ b/libcxx/include/__algorithm/fill_n.h @@ -14,7 +14,7 @@ #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/find.h b/libcxx/include/__algorithm/find.h index 2a6dfbe41a94..641b85e2f645 100644 --- a/libcxx/include/__algorithm/find.h +++ b/libcxx/include/__algorithm/find.h @@ -13,7 +13,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/find_end.h b/libcxx/include/__algorithm/find_end.h index dd0f7d7ac03d..0220c0939711 100644 --- a/libcxx/include/__algorithm/find_end.h +++ b/libcxx/include/__algorithm/find_end.h @@ -15,7 +15,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/find_first_of.h b/libcxx/include/__algorithm/find_first_of.h index 69354f61769f..b968329fc318 100644 --- a/libcxx/include/__algorithm/find_first_of.h +++ b/libcxx/include/__algorithm/find_first_of.h @@ -15,7 +15,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/find_if.h b/libcxx/include/__algorithm/find_if.h index a94196a16ac5..aa98171a1f61 100644 --- a/libcxx/include/__algorithm/find_if.h +++ b/libcxx/include/__algorithm/find_if.h @@ -13,7 +13,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/find_if_not.h b/libcxx/include/__algorithm/find_if_not.h index e057db5efa49..61ddab0b9805 100644 --- a/libcxx/include/__algorithm/find_if_not.h +++ b/libcxx/include/__algorithm/find_if_not.h @@ -13,7 +13,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/for_each.h b/libcxx/include/__algorithm/for_each.h index 1612ffa5c002..bfbd37c3a3a4 100644 --- a/libcxx/include/__algorithm/for_each.h +++ b/libcxx/include/__algorithm/for_each.h @@ -13,7 +13,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/for_each_n.h b/libcxx/include/__algorithm/for_each_n.h index 00e3fb9c1db8..2552b40c2781 100644 --- a/libcxx/include/__algorithm/for_each_n.h +++ b/libcxx/include/__algorithm/for_each_n.h @@ -14,7 +14,7 @@ #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/generate.h b/libcxx/include/__algorithm/generate.h index 10834cdb7438..dacbd8c68195 100644 --- a/libcxx/include/__algorithm/generate.h +++ b/libcxx/include/__algorithm/generate.h @@ -12,7 +12,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/generate_n.h b/libcxx/include/__algorithm/generate_n.h index 595007cdd34b..2650e9e5d8b7 100644 --- a/libcxx/include/__algorithm/generate_n.h +++ b/libcxx/include/__algorithm/generate_n.h @@ -13,7 +13,7 @@ #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/half_positive.h b/libcxx/include/__algorithm/half_positive.h index 5d36ff5da985..7666ef1449c6 100644 --- a/libcxx/include/__algorithm/half_positive.h +++ b/libcxx/include/__algorithm/half_positive.h @@ -13,7 +13,7 @@ #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/in_found_result.h b/libcxx/include/__algorithm/in_found_result.h new file mode 100644 index 000000000000..d43f45cd80ef --- /dev/null +++ b/libcxx/include/__algorithm/in_found_result.h @@ -0,0 +1,49 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_IN_FOUND_RESULT_H +#define _LIBCPP___ALGORITHM_IN_FOUND_RESULT_H + +#include <__concepts/convertible_to.h> +#include <__config> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +template <class _InIter1> +struct in_found_result { + _LIBCPP_NO_UNIQUE_ADDRESS _InIter1 in; + bool found; + + template <class _InIter2> + requires convertible_to<const _InIter1&, _InIter2> + _LIBCPP_HIDE_FROM_ABI constexpr operator in_found_result<_InIter2>() const & { + return {in, found}; + } + + template <class _InIter2> + requires convertible_to<_InIter1, _InIter2> + _LIBCPP_HIDE_FROM_ABI constexpr operator in_found_result<_InIter2>() && { + return {std::move(in), found}; + } +}; +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_IN_FOUND_RESULT_H diff --git a/libcxx/include/__algorithm/in_fun_result.h b/libcxx/include/__algorithm/in_fun_result.h new file mode 100644 index 000000000000..21efa655063d --- /dev/null +++ b/libcxx/include/__algorithm/in_fun_result.h @@ -0,0 +1,49 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_IN_FUN_RESULT_H +#define _LIBCPP___ALGORITHM_IN_FUN_RESULT_H + +#include <__concepts/convertible_to.h> +#include <__config> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +namespace ranges { +template <class _InIter1, class _Func1> +struct in_fun_result { + _LIBCPP_NO_UNIQUE_ADDRESS _InIter1 in; + _LIBCPP_NO_UNIQUE_ADDRESS _Func1 fun; + + template <class _InIter2, class _Func2> + requires convertible_to<const _InIter1&, _InIter2> && convertible_to<const _Func1&, _Func2> + _LIBCPP_HIDE_FROM_ABI constexpr operator in_fun_result<_InIter2, _Func2>() const & { + return {in, fun}; + } + + template <class _InIter2, class _Func2> + requires convertible_to<_InIter1, _InIter2> && convertible_to<_Func1, _Func2> + _LIBCPP_HIDE_FROM_ABI constexpr operator in_fun_result<_InIter2, _Func2>() && { + return {std::move(in), std::move(fun)}; + } +}; +} // namespace ranges + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_IN_FUN_RESULT_H diff --git a/libcxx/include/__algorithm/in_in_out_result.h b/libcxx/include/__algorithm/in_in_out_result.h index e365eb58eb62..e45fef187e0d 100644 --- a/libcxx/include/__algorithm/in_in_out_result.h +++ b/libcxx/include/__algorithm/in_in_out_result.h @@ -14,35 +14,43 @@ #include <__config> #include <__utility/move.h> +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + _LIBCPP_BEGIN_NAMESPACE_STD -#ifndef _LIBCPP_HAS_NO_CONCEPTS +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) namespace ranges { -template <class _I1, class _I2, class _O1> + +template <class _InIter1, class _InIter2, class _OutIter1> struct in_in_out_result { - [[no_unique_address]] _I1 in1; - [[no_unique_address]] _I2 in2; - [[no_unique_address]] _O1 out; + _LIBCPP_NO_UNIQUE_ADDRESS _InIter1 in1; + _LIBCPP_NO_UNIQUE_ADDRESS _InIter2 in2; + _LIBCPP_NO_UNIQUE_ADDRESS _OutIter1 out; - template <class _II1, class _II2, class _OO1> - requires convertible_to<const _I1&, _II1> && convertible_to<const _I2&, _II2> && convertible_to<const _O1&, _OO1> + template <class _InIter3, class _InIter4, class _OutIter2> + requires convertible_to<const _InIter1&, _InIter3> + && convertible_to<const _InIter2&, _InIter4> && convertible_to<const _OutIter1&, _OutIter2> _LIBCPP_HIDE_FROM_ABI constexpr - operator in_in_out_result<_II1, _II2, _OO1>() const& { + operator in_in_out_result<_InIter3, _InIter4, _OutIter2>() const& { return {in1, in2, out}; } - template <class _II1, class _II2, class _OO1> - requires convertible_to<_I1, _II1> && convertible_to<_I2, _II2> && convertible_to<_O1, _OO1> + template <class _InIter3, class _InIter4, class _OutIter2> + requires convertible_to<_InIter1, _InIter3> + && convertible_to<_InIter2, _InIter4> && convertible_to<_OutIter1, _OutIter2> _LIBCPP_HIDE_FROM_ABI constexpr - operator in_in_out_result<_II1, _II2, _OO1>() && { - return {_VSTD::move(in1), _VSTD::move(in2), _VSTD::move(out)}; + operator in_in_out_result<_InIter3, _InIter4, _OutIter2>() && { + return {std::move(in1), std::move(in2), std::move(out)}; } }; + } // namespace ranges -#endif // _LIBCPP_HAS_NO_CONCEPTS +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) _LIBCPP_END_NAMESPACE_STD -#endif // _LIBCPP___ALGORITHM_IN_IN_RESULT_H +#endif // _LIBCPP___ALGORITHM_IN_IN_OUT_RESULT_H diff --git a/libcxx/include/__algorithm/in_in_result.h b/libcxx/include/__algorithm/in_in_result.h index ed14ecedbbdf..39e64ced33b2 100644 --- a/libcxx/include/__algorithm/in_in_result.h +++ b/libcxx/include/__algorithm/in_in_result.h @@ -14,31 +14,39 @@ #include <__config> #include <__utility/move.h> +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + _LIBCPP_BEGIN_NAMESPACE_STD -#ifndef _LIBCPP_HAS_NO_CONCEPTS +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) namespace ranges { -template <class _I1, class _I2> + +template <class _InIter1, class _InIter2> struct in_in_result { - [[no_unique_address]] _I1 in1; - [[no_unique_address]] _I2 in2; + _LIBCPP_NO_UNIQUE_ADDRESS _InIter1 in1; + _LIBCPP_NO_UNIQUE_ADDRESS _InIter2 in2; - template <class _II1, class _II2> - requires convertible_to<const _I1&, _II1> && convertible_to<const _I2&, _II2> + template <class _InIter3, class _InIter4> + requires convertible_to<const _InIter1&, _InIter3> && convertible_to<const _InIter2&, _InIter4> _LIBCPP_HIDE_FROM_ABI constexpr - operator in_in_result<_II1, _II2>() const & { + operator in_in_result<_InIter3, _InIter4>() const & { return {in1, in2}; } - template <class _II1, class _II2> - requires convertible_to<_I1, _II1> && convertible_to<_I2, _II2> + template <class _InIter3, class _InIter4> + requires convertible_to<_InIter1, _InIter3> && convertible_to<_InIter2, _InIter4> _LIBCPP_HIDE_FROM_ABI constexpr - operator in_in_result<_II1, _II2>() && { return {_VSTD::move(in1), _VSTD::move(in2)}; } + operator in_in_result<_InIter3, _InIter4>() && { + return {std::move(in1), std::move(in2)}; + } }; + } // namespace ranges -#endif // _LIBCPP_HAS_NO_CONCEPTS +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/in_out_out_result.h b/libcxx/include/__algorithm/in_out_out_result.h new file mode 100644 index 000000000000..52a883b17627 --- /dev/null +++ b/libcxx/include/__algorithm/in_out_out_result.h @@ -0,0 +1,54 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_IN_OUT_OUT_RESULT_H +#define _LIBCPP___ALGORITHM_IN_OUT_OUT_RESULT_H + +#include <__concepts/convertible_to.h> +#include <__config> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +namespace ranges { +template <class _InIter1, class _OutIter1, class _OutIter2> +struct in_out_out_result { + _LIBCPP_NO_UNIQUE_ADDRESS _InIter1 in; + _LIBCPP_NO_UNIQUE_ADDRESS _OutIter1 out1; + _LIBCPP_NO_UNIQUE_ADDRESS _OutIter2 out2; + + template <class _InIter2, class _OutIter3, class _OutIter4> + requires convertible_to<const _InIter1&, _InIter2> + && convertible_to<const _OutIter1&, _OutIter3> && convertible_to<const _OutIter2&, _OutIter4> + _LIBCPP_HIDE_FROM_ABI constexpr + operator in_out_out_result<_InIter2, _OutIter3, _OutIter4>() const& { + return {in, out1, out2}; + } + + template <class _InIter2, class _OutIter3, class _OutIter4> + requires convertible_to<_InIter1, _InIter2> + && convertible_to<_OutIter1, _OutIter3> && convertible_to<_OutIter2, _OutIter4> + _LIBCPP_HIDE_FROM_ABI constexpr + operator in_out_out_result<_InIter2, _OutIter3, _OutIter4>() && { + return {std::move(in), std::move(out1), std::move(out2)}; + } +}; +} // namespace ranges + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_IN_OUT_OUT_RESULT_H diff --git a/libcxx/include/__algorithm/in_out_result.h b/libcxx/include/__algorithm/in_out_result.h index 8a58d6ada10c..47e6f3907943 100644 --- a/libcxx/include/__algorithm/in_out_result.h +++ b/libcxx/include/__algorithm/in_out_result.h @@ -15,37 +15,38 @@ #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD -#if !defined(_LIBCPP_HAS_NO_CONCEPTS) +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + namespace ranges { -template<class _InputIterator, class _OutputIterator> +template<class _InIter1, class _OutIter1> struct in_out_result { - [[no_unique_address]] _InputIterator in; - [[no_unique_address]] _OutputIterator out; + _LIBCPP_NO_UNIQUE_ADDRESS _InIter1 in; + _LIBCPP_NO_UNIQUE_ADDRESS _OutIter1 out; - template <class _InputIterator2, class _OutputIterator2> - requires convertible_to<const _InputIterator&, _InputIterator2> && convertible_to<const _OutputIterator&, - _OutputIterator2> + template <class _InIter2, class _OutIter2> + requires convertible_to<const _InIter1&, _InIter2> && convertible_to<const _OutIter1&, _OutIter2> _LIBCPP_HIDE_FROM_ABI - constexpr operator in_out_result<_InputIterator2, _OutputIterator2>() const & { + constexpr operator in_out_result<_InIter2, _OutIter2>() const & { return {in, out}; } - template <class _InputIterator2, class _OutputIterator2> - requires convertible_to<_InputIterator, _InputIterator2> && convertible_to<_OutputIterator, _OutputIterator2> + template <class _InIter2, class _OutIter2> + requires convertible_to<_InIter1, _InIter2> && convertible_to<_OutIter1, _OutIter2> _LIBCPP_HIDE_FROM_ABI - constexpr operator in_out_result<_InputIterator2, _OutputIterator2>() && { - return {_VSTD::move(in), _VSTD::move(out)}; + constexpr operator in_out_result<_InIter2, _OutIter2>() && { + return {std::move(in), std::move(out)}; } }; } // namespace ranges -#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/includes.h b/libcxx/include/__algorithm/includes.h index 9d0bc694c0d3..4c87e8d22116 100644 --- a/libcxx/include/__algorithm/includes.h +++ b/libcxx/include/__algorithm/includes.h @@ -15,7 +15,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/inplace_merge.h b/libcxx/include/__algorithm/inplace_merge.h index e6f1efc011b1..58919ddbae76 100644 --- a/libcxx/include/__algorithm/inplace_merge.h +++ b/libcxx/include/__algorithm/inplace_merge.h @@ -17,12 +17,15 @@ #include <__algorithm/rotate.h> #include <__algorithm/upper_bound.h> #include <__config> +#include <__iterator/advance.h> +#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> +#include <__iterator/reverse_iterator.h> #include <__utility/swap.h> #include <memory> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_PUSH_MACROS @@ -166,7 +169,7 @@ __inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, __len11 = __len1 / 2; __m1 = __first; _VSTD::advance(__m1, __len11); - __m2 = _VSTD::__lower_bound<_Compare>(__middle, __last, *__m1, __comp); + __m2 = std::lower_bound(__middle, __last, *__m1, __comp); __len21 = _VSTD::distance(__middle, __m2); } difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) @@ -208,7 +211,10 @@ inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _ difference_type __len1 = _VSTD::distance(__first, __middle); difference_type __len2 = _VSTD::distance(__middle, __last); difference_type __buf_size = _VSTD::min(__len1, __len2); +// TODO: Remove the use of std::get_temporary_buffer +_LIBCPP_SUPPRESS_DEPRECATED_PUSH pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size); +_LIBCPP_SUPPRESS_DEPRECATED_POP unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first); typedef typename __comp_ref_type<_Compare>::type _Comp_ref; return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2, diff --git a/libcxx/include/__algorithm/is_heap.h b/libcxx/include/__algorithm/is_heap.h index 925ba8bfb8bd..fe44e634f6dd 100644 --- a/libcxx/include/__algorithm/is_heap.h +++ b/libcxx/include/__algorithm/is_heap.h @@ -16,7 +16,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_heap_until.h b/libcxx/include/__algorithm/is_heap_until.h index aa23b6d039d3..39f313eb0d3f 100644 --- a/libcxx/include/__algorithm/is_heap_until.h +++ b/libcxx/include/__algorithm/is_heap_until.h @@ -15,7 +15,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_partitioned.h b/libcxx/include/__algorithm/is_partitioned.h index e5b2214aa069..b4f421cfc053 100644 --- a/libcxx/include/__algorithm/is_partitioned.h +++ b/libcxx/include/__algorithm/is_partitioned.h @@ -12,7 +12,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_permutation.h b/libcxx/include/__algorithm/is_permutation.h index 344aa763ad0e..cdd742048412 100644 --- a/libcxx/include/__algorithm/is_permutation.h +++ b/libcxx/include/__algorithm/is_permutation.h @@ -17,7 +17,7 @@ #include <__iterator/next.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_sorted.h b/libcxx/include/__algorithm/is_sorted.h index 57953295a888..56de95bb31b7 100644 --- a/libcxx/include/__algorithm/is_sorted.h +++ b/libcxx/include/__algorithm/is_sorted.h @@ -16,7 +16,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_sorted_until.h b/libcxx/include/__algorithm/is_sorted_until.h index 57cad47761d9..338d28508c17 100644 --- a/libcxx/include/__algorithm/is_sorted_until.h +++ b/libcxx/include/__algorithm/is_sorted_until.h @@ -15,7 +15,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/iter_swap.h b/libcxx/include/__algorithm/iter_swap.h index 9f7d0d77630c..038859e1361d 100644 --- a/libcxx/include/__algorithm/iter_swap.h +++ b/libcxx/include/__algorithm/iter_swap.h @@ -14,7 +14,7 @@ #include <__utility/swap.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h new file mode 100644 index 000000000000..c02f9bf649df --- /dev/null +++ b/libcxx/include/__algorithm/iterator_operations.h @@ -0,0 +1,47 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H +#define _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H + +#include <__config> +#include <__iterator/advance.h> +#include <__iterator/distance.h> +#include <__iterator/iterator_traits.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) +struct _RangesIterOps { + static constexpr auto advance = ranges::advance; + static constexpr auto distance = ranges::distance; +}; +#endif + +struct _StdIterOps { + + template <class _Iterator, class _Distance> + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void advance(_Iterator& __iter, _Distance __count) { + return std::advance(__iter, __count); + } + + template <class _Iterator> + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 + typename iterator_traits<_Iterator>::difference_type distance(_Iterator __first, _Iterator __last) { + return std::distance(__first, __last); + } + +}; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H diff --git a/libcxx/include/__algorithm/lexicographical_compare.h b/libcxx/include/__algorithm/lexicographical_compare.h index 55a1da620125..30ddf2408120 100644 --- a/libcxx/include/__algorithm/lexicographical_compare.h +++ b/libcxx/include/__algorithm/lexicographical_compare.h @@ -15,7 +15,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/lower_bound.h b/libcxx/include/__algorithm/lower_bound.h index 663a0b16228e..fbcd5c7e908a 100644 --- a/libcxx/include/__algorithm/lower_bound.h +++ b/libcxx/include/__algorithm/lower_bound.h @@ -11,54 +11,55 @@ #include <__algorithm/comp.h> #include <__algorithm/half_positive.h> +#include <__algorithm/iterator_operations.h> #include <__config> -#include <iterator> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__iterator/advance.h> +#include <__iterator/distance.h> +#include <__iterator/iterator_traits.h> +#include <__type_traits/is_callable.h> +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD -template <class _Compare, class _ForwardIterator, class _Tp> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) -{ - typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; - difference_type __len = _VSTD::distance(__first, __last); - while (__len != 0) - { - difference_type __l2 = _VSTD::__half_positive(__len); - _ForwardIterator __m = __first; - _VSTD::advance(__m, __l2); - if (__comp(*__m, __value_)) - { - __first = ++__m; - __len -= __l2 + 1; - } - else - __len = __l2; +template <class _IterOps, class _Iter, class _Sent, class _Type, class _Proj, class _Comp> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_Iter __lower_bound_impl(_Iter __first, _Sent __last, const _Type& __value, _Comp& __comp, _Proj& __proj) { + auto __len = _IterOps::distance(__first, __last); + + while (__len != 0) { + auto __l2 = std::__half_positive(__len); + _Iter __m = __first; + _IterOps::advance(__m, __l2); + if (std::__invoke(__comp, std::__invoke(__proj, *__m), __value)) { + __first = ++__m; + __len -= __l2 + 1; + } else { + __len = __l2; } - return __first; + } + return __first; } template <class _ForwardIterator, class _Tp, class _Compare> -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator -lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) -{ - return _VSTD::__lower_bound<_Compare&>(__first, __last, __value_, __comp); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { + static_assert(__is_callable<_Compare, decltype(*__first), const _Tp&>::value, + "The comparator has to be callable"); + auto __proj = std::__identity(); + return std::__lower_bound_impl<_StdIterOps>(__first, __last, __value_, __comp, __proj); } template <class _ForwardIterator, class _Tp> -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator -lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) -{ - return _VSTD::lower_bound(__first, __last, __value_, - __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) { + return std::lower_bound(__first, __last, __value_, + __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/make_heap.h b/libcxx/include/__algorithm/make_heap.h index f489addaf5cc..acac0aabf1e4 100644 --- a/libcxx/include/__algorithm/make_heap.h +++ b/libcxx/include/__algorithm/make_heap.h @@ -16,7 +16,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/make_projected.h b/libcxx/include/__algorithm/make_projected.h new file mode 100644 index 000000000000..8141c4ed176f --- /dev/null +++ b/libcxx/include/__algorithm/make_projected.h @@ -0,0 +1,51 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_MAKE_PROJECTED_H +#define _LIBCPP___ALGORITHM_MAKE_PROJECTED_H + +#include <__concepts/same_as.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__utility/forward.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _Comp, class _Proj> +_LIBCPP_HIDE_FROM_ABI constexpr static +decltype(auto) __make_projected_comp(_Comp& __comp, _Proj& __proj) { + if constexpr (same_as<_Proj, identity>) { + // Avoid creating the lambda and just use the pristine comparator -- for certain algorithms, this would enable + // optimizations that rely on the type of the comparator. + return __comp; + + } else { + return [&](auto&& __lhs, auto&& __rhs) { + return std::invoke(__comp, + std::invoke(__proj, std::forward<decltype(__lhs)>(__lhs)), + std::invoke(__proj, std::forward<decltype(__rhs)>(__rhs))); + }; + } +} + +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_MAKE_PROJECTED_H diff --git a/libcxx/include/__algorithm/max.h b/libcxx/include/__algorithm/max.h index 0bbc971e0a9c..345b235a2193 100644 --- a/libcxx/include/__algorithm/max.h +++ b/libcxx/include/__algorithm/max.h @@ -16,7 +16,7 @@ #include <initializer_list> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_PUSH_MACROS diff --git a/libcxx/include/__algorithm/max_element.h b/libcxx/include/__algorithm/max_element.h index db2937260582..795ec8e1ddc1 100644 --- a/libcxx/include/__algorithm/max_element.h +++ b/libcxx/include/__algorithm/max_element.h @@ -15,7 +15,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/merge.h b/libcxx/include/__algorithm/merge.h index 91826493771a..48360ed5b445 100644 --- a/libcxx/include/__algorithm/merge.h +++ b/libcxx/include/__algorithm/merge.h @@ -16,7 +16,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/min.h b/libcxx/include/__algorithm/min.h index ed2d3b87828a..3d8c73d78f11 100644 --- a/libcxx/include/__algorithm/min.h +++ b/libcxx/include/__algorithm/min.h @@ -16,7 +16,7 @@ #include <initializer_list> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_PUSH_MACROS diff --git a/libcxx/include/__algorithm/min_element.h b/libcxx/include/__algorithm/min_element.h index 407c7f93336d..129833d42bda 100644 --- a/libcxx/include/__algorithm/min_element.h +++ b/libcxx/include/__algorithm/min_element.h @@ -15,7 +15,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/min_max_result.h b/libcxx/include/__algorithm/min_max_result.h new file mode 100644 index 000000000000..ca77dcc5725a --- /dev/null +++ b/libcxx/include/__algorithm/min_max_result.h @@ -0,0 +1,56 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_MIN_MAX_RESULT_H +#define _LIBCPP___ALGORITHM_MIN_MAX_RESULT_H + +#include <__concepts/convertible_to.h> +#include <__config> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +namespace ranges { + +template <class _T1> +struct min_max_result { + _LIBCPP_NO_UNIQUE_ADDRESS _T1 min; + _LIBCPP_NO_UNIQUE_ADDRESS _T1 max; + + template <class _T2> + requires convertible_to<const _T1&, _T2> + _LIBCPP_HIDE_FROM_ABI constexpr operator min_max_result<_T2>() const & { + return {min, max}; + } + + template <class _T2> + requires convertible_to<_T1, _T2> + _LIBCPP_HIDE_FROM_ABI constexpr operator min_max_result<_T2>() && { + return {std::move(min), std::move(max)}; + } +}; + +} // namespace ranges + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ALGORITHM_MIN_MAX_RESULT_H diff --git a/libcxx/include/__algorithm/minmax.h b/libcxx/include/__algorithm/minmax.h index 0bf88a70b8aa..7e10b8b8350c 100644 --- a/libcxx/include/__algorithm/minmax.h +++ b/libcxx/include/__algorithm/minmax.h @@ -10,12 +10,15 @@ #define _LIBCPP___ALGORITHM_MINMAX_H #include <__algorithm/comp.h> +#include <__algorithm/minmax_element.h> #include <__config> +#include <__functional/identity.h> +#include <__type_traits/is_callable.h> +#include <__utility/pair.h> #include <initializer_list> -#include <utility> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD @@ -36,47 +39,18 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<const _Tp&, const _Tp&> minmax(const _Tp& __a, const _Tp& __b) { - return _VSTD::minmax(__a, __b, __less<_Tp>()); + return std::minmax(__a, __b, __less<_Tp>()); } #ifndef _LIBCPP_CXX03_LANG template<class _Tp, class _Compare> -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<_Tp, _Tp> -minmax(initializer_list<_Tp> __t, _Compare __comp) -{ - typedef typename initializer_list<_Tp>::const_iterator _Iter; - _Iter __first = __t.begin(); - _Iter __last = __t.end(); - pair<_Tp, _Tp> __result(*__first, *__first); - - ++__first; - if (__t.size() % 2 == 0) - { - if (__comp(*__first, __result.first)) - __result.first = *__first; - else - __result.second = *__first; - ++__first; - } - - while (__first != __last) - { - _Tp __prev = *__first++; - if (__comp(*__first, __prev)) { - if ( __comp(*__first, __result.first)) __result.first = *__first; - if (!__comp(__prev, __result.second)) __result.second = __prev; - } - else { - if ( __comp(__prev, __result.first)) __result.first = __prev; - if (!__comp(*__first, __result.second)) __result.second = *__first; - } - - __first++; - } - return __result; +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Tp, _Tp> minmax(initializer_list<_Tp> __t, _Compare __comp) { + static_assert(__is_callable<_Compare, _Tp, _Tp>::value, "The comparator has to be callable"); + __identity __proj; + auto __ret = std::__minmax_element_impl(__t.begin(), __t.end(), __comp, __proj); + return pair<_Tp, _Tp>(*__ret.first, *__ret.second); } template<class _Tp> @@ -85,7 +59,7 @@ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Tp, _Tp> minmax(initializer_list<_Tp> __t) { - return _VSTD::minmax(__t, __less<_Tp>()); + return std::minmax(__t, __less<_Tp>()); } #endif // _LIBCPP_CXX03_LANG diff --git a/libcxx/include/__algorithm/minmax_element.h b/libcxx/include/__algorithm/minmax_element.h index 5d768603843b..fe5f20bf1c7f 100644 --- a/libcxx/include/__algorithm/minmax_element.h +++ b/libcxx/include/__algorithm/minmax_element.h @@ -11,73 +11,89 @@ #include <__algorithm/comp.h> #include <__config> +#include <__functional/identity.h> #include <__iterator/iterator_traits.h> -#include <utility> +#include <__utility/pair.h> +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD +template <class _Comp, class _Proj> +class _MinmaxElementLessFunc { + _Comp& __comp; + _Proj& __proj; + +public: + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR + _MinmaxElementLessFunc(_Comp& __comp_, _Proj& __proj_) : __comp(__comp_), __proj(__proj_) {} + + template <class _Iter> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 + bool operator()(_Iter& __it1, _Iter& __it2) { + return std::__invoke(__comp, std::__invoke(__proj, *__it1), std::__invoke(__proj, *__it2)); + } +}; + +template <class _Iter, class _Sent, class _Proj, class _Comp> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter, _Iter> __minmax_element_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __less = _MinmaxElementLessFunc<_Comp, _Proj>(__comp, __proj); + + pair<_Iter, _Iter> __result(__first, __first); + if (__first == __last || ++__first == __last) + return __result; + + if (__less(__first, __result.first)) + __result.first = __first; + else + __result.second = __first; + + while (++__first != __last) { + _Iter __i = __first; + if (++__first == __last) { + if (__less(__i, __result.first)) + __result.first = __i; + else if (!__less(__i, __result.second)) + __result.second = __i; + return __result; + } + + if (__less(__first, __i)) { + if (__less(__first, __result.first)) + __result.first = __first; + if (!__less(__i, __result.second)) + __result.second = __i; + } else { + if (__less(__i, __result.first)) + __result.first = __i; + if (!__less(__first, __result.second)) + __result.second = __first; + } + } + + return __result; +} + template <class _ForwardIterator, class _Compare> _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_ForwardIterator, _ForwardIterator> -minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) -{ +minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp) { static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value, - "std::minmax_element requires a ForwardIterator"); - pair<_ForwardIterator, _ForwardIterator> __result(__first, __first); - if (__first != __last) - { - if (++__first != __last) - { - if (__comp(*__first, *__result.first)) - __result.first = __first; - else - __result.second = __first; - while (++__first != __last) - { - _ForwardIterator __i = __first; - if (++__first == __last) - { - if (__comp(*__i, *__result.first)) - __result.first = __i; - else if (!__comp(*__i, *__result.second)) - __result.second = __i; - break; - } - else - { - if (__comp(*__first, *__i)) - { - if (__comp(*__first, *__result.first)) - __result.first = __first; - if (!__comp(*__i, *__result.second)) - __result.second = __i; - } - else - { - if (__comp(*__i, *__result.first)) - __result.first = __i; - if (!__comp(*__first, *__result.second)) - __result.second = __first; - } - } - } - } - } - return __result; + "std::minmax_element requires a ForwardIterator"); + static_assert(__is_callable<_Compare, decltype(*__first), decltype(*__first)>::value, + "The comparator has to be callable"); + auto __proj = __identity(); + return std::__minmax_element_impl(__first, __last, __comp, __proj); } template <class _ForwardIterator> -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 -pair<_ForwardIterator, _ForwardIterator> -minmax_element(_ForwardIterator __first, _ForwardIterator __last) -{ - return _VSTD::minmax_element(__first, __last, - __less<typename iterator_traits<_ForwardIterator>::value_type>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_ForwardIterator, _ForwardIterator> minmax_element(_ForwardIterator __first, _ForwardIterator __last) { + return std::minmax_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/mismatch.h b/libcxx/include/__algorithm/mismatch.h index 230ade03df19..f2011faf2f9a 100644 --- a/libcxx/include/__algorithm/mismatch.h +++ b/libcxx/include/__algorithm/mismatch.h @@ -13,10 +13,10 @@ #include <__algorithm/comp.h> #include <__config> #include <__iterator/iterator_traits.h> -#include <utility> +#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/move.h b/libcxx/include/__algorithm/move.h index fa118f471669..0b08d31c176e 100644 --- a/libcxx/include/__algorithm/move.h +++ b/libcxx/include/__algorithm/move.h @@ -11,66 +11,103 @@ #include <__algorithm/unwrap_iter.h> #include <__config> +#include <__iterator/iterator_traits.h> +#include <__iterator/reverse_iterator.h> #include <__utility/move.h> +#include <__utility/pair.h> #include <cstring> #include <type_traits> -#include <utility> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD // move -template <class _InputIterator, class _OutputIterator> +template <class _InIter, class _Sent, class _OutIter> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 -_OutputIterator -__move_constexpr(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - for (; __first != __last; ++__first, (void) ++__result) - *__result = _VSTD::move(*__first); - return __result; +pair<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) { + while (__first != __last) { + *__result = std::move(*__first); + ++__first; + ++__result; + } + return std::make_pair(std::move(__first), std::move(__result)); } -template <class _InputIterator, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 -_OutputIterator -__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - return _VSTD::__move_constexpr(__first, __last, __result); +template <class _InType, + class _OutType, + class = __enable_if_t<is_same<typename remove_const<_InType>::type, _OutType>::value + && is_trivially_move_assignable<_OutType>::value> > +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_InType*, _OutType*> __move_impl(_InType* __first, _InType* __last, _OutType* __result) { + if (__libcpp_is_constant_evaluated() +// TODO: Remove this once GCC supports __builtin_memmove during constant evaluation +#ifndef _LIBCPP_COMPILER_GCC + && !is_trivially_copyable<_InType>::value +#endif + ) + return std::__move_impl<_InType*, _InType*, _OutType*>(__first, __last, __result); + const size_t __n = static_cast<size_t>(__last - __first); + ::__builtin_memmove(__result, __first, __n * sizeof(_OutType)); + return std::make_pair(__first + __n, __result + __n); } -template <class _Tp, class _Up> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 -typename enable_if -< - is_same<typename remove_const<_Tp>::type, _Up>::value && - is_trivially_move_assignable<_Up>::value, - _Up* ->::type -__move(_Tp* __first, _Tp* __last, _Up* __result) -{ - const size_t __n = static_cast<size_t>(__last - __first); - if (__n > 0) - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); - return __result + __n; +template <class> +struct __is_trivially_move_assignable_unwrapped_impl : false_type {}; + +template <class _Type> +struct __is_trivially_move_assignable_unwrapped_impl<_Type*> : is_trivially_move_assignable<_Type> {}; + +template <class _Iter> +struct __is_trivially_move_assignable_unwrapped + : __is_trivially_move_assignable_unwrapped_impl<decltype(std::__unwrap_iter<_Iter>(std::declval<_Iter>()))> {}; + +template <class _InIter, + class _OutIter, + __enable_if_t<is_same<typename remove_const<typename iterator_traits<_InIter>::value_type>::type, + typename iterator_traits<_OutIter>::value_type>::value + && __is_cpp17_contiguous_iterator<_InIter>::value + && __is_cpp17_contiguous_iterator<_OutIter>::value + && is_trivially_move_assignable<__iter_value_type<_OutIter> >::value, int> = 0> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX14 +pair<reverse_iterator<_InIter>, reverse_iterator<_OutIter> > +__move_impl(reverse_iterator<_InIter> __first, + reverse_iterator<_InIter> __last, + reverse_iterator<_OutIter> __result) { + auto __first_base = std::__unwrap_iter(__first.base()); + auto __last_base = std::__unwrap_iter(__last.base()); + auto __result_base = std::__unwrap_iter(__result.base()); + auto __result_first = __result_base - (__first_base - __last_base); + std::__move_impl(__last_base, __first_base, __result_first); + return std::make_pair(__last, reverse_iterator<_OutIter>(std::__rewrap_iter(__result.base(), __result_first))); +} + +template <class _InIter, class _Sent, class _OutIter> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +__enable_if_t<is_copy_constructible<_InIter>::value + && is_copy_constructible<_Sent>::value + && is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> > +__move(_InIter __first, _Sent __last, _OutIter __result) { + auto __ret = std::__move_impl(std::__unwrap_iter(__first), std::__unwrap_iter(__last), std::__unwrap_iter(__result)); + return std::make_pair(std::__rewrap_iter(__first, __ret.first), std::__rewrap_iter(__result, __ret.second)); +} + +template <class _InIter, class _Sent, class _OutIter> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +__enable_if_t<!is_copy_constructible<_InIter>::value + || !is_copy_constructible<_Sent>::value + || !is_copy_constructible<_OutIter>::value, pair<_InIter, _OutIter> > +__move(_InIter __first, _Sent __last, _OutIter __result) { + return std::__move_impl(std::move(__first), std::move(__last), std::move(__result)); } template <class _InputIterator, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) -{ - if (__libcpp_is_constant_evaluated()) { - return _VSTD::__move_constexpr(__first, __last, __result); - } else { - return _VSTD::__rewrap_iter(__result, - _VSTD::__move(_VSTD::__unwrap_iter(__first), - _VSTD::__unwrap_iter(__last), - _VSTD::__unwrap_iter(__result))); - } +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_OutputIterator move(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { + return std::__move(__first, __last, __result).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/move_backward.h b/libcxx/include/__algorithm/move_backward.h index a4e3828b6069..a56f6b826ce3 100644 --- a/libcxx/include/__algorithm/move_backward.h +++ b/libcxx/include/__algorithm/move_backward.h @@ -11,12 +11,12 @@ #include <__algorithm/unwrap_iter.h> #include <__config> +#include <__utility/move.h> #include <cstring> #include <type_traits> -#include <utility> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/next_permutation.h b/libcxx/include/__algorithm/next_permutation.h index eb81cceb7bbc..05e56f4a17ff 100644 --- a/libcxx/include/__algorithm/next_permutation.h +++ b/libcxx/include/__algorithm/next_permutation.h @@ -17,7 +17,7 @@ #include <__utility/swap.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/none_of.h b/libcxx/include/__algorithm/none_of.h index 10339e2418c8..b34b1e00ddb8 100644 --- a/libcxx/include/__algorithm/none_of.h +++ b/libcxx/include/__algorithm/none_of.h @@ -13,7 +13,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/nth_element.h b/libcxx/include/__algorithm/nth_element.h index 3afbd6c61846..60b9280f75f0 100644 --- a/libcxx/include/__algorithm/nth_element.h +++ b/libcxx/include/__algorithm/nth_element.h @@ -13,6 +13,7 @@ #include <__algorithm/comp_ref_type.h> #include <__algorithm/sort.h> #include <__config> +#include <__debug> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> @@ -21,7 +22,7 @@ #endif #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/partial_sort.h b/libcxx/include/__algorithm/partial_sort.h index a92a7e56610a..3870c0cc9335 100644 --- a/libcxx/include/__algorithm/partial_sort.h +++ b/libcxx/include/__algorithm/partial_sort.h @@ -15,6 +15,7 @@ #include <__algorithm/sift_down.h> #include <__algorithm/sort_heap.h> #include <__config> +#include <__debug> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> @@ -23,7 +24,7 @@ #endif #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/partial_sort_copy.h b/libcxx/include/__algorithm/partial_sort_copy.h index 67a62bae1f5a..7ed1e538e9b8 100644 --- a/libcxx/include/__algorithm/partial_sort_copy.h +++ b/libcxx/include/__algorithm/partial_sort_copy.h @@ -18,7 +18,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/partition.h b/libcxx/include/__algorithm/partition.h index 131c5d3735d5..73d94831ed87 100644 --- a/libcxx/include/__algorithm/partition.h +++ b/libcxx/include/__algorithm/partition.h @@ -14,7 +14,7 @@ #include <__utility/swap.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/partition_copy.h b/libcxx/include/__algorithm/partition_copy.h index d34944589b9e..cacde0bfd47b 100644 --- a/libcxx/include/__algorithm/partition_copy.h +++ b/libcxx/include/__algorithm/partition_copy.h @@ -11,10 +11,10 @@ #include <__config> #include <__iterator/iterator_traits.h> -#include <utility> // pair +#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/partition_point.h b/libcxx/include/__algorithm/partition_point.h index 18e6e6f6812f..1675534e60d5 100644 --- a/libcxx/include/__algorithm/partition_point.h +++ b/libcxx/include/__algorithm/partition_point.h @@ -11,10 +11,12 @@ #include <__algorithm/half_positive.h> #include <__config> -#include <iterator> +#include <__iterator/advance.h> +#include <__iterator/distance.h> +#include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/pop_heap.h b/libcxx/include/__algorithm/pop_heap.h index c1cc8016ac91..2932a5e31dbc 100644 --- a/libcxx/include/__algorithm/pop_heap.h +++ b/libcxx/include/__algorithm/pop_heap.h @@ -11,13 +11,14 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/push_heap.h> #include <__algorithm/sift_down.h> #include <__config> #include <__iterator/iterator_traits.h> -#include <__utility/swap.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD @@ -28,10 +29,21 @@ void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len) { + using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; + if (__len > 1) { - swap(*__first, *--__last); - _VSTD::__sift_down<_Compare>(__first, __comp, __len - 1, __first); + value_type __top = std::move(*__first); // create a hole at __first + _RandomAccessIterator __hole = std::__floyd_sift_down<_Compare>(__first, __comp, __len); + --__last; + if (__hole == __last) { + *__hole = std::move(__top); + } else { + *__hole = std::move(*__last); + ++__hole; + *__last = std::move(__top); + std::__sift_up<_Compare>(__first, __hole, __comp, __hole - __first); + } } } diff --git a/libcxx/include/__algorithm/prev_permutation.h b/libcxx/include/__algorithm/prev_permutation.h index 457c2695b324..9dbc1dad0124 100644 --- a/libcxx/include/__algorithm/prev_permutation.h +++ b/libcxx/include/__algorithm/prev_permutation.h @@ -17,7 +17,7 @@ #include <__utility/swap.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/push_heap.h b/libcxx/include/__algorithm/push_heap.h index 864d419fa203..66973e082f14 100644 --- a/libcxx/include/__algorithm/push_heap.h +++ b/libcxx/include/__algorithm/push_heap.h @@ -16,7 +16,7 @@ #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_adjacent_find.h b/libcxx/include/__algorithm/ranges_adjacent_find.h new file mode 100644 index 000000000000..e798d568299d --- /dev/null +++ b/libcxx/include/__algorithm/ranges_adjacent_find.h @@ -0,0 +1,78 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_ADJACENT_FIND_H +#define _LIBCPP___ALGORITHM_RANGES_ADJACENT_FIND_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __adjacent_find { +struct __fn { + + template <class _Iter, class _Sent, class _Proj, class _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __adjacent_find_impl(_Iter __first, _Sent __last, _Pred& __pred, _Proj& __proj) { + if (__first == __last) + return __first; + + auto __i = __first; + while (++__i != __last) { + if (std::invoke(__pred, std::invoke(__proj, *__first), std::invoke(__proj, *__i))) + return __first; + __first = __i; + } + return __i; + } + + template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, + class _Proj = identity, + indirect_binary_predicate<projected<_Iter, _Proj>, projected<_Iter, _Proj>> _Pred = ranges::equal_to> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, _Pred __pred = {}, _Proj __proj = {}) const { + return __adjacent_find_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <forward_range _Range, + class _Proj = identity, + indirect_binary_predicate<projected<iterator_t<_Range>, _Proj>, + projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __range, _Pred __pred = {}, _Proj __proj = {}) const { + return __adjacent_find_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj); + } +}; +} // namespace __adjacent_find + +inline namespace __cpo { + inline constexpr auto adjacent_find = __adjacent_find::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_ADJACENT_FIND_H diff --git a/libcxx/include/__algorithm/ranges_all_of.h b/libcxx/include/__algorithm/ranges_all_of.h new file mode 100644 index 000000000000..a146865652a7 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_all_of.h @@ -0,0 +1,68 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_ALL_OF_H +#define _LIBCPP___ALGORITHM_RANGES_ALL_OF_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __all_of { +struct __fn { + + template <class _Iter, class _Sent, class _Proj, class _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr static + bool __all_of_impl(_Iter __first, _Sent __last, _Pred& __pred, _Proj& __proj) { + for (; __first != __last; ++__first) { + if (!std::invoke(__pred, std::invoke(__proj, *__first))) + return false; + } + return true; + } + + template <input_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const { + return __all_of_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <input_range _Range, class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const { + return __all_of_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj); + } +}; +} // namespace __all_of + +inline namespace __cpo { + inline constexpr auto all_of = __all_of::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_ALL_OF_H diff --git a/libcxx/include/__algorithm/ranges_any_of.h b/libcxx/include/__algorithm/ranges_any_of.h new file mode 100644 index 000000000000..11c52cbe21ea --- /dev/null +++ b/libcxx/include/__algorithm/ranges_any_of.h @@ -0,0 +1,68 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_ANY_OF_H +#define _LIBCPP___ALGORITHM_RANGES_ANY_OF_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __any_of { +struct __fn { + + template <class _Iter, class _Sent, class _Proj, class _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr static + bool __any_of_impl(_Iter __first, _Sent __last, _Pred& __pred, _Proj& __proj) { + for (; __first != __last; ++__first) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) + return true; + } + return false; + } + + template <input_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Iter __first, _Sent __last, _Pred __pred = {}, _Proj __proj = {}) const { + return __any_of_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <input_range _Range, class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const { + return __any_of_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj); + } +}; +} // namespace __any_of + +inline namespace __cpo { + inline constexpr auto any_of = __any_of::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_ANY_OF_H diff --git a/libcxx/include/__algorithm/ranges_binary_search.h b/libcxx/include/__algorithm/ranges_binary_search.h new file mode 100644 index 000000000000..68359fb1388f --- /dev/null +++ b/libcxx/include/__algorithm/ranges_binary_search.h @@ -0,0 +1,63 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_BINARY_SEARCH_H +#define _LIBCPP___ALGORITHM_RANGES_BINARY_SEARCH_H + +#include <__algorithm/iterator_operations.h> +#include <__algorithm/lower_bound.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __binary_search { +struct __fn { + template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity, + indirect_strict_weak_order<const _Type*, projected<_Iter, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const { + auto __ret = std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp, __proj); + return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first)); + } + + template <forward_range _Range, class _Type, class _Proj = identity, + indirect_strict_weak_order<const _Type*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Range&& __r, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const { + auto __first = ranges::begin(__r); + auto __last = ranges::end(__r); + auto __ret = std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp, __proj); + return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first)); + } +}; +} // namespace __binary_search + +inline namespace __cpo { + inline constexpr auto binary_search = __binary_search::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_BINARY_SEARCH_H diff --git a/libcxx/include/__algorithm/ranges_copy.h b/libcxx/include/__algorithm/ranges_copy.h new file mode 100644 index 000000000000..f5d6d5cd139a --- /dev/null +++ b/libcxx/include/__algorithm/ranges_copy.h @@ -0,0 +1,65 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_COPY_H +#define _LIBCPP___ALGORITHM_RANGES_COPY_H + +#include <__algorithm/copy.h> +#include <__algorithm/in_out_result.h> +#include <__config> +#include <__functional/identity.h> +#include <__iterator/concepts.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _InIter, class _OutIter> +using copy_result = in_out_result<_InIter, _OutIter>; + +namespace __copy { +struct __fn { + + template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter> + requires indirectly_copyable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + copy_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const { + auto __ret = std::__copy(std::move(__first), std::move(__last), std::move(__result)); + return {std::move(__ret.first), std::move(__ret.second)}; + } + + template <input_range _Range, weakly_incrementable _OutIter> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + copy_result<borrowed_iterator_t<_Range>, _OutIter> operator()(_Range&& __r, _OutIter __result) const { + auto __ret = std::__copy(ranges::begin(__r), ranges::end(__r), std::move(__result)); + return {std::move(__ret.first), std::move(__ret.second)}; + } +}; +} // namespace __copy + +inline namespace __cpo { + inline constexpr auto copy = __copy::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_COPY_H diff --git a/libcxx/include/__algorithm/ranges_copy_backward.h b/libcxx/include/__algorithm/ranges_copy_backward.h new file mode 100644 index 000000000000..49c1b26add6d --- /dev/null +++ b/libcxx/include/__algorithm/ranges_copy_backward.h @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_COPY_BACKWARD_H +#define _LIBCPP___ALGORITHM_RANGES_COPY_BACKWARD_H + +#include <__algorithm/copy_backward.h> +#include <__algorithm/in_out_result.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/reverse_iterator.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template<class _Ip, class _Op> +using copy_backward_result = in_out_result<_Ip, _Op>; + +namespace __copy_backward { +struct __fn { + + template <bidirectional_iterator _InIter1, sentinel_for<_InIter1> _Sent1, bidirectional_iterator _InIter2> + requires indirectly_copyable<_InIter1, _InIter2> + _LIBCPP_HIDE_FROM_ABI constexpr + copy_backward_result<_InIter1, _InIter2> operator()(_InIter1 __first, _Sent1 __last, _InIter2 __result) const { + auto __ret = std::__copy_backward(std::move(__first), std::move(__last), std::move(__result)); + return {std::move(__ret.first), std::move(__ret.second)}; + } + + template <bidirectional_range _Range, bidirectional_iterator _Iter> + requires indirectly_copyable<iterator_t<_Range>, _Iter> + _LIBCPP_HIDE_FROM_ABI constexpr + copy_backward_result<borrowed_iterator_t<_Range>, _Iter> operator()(_Range&& __r, _Iter __result) const { + auto __ret = std::__copy_backward(ranges::begin(__r), + ranges::end(__r), + std::move(__result)); + return {std::move(__ret.first), std::move(__ret.second)}; + } +}; +} // namespace __copy_backward + +inline namespace __cpo { + inline constexpr auto copy_backward = __copy_backward::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_COPY_BACKWARD_H diff --git a/libcxx/include/__algorithm/ranges_copy_if.h b/libcxx/include/__algorithm/ranges_copy_if.h new file mode 100644 index 000000000000..492104fbbfba --- /dev/null +++ b/libcxx/include/__algorithm/ranges_copy_if.h @@ -0,0 +1,81 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_COPY_IF_H +#define _LIBCPP___ALGORITHM_RANGES_COPY_IF_H + +#include <__algorithm/in_out_result.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template<class _Ip, class _Op> +using copy_if_result = in_out_result<_Ip, _Op>; + +namespace __copy_if { +struct __fn { + + template <class _InIter, class _Sent, class _OutIter, class _Proj, class _Pred> + _LIBCPP_HIDE_FROM_ABI static constexpr + copy_if_result <_InIter, _OutIter> + __copy_if_impl(_InIter __first, _Sent __last, _OutIter __result, _Pred& __pred, _Proj& __proj) { + for (; __first != __last; ++__first) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) { + *__result = *__first; + ++__result; + } + } + return {std::move(__first), std::move(__result)}; + } + + template <input_iterator _Iter, sentinel_for<_Iter> _Sent, weakly_incrementable _OutIter, class _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + requires indirectly_copyable<_Iter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + copy_if_result<_Iter, _OutIter> + operator()(_Iter __first, _Sent __last, _OutIter __result, _Pred __pred, _Proj __proj = {}) const { + return __copy_if_impl(std::move(__first), std::move(__last), std::move(__result), __pred, __proj); + } + + template <input_range _Range, weakly_incrementable _OutIter, class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + copy_if_result<borrowed_iterator_t<_Range>, _OutIter> + operator()(_Range&& __r, _OutIter __result, _Pred __pred, _Proj __proj = {}) const { + return __copy_if_impl(ranges::begin(__r), ranges::end(__r), std::move(__result), __pred, __proj); + } +}; +} // namespace __copy_if + +inline namespace __cpo { + inline constexpr auto copy_if = __copy_if::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_COPY_IF_H diff --git a/libcxx/include/__algorithm/ranges_copy_n.h b/libcxx/include/__algorithm/ranges_copy_n.h new file mode 100644 index 000000000000..eaa05c954686 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_copy_n.h @@ -0,0 +1,76 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_COPY_N_H +#define _LIBCPP___ALGORITHM_RANGES_COPY_N_H + +#include <__algorithm/copy.h> +#include <__algorithm/in_out_result.h> +#include <__algorithm/ranges_copy.h> +#include <__config> +#include <__functional/identity.h> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/unreachable_sentinel.h> +#include <__iterator/wrap_iter.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +namespace ranges { + +template <class _Ip, class _Op> +using copy_n_result = in_out_result<_Ip, _Op>; + +namespace __copy_n { +struct __fn { + + template <class _InIter, class _DiffType, class _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr static + copy_n_result<_InIter, _OutIter> __go(_InIter __first, _DiffType __n, _OutIter __result) { + while (__n != 0) { + *__result = *__first; + ++__first; + ++__result; + --__n; + } + return {std::move(__first), std::move(__result)}; + } + + template <random_access_iterator _InIter, class _DiffType, random_access_iterator _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr static + copy_n_result<_InIter, _OutIter> __go(_InIter __first, _DiffType __n, _OutIter __result) { + auto __ret = std::__copy(__first, __first + __n, __result); + return {__ret.first, __ret.second}; + } + + template <input_iterator _Ip, weakly_incrementable _Op> + requires indirectly_copyable<_Ip, _Op> + _LIBCPP_HIDE_FROM_ABI constexpr + copy_n_result<_Ip, _Op> operator()(_Ip __first, iter_difference_t<_Ip> __n, _Op __result) const { + return __go(std::move(__first), __n, std::move(__result)); + } +}; +} // namespace __copy_n + +inline namespace __cpo { + inline constexpr auto copy_n = __copy_n::__fn{}; +} // namespace __cpo +} // namespace ranges + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_RANGES_COPY_N_H diff --git a/libcxx/include/__algorithm/ranges_count.h b/libcxx/include/__algorithm/ranges_count.h new file mode 100644 index 000000000000..670df26911d0 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_count.h @@ -0,0 +1,62 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_COUNT_H +#define _LIBCPP___ALGORITHM_RANGES_COUNT_H + +#include <__algorithm/ranges_count_if.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __count { +struct __fn { + template <input_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type*> + _LIBCPP_HIDE_FROM_ABI constexpr + iter_difference_t<_Iter> operator()(_Iter __first, _Sent __last, const _Type& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __e) { return __e == __value; }; + return ranges::__count_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <input_range _Range, class _Type, class _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*> + _LIBCPP_HIDE_FROM_ABI constexpr + range_difference_t<_Range> operator()(_Range&& __r, const _Type& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __e) { return __e == __value; }; + return ranges::__count_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj); + } +}; +} // namespace __count + +inline namespace __cpo { + inline constexpr auto count = __count::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_COUNT_H diff --git a/libcxx/include/__algorithm/ranges_count_if.h b/libcxx/include/__algorithm/ranges_count_if.h new file mode 100644 index 000000000000..0f34ee9f2b1b --- /dev/null +++ b/libcxx/include/__algorithm/ranges_count_if.h @@ -0,0 +1,72 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_COUNT_IF_H +#define _LIBCPP___ALGORITHM_RANGES_COUNT_IF_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +template <class _Iter, class _Sent, class _Proj, class _Pred> +_LIBCPP_HIDE_FROM_ABI constexpr +iter_difference_t<_Iter> __count_if_impl(_Iter __first, _Sent __last, + _Pred& __pred, _Proj& __proj) { + iter_difference_t<_Iter> __counter(0); + for (; __first != __last; ++__first) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) + ++__counter; + } + return __counter; +} + +namespace __count_if { +struct __fn { + template <input_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Predicate> + _LIBCPP_HIDE_FROM_ABI constexpr + iter_difference_t<_Iter> operator()(_Iter __first, _Sent __last, _Predicate __pred, _Proj __proj = {}) const { + return ranges::__count_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <input_range _Range, class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Predicate> + _LIBCPP_HIDE_FROM_ABI constexpr + range_difference_t<_Range> operator()(_Range&& __r, _Predicate __pred, _Proj __proj = {}) const { + return ranges::__count_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj); + } +}; +} // namespace __count_if + +inline namespace __cpo { + inline constexpr auto count_if = __count_if::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_COUNT_IF_H diff --git a/libcxx/include/__algorithm/ranges_equal.h b/libcxx/include/__algorithm/ranges_equal.h new file mode 100644 index 000000000000..c5f2d2332216 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_equal.h @@ -0,0 +1,115 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_EQUAL_H +#define _LIBCPP___ALGORITHM_RANGES_EQUAL_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/distance.h> +#include <__iterator/indirectly_comparable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __equal { +struct __fn { +private: + template <class _Iter1, class _Sent1, + class _Iter2, class _Sent2, + class _Pred, + class _Proj1, + class _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr static + bool __equal_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2) { + while (__first1 != __last1 && __first2 != __last2) { + if (!std::invoke(__pred, std::invoke(__proj1, *__first1), std::invoke(__proj2, *__first2))) + return false; + ++__first1; + ++__first2; + } + return __first1 == __last1 && __first2 == __last2; + } + +public: + + template <input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, + input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + class _Pred = ranges::equal_to, + class _Proj1 = identity, + class _Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + if constexpr (sized_sentinel_for<_Sent1, _Iter1> && sized_sentinel_for<_Sent2, _Iter2>) { + if (__last1 - __first1 != __last2 - __first2) + return false; + } + return __equal_impl(std::move(__first1), std::move(__last1), + std::move(__first2), std::move(__last2), + __pred, + __proj1, + __proj2); + } + + template <input_range _Range1, + input_range _Range2, + class _Pred = ranges::equal_to, + class _Proj1 = identity, + class _Proj2 = identity> + requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Range1&& __range1, + _Range2&& __range2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + if constexpr (sized_range<_Range1> && sized_range<_Range2>) { + if (ranges::distance(__range1) != ranges::distance(__range2)) + return false; + } + return __equal_impl(ranges::begin(__range1), ranges::end(__range1), + ranges::begin(__range2), ranges::end(__range2), + __pred, + __proj1, + __proj2); + return false; + } +}; +} // namespace __equal + +inline namespace __cpo { + inline constexpr auto equal = __equal::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_EQUAL_H diff --git a/libcxx/include/__algorithm/ranges_fill.h b/libcxx/include/__algorithm/ranges_fill.h new file mode 100644 index 000000000000..846e31885141 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_fill.h @@ -0,0 +1,59 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FILL_H +#define _LIBCPP___ALGORITHM_RANGES_FILL_H + +#include <__algorithm/ranges_fill_n.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __fill { +struct __fn { + template <class _Type, output_iterator<const _Type&> _Iter, sentinel_for<_Iter> _Sent> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, const _Type& __value) const { + if constexpr(random_access_iterator<_Iter>) { + return ranges::fill_n(__first, __last - __first, __value); + } else { + for (; __first != __last; ++__first) + *__first = __value; + return __first; + } + } + + template <class _Type, output_range<const _Type&> _Range> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __range, const _Type& __value) const { + return (*this)(ranges::begin(__range), ranges::end(__range), __value); + } +}; +} // namespace __fill + +inline namespace __cpo { + inline constexpr auto fill = __fill::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FILL_H diff --git a/libcxx/include/__algorithm/ranges_fill_n.h b/libcxx/include/__algorithm/ranges_fill_n.h new file mode 100644 index 000000000000..d93c573406ec --- /dev/null +++ b/libcxx/include/__algorithm/ranges_fill_n.h @@ -0,0 +1,48 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FILL_N_H +#define _LIBCPP___ALGORITHM_RANGES_FILL_N_H + +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __fill_n { +struct __fn { + template <class _Type, output_iterator<const _Type&> _Iter> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, iter_difference_t<_Iter> __n, const _Type& __value) const { + for (; __n != 0; --__n) { + *__first = __value; + ++__first; + } + return __first; + } +}; +} // namespace __fill_n + +inline namespace __cpo { + inline constexpr auto fill_n = __fill_n::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FILL_N_H diff --git a/libcxx/include/__algorithm/ranges_find.h b/libcxx/include/__algorithm/ranges_find.h new file mode 100644 index 000000000000..ca6d2f438295 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find.h @@ -0,0 +1,63 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FIND_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_H + +#include <__algorithm/ranges_find_if.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __find { +struct __fn { + template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, class _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, projected<_Ip, _Proj>, const _Tp*> + _LIBCPP_HIDE_FROM_ABI constexpr + _Ip operator()(_Ip __first, _Sp __last, const _Tp& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __e) { return std::forward<decltype(__e)>(__e) == __value; }; + return ranges::__find_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <input_range _Rp, class _Tp, class _Proj = identity> + requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Rp>, _Proj>, const _Tp*> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __e) { return std::forward<decltype(__e)>(__e) == __value; }; + return ranges::__find_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj); + } +}; +} // namespace __find + +inline namespace __cpo { + inline constexpr auto find = __find::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_H diff --git a/libcxx/include/__algorithm/ranges_find_first_of.h b/libcxx/include/__algorithm/ranges_find_first_of.h new file mode 100644 index 000000000000..ae31d38e6a95 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_first_of.h @@ -0,0 +1,101 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FIND_FIRST_OF_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_FIRST_OF_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/indirectly_comparable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __find_first_of { +struct __fn { + + template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter1 __find_first_of_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2) { + for (; __first1 != __last1; ++__first1) { + for (auto __j = __first2; __j != __last2; ++__j) { + if (std::invoke(__pred, std::invoke(__proj1, *__first1), std::invoke(__proj2, *__j))) + return __first1; + } + } + return __first1; + } + + template <input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, + forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + class _Pred = ranges::equal_to, + class _Proj1 = identity, + class _Proj2 = identity> + requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter1 operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return __find_first_of_impl(std::move(__first1), std::move(__last1), + std::move(__first2), std::move(__last2), + __pred, + __proj1, + __proj2); + } + + template <input_range _Range1, + forward_range _Range2, + class _Pred = ranges::equal_to, + class _Proj1 = identity, + class _Proj2 = identity> + requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range1> operator()(_Range1&& __range1, + _Range2&& __range2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return __find_first_of_impl(ranges::begin(__range1), ranges::end(__range1), + ranges::begin(__range2), ranges::end(__range2), + __pred, + __proj1, + __proj2); + } + +}; +} // namespace __find_first_of + +inline namespace __cpo { + inline constexpr auto find_first_of = __find_first_of::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_FIRST_OF_H diff --git a/libcxx/include/__algorithm/ranges_find_if.h b/libcxx/include/__algorithm/ranges_find_if.h new file mode 100644 index 000000000000..65ac122f6677 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_if.h @@ -0,0 +1,71 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FIND_IF_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_IF_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _Ip, class _Sp, class _Pred, class _Proj> +_LIBCPP_HIDE_FROM_ABI static constexpr +_Ip __find_if_impl(_Ip __first, _Sp __last, _Pred& __pred, _Proj& __proj) { + for (; __first != __last; ++__first) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) + break; + } + return __first; +} + +namespace __find_if { +struct __fn { + + template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity, + indirect_unary_predicate<projected<_Ip, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + _Ip operator()(_Ip __first, _Sp __last, _Pred __pred, _Proj __proj = {}) const { + return ranges::__find_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <input_range _Rp, class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Rp>, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const { + return ranges::__find_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj); + } +}; +} // namespace __find_if + +inline namespace __cpo { + inline constexpr auto find_if = __find_if::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_IF_H diff --git a/libcxx/include/__algorithm/ranges_find_if_not.h b/libcxx/include/__algorithm/ranges_find_if_not.h new file mode 100644 index 000000000000..9a1adf71fc58 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_if_not.h @@ -0,0 +1,63 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FIND_IF_NOT_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_IF_NOT_H + +#include <__algorithm/ranges_find_if.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __find_if_not { +struct __fn { + template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity, + indirect_unary_predicate<projected<_Ip, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + _Ip operator()(_Ip __first, _Sp __last, _Pred __pred, _Proj __proj = {}) const { + auto __pred2 = [&](auto&& __e) { return !std::invoke(__pred, std::forward<decltype(__e)>(__e)); }; + return ranges::__find_if_impl(std::move(__first), std::move(__last), __pred2, __proj); + } + + template <input_range _Rp, class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Rp>, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const { + auto __pred2 = [&](auto&& __e) { return !std::invoke(__pred, std::forward<decltype(__e)>(__e)); }; + return ranges::__find_if_impl(ranges::begin(__r), ranges::end(__r), __pred2, __proj); + } +}; +} // namespace __find_if_not + +inline namespace __cpo { + inline constexpr auto find_if_not = __find_if_not::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FIND_IF_NOT_H diff --git a/libcxx/include/__algorithm/ranges_for_each.h b/libcxx/include/__algorithm/ranges_for_each.h new file mode 100644 index 000000000000..f284c0ee3ad4 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_for_each.h @@ -0,0 +1,78 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FOR_EACH_H +#define _LIBCPP___ALGORITHM_RANGES_FOR_EACH_H + +#include <__algorithm/in_fun_result.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _Iter, class _Func> +using for_each_result = in_fun_result<_Iter, _Func>; + +namespace __for_each { +struct __fn { +private: + template <class _Iter, class _Sent, class _Proj, class _Func> + _LIBCPP_HIDE_FROM_ABI constexpr static + for_each_result<_Iter, _Func> __for_each_impl(_Iter __first, _Sent __last, _Func& __func, _Proj& __proj) { + for (; __first != __last; ++__first) + std::invoke(__func, std::invoke(__proj, *__first)); + return {std::move(__first), std::move(__func)}; + } + +public: + template <input_iterator _Iter, sentinel_for<_Iter> _Sent, + class _Proj = identity, + indirectly_unary_invocable<projected<_Iter, _Proj>> _Func> + _LIBCPP_HIDE_FROM_ABI constexpr + for_each_result<_Iter, _Func> operator()(_Iter __first, _Sent __last, _Func __func, _Proj __proj = {}) const { + return __for_each_impl(std::move(__first), std::move(__last), __func, __proj); + } + + template <input_range _Range, + class _Proj = identity, + indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>> _Func> + _LIBCPP_HIDE_FROM_ABI constexpr + for_each_result<borrowed_iterator_t<_Range>, _Func> operator()(_Range&& __range, + _Func __func, + _Proj __proj = {}) const { + return __for_each_impl(ranges::begin(__range), ranges::end(__range), __func, __proj); + } + +}; +} // namespace __for_each + +inline namespace __cpo { + inline constexpr auto for_each = __for_each::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FOR_EACH_H diff --git a/libcxx/include/__algorithm/ranges_for_each_n.h b/libcxx/include/__algorithm/ranges_for_each_n.h new file mode 100644 index 000000000000..ddf8b047cdb2 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_for_each_n.h @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_FOR_EACH_N_H +#define _LIBCPP___ALGORITHM_RANGES_FOR_EACH_N_H + +#include <__algorithm/in_fun_result.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/projected.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _Iter, class _Func> +using for_each_n_result = in_fun_result<_Iter, _Func>; + +namespace __for_each_n { +struct __fn { + + template <input_iterator _Iter, + class _Proj = identity, + indirectly_unary_invocable<projected<_Iter, _Proj>> _Func> + _LIBCPP_HIDE_FROM_ABI constexpr + for_each_n_result<_Iter, _Func> operator()(_Iter __first, + iter_difference_t<_Iter> __count, + _Func __func, + _Proj __proj = {}) const { + while (__count-- > 0) { + std::invoke(__func, std::invoke(__proj, *__first)); + ++__first; + } + return {std::move(__first), std::move(__func)}; + } + +}; +} // namespace __for_each_n + +inline namespace __cpo { + inline constexpr auto for_each_n = __for_each_n::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_FOR_EACH_N_H diff --git a/libcxx/include/__algorithm/ranges_is_partitioned.h b/libcxx/include/__algorithm/ranges_is_partitioned.h new file mode 100644 index 000000000000..3d572895ebe1 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_is_partitioned.h @@ -0,0 +1,81 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_IS_PARTITIONED_H +#define _LIBCPP___ALGORITHM_RANGES_IS_PARTITIONED_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__iterator/concepts.h> +#include <__iterator/indirectly_comparable.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __is_partitioned { +struct __fn { + + template <class _Iter, class _Sent, class _Proj, class _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr static + bool __is_parititioned_impl(_Iter __first, _Sent __last, _Pred& __pred, _Proj& __proj) { + for (; __first != __last; ++__first) { + if (!std::invoke(__pred, std::invoke(__proj, *__first))) + break; + } + + if (__first == __last) + return true; + ++__first; + + for (; __first != __last; ++__first) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) + return false; + } + + return true; + } + + template <input_iterator _Iter, sentinel_for<_Iter> _Sent, + class _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const { + return __is_parititioned_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <input_range _Range, + class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const { + return __is_parititioned_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj); + } +}; +} // namespace __is_partitioned + +inline namespace __cpo { + inline constexpr auto is_partitioned = __is_partitioned::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_IS_PARTITIONED_H diff --git a/libcxx/include/__algorithm/ranges_is_sorted.h b/libcxx/include/__algorithm/ranges_is_sorted.h new file mode 100644 index 000000000000..938e69afba8d --- /dev/null +++ b/libcxx/include/__algorithm/ranges_is_sorted.h @@ -0,0 +1,61 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP__ALGORITHM_RANGES_IS_SORTED_H +#define _LIBCPP__ALGORITHM_RANGES_IS_SORTED_H + +#include <__algorithm/ranges_is_sorted_until.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __is_sorted { +struct __fn { + template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, + class _Proj = identity, + indirect_strict_weak_order<projected<_Iter, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return ranges::__is_sorted_until_impl(std::move(__first), __last, __comp, __proj) == __last; + } + + template <forward_range _Range, + class _Proj = identity, + indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const { + auto __last = ranges::end(__range); + return ranges::__is_sorted_until_impl(ranges::begin(__range), __last, __comp, __proj) == __last; + } +}; +} // namespace __is_sorted + +inline namespace __cpo { + inline constexpr auto is_sorted = __is_sorted::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP__ALGORITHM_RANGES_IS_SORTED_H diff --git a/libcxx/include/__algorithm/ranges_is_sorted_until.h b/libcxx/include/__algorithm/ranges_is_sorted_until.h new file mode 100644 index 000000000000..c8f0608e1255 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_is_sorted_until.h @@ -0,0 +1,76 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP__ALGORITHM_RANGES_IS_SORTED_UNTIL_H +#define _LIBCPP__ALGORITHM_RANGES_IS_SORTED_UNTIL_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _Iter, class _Sent, class _Proj, class _Comp> +_LIBCPP_HIDE_FROM_ABI constexpr +_Iter __is_sorted_until_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { + if (__first == __last) + return __first; + auto __i = __first; + while (++__i != __last) { + if (std::invoke(__comp, std::invoke(__proj, *__i), std::invoke(__proj, *__first))) + return __i; + __first = __i; + } + return __i; +} + +namespace __is_sorted_until { +struct __fn { + template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, + class _Proj = identity, + indirect_strict_weak_order<projected<_Iter, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return ranges::__is_sorted_until_impl(std::move(__first), std::move(__last), __comp, __proj); + } + + template <forward_range _Range, + class _Proj = identity, + indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const { + return ranges::__is_sorted_until_impl(ranges::begin(__range), ranges::end(__range), __comp, __proj); + } +}; +} // namespace __is_sorted_until + +inline namespace __cpo { + inline constexpr auto is_sorted_until = __is_sorted_until::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP__ALGORITHM_RANGES_IS_SORTED_UNTIL_H diff --git a/libcxx/include/__algorithm/ranges_lexicographical_compare.h b/libcxx/include/__algorithm/ranges_lexicographical_compare.h new file mode 100644 index 000000000000..fe709f7a7f70 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_lexicographical_compare.h @@ -0,0 +1,98 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_LEXICOGRAPHICAL_COMPARE_H +#define _LIBCPP___ALGORITHM_RANGES_LEXICOGRAPHICAL_COMPARE_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __lexicographical_compare { +struct __fn { + + template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Proj1, class _Proj2, class _Comp> + _LIBCPP_HIDE_FROM_ABI constexpr static + bool __lexicographical_compare_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Comp& __comp, + _Proj1& __proj1, + _Proj2& __proj2) { + while (__first2 != __last2) { + if (__first1 == __last1 + || std::invoke(__comp, std::invoke(__proj1, *__first1), std::invoke(__proj2, *__first2))) + return true; + if (std::invoke(__comp, std::invoke(__proj2, *__first2), std::invoke(__proj1, *__first1))) + return false; + ++__first1; + ++__first2; + } + return false; + } + + template <input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, + input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + class _Proj1 = identity, + class _Proj2 = identity, + indirect_strict_weak_order<projected<_Iter1, _Proj1>, projected<_Iter2, _Proj2>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return __lexicographical_compare_impl(std::move(__first1), std::move(__last1), + std::move(__first2), std::move(__last2), + __comp, + __proj1, + __proj2); + } + + template <input_range _Range1, + input_range _Range2, + class _Proj1 = identity, + class _Proj2 = identity, + indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>, + projected<iterator_t<_Range2>, _Proj2>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Range1&& __range1, _Range2&& __range2, _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { + return __lexicographical_compare_impl(ranges::begin(__range1), ranges::end(__range1), + ranges::begin(__range2), ranges::end(__range2), + __comp, + __proj1, + __proj2); + } + +}; +} // namespace __lexicographical_compare + +inline namespace __cpo { + inline constexpr auto lexicographical_compare = __lexicographical_compare::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_LEXICOGRAPHICAL_COMPARE_H diff --git a/libcxx/include/__algorithm/ranges_lower_bound.h b/libcxx/include/__algorithm/ranges_lower_bound.h new file mode 100644 index 000000000000..a73470465cfd --- /dev/null +++ b/libcxx/include/__algorithm/ranges_lower_bound.h @@ -0,0 +1,66 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_LOWER_BOUND_H +#define _LIBCPP___ALGORITHM_RANGES_LOWER_BOUND_H + +#include <__algorithm/iterator_operations.h> +#include <__algorithm/lower_bound.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +namespace __lower_bound { +struct __fn { + template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity, + indirect_strict_weak_order<const _Type*, projected<_Iter, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const { + return std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp, __proj); + } + + template <forward_range _Range, class _Type, class _Proj = identity, + indirect_strict_weak_order<const _Type*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __r, + const _Type& __value, + _Comp __comp = {}, + _Proj __proj = {}) const { + return std::__lower_bound_impl<_RangesIterOps>(ranges::begin(__r), ranges::end(__r), __value, __comp, __proj); + } +}; +} // namespace __lower_bound + +inline namespace __cpo { + inline constexpr auto lower_bound = __lower_bound::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_LOWER_BOUND_H diff --git a/libcxx/include/__algorithm/ranges_max.h b/libcxx/include/__algorithm/ranges_max.h new file mode 100644 index 000000000000..f48bc3ececa2 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_max.h @@ -0,0 +1,93 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MAX_H +#define _LIBCPP___ALGORITHM_RANGES_MAX_H + +#include <__algorithm/ranges_min_element.h> +#include <__assert> +#include <__concepts/copyable.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/move.h> +#include <initializer_list> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __max { +struct __fn { + template <class _Tp, class _Proj = identity, + indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + const _Tp& operator()(const _Tp& __a, const _Tp& __b, _Comp __comp = {}, _Proj __proj = {}) const { + return std::invoke(__comp, std::invoke(__proj, __a), std::invoke(__proj, __b)) ? __b : __a; + } + + template <copyable _Tp, class _Proj = identity, + indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + _Tp operator()(initializer_list<_Tp> __il, _Comp __comp = {}, _Proj __proj = {}) const { + _LIBCPP_ASSERT(__il.begin() != __il.end(), "initializer_list must contain at least one element"); + + auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); }; + return *ranges::__min_element_impl(__il.begin(), __il.end(), __comp_lhs_rhs_swapped, __proj); + } + + template <input_range _Rp, class _Proj = identity, + indirect_strict_weak_order<projected<iterator_t<_Rp>, _Proj>> _Comp = ranges::less> + requires indirectly_copyable_storable<iterator_t<_Rp>, range_value_t<_Rp>*> + _LIBCPP_HIDE_FROM_ABI constexpr + range_value_t<_Rp> operator()(_Rp&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + auto __first = ranges::begin(__r); + auto __last = ranges::end(__r); + + _LIBCPP_ASSERT(__first != __last, "range must contain at least one element"); + + if constexpr (forward_range<_Rp>) { + auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); }; + return *ranges::__min_element_impl(std::move(__first), std::move(__last), __comp_lhs_rhs_swapped, __proj); + } else { + range_value_t<_Rp> __result = *__first; + while (++__first != __last) { + if (std::invoke(__comp, std::invoke(__proj, __result), std::invoke(__proj, *__first))) + __result = *__first; + } + return __result; + } + } +}; +} // namespace __max + +inline namespace __cpo { + inline constexpr auto max = __max::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP_STD_VER > 17 && && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MAX_H diff --git a/libcxx/include/__algorithm/ranges_max_element.h b/libcxx/include/__algorithm/ranges_max_element.h new file mode 100644 index 000000000000..d8d7242e176b --- /dev/null +++ b/libcxx/include/__algorithm/ranges_max_element.h @@ -0,0 +1,61 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MAX_ELEMENT_H +#define _LIBCPP___ALGORITHM_RANGES_MAX_ELEMENT_H + +#include <__algorithm/ranges_min_element.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __max_element { +struct __fn { + template <forward_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity, + indirect_strict_weak_order<projected<_Ip, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + _Ip operator()(_Ip __first, _Sp __last, _Comp __comp = {}, _Proj __proj = {}) const { + auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); }; + return ranges::__min_element_impl(__first, __last, __comp_lhs_rhs_swapped, __proj); + } + + template <forward_range _Rp, class _Proj = identity, + indirect_strict_weak_order<projected<iterator_t<_Rp>, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); }; + return ranges::__min_element_impl(ranges::begin(__r), ranges::end(__r), __comp_lhs_rhs_swapped, __proj); + } +}; +} // namespace __max_element + +inline namespace __cpo { + inline constexpr auto max_element = __max_element::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MAX_ELEMENT_H diff --git a/libcxx/include/__algorithm/ranges_min.h b/libcxx/include/__algorithm/ranges_min.h new file mode 100644 index 000000000000..0bb1e72ac5ac --- /dev/null +++ b/libcxx/include/__algorithm/ranges_min.h @@ -0,0 +1,89 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MIN_H +#define _LIBCPP___ALGORITHM_RANGES_MIN_H + +#include <__algorithm/ranges_min_element.h> +#include <__assert> +#include <__concepts/copyable.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <initializer_list> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __min { +struct __fn { + template <class _Tp, class _Proj = identity, + indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + const _Tp& operator()(const _Tp& __a, const _Tp& __b, _Comp __comp = {}, _Proj __proj = {}) const { + return std::invoke(__comp, std::invoke(__proj, __b), std::invoke(__proj, __a)) ? __b : __a; + } + + template <copyable _Tp, class _Proj = identity, + indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + _Tp operator()(initializer_list<_Tp> __il, _Comp __comp = {}, _Proj __proj = {}) const { + _LIBCPP_ASSERT(__il.begin() != __il.end(), "initializer_list must contain at least one element"); + return *ranges::__min_element_impl(__il.begin(), __il.end(), __comp, __proj); + } + + template <input_range _Rp, class _Proj = identity, + indirect_strict_weak_order<projected<iterator_t<_Rp>, _Proj>> _Comp = ranges::less> + requires indirectly_copyable_storable<iterator_t<_Rp>, range_value_t<_Rp>*> + _LIBCPP_HIDE_FROM_ABI constexpr + range_value_t<_Rp> operator()(_Rp&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + auto __first = ranges::begin(__r); + auto __last = ranges::end(__r); + + _LIBCPP_ASSERT(__first != __last, "range must contain at least one element"); + + if constexpr (forward_range<_Rp>) { + return *ranges::__min_element_impl(__first, __last, __comp, __proj); + } else { + range_value_t<_Rp> __result = *__first; + while (++__first != __last) { + if (std::invoke(__comp, std::invoke(__proj, *__first), std::invoke(__proj, __result))) + __result = *__first; + } + return __result; + } + } +}; +} // namespace __min + +inline namespace __cpo { + inline constexpr auto min = __min::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP_STD_VER > 17 && && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MIN_H diff --git a/libcxx/include/__algorithm/ranges_min_element.h b/libcxx/include/__algorithm/ranges_min_element.h new file mode 100644 index 000000000000..ae82dceb9ad8 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_min_element.h @@ -0,0 +1,73 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MIN_ELEMENT_H +#define _LIBCPP___ALGORITHM_RANGES_MIN_ELEMENT_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _Ip, class _Sp, class _Proj, class _Comp> +_LIBCPP_HIDE_FROM_ABI static constexpr +_Ip __min_element_impl(_Ip __first, _Sp __last, _Comp& __comp, _Proj& __proj) { + if (__first == __last) + return __first; + + _Ip __i = __first; + while (++__i != __last) + if (std::invoke(__comp, std::invoke(__proj, *__i), std::invoke(__proj, *__first))) + __first = __i; + return __first; +} + +namespace __min_element { +struct __fn { + template <forward_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity, + indirect_strict_weak_order<projected<_Ip, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + _Ip operator()(_Ip __first, _Sp __last, _Comp __comp = {}, _Proj __proj = {}) const { + return ranges::__min_element_impl(__first, __last, __comp, __proj); + } + + template <forward_range _Rp, class _Proj = identity, + indirect_strict_weak_order<projected<iterator_t<_Rp>, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + return ranges::__min_element_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; +} // namespace __min_element + +inline namespace __cpo { + inline constexpr auto min_element = __min_element::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MIN_ELEMENT_H diff --git a/libcxx/include/__algorithm/ranges_minmax.h b/libcxx/include/__algorithm/ranges_minmax.h new file mode 100644 index 000000000000..2f4bba0e7cc0 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_minmax.h @@ -0,0 +1,133 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MINMAX_H +#define _LIBCPP___ALGORITHM_RANGES_MINMAX_H + +#include <__algorithm/min_max_result.h> +#include <__algorithm/minmax_element.h> +#include <__assert> +#include <__concepts/copyable.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/forward.h> +#include <__utility/move.h> +#include <initializer_list> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +template <class _T1> +using minmax_result = min_max_result<_T1>; + +namespace __minmax { +struct __fn { + template <class _Type, class _Proj = identity, + indirect_strict_weak_order<projected<const _Type*, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr ranges::minmax_result<const _Type&> + operator()(const _Type& __a, const _Type& __b, _Comp __comp = {}, _Proj __proj = {}) const { + if (std::invoke(__comp, std::invoke(__proj, __b), std::invoke(__proj, __a))) + return {__b, __a}; + return {__a, __b}; + } + + template <copyable _Type, class _Proj = identity, + indirect_strict_weak_order<projected<const _Type*, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + ranges::minmax_result<_Type> operator()(initializer_list<_Type> __il, _Comp __comp = {}, _Proj __proj = {}) const { + _LIBCPP_ASSERT(__il.begin() != __il.end(), "initializer_list has to contain at least one element"); + auto __iters = std::__minmax_element_impl(__il.begin(), __il.end(), __comp, __proj); + return ranges::minmax_result<_Type> { *__iters.first, *__iters.second }; + } + + template <input_range _Range, class _Proj = identity, + indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less> + requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*> + _LIBCPP_HIDE_FROM_ABI constexpr + ranges::minmax_result<range_value_t<_Range>> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + auto __first = ranges::begin(__r); + auto __last = ranges::end(__r); + using _ValueT = range_value_t<_Range>; + + _LIBCPP_ASSERT(__first != __last, "range has to contain at least one element"); + + if constexpr (forward_range<_Range>) { + auto __result = std::__minmax_element_impl(__first, __last, __comp, __proj); + return {*__result.first, *__result.second}; + } else { + // input_iterators can't be copied, so the implementation for input_iterators has to store + // the values instead of a pointer to the correct values + auto __less = [&](auto&& __a, auto&& __b) -> bool { + return std::invoke(__comp, std::invoke(__proj, std::forward<decltype(__a)>(__a)), + std::invoke(__proj, std::forward<decltype(__b)>(__b))); + }; + + ranges::minmax_result<_ValueT> __result = {*__first, __result.min}; + if (__first == __last || ++__first == __last) + return __result; + + if (__less(*__first, __result.min)) + __result.min = *__first; + else + __result.max = *__first; + + while (++__first != __last) { + _ValueT __i = *__first; + if (++__first == __last) { + if (__less(__i, __result.min)) + __result.min = __i; + else if (!__less(__i, __result.max)) + __result.max = __i; + return __result; + } + + if (__less(*__first, __i)) { + if (__less(*__first, __result.min)) + __result.min = *__first; + if (!__less(__i, __result.max)) + __result.max = std::move(__i); + } else { + if (__less(__i, __result.min)) + __result.min = std::move(__i); + if (!__less(*__first, __result.max)) + __result.max = *__first; + } + } + return __result; + } + } +}; +} // namespace __minmax + +inline namespace __cpo { + inline constexpr auto minmax = __minmax::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MINMAX_H diff --git a/libcxx/include/__algorithm/ranges_minmax_element.h b/libcxx/include/__algorithm/ranges_minmax_element.h new file mode 100644 index 000000000000..b7bb26cefe95 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_minmax_element.h @@ -0,0 +1,72 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MINMAX_ELEMENT_H +#define _LIBCPP___ALGORITHM_RANGES_MINMAX_ELEMENT_H + +#include <__algorithm/min_max_result.h> +#include <__algorithm/minmax_element.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> +#include <__utility/pair.h> +#include <type_traits> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _T1> +using minmax_element_result = min_max_result<_T1>; + +namespace __minmax_element { +struct __fn { + template <forward_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity, + indirect_strict_weak_order<projected<_Ip, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + ranges::minmax_element_result<_Ip> operator()(_Ip __first, _Sp __last, _Comp __comp = {}, _Proj __proj = {}) const { + auto __ret = std::__minmax_element_impl(std::move(__first), std::move(__last), __comp, __proj); + return {__ret.first, __ret.second}; + } + + template <forward_range _Rp, class _Proj = identity, + indirect_strict_weak_order<projected<iterator_t<_Rp>, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + ranges::minmax_element_result<borrowed_iterator_t<_Rp>> + operator()(_Rp&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + auto __ret = std::__minmax_element_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + return {__ret.first, __ret.second}; + } +}; +} // namespace __minmax_element + +inline namespace __cpo { + inline constexpr auto minmax_element = __minmax_element::__fn{}; +} // namespace __cpo + +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MINMAX_H diff --git a/libcxx/include/__algorithm/ranges_mismatch.h b/libcxx/include/__algorithm/ranges_mismatch.h new file mode 100644 index 000000000000..4c1440b5da06 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_mismatch.h @@ -0,0 +1,85 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MISMATCH_H +#define _LIBCPP___ALGORITHM_RANGES_MISMATCH_H + +#include <__algorithm/in_in_result.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/indirectly_comparable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +namespace ranges { + +template <class _I1, class _I2> +using mismatch_result = in_in_result<_I1, _I2>; + +namespace __mismatch { +struct __fn { + template <class _I1, class _S1, class _I2, class _S2, + class _Pred, class _Proj1, class _Proj2> + static _LIBCPP_HIDE_FROM_ABI constexpr + mismatch_result<_I1, _I2> + __go(_I1 __first1, _S1 __last1, _I2 __first2, _S2 __last2, + _Pred& __pred, _Proj1& __proj1, _Proj2& __proj2) { + while (__first1 != __last1 && __first2 != __last2) { + if (!std::invoke(__pred, std::invoke(__proj1, *__first1), std::invoke(__proj2, *__first2))) + break; + ++__first1; + ++__first2; + } + return {std::move(__first1), std::move(__first2)}; + } + + template <input_iterator _I1, sentinel_for<_I1> _S1, + input_iterator _I2, sentinel_for<_I2> _S2, + class _Pred = ranges::equal_to, class _Proj1 = identity, class _Proj2 = identity> + requires indirectly_comparable<_I1, _I2, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + mismatch_result<_I1, _I2> operator()(_I1 __first1, _S1 __last1, _I2 __first2, _S2 __last2, + _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { + return __go(std::move(__first1), __last1, std::move(__first2), __last2, __pred, __proj1, __proj2); + } + + template <input_range _R1, input_range _R2, + class _Pred = ranges::equal_to, class _Proj1 = identity, class _Proj2 = identity> + requires indirectly_comparable<iterator_t<_R1>, iterator_t<_R2>, _Pred, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + mismatch_result<borrowed_iterator_t<_R1>, borrowed_iterator_t<_R2>> + operator()(_R1&& __r1, _R2&& __r2, _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { + return __go(ranges::begin(__r1), ranges::end(__r1), ranges::begin(__r2), ranges::end(__r2), + __pred, __proj1, __proj2); + } +}; +} // namespace __mismatch + +inline namespace __cpo { + constexpr inline auto mismatch = __mismatch::__fn{}; +} // namespace __cpo +} // namespace ranges + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ALGORITHM_RANGES_MISMATCH_H diff --git a/libcxx/include/__algorithm/ranges_move.h b/libcxx/include/__algorithm/ranges_move.h new file mode 100644 index 000000000000..ad4342d7c989 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_move.h @@ -0,0 +1,83 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MOVE_H +#define _LIBCPP___ALGORITHM_RANGES_MOVE_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/move.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/iter_move.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _InIter, class _OutIter> +using move_result = in_out_result<_InIter, _OutIter>; + +namespace __move { +struct __fn { + + template <class _InIter, class _Sent, class _OutIter> + requires __iter_move::__move_deref<_InIter> // check that we are allowed to std::move() the value + _LIBCPP_HIDE_FROM_ABI constexpr static + move_result<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) { + auto __ret = std::__move(std::move(__first), std::move(__last), std::move(__result)); + return {std::move(__ret.first), std::move(__ret.second)}; + } + + template <class _InIter, class _Sent, class _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr static + move_result<_InIter, _OutIter> __move_impl(_InIter __first, _Sent __last, _OutIter __result) { + while (__first != __last) { + *__result = ranges::iter_move(__first); + ++__first; + ++__result; + } + return {std::move(__first), std::move(__result)}; + } + + template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter> + requires indirectly_movable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + move_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const { + return __move_impl(std::move(__first), std::move(__last), std::move(__result)); + } + + template <input_range _Range, weakly_incrementable _OutIter> + requires indirectly_movable<iterator_t<_Range>, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + move_result<borrowed_iterator_t<_Range>, _OutIter> operator()(_Range&& __range, _OutIter __result) const { + return __move_impl(ranges::begin(__range), ranges::end(__range), std::move(__result)); + } + +}; +} // namespace __move + +inline namespace __cpo { + inline constexpr auto move = __move::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MOVE_H diff --git a/libcxx/include/__algorithm/ranges_move_backward.h b/libcxx/include/__algorithm/ranges_move_backward.h new file mode 100644 index 000000000000..b3dfa7139603 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_move_backward.h @@ -0,0 +1,75 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_MOVE_BACKWARD_H +#define _LIBCPP___ALGORITHM_RANGES_MOVE_BACKWARD_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/ranges_move.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/iter_move.h> +#include <__iterator/next.h> +#include <__iterator/reverse_iterator.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _InIter, class _OutIter> +using move_backward_result = in_out_result<_InIter, _OutIter>; + +namespace __move_backward { +struct __fn { + + template <class _InIter, class _Sent, class _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr static + move_backward_result<_InIter, _OutIter> __move_backward_impl(_InIter __first, _Sent __last, _OutIter __result) { + auto __ret = ranges::move(std::make_reverse_iterator(ranges::next(__first, __last)), + std::make_reverse_iterator(__first), + std::make_reverse_iterator(__result)); + return {std::move(__ret.in.base()), std::move(__ret.out.base())}; + } + + template <bidirectional_iterator _InIter, sentinel_for<_InIter> _Sent, bidirectional_iterator _OutIter> + requires indirectly_movable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + move_backward_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const { + return __move_backward_impl(std::move(__first), std::move(__last), std::move(__result)); + } + + template <bidirectional_range _Range, bidirectional_iterator _Iter> + requires indirectly_movable<iterator_t<_Range>, _Iter> + _LIBCPP_HIDE_FROM_ABI constexpr + move_backward_result<borrowed_iterator_t<_Range>, _Iter> operator()(_Range&& __range, _Iter __result) const { + return __move_backward_impl(ranges::begin(__range), ranges::end(__range), std::move(__result)); + } + +}; +} // namespace __move_backward + +inline namespace __cpo { + inline constexpr auto move_backward = __move_backward::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MOVE_BACKWARD_H diff --git a/libcxx/include/__algorithm/ranges_none_of.h b/libcxx/include/__algorithm/ranges_none_of.h new file mode 100644 index 000000000000..706ff5cd741d --- /dev/null +++ b/libcxx/include/__algorithm/ranges_none_of.h @@ -0,0 +1,68 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_NONE_OF_H +#define _LIBCPP___ALGORITHM_RANGES_NONE_OF_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __none_of { +struct __fn { + + template <class _Iter, class _Sent, class _Proj, class _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr static + bool __none_of_impl(_Iter __first, _Sent __last, _Pred& __pred, _Proj& __proj) { + for (; __first != __last; ++__first) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) + return false; + } + return true; + } + + template <input_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Iter __first, _Sent __last, _Pred __pred = {}, _Proj __proj = {}) const { + return __none_of_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <input_range _Range, class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + bool operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const { + return __none_of_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj); + } +}; +} // namespace __none_of + +inline namespace __cpo { + inline constexpr auto none_of = __none_of::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_NONE_OF_H diff --git a/libcxx/include/__algorithm/ranges_replace.h b/libcxx/include/__algorithm/ranges_replace.h new file mode 100644 index 000000000000..5e74c3ff80cb --- /dev/null +++ b/libcxx/include/__algorithm/ranges_replace.h @@ -0,0 +1,74 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_REPLACE_H +#define _LIBCPP___ALGORITHM_RANGES_REPLACE_H + +#include <__algorithm/ranges_replace_if.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined (_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __replace { +struct __fn { + + template <input_iterator _Iter, sentinel_for<_Iter> _Sent, + class _Type1, + class _Type2, + class _Proj = identity> + requires indirectly_writable<_Iter, const _Type2&> + && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type1*> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, + const _Type1& __old_value, + const _Type2& __new_value, + _Proj __proj = {}) const { + auto __pred = [&](const auto& __val) { return __val == __old_value; }; + return ranges::__replace_if_impl(std::move(__first), std::move(__last), __pred, __new_value, __proj); + } + + template <input_range _Range, + class _Type1, + class _Type2, + class _Proj = identity> + requires indirectly_writable<iterator_t<_Range>, const _Type2&> + && indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type1*> + _LIBCPP_HIDE_FROM_ABI constexpr borrowed_iterator_t<_Range> + operator()(_Range&& __range, const _Type1& __old_value, const _Type2& __new_value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __val) { return __val == __old_value; }; + return ranges::__replace_if_impl(ranges::begin(__range), ranges::end(__range), __pred, __new_value, __proj); + } + +}; +} // namespace __replace + +inline namespace __cpo { + inline constexpr auto replace = __replace::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined (_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_REPLACE_H diff --git a/libcxx/include/__algorithm/ranges_replace_if.h b/libcxx/include/__algorithm/ranges_replace_if.h new file mode 100644 index 000000000000..0f9555fc35c2 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_replace_if.h @@ -0,0 +1,77 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_REPLACE_IF_H +#define _LIBCPP___ALGORITHM_RANGES_REPLACE_IF_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined (_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _Iter, class _Sent, class _Type, class _Proj, class _Pred> +_LIBCPP_HIDE_FROM_ABI constexpr +_Iter __replace_if_impl(_Iter __first, _Sent __last, _Pred& __pred, const _Type& __new_value, _Proj& __proj) { + for (; __first != __last; ++__first) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) + *__first = __new_value; + } + return __first; +} + +namespace __replace_if { +struct __fn { + + template <input_iterator _Iter, sentinel_for<_Iter> _Sent, + class _Type, + class _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + requires indirectly_writable<_Iter, const _Type&> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, _Pred __pred, const _Type& __new_value, _Proj __proj = {}) const { + return ranges::__replace_if_impl(std::move(__first), std::move(__last), __pred, __new_value, __proj); + } + + template <input_range _Range, + class _Type, + class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + requires indirectly_writable<iterator_t<_Range>, const _Type&> + _LIBCPP_HIDE_FROM_ABI constexpr borrowed_iterator_t<_Range> + operator()(_Range&& __range, _Pred __pred, const _Type& __new_value, _Proj __proj = {}) const { + return ranges::__replace_if_impl(ranges::begin(__range), ranges::end(__range), __pred, __new_value, __proj); + } + +}; +} // namespace __replace_if + +inline namespace __cpo { + inline constexpr auto replace_if = __replace_if::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined (_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_REPLACE_IF_H diff --git a/libcxx/include/__algorithm/ranges_reverse.h b/libcxx/include/__algorithm/ranges_reverse.h new file mode 100644 index 000000000000..e7555d0f9acd --- /dev/null +++ b/libcxx/include/__algorithm/ranges_reverse.h @@ -0,0 +1,83 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_REVERSE_H +#define _LIBCPP___ALGORITHM_RANGES_REVERSE_H + +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/iter_swap.h> +#include <__iterator/next.h> +#include <__iterator/permutable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __reverse { +struct __fn { + + template <bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent> + requires permutable<_Iter> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last) const { + if constexpr (random_access_iterator<_Iter>) { + if (__first == __last) + return __first; + + auto __end = ranges::next(__first, __last); + auto __ret = __end; + + while (__first < --__end) { + ranges::iter_swap(__first, __end); + ++__first; + } + return __ret; + } else { + auto __end = ranges::next(__first, __last); + auto __ret = __end; + + while (__first != __end) { + if (__first == --__end) + break; + + ranges::iter_swap(__first, __end); + ++__first; + } + return __ret; + } + } + + template <bidirectional_range _Range> + requires permutable<iterator_t<_Range>> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __range) const { + return (*this)(ranges::begin(__range), ranges::end(__range)); + } + +}; +} // namespace __reverse + +inline namespace __cpo { + inline constexpr auto reverse = __reverse::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_REVERSE_H diff --git a/libcxx/include/__algorithm/ranges_sort.h b/libcxx/include/__algorithm/ranges_sort.h new file mode 100644 index 000000000000..8297940df237 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_sort.h @@ -0,0 +1,78 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_SORT_H +#define _LIBCPP___ALGORITHM_RANGES_SORT_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/sort.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__iterator/projected.h> +#include <__iterator/sortable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __sort { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __last_iter = ranges::next(__first, __last); + + auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + std::__sort_impl(std::move(__first), __last_iter, __projected_comp); + + return __last_iter; + } + + template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __sort_fn_impl(std::move(__first), std::move(__last), __comp, __proj); + } + + template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity> + requires sortable<iterator_t<_Range>, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + return __sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __sort + +inline namespace __cpo { + inline constexpr auto sort = __sort::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_SORT_H diff --git a/libcxx/include/__algorithm/ranges_stable_sort.h b/libcxx/include/__algorithm/ranges_stable_sort.h new file mode 100644 index 000000000000..20e840426434 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_stable_sort.h @@ -0,0 +1,78 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H +#define _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/stable_sort.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__iterator/projected.h> +#include <__iterator/sortable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/forward.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __stable_sort { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI + static _Iter __stable_sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __last_iter = ranges::next(__first, __last); + + auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + std::__stable_sort_impl(std::move(__first), __last_iter, __projected_comp); + + return __last_iter; + } + + template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity> + requires sortable<_Iter, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI + _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __stable_sort_fn_impl(std::move(__first), std::move(__last), __comp, __proj); + } + + template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity> + requires sortable<iterator_t<_Range>, _Comp, _Proj> + _LIBCPP_HIDE_FROM_ABI + borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const { + return __stable_sort_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __stable_sort + +inline namespace __cpo { + inline constexpr auto stable_sort = __stable_sort::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_STABLE_SORT_H diff --git a/libcxx/include/__algorithm/ranges_swap_ranges.h b/libcxx/include/__algorithm/ranges_swap_ranges.h new file mode 100644 index 000000000000..3254e1c60abb --- /dev/null +++ b/libcxx/include/__algorithm/ranges_swap_ranges.h @@ -0,0 +1,69 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_SWAP_RANGES_H +#define _LIBCPP___ALGORITHM_RANGES_SWAP_RANGES_H + +#include <__algorithm/in_in_result.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/iter_swap.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _I1, class _I2> +using swap_ranges_result = in_in_result<_I1, _I2>; + +namespace __swap_ranges { +struct __fn { + template <input_iterator _I1, sentinel_for<_I1> _S1, + input_iterator _I2, sentinel_for<_I2> _S2> + requires indirectly_swappable<_I1, _I2> + _LIBCPP_HIDE_FROM_ABI constexpr swap_ranges_result<_I1, _I2> + operator()(_I1 __first1, _S1 __last1, _I2 __first2, _S2 __last2) const { + while (__first1 != __last1 && __first2 != __last2) { + ranges::iter_swap(__first1, __first2); + ++__first1; + ++__first2; + } + return {_VSTD::move(__first1), _VSTD::move(__first2)}; + } + + template <input_range _R1, input_range _R2> + requires indirectly_swappable<iterator_t<_R1>, iterator_t<_R2>> + _LIBCPP_HIDE_FROM_ABI constexpr + swap_ranges_result<borrowed_iterator_t<_R1>, borrowed_iterator_t<_R2>> + operator()(_R1&& __r1, _R2&& __r2) const { + return operator()(ranges::begin(__r1), ranges::end(__r1), + ranges::begin(__r2), ranges::end(__r2)); + } +}; +} // namespace __swap_ranges + +inline namespace __cpo { + inline constexpr auto swap_ranges = __swap_ranges::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_SWAP_RANGES_H diff --git a/libcxx/include/__algorithm/ranges_transform.h b/libcxx/include/__algorithm/ranges_transform.h new file mode 100644 index 000000000000..3c13b1b79ff3 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_transform.h @@ -0,0 +1,170 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_TRANSFORM_H +#define _LIBCPP___ALGORITHM_RANGES_TRANSFORM_H + +#include <__algorithm/in_in_out_result.h> +#include <__algorithm/in_out_result.h> +#include <__concepts/constructible.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { + +template <class _Ip, class _Op> +using unary_transform_result = in_out_result<_Ip, _Op>; + +template <class _I1, class _I2, class _O1> +using binary_transform_result = in_in_out_result<_I1, _I2, _O1>; + +namespace __transform { +struct __fn { +private: + template <class _InIter, class _Sent, + class _OutIter, + class _Func, + class _Proj> + _LIBCPP_HIDE_FROM_ABI static constexpr + unary_transform_result<_InIter, _OutIter> __unary(_InIter __first, _Sent __last, + _OutIter __result, + _Func& __operation, + _Proj& __projection) { + while (__first != __last) { + *__result = std::invoke(__operation, std::invoke(__projection, *__first)); + ++__first; + ++__result; + } + + return {std::move(__first), std::move(__result)}; + } + + template <class _InIter1, class _Sent1, + class _InIter2, class _Sent2, + class _OutIter, + class _Func, + class _Proj1, + class _Proj2> + _LIBCPP_HIDE_FROM_ABI static constexpr binary_transform_result<_InIter1, _InIter2, _OutIter> + __binary(_InIter1 __first1, _Sent1 __last1, + _InIter2 __first2, _Sent2 __last2, + _OutIter __result, + _Func& __binary_operation, + _Proj1& __projection1, + _Proj2& __projection2) { + while (__first1 != __last1 && __first2 != __last2) { + *__result = std::invoke(__binary_operation, std::invoke(__projection1, *__first1), + std::invoke(__projection2, *__first2)); + ++__first1; + ++__first2; + ++__result; + } + return {std::move(__first1), std::move(__first2), std::move(__result)}; + } +public: + template <input_iterator _InIter, sentinel_for<_InIter> _Sent, + weakly_incrementable _OutIter, + copy_constructible _Func, + class _Proj = identity> + requires indirectly_writable<_OutIter, indirect_result_t<_Func&, projected<_InIter, _Proj>>> + _LIBCPP_HIDE_FROM_ABI constexpr + unary_transform_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, + _OutIter __result, + _Func __operation, + _Proj __proj = {}) const { + return __unary(std::move(__first), std::move(__last), std::move(__result), __operation, __proj); + } + + template <input_range _Range, + weakly_incrementable _OutIter, + copy_constructible _Func, + class _Proj = identity> + requires indirectly_writable<_OutIter, indirect_result_t<_Func, projected<iterator_t<_Range>, _Proj>>> + _LIBCPP_HIDE_FROM_ABI constexpr + unary_transform_result<borrowed_iterator_t<_Range>, _OutIter> operator()(_Range&& __range, + _OutIter __result, + _Func __operation, + _Proj __projection = {}) const { + return __unary(ranges::begin(__range), ranges::end(__range), std::move(__result), __operation, __projection); + } + + template <input_iterator _InIter1, sentinel_for<_InIter1> _Sent1, + input_iterator _InIter2, sentinel_for<_InIter2> _Sent2, + weakly_incrementable _OutIter, + copy_constructible _Func, + class _Proj1 = identity, + class _Proj2 = identity> + requires indirectly_writable<_OutIter, indirect_result_t<_Func&, projected<_InIter1, _Proj1>, + projected<_InIter2, _Proj2>>> + _LIBCPP_HIDE_FROM_ABI constexpr + binary_transform_result<_InIter1, _InIter2, _OutIter> operator()(_InIter1 __first1, _Sent1 __last1, + _InIter2 __first2, _Sent2 __last2, + _OutIter __result, + _Func __binary_operation, + _Proj1 __projection1 = {}, + _Proj2 __projection2 = {}) const { + return __binary(std::move(__first1), std::move(__last1), + std::move(__first2), std::move(__last2), + std::move(__result), + __binary_operation, + __projection1, + __projection2); + } + + template <input_range _Range1, + input_range _Range2, + weakly_incrementable _OutIter, + copy_constructible _Func, + class _Proj1 = identity, + class _Proj2 = identity> + requires indirectly_writable<_OutIter, indirect_result_t<_Func&, projected<iterator_t<_Range1>, _Proj1>, + projected<iterator_t<_Range2>, _Proj2>>> + _LIBCPP_HIDE_FROM_ABI constexpr + binary_transform_result<borrowed_iterator_t<_Range1>, borrowed_iterator_t<_Range2>, _OutIter> + operator()(_Range1&& __range1, + _Range2&& __range2, + _OutIter __result, + _Func __binary_operation, + _Proj1 __projection1 = {}, + _Proj2 __projection2 = {}) const { + return __binary(ranges::begin(__range1), ranges::end(__range1), + ranges::begin(__range2), ranges::end(__range2), + std::move(__result), + __binary_operation, + __projection1, + __projection2); + } + +}; +} // namespace __transform + +inline namespace __cpo { + inline constexpr auto transform = __transform::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_TRANSFORM_H diff --git a/libcxx/include/__algorithm/ranges_upper_bound.h b/libcxx/include/__algorithm/ranges_upper_bound.h new file mode 100644 index 000000000000..94b5269c86af --- /dev/null +++ b/libcxx/include/__algorithm/ranges_upper_bound.h @@ -0,0 +1,75 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ALGORITHM_RANGES_UPPER_BOUND_H +#define _LIBCPP___ALGORITHM_RANGES_UPPER_BOUND_H + +#include <__algorithm/iterator_operations.h> +#include <__algorithm/lower_bound.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_BEGIN_NAMESPACE_STD + +namespace ranges { +namespace __upper_bound { +struct __fn { + template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity, + indirect_strict_weak_order<const _Type*, projected<_Iter, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const { + auto __comp_lhs_rhs_swapped = [&](const auto& __lhs, const auto& __rhs) { + return !std::invoke(__comp, __rhs, __lhs); + }; + + return std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp_lhs_rhs_swapped, __proj); + } + + template <forward_range _Range, class _Type, class _Proj = identity, + indirect_strict_weak_order<const _Type*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __r, + const _Type& __value, + _Comp __comp = {}, + _Proj __proj = {}) const { + auto __comp_lhs_rhs_swapped = [&](const auto& __lhs, const auto& __rhs) { + return !std::invoke(__comp, __rhs, __lhs); + }; + + return std::__lower_bound_impl<_RangesIterOps>(ranges::begin(__r), + ranges::end(__r), + __value, + __comp_lhs_rhs_swapped, + __proj); + } +}; +} // namespace __upper_bound + +inline namespace __cpo { + inline constexpr auto upper_bound = __upper_bound::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_UPPER_BOUND_H diff --git a/libcxx/include/__algorithm/remove.h b/libcxx/include/__algorithm/remove.h index 681b9cc768d9..c00f96f78a63 100644 --- a/libcxx/include/__algorithm/remove.h +++ b/libcxx/include/__algorithm/remove.h @@ -15,7 +15,7 @@ #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/remove_copy.h b/libcxx/include/__algorithm/remove_copy.h index 338ca94300bb..a29a385af9ac 100644 --- a/libcxx/include/__algorithm/remove_copy.h +++ b/libcxx/include/__algorithm/remove_copy.h @@ -12,7 +12,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/remove_copy_if.h b/libcxx/include/__algorithm/remove_copy_if.h index a55638722074..36ddba4883ab 100644 --- a/libcxx/include/__algorithm/remove_copy_if.h +++ b/libcxx/include/__algorithm/remove_copy_if.h @@ -12,7 +12,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/remove_if.h b/libcxx/include/__algorithm/remove_if.h index 36f817cfa6e1..0ae131498d22 100644 --- a/libcxx/include/__algorithm/remove_if.h +++ b/libcxx/include/__algorithm/remove_if.h @@ -11,10 +11,10 @@ #include <__algorithm/find_if.h> #include <__config> -#include <utility> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/replace.h b/libcxx/include/__algorithm/replace.h index 2bc96ffc87dc..d0ae8f65d4a2 100644 --- a/libcxx/include/__algorithm/replace.h +++ b/libcxx/include/__algorithm/replace.h @@ -12,7 +12,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/replace_copy.h b/libcxx/include/__algorithm/replace_copy.h index c6c5fe32e81c..7c8a5a0b93cb 100644 --- a/libcxx/include/__algorithm/replace_copy.h +++ b/libcxx/include/__algorithm/replace_copy.h @@ -12,7 +12,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/replace_copy_if.h b/libcxx/include/__algorithm/replace_copy_if.h index 274d8e630ef1..9d8a68fdc0f3 100644 --- a/libcxx/include/__algorithm/replace_copy_if.h +++ b/libcxx/include/__algorithm/replace_copy_if.h @@ -12,7 +12,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/replace_if.h b/libcxx/include/__algorithm/replace_if.h index bcc3feb2f507..37c719a34c84 100644 --- a/libcxx/include/__algorithm/replace_if.h +++ b/libcxx/include/__algorithm/replace_if.h @@ -12,7 +12,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/reverse.h b/libcxx/include/__algorithm/reverse.h index 1198aeaf41f4..0202cd740833 100644 --- a/libcxx/include/__algorithm/reverse.h +++ b/libcxx/include/__algorithm/reverse.h @@ -14,7 +14,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/reverse_copy.h b/libcxx/include/__algorithm/reverse_copy.h index 002c0344a794..158390707803 100644 --- a/libcxx/include/__algorithm/reverse_copy.h +++ b/libcxx/include/__algorithm/reverse_copy.h @@ -12,7 +12,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/rotate.h b/libcxx/include/__algorithm/rotate.h index fd6d3e9c114f..c9ea5bad4c5a 100644 --- a/libcxx/include/__algorithm/rotate.h +++ b/libcxx/include/__algorithm/rotate.h @@ -16,11 +16,12 @@ #include <__iterator/iterator_traits.h> #include <__iterator/next.h> #include <__iterator/prev.h> +#include <__utility/move.h> #include <__utility/swap.h> -#include <iterator> +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/rotate_copy.h b/libcxx/include/__algorithm/rotate_copy.h index f9e644c88d0e..ab569ef7c6be 100644 --- a/libcxx/include/__algorithm/rotate_copy.h +++ b/libcxx/include/__algorithm/rotate_copy.h @@ -13,7 +13,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/sample.h b/libcxx/include/__algorithm/sample.h index 33264c4ea3a7..e04466a08d5a 100644 --- a/libcxx/include/__algorithm/sample.h +++ b/libcxx/include/__algorithm/sample.h @@ -10,13 +10,15 @@ #define _LIBCPP___ALGORITHM_SAMPLE_H #include <__algorithm/min.h> +#include <__assert> #include <__config> -#include <__debug> +#include <__iterator/distance.h> +#include <__iterator/iterator_traits.h> #include <__random/uniform_int_distribution.h> -#include <iterator> +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_PUSH_MACROS diff --git a/libcxx/include/__algorithm/search.h b/libcxx/include/__algorithm/search.h index cfaec0ed1e17..d89ec2b1c5bc 100644 --- a/libcxx/include/__algorithm/search.h +++ b/libcxx/include/__algorithm/search.h @@ -13,10 +13,10 @@ #include <__algorithm/comp.h> #include <__config> #include <__iterator/iterator_traits.h> -#include <utility> +#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/search_n.h b/libcxx/include/__algorithm/search_n.h index e4576cc76ac4..4c083de65ee2 100644 --- a/libcxx/include/__algorithm/search_n.h +++ b/libcxx/include/__algorithm/search_n.h @@ -16,7 +16,7 @@ #include <type_traits> // __convert_to_integral #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_difference.h b/libcxx/include/__algorithm/set_difference.h index 00f61e070b4b..5e2dca24e446 100644 --- a/libcxx/include/__algorithm/set_difference.h +++ b/libcxx/include/__algorithm/set_difference.h @@ -16,7 +16,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_intersection.h b/libcxx/include/__algorithm/set_intersection.h index f6aa38217d95..c4163fcd4c3c 100644 --- a/libcxx/include/__algorithm/set_intersection.h +++ b/libcxx/include/__algorithm/set_intersection.h @@ -15,7 +15,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_symmetric_difference.h b/libcxx/include/__algorithm/set_symmetric_difference.h index 5b5c2acff773..2dbfb35d7be6 100644 --- a/libcxx/include/__algorithm/set_symmetric_difference.h +++ b/libcxx/include/__algorithm/set_symmetric_difference.h @@ -16,7 +16,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_union.h b/libcxx/include/__algorithm/set_union.h index 5b3e3af79b4f..0ec6b09380ed 100644 --- a/libcxx/include/__algorithm/set_union.h +++ b/libcxx/include/__algorithm/set_union.h @@ -16,7 +16,7 @@ #include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/shift_left.h b/libcxx/include/__algorithm/shift_left.h index 0466a3188a75..33f06d57e23a 100644 --- a/libcxx/include/__algorithm/shift_left.h +++ b/libcxx/include/__algorithm/shift_left.h @@ -15,7 +15,7 @@ #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/shift_right.h b/libcxx/include/__algorithm/shift_right.h index 121712e85532..14bc761598b2 100644 --- a/libcxx/include/__algorithm/shift_right.h +++ b/libcxx/include/__algorithm/shift_right.h @@ -18,7 +18,7 @@ #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/shuffle.h b/libcxx/include/__algorithm/shuffle.h index 7f6ad50e241e..6c6ff5675dad 100644 --- a/libcxx/include/__algorithm/shuffle.h +++ b/libcxx/include/__algorithm/shuffle.h @@ -10,6 +10,7 @@ #define _LIBCPP___ALGORITHM_SHUFFLE_H #include <__config> +#include <__debug> #include <__iterator/iterator_traits.h> #include <__random/uniform_int_distribution.h> #include <__utility/swap.h> @@ -17,7 +18,7 @@ #include <cstdint> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_PUSH_MACROS diff --git a/libcxx/include/__algorithm/sift_down.h b/libcxx/include/__algorithm/sift_down.h index bf5447698cd6..0351a1c578b0 100644 --- a/libcxx/include/__algorithm/sift_down.h +++ b/libcxx/include/__algorithm/sift_down.h @@ -9,12 +9,13 @@ #ifndef _LIBCPP___ALGORITHM_SIFT_DOWN_H #define _LIBCPP___ALGORITHM_SIFT_DOWN_H +#include <__assert> #include <__config> #include <__iterator/iterator_traits.h> #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD @@ -73,6 +74,38 @@ __sift_down(_RandomAccessIterator __first, _Compare __comp, *__start = _VSTD::move(__top); } +template <class _Compare, class _RandomAccessIterator> +_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator +__floyd_sift_down(_RandomAccessIterator __first, _Compare __comp, + typename iterator_traits<_RandomAccessIterator>::difference_type __len) +{ + using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; + _LIBCPP_ASSERT(__len >= 2, "shouldn't be called unless __len >= 2"); + + _RandomAccessIterator __hole = __first; + _RandomAccessIterator __child_i = __first; + difference_type __child = 0; + + while (true) { + __child_i += difference_type(__child + 1); + __child = 2 * __child + 1; + + if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) { + // right-child exists and is greater than left-child + ++__child_i; + ++__child; + } + + // swap __hole with its largest child + *__hole = std::move(*__child_i); + __hole = __child_i; + + // if __hole is now a leaf, we're done + if (__child > (__len - 2) / 2) + return __hole; + } +} + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ALGORITHM_SIFT_DOWN_H diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h index 5e09b280080a..f7406a5170e1 100644 --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -14,8 +14,14 @@ #include <__algorithm/min_element.h> #include <__algorithm/partial_sort.h> #include <__algorithm/unwrap_iter.h> +#include <__bits> #include <__config> +#include <__debug> +#include <__functional/operations.h> +#include <__functional/ranges_operations.h> +#include <__iterator/iterator_traits.h> #include <__utility/swap.h> +#include <climits> #include <memory> #if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY) @@ -23,7 +29,7 @@ #endif #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD @@ -31,442 +37,489 @@ _LIBCPP_BEGIN_NAMESPACE_STD // stable, 2-3 compares, 0-2 swaps template <class _Compare, class _ForwardIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned -__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c) -{ - unsigned __r = 0; - if (!__c(*__y, *__x)) // if x <= y +_LIBCPP_CONSTEXPR_AFTER_CXX11 unsigned __sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, + _Compare __c) { + unsigned __r = 0; + if (!__c(*__y, *__x)) // if x <= y + { + if (!__c(*__z, *__y)) // if y <= z + return __r; // x <= y && y <= z + // x <= y && y > z + swap(*__y, *__z); // x <= z && y < z + __r = 1; + if (__c(*__y, *__x)) // if x > y { - if (!__c(*__z, *__y)) // if y <= z - return __r; // x <= y && y <= z - // x <= y && y > z - swap(*__y, *__z); // x <= z && y < z - __r = 1; - if (__c(*__y, *__x)) // if x > y - { - swap(*__x, *__y); // x < y && y <= z - __r = 2; - } - return __r; // x <= y && y < z - } - if (__c(*__z, *__y)) // x > y, if y > z - { - swap(*__x, *__z); // x < y && y < z - __r = 1; - return __r; - } - swap(*__x, *__y); // x > y && y <= z - __r = 1; // x < y && x <= z - if (__c(*__z, *__y)) // if y > z - { - swap(*__y, *__z); // x <= y && y < z - __r = 2; + swap(*__x, *__y); // x < y && y <= z + __r = 2; } + return __r; // x <= y && y < z + } + if (__c(*__z, *__y)) // x > y, if y > z + { + swap(*__x, *__z); // x < y && y < z + __r = 1; return __r; -} // x <= y && y <= z + } + swap(*__x, *__y); // x > y && y <= z + __r = 1; // x < y && x <= z + if (__c(*__z, *__y)) // if y > z + { + swap(*__y, *__z); // x <= y && y < z + __r = 2; + } + return __r; +} // x <= y && y <= z // stable, 3-6 compares, 0-5 swaps template <class _Compare, class _ForwardIterator> -unsigned -__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, - _ForwardIterator __x4, _Compare __c) -{ - unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); - if (__c(*__x4, *__x3)) - { - swap(*__x3, *__x4); +unsigned __sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, + _Compare __c) { + unsigned __r = _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); + if (__c(*__x4, *__x3)) { + swap(*__x3, *__x4); + ++__r; + if (__c(*__x3, *__x2)) { + swap(*__x2, *__x3); + ++__r; + if (__c(*__x2, *__x1)) { + swap(*__x1, *__x2); ++__r; - if (__c(*__x3, *__x2)) - { - swap(*__x2, *__x3); - ++__r; - if (__c(*__x2, *__x1)) - { - swap(*__x1, *__x2); - ++__r; - } - } + } } - return __r; + } + return __r; } // stable, 4-10 compares, 0-9 swaps template <class _Compare, class _ForwardIterator> -_LIBCPP_HIDDEN -unsigned -__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, - _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) -{ - unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c); - if (__c(*__x5, *__x4)) - { - swap(*__x4, *__x5); +_LIBCPP_HIDDEN unsigned __sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, + _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c) { + unsigned __r = _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c); + if (__c(*__x5, *__x4)) { + swap(*__x4, *__x5); + ++__r; + if (__c(*__x4, *__x3)) { + swap(*__x3, *__x4); + ++__r; + if (__c(*__x3, *__x2)) { + swap(*__x2, *__x3); ++__r; - if (__c(*__x4, *__x3)) - { - swap(*__x3, *__x4); - ++__r; - if (__c(*__x3, *__x2)) - { - swap(*__x2, *__x3); - ++__r; - if (__c(*__x2, *__x1)) - { - swap(*__x1, *__x2); - ++__r; - } - } + if (__c(*__x2, *__x1)) { + swap(*__x1, *__x2); + ++__r; } + } } - return __r; + } + return __r; +} + +// The comparator being simple is a prerequisite for using the branchless optimization. +template <class _Tp> +struct __is_simple_comparator : false_type {}; +template <class _Tp> +struct __is_simple_comparator<__less<_Tp>&> : true_type {}; +template <class _Tp> +struct __is_simple_comparator<less<_Tp>&> : true_type {}; +template <class _Tp> +struct __is_simple_comparator<greater<_Tp>&> : true_type {}; +#if _LIBCPP_STD_VER > 17 +template <> +struct __is_simple_comparator<ranges::less&> : true_type {}; +template <> +struct __is_simple_comparator<ranges::greater&> : true_type {}; +#endif + +template <class _Compare, class _Iter, class _Tp = typename iterator_traits<_Iter>::value_type> +using __use_branchless_sort = + integral_constant<bool, __is_cpp17_contiguous_iterator<_Iter>::value && sizeof(_Tp) <= sizeof(void*) && + is_arithmetic<_Tp>::value && __is_simple_comparator<_Compare>::value>; + +// Ensures that __c(*__x, *__y) is true by swapping *__x and *__y if necessary. +template <class _Compare, class _RandomAccessIterator> +inline _LIBCPP_HIDE_FROM_ABI void __cond_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, _Compare __c) { + using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; + bool __r = __c(*__x, *__y); + value_type __tmp = __r ? *__x : *__y; + *__y = __r ? *__y : *__x; + *__x = __tmp; +} + +// Ensures that *__x, *__y and *__z are ordered according to the comparator __c, +// under the assumption that *__y and *__z are already ordered. +template <class _Compare, class _RandomAccessIterator> +inline _LIBCPP_HIDE_FROM_ABI void __partially_sorted_swap(_RandomAccessIterator __x, _RandomAccessIterator __y, + _RandomAccessIterator __z, _Compare __c) { + using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; + bool __r = __c(*__z, *__x); + value_type __tmp = __r ? *__z : *__x; + *__z = __r ? *__x : *__z; + __r = __c(__tmp, *__y); + *__x = __r ? *__x : *__y; + *__y = __r ? *__y : __tmp; +} + +template <class _Compare, class _RandomAccessIterator> +inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> +__sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, + _Compare __c) { + _VSTD::__cond_swap<_Compare>(__x2, __x3, __c); + _VSTD::__partially_sorted_swap<_Compare>(__x1, __x2, __x3, __c); +} + +template <class _Compare, class _RandomAccessIterator> +inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> +__sort3_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, + _Compare __c) { + _VSTD::__sort3<_Compare>(__x1, __x2, __x3, __c); +} + +template <class _Compare, class _RandomAccessIterator> +inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> +__sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, + _RandomAccessIterator __x4, _Compare __c) { + _VSTD::__cond_swap<_Compare>(__x1, __x3, __c); + _VSTD::__cond_swap<_Compare>(__x2, __x4, __c); + _VSTD::__cond_swap<_Compare>(__x1, __x2, __c); + _VSTD::__cond_swap<_Compare>(__x3, __x4, __c); + _VSTD::__cond_swap<_Compare>(__x2, __x3, __c); +} + +template <class _Compare, class _RandomAccessIterator> +inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> +__sort4_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, + _RandomAccessIterator __x4, _Compare __c) { + _VSTD::__sort4<_Compare>(__x1, __x2, __x3, __x4, __c); +} + +template <class _Compare, class _RandomAccessIterator> +inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> +__sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, + _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { + _VSTD::__cond_swap<_Compare>(__x1, __x2, __c); + _VSTD::__cond_swap<_Compare>(__x4, __x5, __c); + _VSTD::__partially_sorted_swap<_Compare>(__x3, __x4, __x5, __c); + _VSTD::__cond_swap<_Compare>(__x2, __x5, __c); + _VSTD::__partially_sorted_swap<_Compare>(__x1, __x3, __x4, __c); + _VSTD::__partially_sorted_swap<_Compare>(__x2, __x3, __x4, __c); +} + +template <class _Compare, class _RandomAccessIterator> +inline _LIBCPP_HIDE_FROM_ABI __enable_if_t<!__use_branchless_sort<_Compare, _RandomAccessIterator>::value, void> +__sort5_maybe_branchless(_RandomAccessIterator __x1, _RandomAccessIterator __x2, _RandomAccessIterator __x3, + _RandomAccessIterator __x4, _RandomAccessIterator __x5, _Compare __c) { + _VSTD::__sort5<_Compare>(__x1, __x2, __x3, __x4, __x5, __c); } // Assumes size > 0 template <class _Compare, class _BidirectionalIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX11 void -__selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) -{ - _BidirectionalIterator __lm1 = __last; - for (--__lm1; __first != __lm1; ++__first) - { - _BidirectionalIterator __i = _VSTD::min_element(__first, __last, __comp); - if (__i != __first) - swap(*__first, *__i); - } +_LIBCPP_CONSTEXPR_AFTER_CXX11 void __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, + _Compare __comp) { + _BidirectionalIterator __lm1 = __last; + for (--__lm1; __first != __lm1; ++__first) { + _BidirectionalIterator __i = _VSTD::min_element(__first, __last, __comp); + if (__i != __first) + swap(*__first, *__i); + } } template <class _Compare, class _BidirectionalIterator> -void -__insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) -{ - typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; - if (__first != __last) - { - _BidirectionalIterator __i = __first; - for (++__i; __i != __last; ++__i) - { - _BidirectionalIterator __j = __i; - value_type __t(_VSTD::move(*__j)); - for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) - *__j = _VSTD::move(*__k); - *__j = _VSTD::move(__t); - } +void __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp) { + typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; + if (__first != __last) { + _BidirectionalIterator __i = __first; + for (++__i; __i != __last; ++__i) { + _BidirectionalIterator __j = __i; + value_type __t(_VSTD::move(*__j)); + for (_BidirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) + *__j = _VSTD::move(*__k); + *__j = _VSTD::move(__t); } + } } template <class _Compare, class _RandomAccessIterator> -void -__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; - _RandomAccessIterator __j = __first+difference_type(2); - _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), __j, __comp); - for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i) - { - if (__comp(*__i, *__j)) - { - value_type __t(_VSTD::move(*__i)); - _RandomAccessIterator __k = __j; - __j = __i; - do - { - *__j = _VSTD::move(*__k); - __j = __k; - } while (__j != __first && __comp(__t, *--__k)); - *__j = _VSTD::move(__t); - } - __j = __i; +void __insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; + typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; + _RandomAccessIterator __j = __first + difference_type(2); + _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp); + for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) { + if (__comp(*__i, *__j)) { + value_type __t(_VSTD::move(*__i)); + _RandomAccessIterator __k = __j; + __j = __i; + do { + *__j = _VSTD::move(*__k); + __j = __k; + } while (__j != __first && __comp(__t, *--__k)); + *__j = _VSTD::move(__t); } + __j = __i; + } } template <class _Compare, class _RandomAccessIterator> -bool -__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - switch (__last - __first) - { +bool __insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; + switch (__last - __first) { + case 0: + case 1: + return true; + case 2: + if (__comp(*--__last, *__first)) + swap(*__first, *__last); + return true; + case 3: + _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp); + return true; + case 4: + _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), + --__last, __comp); + return true; + case 5: + _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), + __first + difference_type(3), --__last, __comp); + return true; + } + typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; + _RandomAccessIterator __j = __first + difference_type(2); + _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), __j, __comp); + const unsigned __limit = 8; + unsigned __count = 0; + for (_RandomAccessIterator __i = __j + difference_type(1); __i != __last; ++__i) { + if (__comp(*__i, *__j)) { + value_type __t(_VSTD::move(*__i)); + _RandomAccessIterator __k = __j; + __j = __i; + do { + *__j = _VSTD::move(*__k); + __j = __k; + } while (__j != __first && __comp(__t, *--__k)); + *__j = _VSTD::move(__t); + if (++__count == __limit) + return ++__i == __last; + } + __j = __i; + } + return true; +} + +template <class _Compare, class _BidirectionalIterator> +void __insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1, + typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) { + typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; + if (__first1 != __last1) { + __destruct_n __d(0); + unique_ptr<value_type, __destruct_n&> __h(__first2, __d); + value_type* __last2 = __first2; + ::new ((void*)__last2) value_type(_VSTD::move(*__first1)); + __d.template __incr<value_type>(); + for (++__last2; ++__first1 != __last1; ++__last2) { + value_type* __j2 = __last2; + value_type* __i2 = __j2; + if (__comp(*__first1, *--__i2)) { + ::new ((void*)__j2) value_type(_VSTD::move(*__i2)); + __d.template __incr<value_type>(); + for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) + *__j2 = _VSTD::move(*__i2); + *__j2 = _VSTD::move(*__first1); + } else { + ::new ((void*)__j2) value_type(_VSTD::move(*__first1)); + __d.template __incr<value_type>(); + } + } + __h.release(); + } +} + +template <class _Compare, class _RandomAccessIterator> +void __introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, + typename iterator_traits<_RandomAccessIterator>::difference_type __depth) { + typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; + typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; + const difference_type __limit = + is_trivially_copy_constructible<value_type>::value && is_trivially_copy_assignable<value_type>::value ? 30 : 6; + while (true) { + __restart: + difference_type __len = __last - __first; + switch (__len) { case 0: case 1: - return true; + return; case 2: - if (__comp(*--__last, *__first)) - swap(*__first, *__last); - return true; + if (__comp(*--__last, *__first)) + swap(*__first, *__last); + return; case 3: - _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), --__last, __comp); - return true; + _VSTD::__sort3_maybe_branchless<_Compare>(__first, __first + difference_type(1), --__last, __comp); + return; case 4: - _VSTD::__sort4<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), --__last, __comp); - return true; + _VSTD::__sort4_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), + --__last, __comp); + return; case 5: - _VSTD::__sort5<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), __first+difference_type(3), --__last, __comp); - return true; + _VSTD::__sort5_maybe_branchless<_Compare>(__first, __first + difference_type(1), __first + difference_type(2), + __first + difference_type(3), --__last, __comp); + return; } - typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; - _RandomAccessIterator __j = __first+difference_type(2); - _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), __j, __comp); - const unsigned __limit = 8; - unsigned __count = 0; - for (_RandomAccessIterator __i = __j+difference_type(1); __i != __last; ++__i) - { - if (__comp(*__i, *__j)) - { - value_type __t(_VSTD::move(*__i)); - _RandomAccessIterator __k = __j; - __j = __i; - do - { - *__j = _VSTD::move(*__k); - __j = __k; - } while (__j != __first && __comp(__t, *--__k)); - *__j = _VSTD::move(__t); - if (++__count == __limit) - return ++__i == __last; - } - __j = __i; + if (__len <= __limit) { + _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); + return; } - return true; -} - -template <class _Compare, class _BidirectionalIterator> -void -__insertion_sort_move(_BidirectionalIterator __first1, _BidirectionalIterator __last1, - typename iterator_traits<_BidirectionalIterator>::value_type* __first2, _Compare __comp) -{ - typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; - if (__first1 != __last1) + // __len > 5 + if (__depth == 0) { + // Fallback to heap sort as Introsort suggests. + _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp); + return; + } + --__depth; + _RandomAccessIterator __m = __first; + _RandomAccessIterator __lm1 = __last; + --__lm1; + unsigned __n_swaps; { - __destruct_n __d(0); - unique_ptr<value_type, __destruct_n&> __h(__first2, __d); - value_type* __last2 = __first2; - ::new ((void*)__last2) value_type(_VSTD::move(*__first1)); - __d.template __incr<value_type>(); - for (++__last2; ++__first1 != __last1; ++__last2) - { - value_type* __j2 = __last2; - value_type* __i2 = __j2; - if (__comp(*__first1, *--__i2)) - { - ::new ((void*)__j2) value_type(_VSTD::move(*__i2)); - __d.template __incr<value_type>(); - for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) - *__j2 = _VSTD::move(*__i2); - *__j2 = _VSTD::move(*__first1); - } - else - { - ::new ((void*)__j2) value_type(_VSTD::move(*__first1)); - __d.template __incr<value_type>(); - } - } - __h.release(); + difference_type __delta; + if (__len >= 1000) { + __delta = __len / 2; + __m += __delta; + __delta /= 2; + __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m + __delta, __lm1, __comp); + } else { + __delta = __len / 2; + __m += __delta; + __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); + } } -} - -template <class _Compare, class _RandomAccessIterator> -void -__introsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, - typename iterator_traits<_RandomAccessIterator>::difference_type __depth) -{ - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; - const difference_type __limit = is_trivially_copy_constructible<value_type>::value && - is_trivially_copy_assignable<value_type>::value ? 30 : 6; - while (true) + // *__m is median + // partition [__first, __m) < *__m and *__m <= [__m, __last) + // (this inhibits tossing elements equivalent to __m around unnecessarily) + _RandomAccessIterator __i = __first; + _RandomAccessIterator __j = __lm1; + // j points beyond range to be tested, *__m is known to be <= *__lm1 + // The search going up is known to be guarded but the search coming down isn't. + // Prime the downward search with a guard. + if (!__comp(*__i, *__m)) // if *__first == *__m { - __restart: - difference_type __len = __last - __first; - switch (__len) - { - case 0: - case 1: - return; - case 2: - if (__comp(*--__last, *__first)) - swap(*__first, *__last); - return; - case 3: - _VSTD::__sort3<_Compare>(__first, __first+difference_type(1), --__last, __comp); - return; - case 4: - _VSTD::__sort4<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), --__last, __comp); - return; - case 5: - _VSTD::__sort5<_Compare>(__first, __first+difference_type(1), __first+difference_type(2), __first+difference_type(3), --__last, __comp); - return; - } - if (__len <= __limit) - { - _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); - return; - } - // __len > 5 - if (__depth == 0) - { - // Fallback to heap sort as Introsort suggests. - _VSTD::__partial_sort<_Compare>(__first, __last, __last, __comp); - return; - } - --__depth; - _RandomAccessIterator __m = __first; - _RandomAccessIterator __lm1 = __last; - --__lm1; - unsigned __n_swaps; - { - difference_type __delta; - if (__len >= 1000) - { - __delta = __len/2; - __m += __delta; - __delta /= 2; - __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); - } - else - { - __delta = __len/2; - __m += __delta; - __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); - } - } - // *__m is median - // partition [__first, __m) < *__m and *__m <= [__m, __last) - // (this inhibits tossing elements equivalent to __m around unnecessarily) - _RandomAccessIterator __i = __first; - _RandomAccessIterator __j = __lm1; - // j points beyond range to be tested, *__m is known to be <= *__lm1 - // The search going up is known to be guarded but the search coming down isn't. - // Prime the downward search with a guard. - if (!__comp(*__i, *__m)) // if *__first == *__m - { - // *__first == *__m, *__first doesn't go in first part - // manually guard downward moving __j against __i - while (true) - { - if (__i == --__j) - { - // *__first == *__m, *__m <= all other elements - // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) - ++__i; // __first + 1 - __j = __last; - if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) - { - while (true) - { - if (__i == __j) - return; // [__first, __last) all equivalent elements - if (__comp(*__first, *__i)) - { - swap(*__i, *__j); - ++__n_swaps; - ++__i; - break; - } - ++__i; - } - } - // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 - if (__i == __j) - return; - while (true) - { - while (!__comp(*__first, *__i)) - ++__i; - while (__comp(*__first, *--__j)) - ; - if (__i >= __j) - break; - swap(*__i, *__j); - ++__n_swaps; - ++__i; - } - // [__first, __i) == *__first and *__first < [__i, __last) - // The first part is sorted, sort the second part - // _VSTD::__sort<_Compare>(__i, __last, __comp); - __first = __i; - goto __restart; - } - if (__comp(*__j, *__m)) - { - swap(*__i, *__j); - ++__n_swaps; - break; // found guard for downward moving __j, now use unguarded partition - } - } - } - // It is known that *__i < *__m - ++__i; - // j points beyond range to be tested, *__m is known to be <= *__lm1 - // if not yet partitioned... - if (__i < __j) - { - // known that *(__i - 1) < *__m - // known that __i <= __m - while (true) - { - // __m still guards upward moving __i - while (__comp(*__i, *__m)) - ++__i; - // It is now known that a guard exists for downward moving __j - while (!__comp(*--__j, *__m)) - ; - if (__i > __j) - break; + // *__first == *__m, *__first doesn't go in first part + // manually guard downward moving __j against __i + while (true) { + if (__i == --__j) { + // *__first == *__m, *__m <= all other elements + // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) + ++__i; // __first + 1 + __j = __last; + if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) + { + while (true) { + if (__i == __j) + return; // [__first, __last) all equivalent elements + if (__comp(*__first, *__i)) { swap(*__i, *__j); ++__n_swaps; - // It is known that __m != __j - // If __m just moved, follow it - if (__m == __i) - __m = __j; ++__i; + break; + } + ++__i; } - } - // [__first, __i) < *__m and *__m <= [__i, __last) - if (__i != __m && __comp(*__m, *__i)) - { - swap(*__i, *__m); + } + // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 + if (__i == __j) + return; + while (true) { + while (!__comp(*__first, *__i)) + ++__i; + while (__comp(*__first, *--__j)) + ; + if (__i >= __j) + break; + swap(*__i, *__j); ++__n_swaps; + ++__i; + } + // [__first, __i) == *__first and *__first < [__i, __last) + // The first part is sorted, sort the second part + // _VSTD::__sort<_Compare>(__i, __last, __comp); + __first = __i; + goto __restart; } - // [__first, __i) < *__i and *__i <= [__i+1, __last) - // If we were given a perfect partition, see if insertion sort is quick... - if (__n_swaps == 0) - { - bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); - if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+difference_type(1), __last, __comp)) - { - if (__fs) - return; - __last = __i; - continue; - } - else - { - if (__fs) - { - __first = ++__i; - continue; - } - } + if (__comp(*__j, *__m)) { + swap(*__i, *__j); + ++__n_swaps; + break; // found guard for downward moving __j, now use unguarded partition } - // sort smaller range with recursive call and larger with tail recursion elimination - if (__i - __first < __last - __i) - { - _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth); + } + } + // It is known that *__i < *__m + ++__i; + // j points beyond range to be tested, *__m is known to be <= *__lm1 + // if not yet partitioned... + if (__i < __j) { + // known that *(__i - 1) < *__m + // known that __i <= __m + while (true) { + // __m still guards upward moving __i + while (__comp(*__i, *__m)) + ++__i; + // It is now known that a guard exists for downward moving __j + while (!__comp(*--__j, *__m)) + ; + if (__i > __j) + break; + swap(*__i, *__j); + ++__n_swaps; + // It is known that __m != __j + // If __m just moved, follow it + if (__m == __i) + __m = __j; + ++__i; + } + } + // [__first, __i) < *__m and *__m <= [__i, __last) + if (__i != __m && __comp(*__m, *__i)) { + swap(*__i, *__m); + ++__n_swaps; + } + // [__first, __i) < *__i and *__i <= [__i+1, __last) + // If we were given a perfect partition, see if insertion sort is quick... + if (__n_swaps == 0) { + bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); + if (_VSTD::__insertion_sort_incomplete<_Compare>(__i + difference_type(1), __last, __comp)) { + if (__fs) + return; + __last = __i; + continue; + } else { + if (__fs) { __first = ++__i; + continue; } - else - { - _VSTD::__introsort<_Compare>(__i + difference_type(1), __last, __comp, __depth); - __last = __i; - } + } + } + // sort smaller range with recursive call and larger with tail recursion elimination + if (__i - __first < __last - __i) { + _VSTD::__introsort<_Compare>(__first, __i, __comp, __depth); + __first = ++__i; + } else { + _VSTD::__introsort<_Compare>(__i + difference_type(1), __last, __comp, __depth); + __last = __i; } + } } template <typename _Number> inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) { + if (__n == 0) + return 0; + if (sizeof(__n) <= sizeof(unsigned)) + return sizeof(unsigned) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned>(__n)); + if (sizeof(__n) <= sizeof(unsigned long)) + return sizeof(unsigned long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long>(__n)); + if (sizeof(__n) <= sizeof(unsigned long long)) + return sizeof(unsigned long long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long long>(__n)); + _Number __log2 = 0; while (__n > 1) { __log2++; @@ -483,72 +536,71 @@ void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compar } template <class _Compare, class _Tp> -inline _LIBCPP_INLINE_VISIBILITY -void -__sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) -{ - __less<uintptr_t> __comp; - _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); +inline _LIBCPP_INLINE_VISIBILITY void __sort(_Tp** __first, _Tp** __last, __less<_Tp*>&) { + __less<uintptr_t> __comp; + _VSTD::__sort<__less<uintptr_t>&, uintptr_t*>((uintptr_t*)__first, (uintptr_t*)__last, __comp); } -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&)) +extern template _LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&); #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) +extern template _LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); #endif -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) - -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&)) +extern template _LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); +extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); +extern template _LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&); +extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); +extern template _LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&); +extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); +extern template _LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&); +extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); +extern template _LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); +extern template _LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&); +extern template _LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&); +extern template _LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&); +extern template _LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); + +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&); #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&)) +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&); #endif -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&)) -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&)) - -_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&)) - -template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&); +extern template _LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&); + +extern template _LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&); + +template <class _RandomAccessIterator, class _Comp> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) { _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last); - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + using _Comp_ref = typename __comp_ref_type<_Comp>::type; if (__libcpp_is_constant_evaluated()) { - _VSTD::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); + std::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); } else { - _VSTD::__sort<_Comp_ref>(_VSTD::__unwrap_iter(__first), _VSTD::__unwrap_iter(__last), _Comp_ref(__comp)); + std::__sort<_Comp_ref>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), _Comp_ref(__comp)); } } +template <class _RandomAccessIterator, class _Comp> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) { + std::__sort_impl(std::move(__first), std::move(__last), __comp); +} + template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -sort(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/sort_heap.h b/libcxx/include/__algorithm/sort_heap.h index 64291ff2e8c9..3a63d744fc1c 100644 --- a/libcxx/include/__algorithm/sort_heap.h +++ b/libcxx/include/__algorithm/sort_heap.h @@ -17,7 +17,7 @@ #include <type_traits> // swap #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/stable_partition.h b/libcxx/include/__algorithm/stable_partition.h index 331f0fde77dc..969ac7a6173e 100644 --- a/libcxx/include/__algorithm/stable_partition.h +++ b/libcxx/include/__algorithm/stable_partition.h @@ -11,12 +11,14 @@ #include <__algorithm/rotate.h> #include <__config> +#include <__iterator/advance.h> +#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> #include <memory> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD @@ -130,7 +132,10 @@ __stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate unique_ptr<value_type, __return_temporary_buffer> __h; if (__len >= __alloc_limit) { +// TODO: Remove the use of std::get_temporary_buffer +_LIBCPP_SUPPRESS_DEPRECATED_PUSH __p = _VSTD::get_temporary_buffer<value_type>(__len); +_LIBCPP_SUPPRESS_DEPRECATED_POP __h.reset(__p.first); } return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, __len, __p, forward_iterator_tag()); @@ -276,7 +281,10 @@ __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last unique_ptr<value_type, __return_temporary_buffer> __h; if (__len >= __alloc_limit) { +// TODO: Remove the use of std::get_temporary_buffer +_LIBCPP_SUPPRESS_DEPRECATED_PUSH __p = _VSTD::get_temporary_buffer<value_type>(__len); +_LIBCPP_SUPPRESS_DEPRECATED_POP __h.reset(__p.first); } return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, __len, __p, bidirectional_iterator_tag()); diff --git a/libcxx/include/__algorithm/stable_sort.h b/libcxx/include/__algorithm/stable_sort.h index 4ae17e0e4d94..e3479aad62e6 100644 --- a/libcxx/include/__algorithm/stable_sort.h +++ b/libcxx/include/__algorithm/stable_sort.h @@ -15,12 +15,13 @@ #include <__algorithm/sort.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #include <__utility/swap.h> #include <memory> #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD @@ -199,30 +200,36 @@ __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp } template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY -void -stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - difference_type __len = __last - __first; - pair<value_type*, ptrdiff_t> __buf(0, 0); - unique_ptr<value_type, __return_temporary_buffer> __h; - if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) - { - __buf = _VSTD::get_temporary_buffer<value_type>(__len); - __h.reset(__buf.first); - } - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); +inline _LIBCPP_HIDE_FROM_ABI +void __stable_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; + using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; + + difference_type __len = __last - __first; + pair<value_type*, ptrdiff_t> __buf(0, 0); + unique_ptr<value_type, __return_temporary_buffer> __h; + if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) { +// TODO: Remove the use of std::get_temporary_buffer +_LIBCPP_SUPPRESS_DEPRECATED_PUSH + __buf = std::get_temporary_buffer<value_type>(__len); +_LIBCPP_SUPPRESS_DEPRECATED_POP + __h.reset(__buf.first); + } + + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + std::__stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second); +} + +template <class _RandomAccessIterator, class _Compare> +inline _LIBCPP_HIDE_FROM_ABI +void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + std::__stable_sort_impl(std::move(__first), std::move(__last), __comp); } template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY -void -stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI +void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/swap_ranges.h b/libcxx/include/__algorithm/swap_ranges.h index 2b099c7361f1..0422265bb4be 100644 --- a/libcxx/include/__algorithm/swap_ranges.h +++ b/libcxx/include/__algorithm/swap_ranges.h @@ -11,10 +11,9 @@ #include <__config> #include <__utility/swap.h> -#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/transform.h b/libcxx/include/__algorithm/transform.h index 494cb7128d29..f9db806f5b94 100644 --- a/libcxx/include/__algorithm/transform.h +++ b/libcxx/include/__algorithm/transform.h @@ -12,7 +12,7 @@ #include <__config> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/unique.h b/libcxx/include/__algorithm/unique.h index e17ff1567fa9..264d727d93c8 100644 --- a/libcxx/include/__algorithm/unique.h +++ b/libcxx/include/__algorithm/unique.h @@ -16,7 +16,7 @@ #include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/unique_copy.h b/libcxx/include/__algorithm/unique_copy.h index 4833ae9b59f5..f58517749f51 100644 --- a/libcxx/include/__algorithm/unique_copy.h +++ b/libcxx/include/__algorithm/unique_copy.h @@ -12,10 +12,9 @@ #include <__algorithm/comp.h> #include <__config> #include <__iterator/iterator_traits.h> -#include <utility> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/unwrap_iter.h b/libcxx/include/__algorithm/unwrap_iter.h index 35765330bb7f..7d1807b7bbf9 100644 --- a/libcxx/include/__algorithm/unwrap_iter.h +++ b/libcxx/include/__algorithm/unwrap_iter.h @@ -10,12 +10,12 @@ #define _LIBCPP___ALGORITHM_UNWRAP_ITER_H #include <__config> +#include <__iterator/iterator_traits.h> #include <__memory/pointer_traits.h> -#include <iterator> #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD @@ -43,7 +43,7 @@ struct __unwrap_iter_impl { } }; -#if _LIBCPP_DEBUG_LEVEL < 2 +#ifndef _LIBCPP_ENABLE_DEBUG_MODE template <class _Iter> struct __unwrap_iter_impl<_Iter, true> { @@ -53,7 +53,7 @@ struct __unwrap_iter_impl<_Iter, true> { } }; -#endif // _LIBCPP_DEBUG_LEVEL < 2 +#endif // !_LIBCPP_ENABLE_DEBUG_MODE template<class _Iter, class _Impl = __unwrap_iter_impl<_Iter> > inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR @@ -63,20 +63,34 @@ __unwrap_iter(_Iter __i) _NOEXCEPT return _Impl::__apply(__i); } +template <class _OrigIter, class _UnwrappedIter> +struct __rewrap_iter_impl { + static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter __first, _UnwrappedIter __result) { + // Precondition: __result is reachable from __first + // Precondition: _OrigIter is a contiguous iterator + return __first + (__result - std::__unwrap_iter(__first)); + } +}; + +template <class _OrigIter> +struct __rewrap_iter_impl<_OrigIter, _OrigIter> { + static _LIBCPP_CONSTEXPR _OrigIter __apply(_OrigIter, _OrigIter __result) { + return __result; + } +}; + template<class _OrigIter> -_LIBCPP_HIDE_FROM_ABI +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _OrigIter __rewrap_iter(_OrigIter, _OrigIter __result) { return __result; } -template<class _OrigIter, class _UnwrappedIter> -_LIBCPP_HIDE_FROM_ABI +template<class _OrigIter, class _UnwrappedIter, class _Impl = __rewrap_iter_impl<_OrigIter, _UnwrappedIter> > +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR _OrigIter __rewrap_iter(_OrigIter __first, _UnwrappedIter __result) { - // Precondition: __result is reachable from __first - // Precondition: _OrigIter is a contiguous iterator - return __first + (__result - _VSTD::__unwrap_iter(__first)); + return _Impl::__apply(__first, __result); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/upper_bound.h b/libcxx/include/__algorithm/upper_bound.h index c064f1e35b9a..c6483607e3c6 100644 --- a/libcxx/include/__algorithm/upper_bound.h +++ b/libcxx/include/__algorithm/upper_bound.h @@ -12,10 +12,12 @@ #include <__algorithm/comp.h> #include <__algorithm/half_positive.h> #include <__config> -#include <iterator> +#include <__iterator/advance.h> +#include <__iterator/distance.h> +#include <__iterator/iterator_traits.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) -#pragma GCC system_header +# pragma GCC system_header #endif _LIBCPP_BEGIN_NAMESPACE_STD |