diff options
Diffstat (limited to 'libcxx/include/__algorithm')
65 files changed, 3885 insertions, 459 deletions
diff --git a/libcxx/include/__algorithm/binary_search.h b/libcxx/include/__algorithm/binary_search.h index 121a741d070b..a44007237850 100644 --- a/libcxx/include/__algorithm/binary_search.h +++ b/libcxx/include/__algorithm/binary_search.h @@ -25,20 +25,20 @@ 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) +binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __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); + __first = std::lower_bound<_ForwardIterator, _Tp, _Comp_ref>(__first, __last, __value, __comp); + return __first != __last && !__comp(__value, *__first); } template <class _ForwardIterator, class _Tp> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool -binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) +binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return std::binary_search(__first, __last, __value_, + return std::binary_search(__first, __last, __value, __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); } diff --git a/libcxx/include/__algorithm/count.h b/libcxx/include/__algorithm/count.h index e18128cae8a8..5b546934038d 100644 --- a/libcxx/include/__algorithm/count.h +++ b/libcxx/include/__algorithm/count.h @@ -22,10 +22,10 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Tp> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 typename iterator_traits<_InputIterator>::difference_type - count(_InputIterator __first, _InputIterator __last, const _Tp& __value_) { + count(_InputIterator __first, _InputIterator __last, const _Tp& __value) { typename iterator_traits<_InputIterator>::difference_type __r(0); for (; __first != __last; ++__first) - if (*__first == __value_) + if (*__first == __value) ++__r; return __r; } diff --git a/libcxx/include/__algorithm/equal_range.h b/libcxx/include/__algorithm/equal_range.h index 2a07364bb66f..f30f55be64fc 100644 --- a/libcxx/include/__algorithm/equal_range.h +++ b/libcxx/include/__algorithm/equal_range.h @@ -30,7 +30,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _ForwardIterator, class _Tp> _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator> -__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) +__equal_range(_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); @@ -39,12 +39,12 @@ __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va difference_type __l2 = _VSTD::__half_positive(__len); _ForwardIterator __m = __first; _VSTD::advance(__m, __l2); - if (__comp(*__m, __value_)) + if (__comp(*__m, __value)) { __first = ++__m; __len -= __l2 + 1; } - else if (__comp(__value_, *__m)) + else if (__comp(__value, *__m)) { __last = __m; __len = __l2; @@ -55,8 +55,8 @@ __equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va _ForwardIterator __mp1 = __m; return pair<_ForwardIterator, _ForwardIterator> ( - _VSTD::__lower_bound_impl<_StdIterOps>(__first, __m, __value_, __comp, __proj), - _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value_, __comp) + _VSTD::__lower_bound_impl<_ClassicAlgPolicy>(__first, __m, __value, __comp, __proj), + _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value, __comp) ); } } @@ -67,19 +67,19 @@ template <class _ForwardIterator, class _Tp, class _Compare> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator> -equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) +equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value_, __comp); + return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value, __comp); } template <class _ForwardIterator, class _Tp> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator> -equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) +equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return _VSTD::equal_range(__first, __last, __value_, + return _VSTD::equal_range(__first, __last, __value, __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>()); } diff --git a/libcxx/include/__algorithm/fill.h b/libcxx/include/__algorithm/fill.h index be5b4740a52a..ec9968fdb8b3 100644 --- a/libcxx/include/__algorithm/fill.h +++ b/libcxx/include/__algorithm/fill.h @@ -23,26 +23,26 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void -__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag) +__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, forward_iterator_tag) { for (; __first != __last; ++__first) - *__first = __value_; + *__first = __value; } template <class _RandomAccessIterator, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void -__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag) +__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value, random_access_iterator_tag) { - _VSTD::fill_n(__first, __last - __first, __value_); + _VSTD::fill_n(__first, __last - __first, __value); } template <class _ForwardIterator, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 void -fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) +fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category()); + _VSTD::__fill(__first, __last, __value, typename iterator_traits<_ForwardIterator>::iterator_category()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/fill_n.h b/libcxx/include/__algorithm/fill_n.h index 590c8f38f3fd..7482a4188dd5 100644 --- a/libcxx/include/__algorithm/fill_n.h +++ b/libcxx/include/__algorithm/fill_n.h @@ -22,19 +22,19 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _OutputIterator, class _Size, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) +__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) { for (; __n > 0; ++__first, (void) --__n) - *__first = __value_; + *__first = __value; return __first; } template <class _OutputIterator, class _Size, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_) +fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) { - return _VSTD::__fill_n(__first, _VSTD::__convert_to_integral(__n), __value_); + return _VSTD::__fill_n(__first, _VSTD::__convert_to_integral(__n), __value); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/find.h b/libcxx/include/__algorithm/find.h index 641b85e2f645..ab37d81262f0 100644 --- a/libcxx/include/__algorithm/find.h +++ b/libcxx/include/__algorithm/find.h @@ -20,9 +20,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _Tp> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _InputIterator -find(_InputIterator __first, _InputIterator __last, const _Tp& __value_) { +find(_InputIterator __first, _InputIterator __last, const _Tp& __value) { for (; __first != __last; ++__first) - if (*__first == __value_) + if (*__first == __value) break; return __first; } diff --git a/libcxx/include/__algorithm/find_end.h b/libcxx/include/__algorithm/find_end.h index 0220c0939711..65e9f29b1c1f 100644 --- a/libcxx/include/__algorithm/find_end.h +++ b/libcxx/include/__algorithm/find_end.h @@ -11,8 +11,16 @@ #define _LIBCPP___ALGORITHM_FIND_END_OF_H #include <__algorithm/comp.h> +#include <__algorithm/iterator_operations.h> +#include <__algorithm/search.h> #include <__config> +#include <__functional/identity.h> +#include <__iterator/advance.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__iterator/reverse_iterator.h> +#include <__utility/pair.h> +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -20,35 +28,52 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred, forward_iterator_tag, - forward_iterator_tag) { +template < + class _AlgPolicy, + class _Iter1, + class _Sent1, + class _Iter2, + class _Sent2, + class _Pred, + class _Proj1, + class _Proj2> +_LIBCPP_HIDE_FROM_ABI inline _LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_Iter1, _Iter1> __find_end_impl( + _Iter1 __first1, + _Sent1 __last1, + _Iter2 __first2, + _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + forward_iterator_tag, + forward_iterator_tag) { // modeled after search algorithm - _ForwardIterator1 __r = __last1; // __last1 is the "default" answer + _Iter1 __match_first = _IterOps<_AlgPolicy>::next(__first1, __last1); // __last1 is the "default" answer + _Iter1 __match_last = __match_first; if (__first2 == __last2) - return __r; + return pair<_Iter1, _Iter1>(__match_last, __match_last); while (true) { while (true) { - if (__first1 == __last1) // if source exhausted return last correct answer - return __r; // (or __last1 if never found) - if (__pred(*__first1, *__first2)) + if (__first1 == __last1) // if source exhausted return last correct answer (or __last1 if never found) + return pair<_Iter1, _Iter1>(__match_first, __match_last); + if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) break; ++__first1; } // *__first1 matches *__first2, now match elements after here - _ForwardIterator1 __m1 = __first1; - _ForwardIterator2 __m2 = __first2; + _Iter1 __m1 = __first1; + _Iter2 __m2 = __first2; while (true) { if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one - __r = __first1; + __match_first = __first1; + __match_last = ++__m1; ++__first1; break; } if (++__m1 == __last1) // Source exhausted, return last answer - return __r; - if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first + return pair<_Iter1, _Iter1>(__match_first, __match_last); + // mismatch, restart with a new __first + if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { ++__first1; break; @@ -57,33 +82,52 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 __find_end(_ForwardIterator1 __f } } -template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1 __find_end( - _BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, - _BidirectionalIterator2 __last2, _BinaryPredicate __pred, bidirectional_iterator_tag, bidirectional_iterator_tag) { +template < + class _IterOps, + class _Pred, + class _Iter1, + class _Sent1, + class _Iter2, + class _Sent2, + class _Proj1, + class _Proj2> +_LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter1 __find_end( + _Iter1 __first1, + _Sent1 __sent1, + _Iter2 __first2, + _Sent2 __sent2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + bidirectional_iterator_tag, + bidirectional_iterator_tag) { + auto __last1 = _IterOps::next(__first1, __sent1); + auto __last2 = _IterOps::next(__first2, __sent2); // modeled after search algorithm (in reverse) if (__first2 == __last2) return __last1; // Everything matches an empty sequence - _BidirectionalIterator1 __l1 = __last1; - _BidirectionalIterator2 __l2 = __last2; + _Iter1 __l1 = __last1; + _Iter2 __l2 = __last2; --__l2; while (true) { // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks while (true) { if (__first1 == __l1) // return __last1 if no element matches *__first2 return __last1; - if (__pred(*--__l1, *__l2)) + if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) break; } // *__l1 matches *__l2, now match elements before here - _BidirectionalIterator1 __m1 = __l1; - _BidirectionalIterator2 __m2 = __l2; + _Iter1 __m1 = __l1; + _Iter2 __m2 = __l2; while (true) { if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern) return __m1; if (__m1 == __first1) // Otherwise if source exhaused, pattern not found return __last1; - if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1 + + // if there is a mismatch, restart with a new __l1 + if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(__proj2, *--__m2))) { break; } // else there is a match, check next elements @@ -91,37 +135,53 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _BidirectionalIterator1 __find_end( } } -template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> -_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end( - _RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, - _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag) { - typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; - typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; +template < + class _AlgPolicy, + class _Pred, + class _Iter1, + class _Sent1, + class _Iter2, + class _Sent2, + class _Proj1, + class _Proj2> +_LIBCPP_CONSTEXPR_AFTER_CXX11 _Iter1 __find_end( + _Iter1 __first1, + _Sent1 __sent1, + _Iter2 __first2, + _Sent2 __sent2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + random_access_iterator_tag, + random_access_iterator_tag) { + typedef typename iterator_traits<_Iter1>::difference_type _D1; + auto __last1 = _IterOps<_AlgPolicy>::next(__first1, __sent1); + auto __last2 = _IterOps<_AlgPolicy>::next(__first2, __sent2); // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - _D2 __len2 = __last2 - __first2; + auto __len2 = __last2 - __first2; if (__len2 == 0) return __last1; - _D1 __len1 = __last1 - __first1; + auto __len1 = __last1 - __first1; if (__len1 < __len2) return __last1; - const _RandomAccessIterator1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here - _RandomAccessIterator1 __l1 = __last1; - _RandomAccessIterator2 __l2 = __last2; + const _Iter1 __s = __first1 + _D1(__len2 - 1); // End of pattern match can't go before here + _Iter1 __l1 = __last1; + _Iter2 __l2 = __last2; --__l2; while (true) { while (true) { if (__s == __l1) return __last1; - if (__pred(*--__l1, *__l2)) + if (std::__invoke(__pred, std::__invoke(__proj1, *--__l1), std::__invoke(__proj2, *__l2))) break; } - _RandomAccessIterator1 __m1 = __l1; - _RandomAccessIterator2 __m2 = __l2; + _Iter1 __m1 = __l1; + _Iter2 __m2 = __l2; while (true) { if (__m2 == __first2) return __m1; // no need to check range on __m1 because __s guarantees we have enough source - if (!__pred(*--__m1, *--__m2)) { + if (!std::__invoke(__pred, std::__invoke(__proj1, *--__m1), std::__invoke(*--__m2))) { break; } } @@ -129,20 +189,39 @@ _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1 __find_end( } template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred) { - return _VSTD::__find_end<_BinaryPredicate&>( - __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()); +_LIBCPP_NODISCARD inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +_ForwardIterator1 __find_end_classic(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate& __pred) { + auto __proj = __identity(); + return std::__find_end_impl<_ClassicAlgPolicy>( + __first1, + __last1, + __first2, + __last2, + __pred, + __proj, + __proj, + typename iterator_traits<_ForwardIterator1>::iterator_category(), + typename iterator_traits<_ForwardIterator2>::iterator_category()) + .first; +} + +template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred) { + return std::__find_end_classic(__first1, __last1, __first2, __last2, __pred); } template <class _ForwardIterator1, class _ForwardIterator2> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + using __v1 = typename iterator_traits<_ForwardIterator1>::value_type; + using __v2 = typename iterator_traits<_ForwardIterator2>::value_type; + return std::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/iterator_operations.h b/libcxx/include/__algorithm/iterator_operations.h index c02f9bf649df..eb627e1ace7a 100644 --- a/libcxx/include/__algorithm/iterator_operations.h +++ b/libcxx/include/__algorithm/iterator_operations.h @@ -6,13 +6,20 @@ // //===----------------------------------------------------------------------===// -#ifndef _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H -#define _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H +#ifndef _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H +#define _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H +#include <__algorithm/iter_swap.h> #include <__config> #include <__iterator/advance.h> #include <__iterator/distance.h> +#include <__iterator/iter_move.h> +#include <__iterator/iter_swap.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__utility/forward.h> +#include <__utility/move.h> +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -20,28 +27,69 @@ _LIBCPP_BEGIN_NAMESPACE_STD +template <class _AlgPolicy> struct _IterOps; + #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) -struct _RangesIterOps { +struct _RangeAlgPolicy {}; + +template <> +struct _IterOps<_RangeAlgPolicy> { static constexpr auto advance = ranges::advance; static constexpr auto distance = ranges::distance; + static constexpr auto __iter_move = ranges::iter_move; + static constexpr auto iter_swap = ranges::iter_swap; + static constexpr auto next = ranges::next; + static constexpr auto __advance_to = ranges::advance; }; #endif -struct _StdIterOps { +struct _ClassicAlgPolicy {}; + +template <> +struct _IterOps<_ClassicAlgPolicy> { + + // advance + template <class _Iter, class _Distance> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 + static void advance(_Iter& __iter, _Distance __count) { + std::advance(__iter, __count); + } + + // distance + template <class _Iter> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 + static typename iterator_traits<_Iter>::difference_type distance(_Iter __first, _Iter __last) { + return std::distance(__first, __last); + } + + // iter_move + template <class _Iter> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 + // Declaring the return type is necessary for the C++03 mode (which doesn't support placeholder return types). + static typename iterator_traits<__uncvref_t<_Iter> >::value_type&& __iter_move(_Iter&& __i) { + return std::move(*std::forward<_Iter>(__i)); + } - 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); + // iter_swap + template <class _Iter1, class _Iter2> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 + static void iter_swap(_Iter1&& __a, _Iter2&& __b) { + std::iter_swap(std::forward<_Iter1>(__a), std::forward<_Iter2>(__b)); } + // next 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); + _Iterator next(_Iterator, _Iterator __last) { + return __last; } + template <class _Iter> + _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11 void __advance_to(_Iter& __first, _Iter __last) { + __first = __last; + } }; _LIBCPP_END_NAMESPACE_STD -#endif // _LIBCPP___ALGORIHTM_ITERATOR_OPERATIONS_H +#endif // _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H diff --git a/libcxx/include/__algorithm/lower_bound.h b/libcxx/include/__algorithm/lower_bound.h index fbcd5c7e908a..2c92f715265a 100644 --- a/libcxx/include/__algorithm/lower_bound.h +++ b/libcxx/include/__algorithm/lower_bound.h @@ -19,6 +19,7 @@ #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__type_traits/is_callable.h> +#include <__type_traits/remove_reference.h> #include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -27,15 +28,15 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _IterOps, class _Iter, class _Sent, class _Type, class _Proj, class _Comp> +template <class _AlgPolicy, 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); + auto __len = _IterOps<_AlgPolicy>::distance(__first, __last); while (__len != 0) { auto __l2 = std::__half_positive(__len); _Iter __m = __first; - _IterOps::advance(__m, __l2); + _IterOps<_AlgPolicy>::advance(__m, __l2); if (std::__invoke(__comp, std::__invoke(__proj, *__m), __value)) { __first = ++__m; __len -= __l2 + 1; @@ -48,17 +49,17 @@ _Iter __lower_bound_impl(_Iter __first, _Sent __last, const _Type& __value, _Com template <class _ForwardIterator, class _Tp, class _Compare> _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 -_ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) { +_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); + return std::__lower_bound_impl<_ClassicAlgPolicy>(__first, __last, __value, __comp, __proj); } template <class _ForwardIterator, class _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_, +_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>()); } diff --git a/libcxx/include/__algorithm/make_heap.h b/libcxx/include/__algorithm/make_heap.h index acac0aabf1e4..bc39d82bf916 100644 --- a/libcxx/include/__algorithm/make_heap.h +++ b/libcxx/include/__algorithm/make_heap.h @@ -14,6 +14,7 @@ #include <__algorithm/sift_down.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -22,36 +23,32 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX11 void -__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - difference_type __n = __last - __first; - if (__n > 1) - { - // start from the first parent, there is no need to consider children - for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) - { - _VSTD::__sift_down<_Compare>(__first, __comp, __n, __first + __start); - } +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using _CompRef = typename __comp_ref_type<_Compare>::type; + _CompRef __comp_ref = __comp; + + using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; + difference_type __n = __last - __first; + if (__n > 1) { + // start from the first parent, there is no need to consider children + for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) { + std::__sift_down<_CompRef>(__first, __comp_ref, __n, __first + __start); } + } } template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__make_heap<_Comp_ref>(__first, __last, __comp); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + std::__make_heap(std::move(__first), std::move(__last), __comp); } template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::make_heap(std::move(__first), std::move(__last), + __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/make_projected.h b/libcxx/include/__algorithm/make_projected.h index 8141c4ed176f..6d8ebfd3d90e 100644 --- a/libcxx/include/__algorithm/make_projected.h +++ b/libcxx/include/__algorithm/make_projected.h @@ -13,6 +13,8 @@ #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> +#include <__type_traits/decay.h> +#include <__type_traits/is_member_pointer.h> #include <__utility/forward.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -28,7 +30,7 @@ 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>) { + if constexpr (same_as<decay_t<_Proj>, identity> && !is_member_pointer_v<decay_t<_Comp>>) { // 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; @@ -42,6 +44,24 @@ decltype(auto) __make_projected_comp(_Comp& __comp, _Proj& __proj) { } } +template <class _Comp, class _Proj1, class _Proj2> +_LIBCPP_HIDE_FROM_ABI constexpr static +decltype(auto) __make_projected_comp(_Comp& __comp, _Proj1& __proj1, _Proj2& __proj2) { + if constexpr (same_as<decay_t<_Proj1>, identity> && same_as<decay_t<_Proj2>, identity> && + !is_member_pointer_v<decay_t<_Comp>>) { + // 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(__proj1, std::forward<decltype(__lhs)>(__lhs)), + std::invoke(__proj2, std::forward<decltype(__rhs)>(__rhs))); + }; + } +} + } // namespace ranges _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/minmax_element.h b/libcxx/include/__algorithm/minmax_element.h index fe5f20bf1c7f..cf67184e0b4c 100644 --- a/libcxx/include/__algorithm/minmax_element.h +++ b/libcxx/include/__algorithm/minmax_element.h @@ -24,17 +24,17 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Comp, class _Proj> class _MinmaxElementLessFunc { - _Comp& __comp; - _Proj& __proj; + _Comp& __comp_; + _Proj& __proj_; public: _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR - _MinmaxElementLessFunc(_Comp& __comp_, _Proj& __proj_) : __comp(__comp_), __proj(__proj_) {} + _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)); + return std::__invoke(__comp_, std::__invoke(__proj_, *__it1), std::__invoke(__proj_, *__it2)); } }; diff --git a/libcxx/include/__algorithm/nth_element.h b/libcxx/include/__algorithm/nth_element.h index 60b9280f75f0..c7cdef5be817 100644 --- a/libcxx/include/__algorithm/nth_element.h +++ b/libcxx/include/__algorithm/nth_element.h @@ -14,13 +14,11 @@ #include <__algorithm/sort.h> #include <__config> #include <__debug> +#include <__debug_utils/randomize_range.h> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #include <__utility/swap.h> -#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY) -# include <__algorithm/shuffle.h> -#endif - #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif @@ -223,25 +221,35 @@ __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _Rando } template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp) -{ - _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last); - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); - _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __nth); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void __nth_element_impl(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, + _Compare& __comp) { + if (__nth == __last) + return; + + std::__debug_randomize_range(__first, __last); + + using _Comp_ref = typename __comp_ref_type<_Compare>::type; + std::__nth_element<_Comp_ref>(__first, __nth, __last, __comp); + + std::__debug_randomize_range(__first, __nth); if (__nth != __last) { - _LIBCPP_DEBUG_RANDOMIZE_RANGE(++__nth, __last); + std::__debug_randomize_range(++__nth, __last); } } +template <class _RandomAccessIterator, class _Compare> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, + _Compare __comp) { + std::__nth_element_impl(std::move(__first), std::move(__nth), std::move(__last), __comp); +} + template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) -{ - _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) { + std::nth_element(std::move(__first), std::move(__nth), std::move(__last), __less<typename + iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/partial_sort.h b/libcxx/include/__algorithm/partial_sort.h index 3870c0cc9335..e008c0c99679 100644 --- a/libcxx/include/__algorithm/partial_sort.h +++ b/libcxx/include/__algorithm/partial_sort.h @@ -16,13 +16,10 @@ #include <__algorithm/sort_heap.h> #include <__config> #include <__debug> +#include <__debug_utils/randomize_range.h> #include <__iterator/iterator_traits.h> #include <__utility/swap.h> -#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY) -# include <__algorithm/shuffle.h> -#endif - #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif @@ -55,10 +52,10 @@ void partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp) { - _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __last); + std::__debug_randomize_range(__first, __last); typedef typename __comp_ref_type<_Compare>::type _Comp_ref; _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp); - _LIBCPP_DEBUG_RANDOMIZE_RANGE(__middle, __last); + std::__debug_randomize_range(__middle, __last); } template <class _RandomAccessIterator> diff --git a/libcxx/include/__algorithm/pop_heap.h b/libcxx/include/__algorithm/pop_heap.h index 2932a5e31dbc..cadda81f6c88 100644 --- a/libcxx/include/__algorithm/pop_heap.h +++ b/libcxx/include/__algorithm/pop_heap.h @@ -13,6 +13,7 @@ #include <__algorithm/comp_ref_type.h> #include <__algorithm/push_heap.h> #include <__algorithm/sift_down.h> +#include <__assert> #include <__config> #include <__iterator/iterator_traits.h> #include <__utility/move.h> @@ -24,44 +25,43 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -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; +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp, + typename iterator_traits<_RandomAccessIterator>::difference_type __len) { + _LIBCPP_ASSERT(__len > 0, "The heap given to pop_heap must be non-empty"); - if (__len > 1) - { - 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); - } + using _CompRef = typename __comp_ref_type<_Compare>::type; + _CompRef __comp_ref = __comp; + + using value_type = typename iterator_traits<_RandomAccessIterator>::value_type; + if (__len > 1) { + value_type __top = std::move(*__first); // create a hole at __first + _RandomAccessIterator __hole = std::__floyd_sift_down<_CompRef>(__first, __comp_ref, __len); + --__last; + + if (__hole == __last) { + *__hole = std::move(__top); + } else { + *__hole = std::move(*__last); + ++__hole; + *__last = std::move(__top); + std::__sift_up<_CompRef>(__first, __hole, __comp_ref, __hole - __first); } + } } template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first; + std::__pop_heap(std::move(__first), std::move(__last), __comp, __len); } template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::pop_heap(std::move(__first), std::move(__last), + __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/push_heap.h b/libcxx/include/__algorithm/push_heap.h index 66973e082f14..1e3eec373d4f 100644 --- a/libcxx/include/__algorithm/push_heap.h +++ b/libcxx/include/__algorithm/push_heap.h @@ -22,47 +22,50 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX11 void -__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, - typename iterator_traits<_RandomAccessIterator>::difference_type __len) -{ - typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; - if (__len > 1) - { - __len = (__len - 2) / 2; - _RandomAccessIterator __ptr = __first + __len; - if (__comp(*__ptr, *--__last)) - { - value_type __t(_VSTD::move(*__last)); - do - { - *__last = _VSTD::move(*__ptr); - __last = __ptr; - if (__len == 0) - break; - __len = (__len - 1) / 2; - __ptr = __first + __len; - } while (__comp(*__ptr, __t)); - *__last = _VSTD::move(__t); - } +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __sift_up(_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) { + __len = (__len - 2) / 2; + _RandomAccessIterator __ptr = __first + __len; + + if (__comp(*__ptr, *--__last)) { + value_type __t(std::move(*__last)); + do { + *__last = std::move(*__ptr); + __last = __ptr; + if (__len == 0) + break; + __len = (__len - 1) / 2; + __ptr = __first + __len; + } while (__comp(*__ptr, __t)); + + *__last = std::move(__t); } + } +} + +template <class _RandomAccessIterator, class _Compare> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using _CompRef = typename __comp_ref_type<_Compare>::type; + typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first; + std::__sift_up<_CompRef>(std::move(__first), std::move(__last), __comp, __len); } template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__sift_up<_Comp_ref>(__first, __last, __comp, __last - __first); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + std::__push_heap(std::move(__first), std::move(__last), __comp); } template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::push_heap(std::move(__first), std::move(__last), + __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_binary_search.h b/libcxx/include/__algorithm/ranges_binary_search.h index 68359fb1388f..6da68834aa3b 100644 --- a/libcxx/include/__algorithm/ranges_binary_search.h +++ b/libcxx/include/__algorithm/ranges_binary_search.h @@ -35,7 +35,7 @@ struct __fn { 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); + auto __ret = std::__lower_bound_impl<_RangeAlgPolicy>(__first, __last, __value, __comp, __proj); return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first)); } @@ -45,7 +45,7 @@ struct __fn { 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); + auto __ret = std::__lower_bound_impl<_RangeAlgPolicy>(__first, __last, __value, __comp, __proj); return __ret != __last && !std::invoke(__comp, __value, std::invoke(__proj, *__first)); } }; diff --git a/libcxx/include/__algorithm/ranges_equal_range.h b/libcxx/include/__algorithm/ranges_equal_range.h new file mode 100644 index 000000000000..28d721530bda --- /dev/null +++ b/libcxx/include/__algorithm/ranges_equal_range.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_EQUAL_RANGE_H +#define _LIBCPP___ALGORITHM_RANGES_EQUAL_RANGE_H + +#include <__algorithm/equal_range.h> +#include <__algorithm/make_projected.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/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__ranges/subrange.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 __equal_range { + +struct __fn { + + template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Tp, class _Proj = identity, + indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter> operator()(_Iter __first, _Sent __last, const _Tp& __value, _Comp __comp = {}, + _Proj __proj = {}) const { + // TODO: implement + (void)__first; (void)__last; (void)__value; (void)__comp; (void)__proj; + return {}; + } + + template <forward_range _Range, class _Tp, class _Proj = identity, + indirect_strict_weak_order<const _Tp*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range> operator()(_Range&& __range, const _Tp& __value, _Comp __comp = {}, + _Proj __proj = {}) const { + // TODO: implement + (void)__range; (void)__value; (void)__comp; (void)__proj; + return {}; + } + +}; + +} // namespace __equal_range + +inline namespace __cpo { + inline constexpr auto equal_range = __equal_range::__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_RANGE_H diff --git a/libcxx/include/__algorithm/ranges_find_end.h b/libcxx/include/__algorithm/ranges_find_end.h new file mode 100644 index 000000000000..fec709e79f5a --- /dev/null +++ b/libcxx/include/__algorithm/ranges_find_end.h @@ -0,0 +1,113 @@ +//===----------------------------------------------------------------------===// +// +// 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_END_H +#define _LIBCPP___ALGORITHM_RANGES_FIND_END_H + +#include <__algorithm/find_end.h> +#include <__algorithm/iterator_operations.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/indirectly_comparable.h> +#include <__iterator/iterator_traits.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/subrange.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 + +template <class _Iter> +consteval auto __get_iterator_concept() { + if constexpr (contiguous_iterator<_Iter>) + return contiguous_iterator_tag(); + else if constexpr (random_access_iterator<_Iter>) + return random_access_iterator_tag(); + else if constexpr (bidirectional_iterator<_Iter>) + return bidirectional_iterator_tag(); + else if constexpr (forward_iterator<_Iter>) + return forward_iterator_tag(); + else if constexpr (input_iterator<_Iter>) + return input_iterator_tag(); +} + +template <class _Iter> +using __iterator_concept = decltype(__get_iterator_concept<_Iter>()); + +namespace ranges { +namespace __find_end { +struct __fn { + template <forward_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 + subrange<_Iter1> operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__find_end_impl<_RangeAlgPolicy>( + __first1, + __last1, + __first2, + __last2, + __pred, + __proj1, + __proj2, + __iterator_concept<_Iter1>(), + __iterator_concept<_Iter2>()); + return {__ret.first, __ret.second}; + } + + template <forward_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_subrange_t<_Range1> operator()(_Range1&& __range1, + _Range2&& __range2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__find_end_impl<_RangeAlgPolicy>( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + __pred, + __proj1, + __proj2, + __iterator_concept<iterator_t<_Range1>>(), + __iterator_concept<iterator_t<_Range2>>()); + return {__ret.first, __ret.second}; + } +}; +} // namespace __find_end + +inline namespace __cpo { + inline constexpr auto find_end = __find_end::__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_END_H diff --git a/libcxx/include/__algorithm/ranges_generate.h b/libcxx/include/__algorithm/ranges_generate.h new file mode 100644 index 000000000000..c23645e6d906 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_generate.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_GENERATE_H +#define _LIBCPP___ALGORITHM_RANGES_GENERATE_H + +#include <__algorithm/generate.h> +#include <__algorithm/make_projected.h> +#include <__concepts/constructible.h> +#include <__concepts/invocable.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/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 __generate { + +struct __fn { + + template <input_or_output_iterator _OutIter, sentinel_for<_OutIter> _Sent, copy_constructible _Func> + requires invocable<_Func&> && indirectly_writable<_OutIter, invoke_result_t<_Func&>> + _LIBCPP_HIDE_FROM_ABI constexpr + _OutIter operator()(_OutIter __first, _Sent __last, _Func __gen) const { + // TODO: implement + (void)__first; (void)__last; (void)__gen; + return {}; + } + + template <class _Range, copy_constructible _Func> + requires invocable<_Func&> && output_range<_Range, invoke_result_t<_Func&>> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __range, _Func __gen) const { + // TODO: implement + (void)__range; (void)__gen; + return {}; + } + +}; + +} // namespace __generate + +inline namespace __cpo { + inline constexpr auto generate = __generate::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_GENERATE_H diff --git a/libcxx/include/__algorithm/ranges_generate_n.h b/libcxx/include/__algorithm/ranges_generate_n.h new file mode 100644 index 000000000000..bcf50e025ecc --- /dev/null +++ b/libcxx/include/__algorithm/ranges_generate_n.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_GENERATE_N_H +#define _LIBCPP___ALGORITHM_RANGES_GENERATE_N_H + +#include <__algorithm/generate_n.h> +#include <__algorithm/make_projected.h> +#include <__concepts/constructible.h> +#include <__concepts/invocable.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 <__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 __generate_n { + +struct __fn { + + template <input_or_output_iterator _OutIter, copy_constructible _Func> + requires invocable<_Func&> && indirectly_writable<_OutIter, invoke_result_t<_Func&>> + _LIBCPP_HIDE_FROM_ABI constexpr + _OutIter operator()(_OutIter __first, iter_difference_t<_OutIter> __n, _Func __gen) const { + // TODO: implement + (void)__first; (void)__n; (void)__gen; + return {}; + } + +}; + +} // namespace __generate_n + +inline namespace __cpo { + inline constexpr auto generate_n = __generate_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_GENERATE_N_H diff --git a/libcxx/include/__algorithm/ranges_includes.h b/libcxx/include/__algorithm/ranges_includes.h new file mode 100644 index 000000000000..19c17870ed6f --- /dev/null +++ b/libcxx/include/__algorithm/ranges_includes.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_INCLUDES_H +#define _LIBCPP___ALGORITHM_RANGES_INCLUDES_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/includes.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/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 __includes { + +struct __fn { + + 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 { + // TODO: implement + (void)__first1; (void)__last1; (void)__first2; (void)__last2; (void)__comp; (void)__proj1; (void)__proj2; + return {}; + } + + 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 { + // TODO: implement + (void)__range1; (void)__range2; (void)__comp; (void)__proj1; (void)__proj2; + return {}; + } + +}; + +} // namespace __includes + +inline namespace __cpo { + inline constexpr auto includes = __includes::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_INCLUDES_H diff --git a/libcxx/include/__algorithm/ranges_inplace_merge.h b/libcxx/include/__algorithm/ranges_inplace_merge.h new file mode 100644 index 000000000000..a0867e486c3a --- /dev/null +++ b/libcxx/include/__algorithm/ranges_inplace_merge.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_INPLACE_MERGE_H +#define _LIBCPP___ALGORITHM_RANGES_INPLACE_MERGE_H + +#include <__algorithm/inplace_merge.h> +#include <__algorithm/make_projected.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/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 __inplace_merge { + +struct __fn { + + template <bidirectional_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, _Iter __middle, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + // TODO: implement + (void)__first; (void)__middle; (void)__last; (void)__comp; (void)__proj; + return {}; + } + + template <bidirectional_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&& __range, iterator_t<_Range> __middle, + _Comp __comp = {}, _Proj __proj = {}) const { + // TODO: implement + (void)__range; (void)__middle; (void)__comp; (void)__proj; + return {}; + } + +}; + +} // namespace __inplace_merge + +inline namespace __cpo { + inline constexpr auto inplace_merge = __inplace_merge::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_INPLACE_MERGE_H diff --git a/libcxx/include/__algorithm/ranges_is_heap.h b/libcxx/include/__algorithm/ranges_is_heap.h new file mode 100644 index 000000000000..0f10fa4dcec9 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_is_heap.h @@ -0,0 +1,70 @@ +//===----------------------------------------------------------------------===// +// +// 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_HEAP_H +#define _LIBCPP___ALGORITHM_RANGES_IS_HEAP_H + +#include <__algorithm/is_heap.h> +#include <__algorithm/make_projected.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/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 __is_heap { + +struct __fn { + + template <random_access_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 { + // TODO: implement + (void)__first; (void)__last; (void)__comp; (void)__proj; + return {}; + } + + template <random_access_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 { + // TODO: implement + (void)__range; (void)__comp; (void)__proj; + return {}; + } +}; + +} // namespace __is_heap + +inline namespace __cpo { + inline constexpr auto is_heap = __is_heap::__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_HEAP_H diff --git a/libcxx/include/__algorithm/ranges_is_heap_until.h b/libcxx/include/__algorithm/ranges_is_heap_until.h new file mode 100644 index 000000000000..ad021d6f2525 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_is_heap_until.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_IS_HEAP_UNTIL_H +#define _LIBCPP___ALGORITHM_RANGES_IS_HEAP_UNTIL_H + +#include <__algorithm/is_heap_until.h> +#include <__algorithm/make_projected.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/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 __is_heap_until { + +struct __fn { + + template <random_access_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 { + // TODO: implement + (void)__first; (void)__last; (void)__comp; (void)__proj; + return {}; + } + + template <random_access_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 { + // TODO: implement + (void)__range; (void)__comp; (void)__proj; + return {}; + } + +}; + +} // namespace __is_heap_until + +inline namespace __cpo { + inline constexpr auto is_heap_until = __is_heap_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_HEAP_UNTIL_H diff --git a/libcxx/include/__algorithm/ranges_lower_bound.h b/libcxx/include/__algorithm/ranges_lower_bound.h index a73470465cfd..1a9ae204a1ee 100644 --- a/libcxx/include/__algorithm/ranges_lower_bound.h +++ b/libcxx/include/__algorithm/ranges_lower_bound.h @@ -39,7 +39,7 @@ struct __fn { 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); + return std::__lower_bound_impl<_RangeAlgPolicy>(__first, __last, __value, __comp, __proj); } template <forward_range _Range, class _Type, class _Proj = identity, @@ -49,7 +49,7 @@ struct __fn { const _Type& __value, _Comp __comp = {}, _Proj __proj = {}) const { - return std::__lower_bound_impl<_RangesIterOps>(ranges::begin(__r), ranges::end(__r), __value, __comp, __proj); + return std::__lower_bound_impl<_RangeAlgPolicy>(ranges::begin(__r), ranges::end(__r), __value, __comp, __proj); } }; } // namespace __lower_bound diff --git a/libcxx/include/__algorithm/ranges_make_heap.h b/libcxx/include/__algorithm/ranges_make_heap.h new file mode 100644 index 000000000000..fd488dc11a4b --- /dev/null +++ b/libcxx/include/__algorithm/ranges_make_heap.h @@ -0,0 +1,79 @@ +//===----------------------------------------------------------------------===// +// +// 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_MAKE_HEAP_H +#define _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H + +#include <__algorithm/make_heap.h> +#include <__algorithm/make_projected.h> +#include <__concepts/same_as.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 __make_heap { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __make_heap_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::__make_heap(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 __make_heap_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 __make_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __make_heap + +inline namespace __cpo { + inline constexpr auto make_heap = __make_heap::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H diff --git a/libcxx/include/__algorithm/ranges_merge.h b/libcxx/include/__algorithm/ranges_merge.h new file mode 100644 index 000000000000..c73e09e94ccc --- /dev/null +++ b/libcxx/include/__algorithm/ranges_merge.h @@ -0,0 +1,142 @@ +//===----------------------------------------------------------------------===// +// +// 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_MERGE_H +#define _LIBCPP___ALGORITHM_RANGES_MERGE_H + +#include <__algorithm/in_in_out_result.h> +#include <__algorithm/ranges_copy.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/mergeable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__utility/move.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 _InIter1, class _InIter2, class _OutIter> +using merge_result = in_in_out_result<_InIter1, _InIter2, _OutIter>; + +namespace __merge { + +template < + class _InIter1, + class _Sent1, + class _InIter2, + class _Sent2, + class _OutIter, + class _Comp, + class _Proj1, + class _Proj2> +_LIBCPP_HIDE_FROM_ABI constexpr merge_result<__uncvref_t<_InIter1>, __uncvref_t<_InIter2>, __uncvref_t<_OutIter>> +__merge_impl( + _InIter1&& __first1, + _Sent1&& __last1, + _InIter2&& __first2, + _Sent2&& __last2, + _OutIter&& __result, + _Comp&& __comp, + _Proj1&& __proj1, + _Proj2&& __proj2) { + for (; __first1 != __last1 && __first2 != __last2; ++__result) { + if (std::invoke(__comp, std::invoke(__proj2, *__first2), std::invoke(__proj1, *__first1))) { + *__result = *__first2; + ++__first2; + } else { + *__result = *__first1; + ++__first1; + } + } + auto __ret1 = ranges::copy(std::move(__first1), std::move(__last1), std::move(__result)); + auto __ret2 = ranges::copy(std::move(__first2), std::move(__last2), std::move(__ret1.out)); + return {std::move(__ret1.in), std::move(__ret2.in), std::move(__ret2.out)}; +} + +struct __fn { + template < + input_iterator _InIter1, + sentinel_for<_InIter1> _Sent1, + input_iterator _InIter2, + sentinel_for<_InIter2> _Sent2, + weakly_incrementable _OutIter, + class _Comp = less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr merge_result<_InIter1, _InIter2, _OutIter> operator()( + _InIter1 __first1, + _Sent1 __last1, + _InIter2 __first2, + _Sent2 __last2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return __merge::__merge_impl(__first1, __last1, __first2, __last2, __result, __comp, __proj1, __proj2); + } + + template < + input_range _Range1, + input_range _Range2, + weakly_incrementable _OutIter, + class _Comp = less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable< + iterator_t<_Range1>, + iterator_t<_Range2>, + _OutIter, + _Comp, + _Proj1, + _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr merge_result<borrowed_iterator_t<_Range1>, borrowed_iterator_t<_Range2>, _OutIter> + operator()( + _Range1&& __range1, + _Range2&& __range2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return __merge::__merge_impl( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + __result, + __comp, + __proj1, + __proj2); + } +}; + +} // namespace __merge + +inline namespace __cpo { + inline constexpr auto merge = __merge::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_MERGE_H diff --git a/libcxx/include/__algorithm/ranges_nth_element.h b/libcxx/include/__algorithm/ranges_nth_element.h new file mode 100644 index 000000000000..2a929eacb89d --- /dev/null +++ b/libcxx/include/__algorithm/ranges_nth_element.h @@ -0,0 +1,79 @@ +//===----------------------------------------------------------------------===// +// +// 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_NTH_ELEMENT_H +#define _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/nth_element.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 __nth_element { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __nth_element_fn_impl(_Iter __first, _Iter __nth, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __last_iter = ranges::next(__first, __last); + + auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + std::__nth_element_impl(std::move(__first), std::move(__nth), __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, _Iter __nth, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + return __nth_element_fn_impl(std::move(__first), std::move(__nth), 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, iterator_t<_Range> __nth, _Comp __comp = {}, + _Proj __proj = {}) const { + return __nth_element_fn_impl(ranges::begin(__r), std::move(__nth), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __nth_element + +inline namespace __cpo { + inline constexpr auto nth_element = __nth_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_NTH_ELEMENT_H diff --git a/libcxx/include/__algorithm/ranges_partial_sort_copy.h b/libcxx/include/__algorithm/ranges_partial_sort_copy.h new file mode 100644 index 000000000000..55ad2ca4e686 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_partial_sort_copy.h @@ -0,0 +1,88 @@ +//===----------------------------------------------------------------------===// +// +// 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_PARTIAL_SORT_COPY_H +#define _LIBCPP___ALGORITHM_RANGES_PARTIAL_SORT_COPY_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/partial_sort_copy.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/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 { + +template <class _InIter, class _OutIter> +using partial_sort_copy_result = in_out_result<_InIter, _OutIter>; + +namespace __partial_sort_copy { + +struct __fn { + + template <input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, + random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2, + class _Comp = ranges::less, class _Proj1 = identity, class _Proj2 = identity> + requires indirectly_copyable<_Iter1, _Iter2> && sortable<_Iter2, _Comp, _Proj2> && + indirect_strict_weak_order<_Comp, projected<_Iter1, _Proj1>, projected<_Iter2, _Proj2>> + _LIBCPP_HIDE_FROM_ABI constexpr + partial_sort_copy_result<_Iter1, _Iter2> + operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result_first, _Sent2 __result_last, + _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { + // TODO: implement + (void)__first; (void)__last; (void)__result_first; (void)__result_last; (void)__comp; (void)__proj1; (void)__proj2; + return {}; + } + + template <input_range _Range1, random_access_range _Range2, class _Comp = ranges::less, + class _Proj1 = identity, class _Proj2 = identity> + requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>> && + sortable<iterator_t<_Range2>, _Comp, _Proj2> && + indirect_strict_weak_order<_Comp, projected<iterator_t<_Range1>, _Proj1>, + projected<iterator_t<_Range2>, _Proj2>> + _LIBCPP_HIDE_FROM_ABI constexpr + partial_sort_copy_result<borrowed_iterator_t<_Range1>, borrowed_iterator_t<_Range2>> + operator()(_Range1&& __range, _Range2&& __result_range, _Comp __comp = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { + // TODO: implement + (void)__range; (void)__result_range; (void)__comp; (void)__proj1; (void)__proj2; + return {}; + } + +}; + +} // namespace __partial_sort_copy + +inline namespace __cpo { + inline constexpr auto partial_sort_copy = __partial_sort_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_PARTIAL_SORT_COPY_H diff --git a/libcxx/include/__algorithm/ranges_partition.h b/libcxx/include/__algorithm/ranges_partition.h new file mode 100644 index 000000000000..c145e7bdb4a2 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_partition.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_PARTITION_H +#define _LIBCPP___ALGORITHM_RANGES_PARTITION_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/partition.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/permutable.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__ranges/subrange.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 __partition { + +struct __fn { + + template <permutable _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter> operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const { + // TODO: implement + (void)__first; (void)__last; (void)__pred; (void)__proj; + return {}; + } + + template <forward_range _Range, class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + requires permutable<iterator_t<_Range>> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range> operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const { + // TODO: implement + (void)__range; (void)__pred; (void)__proj; + return {}; + } + +}; + +} // namespace __partition + +inline namespace __cpo { + inline constexpr auto partition = __partition::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_PARTITION_H diff --git a/libcxx/include/__algorithm/ranges_partition_copy.h b/libcxx/include/__algorithm/ranges_partition_copy.h new file mode 100644 index 000000000000..f55089b94ea5 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_partition_copy.h @@ -0,0 +1,82 @@ +//===----------------------------------------------------------------------===// +// +// 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_PARTITION_COPY_H +#define _LIBCPP___ALGORITHM_RANGES_PARTITION_COPY_H + +#include <__algorithm/in_out_out_result.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/partition_copy.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/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 { + +template <class _InIter, class _OutIter1, class _OutIter2> +using partition_copy_result = in_out_out_result<_InIter, _OutIter1, _OutIter2>; + +namespace __partition_copy { + +struct __fn { + + template <input_iterator _InIter, sentinel_for<_InIter> _Sent, + weakly_incrementable _OutIter1, weakly_incrementable _OutIter2, + class _Proj = identity, indirect_unary_predicate<projected<_InIter, _Proj>> _Pred> + requires indirectly_copyable<_InIter, _OutIter1> && indirectly_copyable<_InIter, _OutIter2> + _LIBCPP_HIDE_FROM_ABI constexpr + partition_copy_result<_InIter, _OutIter1, _OutIter2> + operator()(_InIter __first, _Sent __last, _OutIter1 __out_true, _OutIter2 __out_false, + _Pred __pred, _Proj __proj = {}) const { + // TODO: implement + (void)__first; (void)__last; (void)__out_true; (void)__out_false; (void)__pred; (void)__proj; + return {}; + } + + template <input_range _Range, weakly_incrementable _OutIter1, weakly_incrementable _OutIter2, + class _Proj = identity, indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + requires indirectly_copyable<iterator_t<_Range>, _OutIter1> && indirectly_copyable<iterator_t<_Range>, _OutIter2> + _LIBCPP_HIDE_FROM_ABI constexpr + partition_copy_result<borrowed_iterator_t<_Range>, _OutIter1, _OutIter2> + operator()(_Range&& __range, _OutIter1 __out_true, _OutIter2 __out_false, _Pred __pred, _Proj __proj = {}) const { + // TODO: implement + (void)__range; (void)__out_true; (void)__out_false; (void)__pred; (void)__proj; + return {}; + } + +}; + +} // namespace __partition_copy + +inline namespace __cpo { + inline constexpr auto partition_copy = __partition_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_PARTITION_COPY_H diff --git a/libcxx/include/__algorithm/ranges_partition_point.h b/libcxx/include/__algorithm/ranges_partition_point.h new file mode 100644 index 000000000000..336b29f63284 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_partition_point.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_PARTITION_POINT_H +#define _LIBCPP___ALGORITHM_RANGES_PARTITION_POINT_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/partition_point.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/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 __partition_point { + +struct __fn { + + template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + _Iter operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const { + // TODO: implement + (void)__first; (void)__last; (void)__pred; (void)__proj; + return {}; + } + + template <forward_range _Range, class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_iterator_t<_Range> operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const { + // TODO: implement + (void)__range; (void)__pred; (void)__proj; + return {}; + } + +}; + +} // namespace __partition_point + +inline namespace __cpo { + inline constexpr auto partition_point = __partition_point::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_PARTITION_POINT_H diff --git a/libcxx/include/__algorithm/ranges_pop_heap.h b/libcxx/include/__algorithm/ranges_pop_heap.h new file mode 100644 index 000000000000..d0b8314e5b0a --- /dev/null +++ b/libcxx/include/__algorithm/ranges_pop_heap.h @@ -0,0 +1,80 @@ +//===----------------------------------------------------------------------===// +// +// 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_POP_HEAP_H +#define _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/pop_heap.h> +#include <__concepts/same_as.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 __pop_heap { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __pop_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) { + auto __last_iter = ranges::next(__first, __last); + auto __len = __last_iter - __first; + + auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj); + std::__pop_heap(std::move(__first), __last_iter, __projected_comp, __len); + + 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 __pop_heap_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 __pop_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __pop_heap + +inline namespace __cpo { + inline constexpr auto pop_heap = __pop_heap::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H diff --git a/libcxx/include/__algorithm/ranges_push_heap.h b/libcxx/include/__algorithm/ranges_push_heap.h new file mode 100644 index 000000000000..e46ad19cfed7 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_push_heap.h @@ -0,0 +1,79 @@ +//===----------------------------------------------------------------------===// +// +// 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_PUSH_HEAP_H +#define _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/push_heap.h> +#include <__concepts/same_as.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 __push_heap { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __push_heap_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::__push_heap(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 __push_heap_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 __push_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __push_heap + +inline namespace __cpo { + inline constexpr auto push_heap = __push_heap::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H diff --git a/libcxx/include/__algorithm/ranges_remove.h b/libcxx/include/__algorithm/ranges_remove.h new file mode 100644 index 000000000000..a6a1200763d2 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_remove.h @@ -0,0 +1,64 @@ +//===----------------------------------------------------------------------===// +// +// 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_REMOVE_H +#define _LIBCPP___ALGORITHM_RANGES_REMOVE_H +#include <__config> + +#include <__algorithm/ranges_remove_if.h> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/permutable.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/subrange.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 __remove { +struct __fn { + + template <permutable _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 + subrange<_Iter> operator()(_Iter __first, _Sent __last, const _Type& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __other) { return __value == __other; }; + return ranges::__remove_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <forward_range _Range, class _Type, class _Proj = identity> + requires permutable<iterator_t<_Range>> + && indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range> operator()(_Range&& __range, const _Type& __value, _Proj __proj = {}) const { + auto __pred = [&](auto&& __other) { return __value == __other; }; + return ranges::__remove_if_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj); + } +}; +} // namespace __remove + +inline namespace __cpo { + inline constexpr auto remove = __remove::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_REMOVE_H diff --git a/libcxx/include/__algorithm/ranges_remove_copy.h b/libcxx/include/__algorithm/ranges_remove_copy.h new file mode 100644 index 000000000000..16e9009e7ef0 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_remove_copy.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_REMOVE_COPY_H +#define _LIBCPP___ALGORITHM_RANGES_REMOVE_COPY_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/remove_copy.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/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 { + +template <class _InIter, class _OutIter> +using remove_copy_result = in_out_result<_InIter, _OutIter>; + +namespace __remove_copy { + +struct __fn { + + template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter, class _Type, + class _Proj = identity> + requires indirectly_copyable<_InIter, _OutIter> && + indirect_binary_predicate<ranges::equal_to, projected<_InIter, _Proj>, const _Type*> + _LIBCPP_HIDE_FROM_ABI constexpr + remove_copy_result<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result, const _Type& __value, _Proj __proj = {}) const { + // TODO: implement + (void)__first; (void)__last; (void)__result; (void)__value; (void)__proj; + return {}; + } + + template <input_range _Range, weakly_incrementable _OutIter, class _Type, class _Proj = identity> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> && + indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*> + _LIBCPP_HIDE_FROM_ABI constexpr + remove_copy_result<borrowed_iterator_t<_Range>, _OutIter> + operator()(_Range&& __range, _OutIter __result, const _Type& __value, _Proj __proj = {}) const { + // TODO: implement + (void)__range; (void)__result; (void)__value; (void)__proj; + return {}; + } + +}; + +} // namespace __remove_copy + +inline namespace __cpo { + inline constexpr auto remove_copy = __remove_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_REMOVE_COPY_H diff --git a/libcxx/include/__algorithm/ranges_remove_copy_if.h b/libcxx/include/__algorithm/ranges_remove_copy_if.h new file mode 100644 index 000000000000..4eafe425b8e3 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_remove_copy_if.h @@ -0,0 +1,80 @@ +//===----------------------------------------------------------------------===// +// +// 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_REMOVE_COPY_IF_H +#define _LIBCPP___ALGORITHM_RANGES_REMOVE_COPY_IF_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/remove_copy_if.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/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 { + +template <class _InIter, class _OutIter> +using remove_copy_if_result = in_out_result<_InIter, _OutIter>; + +namespace __remove_copy_if { + +struct __fn { + + template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter, + class _Proj = identity, indirect_unary_predicate<projected<_InIter, _Proj>> _Pred> + requires indirectly_copyable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + remove_copy_if_result<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result, _Pred __pred, _Proj __proj = {}) const { + // TODO: implement + (void)__first; (void)__last; (void)__result; (void)__pred; (void)__proj; + return {}; + } + + 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 + remove_copy_if_result<borrowed_iterator_t<_Range>, _OutIter> + operator()(_Range&& __range, _OutIter __result, _Pred __pred, _Proj __proj = {}) const { + // TODO: implement + (void)__range; (void)__result; (void)__pred; (void)__proj; + return {}; + } + +}; + +} // namespace __remove_copy_if + +inline namespace __cpo { + inline constexpr auto remove_copy_if = __remove_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_REMOVE_COPY_IF_H diff --git a/libcxx/include/__algorithm/ranges_remove_if.h b/libcxx/include/__algorithm/ranges_remove_if.h new file mode 100644 index 000000000000..d4e382e551c6 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_remove_if.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_REMOVE_IF_H +#define _LIBCPP___ALGORITHM_RANGES_REMOVE_IF_H +#include <__config> + +#include <__algorithm/ranges_find_if.h> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/iter_move.h> +#include <__iterator/permutable.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/subrange.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 +subrange<_Iter> __remove_if_impl(_Iter __first, _Sent __last, _Pred& __pred, _Proj& __proj) { + auto __new_end = ranges::__find_if_impl(__first, __last, __pred, __proj); + if (__new_end == __last) + return {__new_end, __new_end}; + + _Iter __i = __new_end; + while (++__i != __last) { + if (!std::invoke(__pred, std::invoke(__proj, *__i))) { + *__new_end = ranges::iter_move(__i); + ++__new_end; + } + } + return {__new_end, __i}; +} + +namespace __remove_if { +struct __fn { + + template <permutable _Iter, sentinel_for<_Iter> _Sent, + class _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter> operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const { + return ranges::__remove_if_impl(std::move(__first), std::move(__last), __pred, __proj); + } + + template <forward_range _Range, + class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + requires permutable<iterator_t<_Range>> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range> operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const { + return ranges::__remove_if_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj); + } + +}; +} // namespace __remove_if + +inline namespace __cpo { + inline constexpr auto remove_if = __remove_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_REMOVE_IF_H diff --git a/libcxx/include/__algorithm/ranges_replace_copy.h b/libcxx/include/__algorithm/ranges_replace_copy.h new file mode 100644 index 000000000000..19ef635d6f15 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_replace_copy.h @@ -0,0 +1,84 @@ +//===----------------------------------------------------------------------===// +// +// 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_COPY_H +#define _LIBCPP___ALGORITHM_RANGES_REPLACE_COPY_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/replace_copy.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/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 { + +template <class _InIter, class _OutIter> +using replace_copy_result = in_out_result<_InIter, _OutIter>; + +namespace __replace_copy { + +struct __fn { + + template <input_iterator _InIter, sentinel_for<_InIter> _Sent, class _Type1, class _Type2, + output_iterator<const _Type2&> _OutIter, class _Proj = identity> + requires indirectly_copyable<_InIter, _OutIter> && + indirect_binary_predicate<ranges::equal_to, projected<_InIter, _Proj>, const _Type1*> + _LIBCPP_HIDE_FROM_ABI constexpr + replace_copy_result<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result, const _Type1& __old_value, const _Type2& __new_value, + _Proj __proj = {}) const { + // TODO: implement + (void)__first; (void)__last; (void)__result; (void)__old_value; (void)__new_value; (void)__proj; + return {}; + } + + template <input_range _Range, class _Type1, class _Type2, output_iterator<const _Type2&> _OutIter, + class _Proj = identity> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> && + indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type1*> + _LIBCPP_HIDE_FROM_ABI constexpr + replace_copy_result<borrowed_iterator_t<_Range>, _OutIter> + operator()(_Range&& __range, _OutIter __result, const _Type1& __old_value, const _Type2& __new_value, + _Proj __proj = {}) const { + // TODO: implement + (void)__range; (void)__result; (void)__old_value; (void)__new_value; (void)__proj; + return {}; + } + +}; + +} // namespace __replace_copy + +inline namespace __cpo { + inline constexpr auto replace_copy = __replace_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_REPLACE_COPY_H diff --git a/libcxx/include/__algorithm/ranges_replace_copy_if.h b/libcxx/include/__algorithm/ranges_replace_copy_if.h new file mode 100644 index 000000000000..2a908e2057af --- /dev/null +++ b/libcxx/include/__algorithm/ranges_replace_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_REPLACE_COPY_IF_H +#define _LIBCPP___ALGORITHM_RANGES_REPLACE_COPY_IF_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/replace_copy_if.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/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 { + +template <class _InIter, class _OutIter> +using replace_copy_if_result = in_out_result<_InIter, _OutIter>; + +namespace __replace_copy_if { + +struct __fn { + + template <input_iterator _InIter, sentinel_for<_InIter> _Sent, class _Type, output_iterator<const _Type&> _OutIter, + class _Proj = identity, indirect_unary_predicate<projected<_InIter, _Proj>> _Pred> + requires indirectly_copyable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + replace_copy_if_result<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result, _Pred __pred, const _Type& __new_value, + _Proj __proj = {}) const { + // TODO: implement + (void)__first; (void)__last; (void)__result; (void)__pred; (void)__new_value; (void)__proj; + return {}; + } + + template <input_range _Range, class _Type, output_iterator<const _Type&> _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 + replace_copy_if_result<borrowed_iterator_t<_Range>, _OutIter> + operator()(_Range&& __range, _OutIter __result, _Pred __pred, const _Type& __new_value, _Proj __proj = {}) const { + // TODO: implement + (void)__range; (void)__result; (void)__pred; (void)__new_value; (void)__proj; + return {}; + } + +}; + +} // namespace __replace_copy_if + +inline namespace __cpo { + inline constexpr auto replace_copy_if = __replace_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_REPLACE_COPY_IF_H diff --git a/libcxx/include/__algorithm/ranges_reverse_copy.h b/libcxx/include/__algorithm/ranges_reverse_copy.h new file mode 100644 index 000000000000..e2da9b484aaf --- /dev/null +++ b/libcxx/include/__algorithm/ranges_reverse_copy.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_REVERSE_COPY_H +#define _LIBCPP___ALGORITHM_RANGES_REVERSE_COPY_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/ranges_copy.h> +#include <__config> +#include <__iterator/concepts.h> +#include <__iterator/next.h> +#include <__iterator/reverse_iterator.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__ranges/subrange.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 reverse_copy_result = in_out_result<_InIter, _OutIter>; + +namespace __reverse_copy { +struct __fn { + + template <bidirectional_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter> + requires indirectly_copyable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + reverse_copy_result<_InIter, _OutIter> operator()(_InIter __first, _Sent __last, _OutIter __result) const { + return (*this)(subrange(std::move(__first), std::move(__last)), std::move(__result)); + } + + template <bidirectional_range _Range, weakly_incrementable _OutIter> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + reverse_copy_result<borrowed_iterator_t<_Range>, _OutIter> operator()(_Range&& __range, _OutIter __result) const { + auto __ret = ranges::copy(std::__reverse_range(__range), std::move(__result)); + return {ranges::next(ranges::begin(__range), ranges::end(__range)), std::move(__ret.out)}; + } + +}; +} // namespace __reverse_copy + +inline namespace __cpo { + inline constexpr auto reverse_copy = __reverse_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_REVERSE_COPY_H diff --git a/libcxx/include/__algorithm/ranges_rotate_copy.h b/libcxx/include/__algorithm/ranges_rotate_copy.h new file mode 100644 index 000000000000..d7a282c86750 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_rotate_copy.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_ROTATE_COPY_H +#define _LIBCPP___ALGORITHM_RANGES_ROTATE_COPY_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/ranges_copy.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 _InIter, class _OutIter> +using rotate_copy_result = in_out_result<_InIter, _OutIter>; + +namespace __rotate_copy { +struct __fn { + + template <bidirectional_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter> + requires indirectly_copyable<_InIter, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + rotate_copy_result<_InIter, _OutIter> + operator()(_InIter __first, _InIter __middle, _Sent __last, _OutIter __result) const { + auto __res1 = ranges::copy(__middle, __last, std::move(__result)); + auto __res2 = ranges::copy(__first, __middle, std::move(__res1.out)); + return {std::move(__res1.in), std::move(__res2.out)}; + } + + template <bidirectional_range _Range, weakly_incrementable _OutIter> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> + _LIBCPP_HIDE_FROM_ABI constexpr + rotate_copy_result<borrowed_iterator_t<_Range>, _OutIter> + operator()(_Range&& __range, iterator_t<_Range> __middle, _OutIter __result) const { + return (*this)(ranges::begin(__range), std::move(__middle), ranges::end(__range), std::move(__result)); + } + +}; +} // namespace __rotate_copy + +inline namespace __cpo { + inline constexpr auto rotate_copy = __rotate_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_ROTATE_COPY_H diff --git a/libcxx/include/__algorithm/ranges_search.h b/libcxx/include/__algorithm/ranges_search.h new file mode 100644 index 000000000000..0564bbe1f8b3 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_search.h @@ -0,0 +1,134 @@ +//===----------------------------------------------------------------------===// +// +// 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_SEARCH_H +#define _LIBCPP___ALGORITHM_RANGES_SEARCH_H + +#include <__algorithm/iterator_operations.h> +#include <__algorithm/search.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> +#include <__iterator/distance.h> +#include <__iterator/indirectly_comparable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/size.h> +#include <__ranges/subrange.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 __search { +struct __fn { + template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Pred, class _Proj1, class _Proj2> + _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_impl( + _Iter1 __first1, + _Sent1 __last1, + _Iter2 __first2, + _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2) { + if constexpr (sized_sentinel_for<_Sent2, _Iter2>) { + auto __size2 = ranges::distance(__first2, __last2); + if (__size2 == 0) + return {__first1, __first1}; + + if constexpr (sized_sentinel_for<_Sent1, _Iter1>) { + auto __size1 = ranges::distance(__first1, __last1); + if (__size1 < __size2) { + ranges::advance(__first1, __last1); + return {__first1, __first1}; + } + + if constexpr (random_access_iterator<_Iter1> && random_access_iterator<_Iter2>) { + auto __ret = std::__search_random_access_impl<_RangeAlgPolicy>( + __first1, __last1, __first2, __last2, __pred, __proj1, __proj2, __size1, __size2); + return {__ret.first, __ret.second}; + } + } + } + + auto __ret = + std::__search_forward_impl<_RangeAlgPolicy>(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); + return {__ret.first, __ret.second}; + } + + template <forward_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 + subrange<_Iter1> operator()(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return __ranges_search_impl(__first1, __last1, __first2, __last2, __pred, __proj1, __proj2); + } + + template <forward_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_subrange_t<_Range1> operator()(_Range1&& __range1, + _Range2&& __range2, + _Pred __pred = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __first1 = ranges::begin(__range1); + if constexpr (sized_range<_Range2>) { + auto __size2 = ranges::size(__range2); + if (__size2 == 0) + return {__first1, __first1}; + if constexpr (sized_range<_Range1>) { + auto __size1 = ranges::size(__range1); + if (__size1 < __size2) { + ranges::advance(__first1, ranges::end(__range1)); + return {__first1, __first1}; + } + } + } + + return __ranges_search_impl( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + __pred, + __proj1, + __proj2); + } + +}; +} // namespace __search + +inline namespace __cpo { + inline constexpr auto search = __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_SEARCH_H diff --git a/libcxx/include/__algorithm/ranges_search_n.h b/libcxx/include/__algorithm/ranges_search_n.h new file mode 100644 index 000000000000..29fdbfb1c725 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_search_n.h @@ -0,0 +1,120 @@ +//===----------------------------------------------------------------------===// +// +// 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_SEARCH_N_H +#define _LIBCPP___ALGORITHM_RANGES_SEARCH_N_H + +#include <__algorithm/iterator_operations.h> +#include <__algorithm/search_n.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> +#include <__iterator/distance.h> +#include <__iterator/incrementable_traits.h> +#include <__iterator/indirectly_comparable.h> +#include <__iterator/iterator_traits.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/size.h> +#include <__ranges/subrange.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 __search_n { +struct __fn { + + template <class _Iter1, class _Sent1, class _SizeT, class _Type, class _Pred, class _Proj> + _LIBCPP_HIDE_FROM_ABI static constexpr subrange<_Iter1> __ranges_search_n_impl( + _Iter1 __first, _Sent1 __last, _SizeT __count, const _Type& __value, _Pred& __pred, _Proj& __proj) { + if (__count == 0) + return {__first, __first}; + + if constexpr (sized_sentinel_for<_Sent1, _Iter1>) { + auto __size = ranges::distance(__first, __last); + if (__size < __count) { + ranges::advance(__first, __last); + return {__first, __first}; + } + + if constexpr (random_access_iterator<_Iter1>) { + auto __ret = __search_n_random_access_impl<_RangeAlgPolicy>(__first, __last, + __count, + __value, + __pred, + __proj, + __size); + return {std::move(__ret.first), std::move(__ret.second)}; + } + } + + auto __ret = std::__search_n_forward_impl<_RangeAlgPolicy>(__first, __last, + __count, + __value, + __pred, + __proj); + return {std::move(__ret.first), std::move(__ret.second)}; + } + + template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, + class _Type, + class _Pred = ranges::equal_to, + class _Proj = identity> + requires indirectly_comparable<_Iter, const _Type*, _Pred, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter> operator()(_Iter __first, _Sent __last, + iter_difference_t<_Iter> __count, + const _Type& __value, + _Pred __pred = {}, + _Proj __proj = _Proj{}) const { + return __ranges_search_n_impl(__first, __last, __count, __value, __pred, __proj); + } + + template <forward_range _Range, class _Type, class _Pred = ranges::equal_to, class _Proj = identity> + requires indirectly_comparable<iterator_t<_Range>, const _Type*, _Pred, _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range> operator()(_Range&& __range, + range_difference_t<_Range> __count, + const _Type& __value, + _Pred __pred = {}, + _Proj __proj = {}) const { + auto __first = ranges::begin(__range); + if (__count <= 0) + return {__first, __first}; + if constexpr (sized_range<_Range>) { + auto __size1 = ranges::size(__range); + if (__size1 < static_cast<range_size_t<_Range>>(__count)) { + ranges::advance(__first, ranges::end(__range)); + return {__first, __first}; + } + } + + return __ranges_search_n_impl(ranges::begin(__range), ranges::end(__range), __count, __value, __pred, __proj); + } +}; +} // namespace __search_n + +inline namespace __cpo { + inline constexpr auto search_n = __search_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_SEARCH_N_H diff --git a/libcxx/include/__algorithm/ranges_set_difference.h b/libcxx/include/__algorithm/ranges_set_difference.h new file mode 100644 index 000000000000..4eb3efad3895 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_set_difference.h @@ -0,0 +1,104 @@ +//===----------------------------------------------------------------------===// +// +// 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_SET_DIFFERENCE_H +#define _LIBCPP___ALGORITHM_RANGES_SET_DIFFERENCE_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/set_difference.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/mergeable.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__type_traits/decay.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 set_difference_result = in_out_result<_InIter, _OutIter>; + +namespace __set_difference { + +struct __fn { + template < + input_iterator _InIter1, + sentinel_for<_InIter1> _Sent1, + input_iterator _InIter2, + sentinel_for<_InIter2> _Sent2, + weakly_incrementable _OutIter, + class _Comp = less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr set_difference_result<_InIter1, _OutIter> operator()( + _InIter1 __first1, + _Sent1 __last1, + _InIter2 __first2, + _Sent2 __last2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__set_difference( + __first1, __last1, __first2, __last2, __result, ranges::__make_projected_comp(__comp, __proj1, __proj2)); + return {std::move(__ret.first), std::move(__ret.second)}; + } + + template < + input_range _Range1, + input_range _Range2, + weakly_incrementable _OutIter, + class _Comp = less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _OutIter, _Comp, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr set_difference_result<borrowed_iterator_t<_Range1>, _OutIter> + operator()( + _Range1&& __range1, + _Range2&& __range2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__set_difference( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + __result, + ranges::__make_projected_comp(__comp, __proj1, __proj2)); + return {std::move(__ret.first), std::move(__ret.second)}; + } +}; + +} // namespace __set_difference + +inline namespace __cpo { + inline constexpr auto set_difference = __set_difference::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) +#endif // _LIBCPP___ALGORITHM_RANGES_SET_DIFFERENCE_H diff --git a/libcxx/include/__algorithm/ranges_set_intersection.h b/libcxx/include/__algorithm/ranges_set_intersection.h new file mode 100644 index 000000000000..05af91ae29e5 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_set_intersection.h @@ -0,0 +1,117 @@ +//===----------------------------------------------------------------------===// +// +// 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_SET_INTERSECTION_H +#define _LIBCPP___ALGORITHM_RANGES_SET_INTERSECTION_H + +#include <__algorithm/in_in_out_result.h> +#include <__algorithm/iterator_operations.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/set_intersection.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/mergeable.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 _InIter1, class _InIter2, class _OutIter> +using set_intersection_result = in_in_out_result<_InIter1, _InIter2, _OutIter>; + +namespace __set_intersection { + +struct __fn { + template < + input_iterator _InIter1, + sentinel_for<_InIter1> _Sent1, + input_iterator _InIter2, + sentinel_for<_InIter2> _Sent2, + weakly_incrementable _OutIter, + class _Comp = less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr set_intersection_result<_InIter1, _InIter2, _OutIter> operator()( + _InIter1 __first1, + _Sent1 __last1, + _InIter2 __first2, + _Sent2 __last2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__set_intersection<_RangeAlgPolicy>( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::move(__result), + ranges::__make_projected_comp(__comp, __proj1, __proj2)); + return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)}; + } + + template < + input_range _Range1, + input_range _Range2, + weakly_incrementable _OutIter, + class _Comp = less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable< + iterator_t<_Range1>, + iterator_t<_Range2>, + _OutIter, + _Comp, + _Proj1, + _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr set_intersection_result<borrowed_iterator_t<_Range1>, + borrowed_iterator_t<_Range2>, + _OutIter> + operator()( + _Range1&& __range1, + _Range2&& __range2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__set_intersection<_RangeAlgPolicy>( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + std::move(__result), + ranges::__make_projected_comp(__comp, __proj1, __proj2)); + return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)}; + } +}; + +} // namespace __set_intersection + +inline namespace __cpo { + inline constexpr auto set_intersection = __set_intersection::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) +#endif // _LIBCPP___ALGORITHM_RANGES_SET_INTERSECTION_H diff --git a/libcxx/include/__algorithm/ranges_set_symmetric_difference.h b/libcxx/include/__algorithm/ranges_set_symmetric_difference.h new file mode 100644 index 000000000000..c54cf3a65112 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_set_symmetric_difference.h @@ -0,0 +1,116 @@ +//===----------------------------------------------------------------------===// +// +// 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_SET_SYMMETRIC_DIFFERENCE_H +#define _LIBCPP___ALGORITHM_RANGES_SET_SYMMETRIC_DIFFERENCE_H + +#include <__algorithm/in_in_out_result.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/set_symmetric_difference.h> +#include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/mergeable.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 _InIter1, class _InIter2, class _OutIter> +using set_symmetric_difference_result = in_in_out_result<_InIter1, _InIter2, _OutIter>; + +namespace __set_symmetric_difference { + +struct __fn { + template < + input_iterator _InIter1, + sentinel_for<_InIter1> _Sent1, + input_iterator _InIter2, + sentinel_for<_InIter2> _Sent2, + weakly_incrementable _OutIter, + class _Comp = ranges::less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr set_symmetric_difference_result<_InIter1, _InIter2, _OutIter> operator()( + _InIter1 __first1, + _Sent1 __last1, + _InIter2 __first2, + _Sent2 __last2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__set_symmetric_difference( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::move(__result), + ranges::__make_projected_comp(__comp, __proj1, __proj2)); + return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)}; + } + + template < + input_range _Range1, + input_range _Range2, + weakly_incrementable _OutIter, + class _Comp = ranges::less, + class _Proj1 = identity, + class _Proj2 = identity> + requires mergeable< + iterator_t<_Range1>, + iterator_t<_Range2>, + _OutIter, + _Comp, + _Proj1, + _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>, + borrowed_iterator_t<_Range2>, + _OutIter> + operator()( + _Range1&& __range1, + _Range2&& __range2, + _OutIter __result, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + auto __ret = std::__set_symmetric_difference( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + std::move(__result), + ranges::__make_projected_comp(__comp, __proj1, __proj2)); + return {std::move(__ret.__in1_), std::move(__ret.__in2_), std::move(__ret.__out_)}; + } +}; + +} // namespace __set_symmetric_difference + +inline namespace __cpo { + inline constexpr auto set_symmetric_difference = __set_symmetric_difference::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) +#endif // _LIBCPP___ALGORITHM_RANGES_SET_SYMMETRIC_DIFFERENCE_H diff --git a/libcxx/include/__algorithm/ranges_set_union.h b/libcxx/include/__algorithm/ranges_set_union.h new file mode 100644 index 000000000000..39537503b98f --- /dev/null +++ b/libcxx/include/__algorithm/ranges_set_union.h @@ -0,0 +1,86 @@ +//===----------------------------------------------------------------------===// +// +// 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_SET_UNION_H +#define _LIBCPP___ALGORITHM_RANGES_SET_UNION_H + +#include <__algorithm/in_in_out_result.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/set_union.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/mergeable.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 { + +template <class _InIter1, class _InIter2, class _OutIter> +using set_union_result = in_in_out_result<_InIter1, _InIter2, _OutIter>; + +namespace __set_union { + +struct __fn { + + template <input_iterator _InIter1, sentinel_for<_InIter1> _Sent1, + input_iterator _InIter2, sentinel_for<_InIter2> _Sent2, + weakly_incrementable _OutIter, class _Comp = ranges::less, + class _Proj1 = identity, class _Proj2 = identity> + requires mergeable<_InIter1, _InIter2, _OutIter, _Comp, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + set_union_result<_InIter1, _InIter2, _OutIter> + operator()(_InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Comp __comp = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { + // TODO: implement + (void)__first1; (void)__last1; (void)__first2; (void)__last2; (void)__result; (void)__comp; (void)__proj1; + (void)__proj2; + return {}; + } + + template <input_range _Range1, input_range _Range2, weakly_incrementable _OutIter, + class _Comp = ranges::less, class _Proj1 = identity, class _Proj2 = identity> + requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _OutIter, _Comp, _Proj1, _Proj2> + _LIBCPP_HIDE_FROM_ABI constexpr + set_union_result<borrowed_iterator_t<_Range1>, borrowed_iterator_t<_Range2>, _OutIter> + operator()(_Range1&& __range1, _Range2&& __range2, _OutIter __result, _Comp __comp = {}, + _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { + // TODO: implement + (void)__range1; (void)__range2; (void)__result; (void)__comp; (void)__proj1; (void)__proj2; + return {}; + } + +}; + +} // namespace __set_union + +inline namespace __cpo { + inline constexpr auto set_union = __set_union::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_SET_UNION_H diff --git a/libcxx/include/__algorithm/ranges_shuffle.h b/libcxx/include/__algorithm/ranges_shuffle.h new file mode 100644 index 000000000000..bf9c28b4ce26 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_shuffle.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_SHUFFLE_H +#define _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/shuffle.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/permutable.h> +#include <__iterator/projected.h> +#include <__random/uniform_random_bit_generator.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__type_traits/remove_reference.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 __shuffle { + +struct __fn { + + template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Gen> + requires permutable<_Iter> && uniform_random_bit_generator<remove_reference_t<_Gen>> + _LIBCPP_HIDE_FROM_ABI + _Iter operator()(_Iter __first, _Sent __last, _Gen&& __gen) const { + // TODO: implement + (void)__first; (void)__last; (void)__gen; + return {}; + } + + template<random_access_range _Range, class _Gen> + requires permutable<iterator_t<_Range>> && uniform_random_bit_generator<remove_reference_t<_Gen>> + _LIBCPP_HIDE_FROM_ABI + borrowed_iterator_t<_Range> operator()(_Range&& __range, _Gen&& __gen) const { + // TODO: implement + (void)__range; (void)__gen; + return {}; + } + +}; + +} // namespace __shuffle + +inline namespace __cpo { + inline constexpr auto shuffle = __shuffle::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_SHUFFLE_H diff --git a/libcxx/include/__algorithm/ranges_sort_heap.h b/libcxx/include/__algorithm/ranges_sort_heap.h new file mode 100644 index 000000000000..c753e20c44a6 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_sort_heap.h @@ -0,0 +1,79 @@ +//===----------------------------------------------------------------------===// +// +// 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_HEAP_H +#define _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/sort_heap.h> +#include <__concepts/same_as.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_heap { + +struct __fn { + template <class _Iter, class _Sent, class _Comp, class _Proj> + _LIBCPP_HIDE_FROM_ABI constexpr static + _Iter __sort_heap_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_heap(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_heap_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_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj); + } +}; + +} // namespace __sort_heap + +inline namespace __cpo { + inline constexpr auto sort_heap = __sort_heap::__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_HEAP_H diff --git a/libcxx/include/__algorithm/ranges_stable_partition.h b/libcxx/include/__algorithm/ranges_stable_partition.h new file mode 100644 index 000000000000..178c953ebdae --- /dev/null +++ b/libcxx/include/__algorithm/ranges_stable_partition.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_STABLE_PARTITION_H +#define _LIBCPP___ALGORITHM_RANGES_STABLE_PARTITION_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/stable_partition.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/permutable.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__ranges/subrange.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_partition { + +struct __fn { + + template <bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity, + indirect_unary_predicate<projected<_Iter, _Proj>> _Pred> + requires permutable<_Iter> + _LIBCPP_HIDE_FROM_ABI + subrange<_Iter> operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const { + // TODO: implement + (void)__first; (void)__last; (void)__pred; (void)__proj; + return {}; + } + + template <bidirectional_range _Range, class _Proj = identity, + indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred> + requires permutable<iterator_t<_Range>> + _LIBCPP_HIDE_FROM_ABI + borrowed_subrange_t<_Range> operator()(_Range&& __range, _Pred __pred, _Proj __proj = {}) const { + // TODO: implement + (void)__range; (void)__pred; (void)__proj; + return {}; + } + +}; + +} // namespace __stable_partition + +inline namespace __cpo { + inline constexpr auto stable_partition = __stable_partition::__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_PARTITION_H diff --git a/libcxx/include/__algorithm/ranges_unique.h b/libcxx/include/__algorithm/ranges_unique.h new file mode 100644 index 000000000000..bdf755e9406e --- /dev/null +++ b/libcxx/include/__algorithm/ranges_unique.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_UNIQUE_H +#define _LIBCPP___ALGORITHM_RANGES_UNIQUE_H + +#include <__algorithm/make_projected.h> +#include <__algorithm/unique.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/permutable.h> +#include <__iterator/projected.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/dangling.h> +#include <__ranges/subrange.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 __unique { + +struct __fn { + + template <permutable _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity, + indirect_equivalence_relation<projected<_Iter, _Proj>> _Comp = ranges::equal_to> + _LIBCPP_HIDE_FROM_ABI constexpr + subrange<_Iter> operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const { + // TODO: implement + (void)__first; (void)__last; (void)__comp; (void)__proj; + return {}; + } + + template <forward_range _Range, class _Proj = identity, + indirect_equivalence_relation<projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to> + requires permutable<iterator_t<_Range>> + _LIBCPP_HIDE_FROM_ABI constexpr + borrowed_subrange_t<_Range> operator()(_Range&& __range, _Comp __comp = {}, _Proj __proj = {}) const { + // TODO: implement + (void)__range; (void)__comp; (void)__proj; + return {}; + } + +}; + +} // namespace __unique + +inline namespace __cpo { + inline constexpr auto unique = __unique::__fn{}; +} // namespace __cpo +} // namespace ranges + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +#endif // _LIBCPP___ALGORITHM_RANGES_UNIQUE_H diff --git a/libcxx/include/__algorithm/ranges_unique_copy.h b/libcxx/include/__algorithm/ranges_unique_copy.h new file mode 100644 index 000000000000..56361aa8ae2f --- /dev/null +++ b/libcxx/include/__algorithm/ranges_unique_copy.h @@ -0,0 +1,88 @@ +//===----------------------------------------------------------------------===// +// +// 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_UNIQUE_COPY_H +#define _LIBCPP___ALGORITHM_RANGES_UNIQUE_COPY_H + +#include <__algorithm/in_out_result.h> +#include <__algorithm/make_projected.h> +#include <__algorithm/unique_copy.h> +#include <__concepts/same_as.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/readable_traits.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 { + +template <class _InIter, class _OutIter> +using unique_copy_result = in_out_result<_InIter, _OutIter>; + +namespace __unique_copy { + +struct __fn { + + template <input_iterator _InIter, sentinel_for<_InIter> _Sent, weakly_incrementable _OutIter, class _Proj = identity, + indirect_equivalence_relation<projected<_InIter, _Proj>> _Comp = ranges::equal_to> + requires indirectly_copyable<_InIter, _OutIter> && + (forward_iterator<_InIter> || + (input_iterator<_OutIter> && same_as<iter_value_t<_InIter>, iter_value_t<_OutIter>>) || + indirectly_copyable_storable<_InIter, _OutIter>) + _LIBCPP_HIDE_FROM_ABI constexpr + unique_copy_result<_InIter, _OutIter> + operator()(_InIter __first, _Sent __last, _OutIter __result, _Comp __comp = {}, _Proj __proj = {}) const { + // TODO: implement + (void)__first; (void)__last; (void)__result; (void)__comp; (void)__proj; + return {}; + } + + template <input_range _Range, weakly_incrementable _OutIter, class _Proj = identity, + indirect_equivalence_relation<projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to> + requires indirectly_copyable<iterator_t<_Range>, _OutIter> && + (forward_iterator<iterator_t<_Range>> || + (input_iterator<_OutIter> && same_as<range_value_t<_Range>, iter_value_t<_OutIter>>) || + indirectly_copyable_storable<iterator_t<_Range>, _OutIter>) + _LIBCPP_HIDE_FROM_ABI constexpr + unique_copy_result<borrowed_iterator_t<_Range>, _OutIter> + operator()(_Range&& __range, _OutIter __result, _Comp __comp = {}, _Proj __proj = {}) const { + // TODO: implement + (void)__range; (void)__result; (void)__comp; (void)__proj; + return {}; + } + +}; + +} // namespace __unique_copy + +inline namespace __cpo { + inline constexpr auto unique_copy = __unique_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_UNIQUE_COPY_H diff --git a/libcxx/include/__algorithm/ranges_upper_bound.h b/libcxx/include/__algorithm/ranges_upper_bound.h index 94b5269c86af..3c63249248fa 100644 --- a/libcxx/include/__algorithm/ranges_upper_bound.h +++ b/libcxx/include/__algorithm/ranges_upper_bound.h @@ -40,7 +40,7 @@ struct __fn { return !std::invoke(__comp, __rhs, __lhs); }; - return std::__lower_bound_impl<_RangesIterOps>(__first, __last, __value, __comp_lhs_rhs_swapped, __proj); + return std::__lower_bound_impl<_RangeAlgPolicy>(__first, __last, __value, __comp_lhs_rhs_swapped, __proj); } template <forward_range _Range, class _Type, class _Proj = identity, @@ -54,7 +54,7 @@ struct __fn { return !std::invoke(__comp, __rhs, __lhs); }; - return std::__lower_bound_impl<_RangesIterOps>(ranges::begin(__r), + return std::__lower_bound_impl<_RangeAlgPolicy>(ranges::begin(__r), ranges::end(__r), __value, __comp_lhs_rhs_swapped, diff --git a/libcxx/include/__algorithm/remove.h b/libcxx/include/__algorithm/remove.h index c00f96f78a63..8a7e99ba09a1 100644 --- a/libcxx/include/__algorithm/remove.h +++ b/libcxx/include/__algorithm/remove.h @@ -22,15 +22,15 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _ForwardIterator, class _Tp> _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) +remove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - __first = _VSTD::find(__first, __last, __value_); + __first = _VSTD::find(__first, __last, __value); if (__first != __last) { _ForwardIterator __i = __first; while (++__i != __last) { - if (!(*__i == __value_)) + if (!(*__i == __value)) { *__first = _VSTD::move(*__i); ++__first; diff --git a/libcxx/include/__algorithm/remove_copy.h b/libcxx/include/__algorithm/remove_copy.h index a29a385af9ac..55fc1d90a1e7 100644 --- a/libcxx/include/__algorithm/remove_copy.h +++ b/libcxx/include/__algorithm/remove_copy.h @@ -20,11 +20,11 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _InputIterator, class _OutputIterator, class _Tp> inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_) +remove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value) { for (; __first != __last; ++__first) { - if (!(*__first == __value_)) + if (!(*__first == __value)) { *__result = *__first; ++__result; diff --git a/libcxx/include/__algorithm/search.h b/libcxx/include/__algorithm/search.h index d89ec2b1c5bc..4ead6cac82b7 100644 --- a/libcxx/include/__algorithm/search.h +++ b/libcxx/include/__algorithm/search.h @@ -11,9 +11,15 @@ #define _LIBCPP___ALGORITHM_SEARCH_H #include <__algorithm/comp.h> +#include <__algorithm/iterator_operations.h> #include <__config> +#include <__functional/identity.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> #include <__iterator/iterator_traits.h> +#include <__type_traits/is_callable.h> #include <__utility/pair.h> +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,31 +27,43 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2> -pair<_ForwardIterator1, _ForwardIterator1> - _LIBCPP_CONSTEXPR_AFTER_CXX11 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, - _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag) { +template <class _AlgPolicy, + class _Iter1, class _Sent1, + class _Iter2, class _Sent2, + class _Pred, + class _Proj1, + class _Proj2> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_forward_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2) { if (__first2 == __last2) - return _VSTD::make_pair(__first1, __first1); // Everything matches an empty sequence + return std::make_pair(__first1, __first1); // Everything matches an empty sequence while (true) { // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks while (true) { - if (__first1 == __last1) // return __last1 if no element matches *__first2 - return _VSTD::make_pair(__last1, __last1); - if (__pred(*__first1, *__first2)) + if (__first1 == __last1) { // return __last1 if no element matches *__first2 + _IterOps<_AlgPolicy>::__advance_to(__first1, __last1); + return std::make_pair(__first1, __first1); + } + if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) break; ++__first1; } // *__first1 matches *__first2, now match elements after here - _ForwardIterator1 __m1 = __first1; - _ForwardIterator2 __m2 = __first2; + _Iter1 __m1 = __first1; + _Iter2 __m2 = __first2; while (true) { if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern) - return _VSTD::make_pair(__first1, __m1); - if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found - return _VSTD::make_pair(__last1, __last1); - if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1 + return std::make_pair(__first1, ++__m1); + if (++__m1 == __last1) { // Otherwise if source exhaused, pattern not found + return std::make_pair(__m1, __m1); + } + + // if there is a mismatch, restart with a new __first1 + if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { ++__first1; break; @@ -54,38 +72,42 @@ pair<_ForwardIterator1, _ForwardIterator1> } } -template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2> -_LIBCPP_CONSTEXPR_AFTER_CXX11 pair<_RandomAccessIterator1, _RandomAccessIterator1> -__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, - _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, - random_access_iterator_tag) { - typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; - typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; - // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern - const _D2 __len2 = __last2 - __first2; - if (__len2 == 0) - return _VSTD::make_pair(__first1, __first1); - const _D1 __len1 = __last1 - __first1; - if (__len1 < __len2) - return _VSTD::make_pair(__last1, __last1); - const _RandomAccessIterator1 __s = __last1 - _D1(__len2 - 1); // Start of pattern match can't go beyond here +template <class _AlgPolicy, + class _Iter1, class _Sent1, + class _Iter2, class _Sent2, + class _Pred, + class _Proj1, + class _Proj2, + class _DiffT1, + class _DiffT2> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_random_access_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + _DiffT1 __size1, + _DiffT2 __size2) { + const _Iter1 __s = __first1 + __size1 - _DiffT1(__size2 - 1); // Start of pattern match can't go beyond here while (true) { while (true) { - if (__first1 == __s) - return _VSTD::make_pair(__last1, __last1); - if (__pred(*__first1, *__first2)) + if (__first1 == __s) { + _IterOps<_AlgPolicy>::__advance_to(__first1, __last1); + return std::make_pair(__first1, __first1); + } + if (std::__invoke(__pred, std::__invoke(__proj1, *__first1), std::__invoke(__proj2, *__first2))) break; ++__first1; } - _RandomAccessIterator1 __m1 = __first1; - _RandomAccessIterator2 __m2 = __first2; + _Iter1 __m1 = __first1; + _Iter2 __m2 = __first2; while (true) { if (++__m2 == __last2) - return _VSTD::make_pair(__first1, __first1 + _D1(__len2)); + return std::make_pair(__first1, __first1 + _DiffT1(__size2)); ++__m1; // no need to check range on __m1 because __s guarantees we have enough source - if (!__pred(*__m1, *__m2)) { + if (!std::__invoke(__pred, std::__invoke(__proj1, *__m1), std::__invoke(__proj2, *__m2))) { ++__first1; break; } @@ -93,22 +115,78 @@ __search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _Rando } } +template <class _Iter1, class _Sent1, + class _Iter2, class _Sent2, + class _Pred, + class _Proj1, + class _Proj2> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + __enable_if_t<__is_cpp17_random_access_iterator<_Iter1>::value + && __is_cpp17_random_access_iterator<_Iter2>::value>* = nullptr) { + + auto __size2 = __last2 - __first2; + if (__size2 == 0) + return std::make_pair(__first1, __first1); + + auto __size1 = __last1 - __first1; + if (__size1 < __size2) { + return std::make_pair(__last1, __last1); + } + + return std::__search_random_access_impl<_ClassicAlgPolicy>(__first1, __last1, + __first2, __last2, + __pred, + __proj1, + __proj2, + __size1, + __size2); +} + +template <class _Iter1, class _Sent1, + class _Iter2, class _Sent2, + class _Pred, + class _Proj1, + class _Proj2> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_impl(_Iter1 __first1, _Sent1 __last1, + _Iter2 __first2, _Sent2 __last2, + _Pred& __pred, + _Proj1& __proj1, + _Proj2& __proj2, + __enable_if_t<__is_cpp17_forward_iterator<_Iter1>::value + && __is_cpp17_forward_iterator<_Iter2>::value + && !(__is_cpp17_random_access_iterator<_Iter1>::value + && __is_cpp17_random_access_iterator<_Iter2>::value)>* = nullptr) { + return std::__search_forward_impl<_ClassicAlgPolicy>(__first1, __last1, + __first2, __last2, + __pred, + __proj1, + __proj2); +} + template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, - _BinaryPredicate __pred) { - return _VSTD::__search<_BinaryPredicate&>( - __first1, __last1, __first2, __last2, __pred, - typename iterator_traits<_ForwardIterator1>::iterator_category(), - typename iterator_traits<_ForwardIterator2>::iterator_category()).first; +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2, + _BinaryPredicate __pred) { + static_assert(__is_callable<_BinaryPredicate, decltype(*__first1), decltype(*__first2)>::value, + "BinaryPredicate has to be callable"); + auto __proj = __identity(); + return std::__search_impl(__first1, __last1, __first2, __last2, __pred, __proj, __proj).first; } template <class _ForwardIterator1, class _ForwardIterator2> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1 -search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { - typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; - typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; - return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, + _ForwardIterator2 __first2, _ForwardIterator2 __last2) { + using __v1 = typename iterator_traits<_ForwardIterator1>::value_type; + using __v2 = typename iterator_traits<_ForwardIterator2>::value_type; + return std::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>()); } #if _LIBCPP_STD_VER > 14 diff --git a/libcxx/include/__algorithm/search_n.h b/libcxx/include/__algorithm/search_n.h index 4c083de65ee2..2a0547565ee9 100644 --- a/libcxx/include/__algorithm/search_n.h +++ b/libcxx/include/__algorithm/search_n.h @@ -11,8 +11,15 @@ #define _LIBCPP___ALGORITHM_SEARCH_N_H #include <__algorithm/comp.h> +#include <__algorithm/iterator_operations.h> #include <__config> +#include <__functional/identity.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> +#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> +#include <__ranges/concepts.h> +#include <__utility/pair.h> #include <type_traits> // __convert_to_integral #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -21,30 +28,39 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __first, _ForwardIterator __last, - _Size __count, const _Tp& __value_, _BinaryPredicate __pred, - forward_iterator_tag) { +template <class _AlgPolicy, class _Pred, class _Iter, class _Sent, class _SizeT, class _Type, class _Proj> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter, _Iter> __search_n_forward_impl(_Iter __first, _Sent __last, + _SizeT __count, + const _Type& __value, + _Pred& __pred, + _Proj& __proj) { if (__count <= 0) - return __first; + return std::make_pair(__first, __first); while (true) { - // Find first element in sequence that matchs __value_, with a mininum of loop checks + // Find first element in sequence that matchs __value, with a mininum of loop checks while (true) { - if (__first == __last) // return __last if no element matches __value_ - return __last; - if (__pred(*__first, __value_)) + if (__first == __last) { // return __last if no element matches __value + _IterOps<_AlgPolicy>::__advance_to(__first, __last); + return std::make_pair(__first, __first); + } + if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value)) break; ++__first; } - // *__first matches __value_, now match elements after here - _ForwardIterator __m = __first; - _Size __c(0); + // *__first matches __value, now match elements after here + _Iter __m = __first; + _SizeT __c(0); while (true) { if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) - return __first; - if (++__m == __last) // Otherwise if source exhaused, pattern not found - return __last; - if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first + return std::make_pair(__first, ++__m); + if (++__m == __last) { // Otherwise if source exhaused, pattern not found + _IterOps<_AlgPolicy>::__advance_to(__first, __last); + return std::make_pair(__first, __first); + } + + // if there is a mismatch, restart with a new __first + if (!std::__invoke(__pred, std::__invoke(__proj, *__m), __value)) { __first = __m; ++__first; @@ -54,35 +70,44 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator __search_n(_ForwardIterator __fir } } -template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIterator __first, - _RandomAccessIterator __last, _Size __count, - const _Tp& __value_, _BinaryPredicate __pred, - random_access_iterator_tag) { - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - if (__count <= 0) - return __first; - _Size __len = static_cast<_Size>(__last - __first); - if (__len < __count) - return __last; - const _RandomAccessIterator __s = __last - difference_type(__count - 1); // Start of pattern match can't go beyond here +template <class _AlgPolicy, class _Pred, class _Iter, class _Sent, class _SizeT, class _Type, class _Proj, class _DiffT> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +std::pair<_Iter, _Iter> __search_n_random_access_impl(_Iter __first, _Sent __last, + _SizeT __count, + const _Type& __value, + _Pred& __pred, + _Proj& __proj, + _DiffT __size1) { + using difference_type = typename iterator_traits<_Iter>::difference_type; + if (__count == 0) + return std::make_pair(__first, __first); + if (__size1 < static_cast<_DiffT>(__count)) { + _IterOps<_AlgPolicy>::__advance_to(__first, __last); + return std::make_pair(__first, __first); + } + + const auto __s = __first + __size1 - difference_type(__count - 1); // Start of pattern match can't go beyond here while (true) { - // Find first element in sequence that matchs __value_, with a mininum of loop checks + // Find first element in sequence that matchs __value, with a mininum of loop checks while (true) { - if (__first >= __s) // return __last if no element matches __value_ - return __last; - if (__pred(*__first, __value_)) + if (__first >= __s) { // return __last if no element matches __value + _IterOps<_AlgPolicy>::__advance_to(__first, __last); + return std::make_pair(__first, __first); + } + if (std::__invoke(__pred, std::__invoke(__proj, *__first), __value)) break; ++__first; } // *__first matches __value_, now match elements after here - _RandomAccessIterator __m = __first; - _Size __c(0); + auto __m = __first; + _SizeT __c(0); while (true) { if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) - return __first; - ++__m; // no need to check range on __m because __s guarantees we have enough source - if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first + return std::make_pair(__first, __first + _DiffT(__count)); + ++__m; // no need to check range on __m because __s guarantees we have enough source + + // if there is a mismatch, restart with a new __first + if (!std::__invoke(__pred, std::__invoke(__proj, *__m), __value)) { __first = __m; ++__first; @@ -92,19 +117,63 @@ _LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator __search_n(_RandomAccessIter } } +template <class _Iter, class _Sent, + class _DiffT, + class _Type, + class _Pred, + class _Proj> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter, _Iter> __search_n_impl(_Iter __first, _Sent __last, + _DiffT __count, + const _Type& __value, + _Pred& __pred, + _Proj& __proj, + __enable_if_t<__is_cpp17_random_access_iterator<_Iter>::value>* = nullptr) { + return std::__search_n_random_access_impl<_ClassicAlgPolicy>(__first, __last, + __count, + __value, + __pred, + __proj, + __last - __first); +} + +template <class _Iter1, class _Sent1, + class _DiffT, + class _Type, + class _Pred, + class _Proj> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +pair<_Iter1, _Iter1> __search_n_impl(_Iter1 __first, _Sent1 __last, + _DiffT __count, + const _Type& __value, + _Pred& __pred, + _Proj& __proj, + __enable_if_t<__is_cpp17_forward_iterator<_Iter1>::value + && !__is_cpp17_random_access_iterator<_Iter1>::value>* = nullptr) { + return std::__search_n_forward_impl<_ClassicAlgPolicy>(__first, __last, + __count, + __value, + __pred, + __proj); +} + template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator search_n( - _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred) { - return _VSTD::__search_n<_BinaryPredicate&>( - __first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred, - typename iterator_traits<_ForwardIterator>::iterator_category()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, + _Size __count, + const _Tp& __value, + _BinaryPredicate __pred) { + static_assert(__is_callable<_BinaryPredicate, decltype(*__first), decltype(*__last)>::value, + "BinaryPredicate has to be callable"); + auto __proj = __identity(); + return std::__search_n_impl(__first, __last, std::__convert_to_integral(__count), __value, __pred, __proj).first; } template <class _ForwardIterator, class _Size, class _Tp> -_LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) { +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +_ForwardIterator search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value) { typedef typename iterator_traits<_ForwardIterator>::value_type __v; - return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), __value_, __equal_to<__v, _Tp>()); + return std::search_n(__first, __last, std::__convert_to_integral(__count), __value, __equal_to<__v, _Tp>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_difference.h b/libcxx/include/__algorithm/set_difference.h index 5e2dca24e446..4378bd5304d9 100644 --- a/libcxx/include/__algorithm/set_difference.h +++ b/libcxx/include/__algorithm/set_difference.h @@ -13,7 +13,12 @@ #include <__algorithm/comp_ref_type.h> #include <__algorithm/copy.h> #include <__config> +#include <__functional/identity.h> +#include <__functional/invoke.h> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> +#include <__utility/pair.h> +#include <type_traits> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,50 +26,52 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -__set_difference(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) -{ - while (__first1 != __last1) - { - if (__first2 == __last2) - return _VSTD::copy(__first1, __last1, __result); - if (__comp(*__first1, *__first2)) - { - *__result = *__first1; - ++__result; - ++__first1; - } - else - { - if (!__comp(*__first2, *__first1)) - ++__first1; - ++__first2; - } +template < class _Comp, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<__uncvref_t<_InIter1>, __uncvref_t<_OutIter> > +__set_difference( + _InIter1&& __first1, _Sent1&& __last1, _InIter2&& __first2, _Sent2&& __last2, _OutIter&& __result, _Comp&& __comp) { + while (__first1 != __last1 && __first2 != __last2) { + if (__comp(*__first1, *__first2)) { + *__result = *__first1; + ++__first1; + ++__result; + } else if (__comp(*__first2, *__first1)) { + ++__first2; + } else { + ++__first1; + ++__first2; } - return __result; + } + return std::__copy(std::move(__first1), std::move(__last1), std::move(__result)); } template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -set_difference(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_difference( + _InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2, + _OutputIterator __result, + _Compare __comp) { + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return std::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp).second; } template <class _InputIterator1, class _InputIterator2, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -set_difference(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) -{ - return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result, - __less<typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_difference( + _InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2, + _OutputIterator __result) { + return std::__set_difference( + __first1, + __last1, + __first2, + __last2, + __result, + __less<typename iterator_traits<_InputIterator1>::value_type, + typename iterator_traits<_InputIterator2>::value_type>()).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_intersection.h b/libcxx/include/__algorithm/set_intersection.h index c4163fcd4c3c..77cc83738d1f 100644 --- a/libcxx/include/__algorithm/set_intersection.h +++ b/libcxx/include/__algorithm/set_intersection.h @@ -11,8 +11,11 @@ #include <__algorithm/comp.h> #include <__algorithm/comp_ref_type.h> +#include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__iterator/next.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -20,48 +23,76 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) -{ - while (__first1 != __last1 && __first2 != __last2) - { - if (__comp(*__first1, *__first2)) - ++__first1; - else - { - if (!__comp(*__first2, *__first1)) - { - *__result = *__first1; - ++__result; - ++__first1; - } - ++__first2; - } +template <class _InIter1, class _InIter2, class _OutIter> +struct __set_intersection_result { + _InIter1 __in1_; + _InIter2 __in2_; + _OutIter __out_; + + // need a constructor as C++03 aggregate init is hard + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 + __set_intersection_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter) + : __in1_(std::move(__in_iter1)), __in2_(std::move(__in_iter2)), __out_(std::move(__out_iter)) {} +}; + +template <class _AlgPolicy, class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 __set_intersection_result<_InIter1, _InIter2, _OutIter> +__set_intersection( + _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) { + while (__first1 != __last1 && __first2 != __last2) { + if (__comp(*__first1, *__first2)) + ++__first1; + else { + if (!__comp(*__first2, *__first1)) { + *__result = *__first1; + ++__result; + ++__first1; + } + ++__first2; } - return __result; + } + + return __set_intersection_result<_InIter1, _InIter2, _OutIter>( + _IterOps<_AlgPolicy>::next(std::move(__first1), std::move(__last1)), + _IterOps<_AlgPolicy>::next(std::move(__first2), std::move(__last2)), + std::move(__result)); } template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_intersection( + _InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2, + _OutputIterator __result, + _Compare __comp) { + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return std::__set_intersection<_ClassicAlgPolicy, _Comp_ref>( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::move(__result), + __comp) + .__out_; } template <class _InputIterator1, class _InputIterator2, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) -{ - return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result, - __less<typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_intersection( + _InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2, + _OutputIterator __result) { + return std::__set_intersection<_ClassicAlgPolicy>( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::move(__result), + __less<typename iterator_traits<_InputIterator1>::value_type, + typename iterator_traits<_InputIterator2>::value_type>()) + .__out_; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_symmetric_difference.h b/libcxx/include/__algorithm/set_symmetric_difference.h index 2dbfb35d7be6..cd532ab5800d 100644 --- a/libcxx/include/__algorithm/set_symmetric_difference.h +++ b/libcxx/include/__algorithm/set_symmetric_difference.h @@ -14,6 +14,7 @@ #include <__algorithm/copy.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,55 +22,81 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) -{ - while (__first1 != __last1) - { - if (__first2 == __last2) - return _VSTD::copy(__first1, __last1, __result); - if (__comp(*__first1, *__first2)) - { - *__result = *__first1; - ++__result; - ++__first1; - } - else - { - if (__comp(*__first2, *__first1)) - { - *__result = *__first2; - ++__result; - } - else - ++__first1; - ++__first2; - } +template <class _InIter1, class _InIter2, class _OutIter> +struct __set_symmetric_difference_result { + _InIter1 __in1_; + _InIter2 __in2_; + _OutIter __out_; + + // need a constructor as C++03 aggregate init is hard + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 + __set_symmetric_difference_result(_InIter1&& __in_iter1, _InIter2&& __in_iter2, _OutIter&& __out_iter) + : __in1_(std::move(__in_iter1)), __in2_(std::move(__in_iter2)), __out_(std::move(__out_iter)) {} +}; + +template <class _Compare, class _InIter1, class _Sent1, class _InIter2, class _Sent2, class _OutIter> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 __set_symmetric_difference_result<_InIter1, _InIter2, _OutIter> +__set_symmetric_difference( + _InIter1 __first1, _Sent1 __last1, _InIter2 __first2, _Sent2 __last2, _OutIter __result, _Compare&& __comp) { + while (__first1 != __last1) { + if (__first2 == __last2) { + auto __ret1 = std::__copy_impl(std::move(__first1), std::move(__last1), std::move(__result)); + return __set_symmetric_difference_result<_InIter1, _InIter2, _OutIter>( + std::move(__ret1.first), std::move(__first2), std::move((__ret1.second))); + } + if (__comp(*__first1, *__first2)) { + *__result = *__first1; + ++__result; + ++__first1; + } else { + if (__comp(*__first2, *__first1)) { + *__result = *__first2; + ++__result; + } else { + ++__first1; + } + ++__first2; } - return _VSTD::copy(__first2, __last2, __result); + } + auto __ret2 = std::__copy_impl(std::move(__first2), std::move(__last2), std::move(__result)); + return __set_symmetric_difference_result<_InIter1, _InIter2, _OutIter>( + std::move(__first1), std::move(__ret2.first), std::move((__ret2.second))); } template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_symmetric_difference( + _InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2, + _OutputIterator __result, + _Compare __comp) { + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return std::__set_symmetric_difference<_Comp_ref>( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::move(__result), + __comp) + .__out_; } template <class _InputIterator1, class _InputIterator2, class _OutputIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -_OutputIterator -set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) -{ - return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, - __less<typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator set_symmetric_difference( + _InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2, + _OutputIterator __result) { + return std::set_symmetric_difference( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + std::move(__result), + __less<typename iterator_traits<_InputIterator1>::value_type, + typename iterator_traits<_InputIterator2>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h index f7406a5170e1..76a18215731b 100644 --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -17,6 +17,7 @@ #include <__bits> #include <__config> #include <__debug> +#include <__debug_utils/randomize_range.h> #include <__functional/operations.h> #include <__functional/ranges_operations.h> #include <__iterator/iterator_traits.h> @@ -24,10 +25,6 @@ #include <climits> #include <memory> -#if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY) -# include <__algorithm/shuffle.h> -#endif - #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header #endif @@ -582,7 +579,7 @@ extern template _LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long dou 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); + std::__debug_randomize_range(__first, __last); using _Comp_ref = typename __comp_ref_type<_Comp>::type; if (__libcpp_is_constant_evaluated()) { std::__partial_sort<_Comp_ref>(__first, __last, __last, _Comp_ref(__comp)); diff --git a/libcxx/include/__algorithm/sort_heap.h b/libcxx/include/__algorithm/sort_heap.h index 3a63d744fc1c..261adedd0eaf 100644 --- a/libcxx/include/__algorithm/sort_heap.h +++ b/libcxx/include/__algorithm/sort_heap.h @@ -14,6 +14,7 @@ #include <__algorithm/pop_heap.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #include <type_traits> // swap #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -23,29 +24,27 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _RandomAccessIterator> -_LIBCPP_CONSTEXPR_AFTER_CXX17 void -__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n) - _VSTD::__pop_heap<_Compare>(__first, __last, __comp, __n); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11 +void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) { + using _CompRef = typename __comp_ref_type<_Compare>::type; + _CompRef __comp_ref = __comp; + + using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; + for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n) + std::__pop_heap<_CompRef>(__first, __last, __comp_ref, __n); } template <class _RandomAccessIterator, class _Compare> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - _VSTD::__sort_heap<_Comp_ref>(__first, __last, __comp); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) { + std::__sort_heap(std::move(__first), std::move(__last), __comp); } template <class _RandomAccessIterator> -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -void -sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) -{ - _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 +void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { + std::sort_heap(std::move(__first), std::move(__last), + __less<typename iterator_traits<_RandomAccessIterator>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/upper_bound.h b/libcxx/include/__algorithm/upper_bound.h index c6483607e3c6..3fc254873532 100644 --- a/libcxx/include/__algorithm/upper_bound.h +++ b/libcxx/include/__algorithm/upper_bound.h @@ -24,7 +24,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Compare, class _ForwardIterator, class _Tp> _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) +__upper_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); @@ -33,7 +33,7 @@ __upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __va difference_type __l2 = _VSTD::__half_positive(__len); _ForwardIterator __m = __first; _VSTD::advance(__m, __l2); - if (__comp(__value_, *__m)) + if (__comp(__value, *__m)) __len = __l2; else { @@ -48,18 +48,18 @@ template <class _ForwardIterator, class _Tp, class _Compare> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp) +upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) { - return _VSTD::__upper_bound<_Compare&>(__first, __last, __value_, __comp); + return _VSTD::__upper_bound<_Compare&>(__first, __last, __value, __comp); } template <class _ForwardIterator, class _Tp> _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator -upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_) +upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return _VSTD::upper_bound(__first, __last, __value_, + return _VSTD::upper_bound(__first, __last, __value, __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>()); } |