diff --git a/libcxx/docs/Status/RangesAlgorithms.csv b/libcxx/docs/Status/RangesAlgorithms.csv --- a/libcxx/docs/Status/RangesAlgorithms.csv +++ b/libcxx/docs/Status/RangesAlgorithms.csv @@ -29,7 +29,7 @@ Read-only,is_partitioned,Nikolas Klauser,`D124440 `_,✅ Read-only,is_sorted,Nikolas Klauser,`D125608 `_,✅ Read-only,is_sorted_until,Nikolas Klauser,`D125608 `_,✅ -Read-only,includes,Nikolas Klauser,n/a,Not started +Read-only,includes,Hui Xie,`D130116 `,✅ Read-only,is_heap,Nikolas Klauser,n/a,Not started Read-only,is_heap_until,Nikolas Klauser,n/a,Not started Read-only,clamp,Nikolas Klauser,`D126193 `_,Under review diff --git a/libcxx/include/__algorithm/includes.h b/libcxx/include/__algorithm/includes.h --- a/libcxx/include/__algorithm/includes.h +++ b/libcxx/include/__algorithm/includes.h @@ -13,6 +13,7 @@ #include <__algorithm/comp_ref_type.h> #include <__config> #include <__iterator/iterator_traits.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -20,41 +21,40 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_LIBCPP_CONSTEXPR_AFTER_CXX17 bool -__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, - _Compare __comp) -{ - for (; __first2 != __last2; ++__first1) - { - if (__first1 == __last1 || __comp(*__first2, *__first1)) - return false; - if (!__comp(*__first1, *__first2)) - ++__first2; - } - return true; +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +__includes(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Comp&& __comp) { + for (; __first2 != __last2; ++__first1) { + if (__first1 == __last1 || __comp(*__first2, *__first1)) + return false; + if (!__comp(*__first1, *__first2)) + ++__first2; + } + return true; } template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, - _Compare __comp) -{ - typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool includes( + _InputIterator1 __first1, + _InputIterator1 __last1, + _InputIterator2 __first2, + _InputIterator2 __last2, + _Compare __comp) { + typedef typename __comp_ref_type<_Compare>::type _Comp_ref; + return std::__includes( + std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), static_cast<_Comp_ref>(__comp)); } template -_LIBCPP_NODISCARD_EXT inline -_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 -bool -includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) -{ - return _VSTD::includes(__first1, __last1, __first2, __last2, - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); +_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool +includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { + return std::includes( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + __less::value_type, + typename iterator_traits<_InputIterator2>::value_type>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_includes.h b/libcxx/include/__algorithm/ranges_includes.h --- a/libcxx/include/__algorithm/ranges_includes.h +++ b/libcxx/include/__algorithm/ranges_includes.h @@ -9,8 +9,8 @@ #ifndef _LIBCPP___ALGORITHM_RANGES_INCLUDES_H #define _LIBCPP___ALGORITHM_RANGES_INCLUDES_H -#include <__algorithm/make_projected.h> #include <__algorithm/includes.h> +#include <__algorithm/make_projected.h> #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> @@ -35,29 +35,46 @@ namespace __includes { struct __fn { - - template _Sent1, input_iterator _Iter2, sentinel_for<_Iter2> _Sent2, - class _Proj1 = identity, class _Proj2 = identity, - indirect_strict_weak_order, 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_iterator _Iter1, + sentinel_for<_Iter1> _Sent1, + input_iterator _Iter2, + sentinel_for<_Iter2> _Sent2, + class _Proj1 = identity, + class _Proj2 = identity, + indirect_strict_weak_order, projected<_Iter2, _Proj2>> _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr bool operator()( + _Iter1 __first1, + _Sent1 __last1, + _Iter2 __first2, + _Sent2 __last2, + _Comp __comp = {}, + _Proj1 __proj1 = {}, + _Proj2 __proj2 = {}) const { + return std::__includes( + std::move(__first1), + std::move(__last1), + std::move(__first2), + std::move(__last2), + ranges::__make_projected_comp(__comp, __proj1, __proj2)); } - template , _Proj1>, - projected, _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 {}; + template < + input_range _Range1, + input_range _Range2, + class _Proj1 = identity, + class _Proj2 = identity, + indirect_strict_weak_order, _Proj1>, projected, _Proj2>> + _Comp = ranges::less> + _LIBCPP_HIDE_FROM_ABI constexpr bool operator()( + _Range1&& __range1, _Range2&& __range2, _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const { + return std::__includes( + ranges::begin(__range1), + ranges::end(__range1), + ranges::begin(__range2), + ranges::end(__range2), + ranges::__make_projected_comp(__comp, __proj1, __proj2)); } - }; } // namespace __includes diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -801,6 +801,20 @@ constexpr set_union_result, borrowed_iterator_t, O> set_union(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + + template S1, input_iterator I2, sentinel_for S2, + class Proj1 = identity, class Proj2 = identity, + indirect_strict_weak_order, projected> Comp = + ranges::less> + constexpr bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 + + template, Proj1>, + projected, Proj2>> Comp = ranges::less> + constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {}, + Proj1 proj1 = {}, Proj2 proj2 = {}); // Since C++20 } constexpr bool // constexpr in C++20 @@ -1551,6 +1565,7 @@ #include <__algorithm/ranges_find_if_not.h> #include <__algorithm/ranges_for_each.h> #include <__algorithm/ranges_for_each_n.h> +#include <__algorithm/ranges_includes.h> #include <__algorithm/ranges_is_partitioned.h> #include <__algorithm/ranges_is_sorted.h> #include <__algorithm/ranges_is_sorted_until.h> diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp @@ -124,8 +124,8 @@ //(void)std::ranges::generate(first, last, NullaryValue(&copies)); assert(copies == 0); //(void)std::ranges::generate(a, NullaryValue(&copies)); assert(copies == 0); //(void)std::ranges::generate_n(first, count, NullaryValue(&copies)); assert(copies == 0); - //(void)std::ranges::includes(first, last, first2, last2, Less(&copies)); assert(copies == 0); - //(void)std::ranges::includes(a, b, Less(&copies)); assert(copies == 0); + (void)std::ranges::includes(first, last, first2, last2, Less(&copies)); assert(copies == 0); + (void)std::ranges::includes(a, b, Less(&copies)); assert(copies == 0); //(void)std::ranges::is_heap(first, last, Less(&copies)); assert(copies == 0); //(void)std::ranges::is_heap(a, Less(&copies)); assert(copies == 0); //(void)std::ranges::is_heap_until(first, last, Less(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp --- a/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp +++ b/libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp @@ -107,8 +107,8 @@ (void)std::ranges::for_each(first, last, UnaryVoid(), Proj(&copies)); assert(copies == 0); (void)std::ranges::for_each(a, UnaryVoid(), Proj(&copies)); assert(copies == 0); (void)std::ranges::for_each_n(first, count, UnaryVoid(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::includes(first, last, first2, last2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::includes(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::includes(first, last, first2, last2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::includes(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); //(void)std::ranges::is_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::is_heap(a, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::is_heap_until(first, last, Less(), Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/ranges_includes.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/ranges_includes.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/ranges_includes.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/ranges_includes.pass.cpp @@ -30,16 +30,318 @@ #include #include #include +#include #include "almost_satisfies_types.h" #include "test_iterators.h" -// TODO: SFINAE tests. +template < + class Iter1 = int*, + class Sent1 = int*, + class Iter2 = int*, + class Sent2 = int*, + class Comp = std::ranges::less, + class Proj1 = std::identity, + class Proj2 = std::identity> +concept HasIncludesIter = + requires(Iter1&& iter1, Sent1&& sent1, Iter2&& iter2, Sent2&& sent2, Comp&& comp, Proj1&& proj1, Proj2&& proj2) { + std::ranges::includes( + std::forward(iter1), + std::forward(sent1), + std::forward(iter2), + std::forward(sent2), + std::forward(comp), + std::forward(proj1), + std::forward(proj2)); + }; + +static_assert(HasIncludesIter); + +// !std::input_iterator +static_assert(!HasIncludesIter); + +// !std::sentinel_for +static_assert(!HasIncludesIter); + +// !std::input_iterator +static_assert(!HasIncludesIter); + +// !std::sentinel_for +static_assert(!HasIncludesIter); + +// !indirect_strict_weak_order, projected> +struct NotAComparator {}; +static_assert(!HasIncludesIter); + +template < + class Range1, + class Range2, + class Comp = std::ranges::less, + class Proj1 = std::identity, + class Proj2 = std::identity> +concept HasIncludesRange = + requires(Range1&& range1, Range2&& range2, Comp&& comp, Proj1&& proj1, Proj2&& proj2) { + std::ranges::includes( + std::forward(range1), + std::forward(range2), + std::forward(comp), + std::forward(proj1), + std::forward(proj2)); + }; + +template +using R = UncheckedRange; + +static_assert(HasIncludesRange, R>); + +// !std::input_range +static_assert(!HasIncludesRange, R>); + +// !std::input_range +static_assert(!HasIncludesRange, R>); + +// !indirect_strict_weak_order, Proj1>, +// projected, Proj2>> +static_assert(!HasIncludesRange, R, NotAComparator>); + +template class SentWrapper, std::size_t N1, std::size_t N2> +constexpr void testIncludesImpl(std::array in1, std::array in2, bool expected) { + using Sent1 = SentWrapper; + using Sent2 = SentWrapper; + + // iterator overload + { + std::same_as decltype(auto) result = std::ranges::includes( + In1{in1.data()}, Sent1{In1{in1.data() + in1.size()}}, In2{in2.data()}, Sent2{In2{in2.data() + in2.size()}}); + assert(result == expected); + } + + // range overload + { + std::ranges::subrange r1{In1{in1.data()}, Sent1{In1{in1.data() + in1.size()}}}; + std::ranges::subrange r2{In2{in2.data()}, Sent2{In2{in2.data() + in2.size()}}}; + std::same_as decltype(auto) result = std::ranges::includes(r1, r2); + assert(result == expected); + } +} + +template class SentWrapper> +constexpr void testImpl() { + // range 1 shorter than range2 + { + std::array in1{0, 1, 5, 6, 9, 10}; + std::array in2{3, 6, 7, 9, 13, 15, 100}; + bool expected = false; + testIncludesImpl(in1, in2, expected); + } + // range 2 shorter than range 1 but not subsequence + { + std::array in1{2, 6, 8, 12, 15, 16}; + std::array in2{0, 2, 8}; + bool expected = false; + testIncludesImpl(in1, in2, expected); + } + + // range 1 and range 2 has the same length but different elements + { + std::array in1{2, 6, 8, 12, 15, 16}; + std::array in2{0, 2, 8, 15, 17, 19}; + bool expected = false; + testIncludesImpl(in1, in2, expected); + } + + // range 1 == range 2 + { + std::array in1{0, 1, 2}; + std::array in2{0, 1, 2}; + bool expected = true; + testIncludesImpl(in1, in2, expected); + } + + // range 2 is subsequence of range 1 + { + std::array in1{8, 9, 10, 12, 13}; + std::array in2{8, 10}; + bool expected = true; + testIncludesImpl(in1, in2, expected); + } + + // range 1 is subsequence of range 2 + { + std::array in1{0, 1, 1}; + std::array in2{0, 1, 1, 2, 5}; + bool expected = false; + testIncludesImpl(in1, in2, expected); + } + + // range 2 is subsequence of range 1 with duplicated elements + { + std::array in1{8, 9, 10, 12, 12, 12}; + std::array in2{8, 12, 12}; + bool expected = true; + testIncludesImpl(in1, in2, expected); + } + + // range 2 is not a subsequence of range 1 because of duplicated elements + { + std::array in1{8, 9, 10, 12, 13}; + std::array in2{8, 10, 10}; + bool expected = false; + testIncludesImpl(in1, in2, expected); + } + + // range 1 is empty + { + std::array in1{}; + std::array in2{3, 4, 5}; + bool expected = false; + testIncludesImpl(in1, in2, expected); + } + + // range 2 is empty + { + std::array in1{3, 4, 5}; + std::array in2{}; + bool expected = true; + testIncludesImpl(in1, in2, expected); + } + + // both ranges are empty + { + std::array in1{}; + std::array in2{}; + bool expected = true; + testIncludesImpl(in1, in2, expected); + } +} + +template class SentWrapper> +constexpr void withAllPermutationsOfIter1() { + // C++17 InputIterator may or may not satisfy std::input_iterator + testImpl, Iter2, sentinel_wrapper>(); + testImpl, Iter2, SentWrapper>(); + testImpl, Iter2, SentWrapper>(); + testImpl, Iter2, SentWrapper>(); + testImpl, Iter2, SentWrapper>(); + testImpl(); +} + +template