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 @@ -61,7 +61,7 @@ Write,partition_copy,Not assigned,n/a,Not started Write,partial_sort_copy,Not assigned,n/a,Not started Merge,merge,Hui Xie,`D128611 `_,✅ -Merge,set_difference,Hui Xie,n/a,Not started +Merge,set_difference,Hui Xie,`D128983 `,✅ Merge,set_intersection,Hui Xie,n/a,Not started Merge,set_symmetric_difference,Hui Xie,n/a,Not started Merge,set_union,Not assigned,Hui Xie,Not started diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -106,6 +106,7 @@ __algorithm/ranges_replace.h __algorithm/ranges_replace_if.h __algorithm/ranges_reverse.h + __algorithm/ranges_set_difference.h __algorithm/ranges_sort.h __algorithm/ranges_stable_sort.h __algorithm/ranges_swap_ranges.h diff --git a/libcxx/include/__algorithm/make_projected.h b/libcxx/include/__algorithm/make_projected.h --- 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) @@ -42,6 +44,23 @@ } } +template +_LIBCPP_HIDE_FROM_ABI constexpr static +decltype(auto) __make_projected_comp(_Comp& __comp, _Proj1& __proj1, _Proj2& __proj2) { + if constexpr (same_as<_Proj1, identity> && same_as<_Proj2, identity> && !is_member_pointer_v>) { + // 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(__lhs)), + std::invoke(__proj2, std::forward(__rhs))); + }; + } +} + } // namespace ranges _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/ranges_set_difference.h b/libcxx/include/__algorithm/ranges_set_difference.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__algorithm/ranges_set_difference.h @@ -0,0 +1,109 @@ +//===----------------------------------------------------------------------===// +// +// 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 +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, _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 \ No newline at end of file diff --git a/libcxx/include/__algorithm/set_difference.h b/libcxx/include/__algorithm/set_difference.h --- 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 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,50 +26,54 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -_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 -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; + auto __ret = std::__set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); + return std::move(__ret.second); } template -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::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) { + auto __ret = std::__set_difference( + __first1, + __last1, + __first2, + __last2, + __result, + __less::value_type, + typename iterator_traits<_InputIterator2>::value_type>()); + return std::move(__ret.second); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -511,6 +511,24 @@ merge(R1&& r1, R2&& r2, O result, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + template + using set_difference_result = in_out_result; // since C++20 + + template S1, input_­iterator I2, sentinel_­for S2, + weakly_­incrementable O, class Comp = ranges::less, + class Proj1 = identity, class Proj2 = identity> + requires mergeable + constexpr set_difference_result + set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, + Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + + template + requires mergeable, iterator_t, O, Comp, Proj1, Proj2> + constexpr set_difference_result, O> + set_difference(R1&& r1, R2&& r2, O result, + Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + } constexpr bool // constexpr in C++20 @@ -1278,6 +1296,7 @@ #include <__algorithm/ranges_replace.h> #include <__algorithm/ranges_replace_if.h> #include <__algorithm/ranges_reverse.h> +#include <__algorithm/ranges_set_difference.h> #include <__algorithm/ranges_sort.h> #include <__algorithm/ranges_stable_sort.h> #include <__algorithm/ranges_swap_ranges.h> diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -345,6 +345,7 @@ module ranges_replace { private header "__algorithm/ranges_replace.h" } module ranges_replace_if { private header "__algorithm/ranges_replace_if.h" } module ranges_reverse { private header "__algorithm/ranges_reverse.h" } + module ranges_set_difference { private header "__algorithm/ranges_set_difference.h" } module ranges_sort { private header "__algorithm/ranges_sort.h" } module ranges_stable_sort { private header "__algorithm/ranges_stable_sort.h" } module ranges_swap_ranges { private header "__algorithm/ranges_swap_ranges.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 @@ -199,8 +199,8 @@ //(void)std::ranges::search(a, b, Equal(&copies)); assert(copies == 0); //(void)std::ranges::search_n(first, last, count, value, Equal(&copies)); assert(copies == 0); //(void)std::ranges::search_n(a, count, value, Equal(&copies)); assert(copies == 0); - //(void)std::ranges::set_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0); - //(void)std::ranges::set_difference(a, b, first2, Less(&copies)); assert(copies == 0); + (void)std::ranges::set_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0); + (void)std::ranges::set_difference(a, b, first2, Less(&copies)); assert(copies == 0); //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0); //(void)std::ranges::set_intersection(a, b, first2, Less(&copies)); assert(copies == 0); //(void)std::ranges::set_symmetric_difference(first, mid, mid, last, first2, 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 @@ -190,8 +190,8 @@ //(void)std::ranges::search(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0); //(void)std::ranges::search_n(first, last, count, value, Equal(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::search_n(a, count, value, Equal(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::set_difference(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::set_difference(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::set_difference(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); + (void)std::ranges::set_difference(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); //(void)std::ranges::set_intersection(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); //(void)std::ranges::set_symmetric_difference(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -143,6 +143,7 @@ #include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}} #include <__algorithm/ranges_replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}} #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}} +#include <__algorithm/ranges_set_difference.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_difference.h'}} #include <__algorithm/ranges_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort.h'}} #include <__algorithm/ranges_stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_stable_sort.h'}} #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}} diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/ranges_merge.pass.cpp @@ -11,15 +11,15 @@ // UNSUPPORTED: c++03, c++11, c++14, c++17 // UNSUPPORTED: libcpp-has-no-incomplete-ranges -// template S1, input_­iterator I2, sentinel_­for S2, -// weakly_­incrementable O, class Comp = ranges::less, class Proj1 = identity, +// template S1, input_iterator I2, sentinel_for S2, +// weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity, // class Proj2 = identity> // requires mergeable // constexpr merge_result // merge(I1 first1, S1 last1, I2 first2, S2 last2, O result, // Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 // -// template // requires mergeable, iterator_t, O, Comp, Proj1, Proj2> // constexpr merge_result, borrowed_iterator_t, O> @@ -33,6 +33,7 @@ #include "almost_satisfies_types.h" #include "MoveOnly.h" #include "test_iterators.h" +#include "../sortable_helpers.h" // Test iterator overload's constraints: // ===================================== @@ -251,15 +252,15 @@ } constexpr void runAllIteratorPermutationsTests() { - withAllPermutationsOfInIter1AndInIter2>(); withAllPermutationsOfInIter1AndInIter2>(); + withAllPermutationsOfInIter1AndInIter2>(); withAllPermutationsOfInIter1AndInIter2>(); withAllPermutationsOfInIter1AndInIter2>(); withAllPermutationsOfInIter1AndInIter2>(); withAllPermutationsOfInIter1AndInIter2>(); - static_assert(withAllPermutationsOfInIter1AndInIter2>()); static_assert(withAllPermutationsOfInIter1AndInIter2>()); + static_assert(withAllPermutationsOfInIter1AndInIter2>()); static_assert(withAllPermutationsOfInIter1AndInIter2>()); static_assert(withAllPermutationsOfInIter1AndInIter2>()); static_assert(withAllPermutationsOfInIter1AndInIter2>()); @@ -268,26 +269,6 @@ constexpr bool test() { // check that every element is copied exactly once - struct TracedCopy { - int copy_assign = 0; - int data = 0; - - constexpr TracedCopy() = default; - constexpr TracedCopy(int i) : data(i) {} - constexpr TracedCopy(const TracedCopy& other) : copy_assign(other.copy_assign), data(other.data) {} - - constexpr TracedCopy(TracedCopy&& other) = delete; - constexpr TracedCopy& operator=(TracedCopy&& other) = delete; - - constexpr TracedCopy& operator=(const TracedCopy& other) { - copy_assign = other.copy_assign + 1; - data = other.data; - return *this; - } - - constexpr bool operator==(const TracedCopy& o) const { return data == o.data; } - constexpr auto operator<=>(const TracedCopy& o) const { return data <=> o.data; } - }; { std::array r1{3, 5, 8}; std::array r2{1, 3, 8}; @@ -302,7 +283,7 @@ assert(result.out == out.end()); assert(std::ranges::equal(out, std::array{1, 3, 3, 5, 8, 8})); - assert(std::ranges::all_of(out, [](const TracedCopy& e) { return e.copy_assign == 1; })); + assert(std::ranges::all_of(out, &TracedCopy::copiedOnce)); } // range overload @@ -315,7 +296,7 @@ assert(result.out == out.end()); assert(std::ranges::equal(out, std::array{1, 3, 3, 5, 8, 8})); - assert(std::ranges::all_of(out, [](const TracedCopy& e) { return e.copy_assign == 1; })); + assert(std::ranges::all_of(out, &TracedCopy::copiedOnce)); } } diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/ranges_set_difference.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/ranges_set_difference.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/algorithms/alg.sorting/alg.set.operations/set.difference/ranges_set_difference.pass.cpp @@ -0,0 +1,568 @@ + +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template S1, input_iterator I2, sentinel_for S2, +// weakly_incrementable O, class Comp = ranges::less, +// class Proj1 = identity, class Proj2 = identity> +// requires mergeable +// constexpr set_difference_result +// set_difference(I1 first1, S1 last1, I2 first2, S2 last2, O result, +// Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + +// template +// requires mergeable, iterator_t, O, Comp, Proj1, Proj2> +// constexpr set_difference_result, O> +// set_difference(R1&& r1, R2&& r2, O result, +// Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // since C++20 + +#include +#include +#include + +#include "almost_satisfies_types.h" +#include "MoveOnly.h" +#include "test_iterators.h" +#include "../../sortable_helpers.h" + +// Test iterator overload's constraints: +// ===================================== +template < + class InIter1, + class InIter2, + class OutIter, + class Sent1 = sentinel_wrapper, + class Sent2 = sentinel_wrapper> +concept HasSetDifferenceIter = + requires(InIter1&& inIter1, InIter2&& inIter2, OutIter&& outIter, Sent1&& sent1, Sent2&& sent2) { + std::ranges::set_difference( + std::forward(inIter1), + std::forward(sent1), + std::forward(inIter2), + std::forward(sent2), + std::forward(outIter)); + }; + +static_assert(HasSetDifferenceIter); + +// !std::input_iterator +static_assert(!HasSetDifferenceIter); + +// !std::sentinel_for +static_assert(!HasSetDifferenceIter); + +// !std::input_iterator +static_assert(!HasSetDifferenceIter); + +// !std::sentinel_for +static_assert(!HasSetDifferenceIter); + +// !std::weakly_incrementable +static_assert(!HasSetDifferenceIter); + +// !std::mergeable +static_assert(!HasSetDifferenceIter); + +// Test range overload's constraints: +// ===================================== + +template +concept HasSetDifferenceRange = + requires(Range1&& range1, Range2&& range2, OutIter&& outIter) { + std::ranges::set_difference( + std::forward(range1), std::forward(range2), std::forward(outIter)); + }; + +static_assert(HasSetDifferenceRange, UncheckedRange, int*>); + +// !std::input_range +static_assert(!HasSetDifferenceRange, UncheckedRange, int*>); + +// !std::input_range +static_assert(!HasSetDifferenceRange, UncheckedRange, int*>); + +// !std::weakly_incrementable +static_assert(!HasSetDifferenceRange, UncheckedRange, WeaklyIncrementableNotMovable >); + +// !std::mergeable, iterator_t, O, Comp, Proj1, Proj2> +static_assert(!HasSetDifferenceRange< UncheckedRange, UncheckedRange, MoveOnly*>); + +using std::ranges::set_difference_result; + +template +constexpr void testSetDifferenceImpl(std::array in1, std::array in2, std::array expected) { + // TODO: std::ranges::set_difference calls std::ranges::copy + // std::ranges::copy(contiguous_iterator, sentinel_wrapper>, contiguous_iterator) doesn't seem to work. + // It seems that std::ranges::copy calls std::copy, which unwraps contiguous_iterator into int*, + // and then it failed because there is no == between int* and sentinel_wrapper> + using Sent1 = std::conditional_t, In1, sentinel_wrapper>; + using Sent2 = std::conditional_t, In2, sentinel_wrapper>; + + // iterator overload + { + std::array out; + std::same_as> decltype(auto) result = std::ranges::set_difference( + In1{in1.data()}, + Sent1{In1{in1.data() + in1.size()}}, + In2{in2.data()}, + Sent2{In2{in2.data() + in2.size()}}, + Out{out.data()}); + assert(std::ranges::equal(out, expected)); + + assert(base(result.in) == in1.data() + in1.size()); + assert(base(result.out) == out.data() + out.size()); + } + + // range overload + { + std::array out; + 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::set_difference(r1, r2, Out{out.data()}); + assert(std::ranges::equal(out, expected)); + + assert(base(result.in) == in1.data() + in1.size()); + assert(base(result.out) == out.data() + out.size()); + } +} + +template +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}; + std::array expected{0, 1, 5, 10}; + testSetDifferenceImpl(in1, in2, expected); + } + + // range 2 shorter than range 1 + { + std::array in1{2, 6, 8, 12, 15, 16}; + std::array in2{0, 2, 8}; + std::array expected{6, 12, 15, 16}; + testSetDifferenceImpl(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}; + std::array expected{6, 12, 16}; + testSetDifferenceImpl(in1, in2, expected); + } + + // range 1 == range 2 + { + std::array in1{0, 1, 2}; + std::array in2{0, 1, 2}; + std::array expected{}; + testSetDifferenceImpl(in1, in2, expected); + } + + // range 1 is super set of range 2 + { + std::array in1{8, 8, 10, 12, 13}; + std::array in2{8, 10}; + std::array expected{8, 12, 13}; + testSetDifferenceImpl(in1, in2, expected); + } + + // range 2 is super set of range 1 + { + std::array in1{0, 1, 1}; + std::array in2{0, 1, 1, 2, 5}; + std::array expected{}; + testSetDifferenceImpl(in1, in2, expected); + } + + // range 1 is empty + { + std::array in1{}; + std::array in2{3, 4, 5}; + std::array expected{}; + testSetDifferenceImpl(in1, in2, expected); + } + + // range 2 is empty + { + std::array in1{3, 4, 5}; + std::array in2{}; + std::array expected{3, 4, 5}; + testSetDifferenceImpl(in1, in2, expected); + } + + // both ranges are empty + { + std::array in1{}; + std::array in2{}; + std::array expected{}; + testSetDifferenceImpl(in1, in2, expected); + } + + // check that ranges::dangling is returned for non-borrowed_range + { + struct NonBorrowedRange { + int* data_; + size_t size_; + + // TODO: std::ranges::set_difference calls std::__copy + // std::ranges::copy(contiguous_iterator, sentinel_wrapper>, contiguous_iterator) doesn't seem to work. + // It seems that std::ranges::copy calls std::copy, which unwraps contiguous_iterator into int*, + // and then it failed because there is no == between int* and sentinel_wrapper> + using Sent = std::conditional_t, In2, sentinel_wrapper>; + + constexpr NonBorrowedRange(int* d, size_t s) : data_{d}, size_{s} {} + + constexpr In2 begin() const { return In2{data_}; }; + constexpr Sent end() const { return Sent{In2{data_ + size_}}; }; + }; + + std::array r1{3, 6, 7, 9}; + std::array r2{2, 3, 4, 5, 6}; + std::array out; + std::same_as> decltype(auto) result = + std::ranges::set_difference(NonBorrowedRange{r1.data(), r1.size()}, r2, out.data()); + assert(base(result.out) == out.data() + out.size()); + assert(std::ranges::equal(out, std::array{7, 9})); + } +} + +template +constexpr void withAllPermutationsOfInIter1() { + testImpl, InIter2, OutIter>(); + testImpl, InIter2, OutIter>(); + testImpl, InIter2, OutIter>(); + testImpl, InIter2, OutIter>(); + testImpl, InIter2, OutIter>(); +} + +template +constexpr bool withAllPermutationsOfInIter1AndInIter2() { + withAllPermutationsOfInIter1, OutIter>(); + withAllPermutationsOfInIter1, OutIter>(); + withAllPermutationsOfInIter1, OutIter>(); + withAllPermutationsOfInIter1, OutIter>(); + withAllPermutationsOfInIter1, OutIter>(); + return true; +} + +constexpr void runAllIteratorPermutationsTests() { + withAllPermutationsOfInIter1AndInIter2>(); + withAllPermutationsOfInIter1AndInIter2>(); + withAllPermutationsOfInIter1AndInIter2>(); + withAllPermutationsOfInIter1AndInIter2>(); + withAllPermutationsOfInIter1AndInIter2>(); + withAllPermutationsOfInIter1AndInIter2>(); + + static_assert(withAllPermutationsOfInIter1AndInIter2>()); + static_assert(withAllPermutationsOfInIter1AndInIter2>()); + static_assert(withAllPermutationsOfInIter1AndInIter2>()); + static_assert(withAllPermutationsOfInIter1AndInIter2>()); + static_assert(withAllPermutationsOfInIter1AndInIter2>()); + static_assert(withAllPermutationsOfInIter1AndInIter2>()); +} + +constexpr bool test() { + // check that every element is copied exactly once + { + std::array r1{3, 5, 8, 15, 16}; + std::array r2{1, 3, 8}; + + // iterator overload + { + std::array out; + auto result = std::ranges::set_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data()); + + assert(result.in == r1.end()); + assert(result.out == out.end()); + assert(std::ranges::equal(out, std::array{5, 15, 16})); + + assert(std::ranges::all_of(out, &TracedCopy::copiedOnce)); + } + + // range overload + { + std::array out; + auto result = std::ranges::set_difference(r1, r2, out.data()); + + assert(result.in == r1.end()); + assert(result.out == out.end()); + assert(std::ranges::equal(out, std::array{5, 15, 16})); + + assert(std::ranges::all_of(out, &TracedCopy::copiedOnce)); + } + } + + struct IntAndOrder { + int data; + int order; + + constexpr auto operator==(const IntAndOrder& o) const { return data == o.data; } + constexpr auto operator<=>(const IntAndOrder& o) const { return data <=> o.data; } + }; + + // equal elements should be copied in the original order and only m-n elements are copied + { + std::array r1{{{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}}}; + std::array r2{{{0, 1}, {0, 2}, {0, 3}}}; + + // iterator overload + { + std::array out; + std::ranges::set_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data()); + + assert(std::ranges::equal(out, std::array{0, 0}, {}, &IntAndOrder::data)); + // m-n elements are copied in order + assert(std::ranges::equal(out, std::array{3, 4}, {}, &IntAndOrder::order)); + } + + // range overload + { + std::array out; + std::ranges::set_difference(r1, r2, out.data()); + + assert(std::ranges::equal(out, std::array{0, 0}, {}, &IntAndOrder::data)); + // ID should be in their original order + assert(std::ranges::equal(out, std::array{3, 4}, {}, &IntAndOrder::order)); + } + } + + struct Data { + int data; + + constexpr bool smallerThan(const Data& o) const { return data < o.data; } + }; + + // Test custom comparator + { + std::array r1{Data{4}, Data{8}, Data{12}}; + std::array r2{Data{8}, Data{9}}; + using Iter1 = std::array::iterator; + + // iterator overload + { + std::array out; + std::same_as> decltype(auto) result = std::ranges::set_difference( + r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), [](const Data& x, const Data& y) { + return x.data < y.data; + }); + + assert(std::ranges::equal(out, std::array{4, 12}, {}, &Data::data)); + + assert(result.in == r1.end()); + assert(result.out == out.end()); + } + + // range overload + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::set_difference(r1, r2, out.data(), [](const Data& x, const Data& y) { return x.data < y.data; }); + + assert(std::ranges::equal(out, std::array{4, 12}, {}, &Data::data)); + + assert(result.in == r1.end()); + assert(result.out == out.end()); + } + + // member pointer Comparator iterator overload + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::set_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), &Data::smallerThan); + + assert(std::ranges::equal(out, std::array{4, 12}, {}, &Data::data)); + + assert(result.in == r1.end()); + assert(result.out == out.end()); + } + + // member pointer Comparator range overload + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::set_difference(r1, r2, out.data(), &Data::smallerThan); + + assert(std::ranges::equal(out, std::array{4, 12}, {}, &Data::data)); + + assert(result.in == r1.end()); + assert(result.out == out.end()); + } + } + + // Test Projection + { + std::array r1{Data{1}, Data{3}, Data{5}}; + std::array r2{Data{2}, Data{3}, Data{4}}; + using Iter1 = std::array::iterator; + + const auto proj = [](const Data& d) { return d.data; }; + + // iterator overload + { + std::array out; + std::same_as> decltype(auto) result = std::ranges::set_difference( + r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), std::ranges::less{}, proj, proj); + + assert(std::ranges::equal(out, std::array{1, 5}, {}, &Data::data)); + + assert(result.in == r1.end()); + assert(result.out == out.end()); + } + + // range overload + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::set_difference(r1, r2, out.data(), std::ranges::less{}, proj, proj); + + assert(std::ranges::equal(out, std::array{1, 5}, {}, &Data::data)); + + assert(result.in == r1.end()); + assert(result.out == out.end()); + } + + // member pointer Projection iterator overload + { + std::array out; + std::same_as> decltype(auto) result = std::ranges::set_difference( + r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), {}, &Data::data, &Data::data); + + assert(std::ranges::equal(out, std::array{1, 5}, {}, &Data::data)); + + assert(result.in == r1.end()); + assert(result.out == out.end()); + } + + // member pointer Projection range overload + { + std::array out; + std::same_as> decltype(auto) result = + std::ranges::set_difference(r1, r2, out.data(), std::ranges::less{}, &Data::data, &Data::data); + + assert(std::ranges::equal(out, std::array{1, 5}, {}, &Data::data)); + + assert(result.in == r1.end()); + assert(result.out == out.end()); + } + } + + // Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons and applications of each projection. + { + std::array r1{{{4}, {8}, {12}}}; + std::array r2{{{1}, {2}, {3}, {5}, {6}, {7}, {9}, {10}, {11}}}; + std::array expected{4, 8, 12}; + + const std::size_t maxOperation = 2 * (r1.size() + r2.size()) - 1; + + // iterator overload + { + std::array out; + std::size_t numberOfComp = 0; + std::size_t numberOfProj1 = 0; + std::size_t numberOfProj2 = 0; + + const auto comp = [&numberOfComp](int x, int y) { + ++numberOfComp; + return x < y; + }; + + const auto proj1 = [&numberOfProj1](const Data& d) { + ++numberOfProj1; + return d.data; + }; + + const auto proj2 = [&numberOfProj2](const Data& d) { + ++numberOfProj2; + return d.data; + }; + + std::ranges::set_difference(r1.begin(), r1.end(), r2.begin(), r2.end(), out.data(), comp, proj1, proj2); + + assert(std::ranges::equal(out, expected, {}, &Data::data)); + assert(numberOfComp < maxOperation); + assert(numberOfProj1 < maxOperation); + assert(numberOfProj2 < maxOperation); + } + + // range overload + { + std::array out; + std::size_t numberOfComp = 0; + std::size_t numberOfProj1 = 0; + std::size_t numberOfProj2 = 0; + + const auto comp = [&numberOfComp](int x, int y) { + ++numberOfComp; + return x < y; + }; + + const auto proj1 = [&numberOfProj1](const Data& d) { + ++numberOfProj1; + return d.data; + }; + + const auto proj2 = [&numberOfProj2](const Data& d) { + ++numberOfProj2; + return d.data; + }; + + std::ranges::set_difference(r1, r2, out.data(), comp, proj1, proj2); + + assert(std::ranges::equal(out, expected, {}, &Data::data)); + assert(numberOfComp < maxOperation); + assert(numberOfProj1 < maxOperation); + assert(numberOfProj2 < maxOperation); + } + } + + // Comparator convertible to bool + { + struct ConvertibleToBool { + bool b; + constexpr operator bool() const { return b; } + }; + Data r1[] = {{2}, {4}}; + Data r2[] = {{3}, {4}, {5}}; + + const auto comp = [](const Data& x, const Data& y) { return ConvertibleToBool{x.data < y.data}; }; + + // iterator overload + { + std::array out; + std::ranges::set_difference(r1, r1 + 2, r2, r2 + 3, out.data(), comp); + assert(std::ranges::equal(out, std::array{2}, {}, &Data::data)); + } + + // range overload + { + std::array out; + std::ranges::set_difference(r1, r2, out.data(), comp); + assert(std::ranges::equal(out, std::array{2}, {}, &Data::data)); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + runAllIteratorPermutationsTests(); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.sorting/sortable_helpers.h b/libcxx/test/std/algorithms/alg.sorting/sortable_helpers.h --- a/libcxx/test/std/algorithms/alg.sorting/sortable_helpers.h +++ b/libcxx/test/std/algorithms/alg.sorting/sortable_helpers.h @@ -13,6 +13,10 @@ #include "test_macros.h" +#if TEST_STD_VER > 17 +#include +#endif + struct TrivialSortable { int value; TEST_CONSTEXPR TrivialSortable() : value(0) {} @@ -75,4 +79,29 @@ static_assert(!std::is_trivially_copyable::value, ""); static_assert(!std::is_trivially_copyable::value, ""); +#if TEST_STD_VER > 17 +struct TracedCopy { + int copied = 0; + int data = 0; + + constexpr TracedCopy() = default; + constexpr TracedCopy(int i) : data(i) {} + constexpr TracedCopy(const TracedCopy& other) : copied(other.copied + 1), data(other.data) {} + + constexpr TracedCopy(TracedCopy&& other) = delete; + constexpr TracedCopy& operator=(TracedCopy&& other) = delete; + + constexpr TracedCopy& operator=(const TracedCopy& other) { + copied = other.copied + 1; + data = other.data; + return *this; + } + + constexpr bool copiedOnce() const { return copied == 1; } + + constexpr bool operator==(const TracedCopy& o) const { return data == o.data; } + constexpr auto operator<=>(const TracedCopy& o) const { return data <=> o.data; } +}; +#endif // TEST_STD_VER > 17 + #endif // SORTABLE_HELPERS_H diff --git a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp --- a/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp +++ b/libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp @@ -132,7 +132,7 @@ //static_assert(test(std::ranges::sample, a, a, 5)); //static_assert(test(std::ranges::search, a, a)); //static_assert(test(std::ranges::search_n, a, 10, 42)); -//static_assert(test(std::ranges::set_difference, a, a, a)); +static_assert(test(std::ranges::set_difference, a, a, a)); //static_assert(test(std::ranges::set_intersection, a, a, a)); //static_assert(test(std::ranges::set_symmetric_difference, a, a, a)); //static_assert(test(std::ranges::set_union, a, a, a));