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 @@ -10,7 +10,7 @@ Search,mismatch,Nikolas Klauser,`D117817 `_,✅ Search,equal,Nikolas Klauser,`D123681 `_,✅ Search,lexicographical_compare,Nikolas Klauser,`D127130 `_,✅ -Search,partition_point,Konstantin Varlamov,n/a,In progress +Search,partition_point,Konstantin Varlamov,`D130070 `_,✅ Search,lower_bound,Nikolas Klauser,`D121964 `_,✅ Search,upper_bound,Nikolas Klauser,`D121964 `_,✅ Search,equal_range,Christopher Di Bella,n/a,Not started @@ -58,7 +58,7 @@ Write,rotate_copy,Nikolas Klauser,`D127211 `_,✅ Write,sample,Not assigned,n/a,Not started Write,unique_copy,Not assigned,n/a,Not started -Write,partition_copy,Konstantin Varlamov,n/a,In progress +Write,partition_copy,Konstantin Varlamov,`D130070 `_,✅ Write,partial_sort_copy,Not assigned,n/a,Not started Merge,merge,Hui Xie,`D128611 `_,✅ Merge,set_difference,Hui Xie,`D128983 `_,✅ diff --git a/libcxx/include/__algorithm/ranges_partition_copy.h b/libcxx/include/__algorithm/ranges_partition_copy.h --- a/libcxx/include/__algorithm/ranges_partition_copy.h +++ b/libcxx/include/__algorithm/ranges_partition_copy.h @@ -10,19 +10,15 @@ #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) @@ -42,6 +38,26 @@ struct __fn { + // TODO(ranges): delegate to the classic algorithm. + template + _LIBCPP_HIDE_FROM_ABI constexpr + static partition_copy_result<_InIter, _OutIter1, _OutIter2> __partition_copy_fn_impl( + _InIter&& __first, _Sent&& __last, _OutIter1&& __out_true, _OutIter2&& __out_false, + _Pred& __pred, _Proj& __proj) { + for (; __first != __last; ++__first) { + if (std::invoke(__pred, std::invoke(__proj, *__first))) { + *__out_true = *__first; + ++__out_true; + + } else { + *__out_false = *__first; + ++__out_false; + } + } + + return {std::move(__first), std::move(__out_true), std::move(__out_false)}; + } + template _Sent, weakly_incrementable _OutIter1, weakly_incrementable _OutIter2, class _Proj = identity, indirect_unary_predicate> _Pred> @@ -50,9 +66,8 @@ 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 {}; + return __partition_copy_fn_impl( + std::move(__first), std::move(__last), std::move(__out_true), std::move(__out_false), __pred, __proj); } template , _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 {}; + return __partition_copy_fn_impl( + ranges::begin(__range), ranges::end(__range), std::move(__out_true), std::move(__out_false), __pred, __proj); } }; diff --git a/libcxx/include/__algorithm/ranges_partition_point.h b/libcxx/include/__algorithm/ranges_partition_point.h --- a/libcxx/include/__algorithm/ranges_partition_point.h +++ b/libcxx/include/__algorithm/ranges_partition_point.h @@ -9,19 +9,18 @@ #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 <__algorithm/half_positive.h> #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> -#include <__functional/ranges_operations.h> #include <__iterator/concepts.h> +#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.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) @@ -37,22 +36,40 @@ struct __fn { + // TODO(ranges): delegate to the classic algorithm. + template + _LIBCPP_HIDE_FROM_ABI constexpr + static _Iter __partition_point_fn_impl(_Iter&& __first, _Sent&& __last, _Pred& __pred, _Proj& __proj) { + auto __len = ranges::distance(__first, __last); + + while (__len != 0) { + auto __half_len = std::__half_positive(__len); + auto __mid = ranges::next(__first, __half_len); + + if (std::invoke(__pred, std::invoke(__proj, *__mid))) { + __first = ++__mid; + __len -= __half_len + 1; + + } else { + __len = __half_len; + } + } + + return __first; + } + template _Sent, class _Proj = identity, indirect_unary_predicate> _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 {}; + return __partition_point_fn_impl(std::move(__first), std::move(__last), __pred, __proj); } template , _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 {}; + return __partition_point_fn_impl(ranges::begin(__range), ranges::end(__range), __pred, __proj); } }; diff --git a/libcxx/include/algorithm b/libcxx/include/algorithm --- a/libcxx/include/algorithm +++ b/libcxx/include/algorithm @@ -570,6 +570,34 @@ constexpr ranges::move_result, O> ranges::move(R&& r, O result); // since C++20 + template + using partition_copy_result = in_out_out_result; // since C++20 + + template S, + weakly_incrementable O1, weakly_incrementable O2, + class Proj = identity, indirect_unary_predicate> Pred> + requires indirectly_copyable && indirectly_copyable + constexpr partition_copy_result + partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred, + Proj proj = {}); // Since C++20 + + template, Proj>> Pred> + requires indirectly_copyable, O1> && + indirectly_copyable, O2> + constexpr partition_copy_result, O1, O2> + partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {}); // Since C++20 + + template S, class Proj = identity, + indirect_unary_predicate> Pred> + constexpr I partition_point(I first, S last, Pred pred, Proj proj = {}); // Since C++20 + + template, Proj>> Pred> + constexpr borrowed_iterator_t + partition_point(R&& r, Pred pred, Proj proj = {}); // Since C++20 + template using merge_result = in_in_out_result; // since C++20 @@ -1519,6 +1547,8 @@ #include <__algorithm/ranges_none_of.h> #include <__algorithm/ranges_nth_element.h> #include <__algorithm/ranges_partition.h> +#include <__algorithm/ranges_partition_copy.h> +#include <__algorithm/ranges_partition_point.h> #include <__algorithm/ranges_pop_heap.h> #include <__algorithm/ranges_push_heap.h> #include <__algorithm/ranges_remove.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 @@ -177,10 +177,10 @@ //(void)std::ranges::partial_sort_copy(a, b, Less(&copies)); assert(copies == 0); (void)std::ranges::partition(first, last, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::partition(a, UnaryTrue(&copies)); assert(copies == 0); - //(void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(&copies)); assert(copies == 0); - //(void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(&copies)); assert(copies == 0); - //(void)std::ranges::partition_point(first, last, UnaryTrue(&copies)); assert(copies == 0); - //(void)std::ranges::partition_point(a, UnaryTrue(&copies)); assert(copies == 0); + (void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(&copies)); assert(copies == 0); + (void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(&copies)); assert(copies == 0); + (void)std::ranges::partition_point(first, last, UnaryTrue(&copies)); assert(copies == 0); + (void)std::ranges::partition_point(a, UnaryTrue(&copies)); assert(copies == 0); (void)std::ranges::pop_heap(first, last, Less(&copies)); assert(copies == 0); (void)std::ranges::pop_heap(a, Less(&copies)); assert(copies == 0); //(void)std::ranges::prev_permutation(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 @@ -160,10 +160,10 @@ //(void)std::ranges::partial_sort_copy(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0); (void)std::ranges::partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::partition_point(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); - //(void)std::ranges::partition_point(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::partition_point(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); + (void)std::ranges::partition_point(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); (void)std::ranges::pop_heap(first, last, Less(), Proj(&copies)); assert(copies == 0); (void)std::ranges::pop_heap(a, Less(), Proj(&copies)); assert(copies == 0); //(void)std::ranges::prev_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0); diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition.pass.cpp @@ -72,7 +72,7 @@ // !forward_range static_assert(!HasPartitionRange); -static_assert(!HasPartitionRange); +static_assert(!HasPartitionRange); // !indirect_unary_predicate, Proj>> Pred> static_assert(!HasPartitionRange, IndirectUnaryPredicateNotPredicate>); @@ -147,6 +147,10 @@ test_one({4, 6, 8, 1, 3, 5}, is_odd, 3); // Repeating pattern. test_one({1, 2, 1, 2, 1, 2}, is_odd, 3); + + auto is_negative = [](int x) { return x < 0; }; + // Different comparator. + test_one({-3, 5, 7, -6, 2}, is_negative, 2); } template diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp @@ -32,16 +32,270 @@ #include #include #include +#include #include "almost_satisfies_types.h" +#include "counting_predicates.h" +#include "counting_projection.h" #include "test_iterators.h" -// TODO: SFINAE tests. +struct UnaryPred { bool operator()(int) const; }; + +// Test constraints of the (iterator, sentinel) overload. +// ====================================================== + +template +concept HasPartitionCopyIter = + requires(InIter&& input, Sent&& sent, Output1&& output1, Output2&& output2, Pred&& pred) { + std::ranges::partition_copy(std::forward(input), std::forward(sent), + std::forward(output1), std::forward(output2), std::forward(pred)); + }; + +static_assert(HasPartitionCopyIter); + +// !input_iterator +static_assert(!HasPartitionCopyIter); +static_assert(!HasPartitionCopyIter); +static_assert(!HasPartitionCopyIter); + +// !sentinel_for +static_assert(!HasPartitionCopyIter); +static_assert(!HasPartitionCopyIter); + +// !weakly_incrementable +static_assert(!HasPartitionCopyIter); + +// !weakly_incrementable +static_assert(!HasPartitionCopyIter); + +// !indirect_unary_predicate> +static_assert(!HasPartitionCopyIter); +static_assert(!HasPartitionCopyIter); + +struct Uncopyable { + Uncopyable(int&&); + Uncopyable(const int&) = delete; +}; +// !indirectly_copyable +static_assert(!HasPartitionCopyIter); +// !indirectly_copyable +static_assert(!HasPartitionCopyIter); + +// Test constraints of the (range) overload. +// ========================================= + +template +concept HasPartitionCopyRange = + requires(InputRange&& input, Output1&& output1, Output2&& output2, Pred&& pred) { + std::ranges::partition_copy(std::forward(input), + std::forward(output1), std::forward(output2), std::forward(pred)); + }; + +template +using R = UncheckedRange; + +static_assert(HasPartitionCopyRange, int*, int*, UnaryPred>); + +// !input_iterator +static_assert(!HasPartitionCopyRange); +static_assert(!HasPartitionCopyRange); +static_assert(!HasPartitionCopyRange); + +// !weakly_incrementable +static_assert(!HasPartitionCopyRange, WeaklyIncrementableNotMovable>); + +// !weakly_incrementable +static_assert(!HasPartitionCopyRange, int*, WeaklyIncrementableNotMovable>); + +// !indirect_unary_predicate> +static_assert(!HasPartitionCopyRange, int*, int*, IndirectUnaryPredicateNotPredicate>); +static_assert(!HasPartitionCopyRange, int*, int*, IndirectUnaryPredicateNotCopyConstructible>); + +// !indirectly_copyable +static_assert(!HasPartitionCopyRange, Uncopyable*>); +// !indirectly_copyable +static_assert(!HasPartitionCopyRange, int*, Uncopyable*>); + +static_assert(std::is_same_v, + std::ranges::in_out_out_result>); + +template +constexpr void test_one(std::array input, Pred pred, std::array expected_true, + std::array expected_false) { + static_assert(N2 + N3 == N1); + using ResultT = std::ranges::partition_copy_result; + + auto begin = input.data(); + auto end = input.data() + input.size(); + auto neg_pred = [&](int x) { return !pred(x); }; + + { // (iterator, sentinel) overload. + std::array out1; // Allocate a bigger size in case of buffer overflow. + std::array out2; + + std::same_as decltype(auto) result = std::ranges::partition_copy( + Iter(begin), Sent(Iter(end)), OutIter1(out1.begin()), OutIter2(out2.begin()), pred); + + assert(base(result.in) == input.data() + input.size()); + assert(base(result.out1) == out1.data() + expected_true.size()); + assert(base(result.out2) == out2.data() + expected_false.size()); + + assert(std::ranges::all_of(out1.begin(), base(result.out1), pred)); + assert(std::ranges::all_of(out2.begin(), base(result.out2), neg_pred)); + } + + { // (range) overload. + std::ranges::subrange range{Iter(begin), Sent(Iter(end))}; + std::array out1; // Allocate a bigger size in case of buffer overflow. + std::array out2; + + std::same_as decltype(auto) result = std::ranges::partition_copy( + range, OutIter1(out1.begin()), OutIter2(out2.begin()), pred); + + assert(base(result.in) == input.data() + input.size()); + assert(base(result.out1) == out1.data() + expected_true.size()); + assert(base(result.out2) == out2.data() + expected_false.size()); + + assert(std::ranges::all_of(out1.begin(), base(result.out1), pred)); + assert(std::ranges::all_of(out2.begin(), base(result.out2), neg_pred)); + } +} + +template +constexpr void test_iterators_in_sent_out1_out2() { + auto is_odd = [](int x) { return x % 2 != 0; }; + + // Empty sequence. + test_one({}, is_odd, {}, {}); + // 1-element sequence, the element satisfies the predicate. + test_one({1}, is_odd, {1}, {}); + // 1-element sequence, the element doesn't satisfy the predicate. + test_one({2}, is_odd, {}, {1}); + // 2-element sequence, not in order. + test_one({2, 1}, is_odd, {1}, {2}); + // 2-element sequence, already in order. + test_one({1, 2}, is_odd, {1}, {2}); + // 3-element sequence. + test_one({2, 1, 3}, is_odd, {1, 3}, {2}); + // Longer sequence. + test_one({2, 1, 3, 6, 8, 4, 11, 5}, is_odd, {1, 3, 11, 5}, {2, 6, 8, 4}); + // Longer sequence with duplicates. + test_one({2, 1, 3, 6, 2, 8, 1, 6}, is_odd, {1, 3, 1}, {2, 6, 2, 8, 6}); + // All elements are the same and satisfy the predicate. + test_one({1, 1, 1}, is_odd, {1, 1, 1}, {}); + // All elements are the same and don't satisfy the predicate. + test_one({2, 2, 2}, is_odd, {}, {2, 2, 2}); + // Already partitioned. + test_one({1, 3, 5, 4, 6, 8}, is_odd, {1, 3, 5}, {4, 6, 8}); + // Reverse-partitioned. + test_one({4, 6, 8, 1, 3, 5}, is_odd, {1, 3, 5}, {4, 6, 8}); + // Repeating pattern. + test_one({1, 2, 1, 2, 1, 2}, is_odd, {1, 1, 1}, {2, 2, 2}); + + auto is_negative = [](int x) { return x < 0; }; + // Different comparator. + test_one({-3, 5, 7, -6, 2}, is_negative, {-3, -6}, {5, 7, 2}); +} + +template +constexpr void test_iterators_in_sent_out1() { + test_iterators_in_sent_out1_out2>(); + test_iterators_in_sent_out1_out2>(); + test_iterators_in_sent_out1_out2>(); + test_iterators_in_sent_out1_out2(); +} + +template +constexpr void test_iterators_in_sent() { + test_iterators_in_sent_out1>(); + test_iterators_in_sent_out1>(); + test_iterators_in_sent_out1>(); + test_iterators_in_sent_out1(); +} + +template +constexpr void test_iterators_in() { + if constexpr (std::sentinel_for) { + test_iterators_in_sent(); + } + test_iterators_in_sent>(); +} + +constexpr void test_iterators() { + // Note: deliberately testing with only the weakest and "strongest" iterator types to minimize combinatorial + // explosion. + test_iterators_in>(); + test_iterators_in>(); + test_iterators_in(); +} constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. + test_iterators(); + + { // A custom projection works. + const std::array in = {1, 3, 9, -2, -5, -8}; + auto is_negative = [](int x) { return x < 0; }; + auto negate = [](int x) { return -x; }; + const std::array expected_negative = {-2, -5, -8}; + const std::array expected_positive = {1, 3, 9}; + + { // (iterator, sentinel) overload. + { + std::array out1, out2; + std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), is_negative); + assert(out1 == expected_negative); + assert(out2 == expected_positive); + } + { + std::array out1, out2; + std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), is_negative, negate); + assert(out1 == expected_positive); + assert(out2 == expected_negative); + } + } + + { // (range) overload. + { + std::array out1, out2; + std::ranges::partition_copy(in, out1.begin(), out2.begin(), is_negative); + assert(out1 == expected_negative); + assert(out2 == expected_positive); + } + { + std::array out1, out2; + std::ranges::partition_copy(in, out1.begin(), out2.begin(), is_negative, negate); + assert(out1 == expected_positive); + assert(out2 == expected_negative); + } + } + } + + { // Complexity: Exactly `last - first` applications of `pred` and `proj`. + { + const std::array in = {-2, -5, -8, -11, -10, -5, 1, 3, 9, 6, 8, 2, 4, 2}; + auto is_negative = [](int x) { return x < 0; }; + std::array out1; + std::array out2; + + int pred_count = 0, proj_count = 0; + counting_predicate pred(is_negative, pred_count); + counting_projection proj(proj_count); + + { + std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), pred, proj); + assert(pred_count == in.size()); + assert(proj_count == in.size()); + pred_count = proj_count = 0; + } + + { + std::ranges::partition_copy(in, out1.begin(), out2.begin(), pred, proj); + assert(pred_count == in.size()); + assert(proj_count == in.size()); + pred_count = proj_count = 0; + } + } + } return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point.pass.cpp @@ -25,16 +25,152 @@ #include #include #include +#include #include "almost_satisfies_types.h" #include "test_iterators.h" -// TODO: SFINAE tests. +struct UnaryPred { bool operator()(int) const; }; + +// Test constraints of the (iterator, sentinel) overload. +// ====================================================== + +template +concept HasPartitionPointIter = + requires(Iter&& iter, Sent&& sent, Pred&& pred) { + std::ranges::partition_point(std::forward(iter), std::forward(sent), std::forward(pred)); + }; + +static_assert(HasPartitionPointIter); + +// !forward_iterator +static_assert(!HasPartitionPointIter); +static_assert(!HasPartitionPointIter); + +// !sentinel_for +static_assert(!HasPartitionPointIter); +static_assert(!HasPartitionPointIter); + +// !indirect_unary_predicate> +static_assert(!HasPartitionPointIter); +static_assert(!HasPartitionPointIter); + +// Test constraints of the (range) overload. +// ========================================= + +template +concept HasPartitionPointRange = + requires(Range&& range, Pred&& pred) { + std::ranges::partition_point(std::forward(range), std::forward(pred)); + }; + +template +using R = UncheckedRange; + +static_assert(HasPartitionPointRange, UnaryPred>); + +// !forward_range +static_assert(!HasPartitionPointRange); +static_assert(!HasPartitionPointRange); + +// !indirect_unary_predicate, Proj>> Pred> +static_assert(!HasPartitionPointRange, IndirectUnaryPredicateNotPredicate>); +static_assert(!HasPartitionPointRange, IndirectUnaryPredicateNotCopyConstructible>); + +template +constexpr void test_one(std::array input, Pred pred, size_t partition_point) { + assert(std::ranges::is_partitioned(input, pred)); + + auto begin = Iter(input.data()); + auto end = Sent(Iter(input.data() + input.size())); + auto neg_pred = [&](int x) { return !pred(x); }; + + { // (iterator, sentinel) overload. + std::same_as decltype(auto) result = std::ranges::partition_point(begin, end, pred); + + assert(base(result) == input.data() + partition_point); + assert(std::ranges::all_of(begin, result, pred)); + assert(std::ranges::all_of(result, end, neg_pred)); + } + + { // (range) overload. + auto range = std::ranges::subrange(begin, end); + std::same_as decltype(auto) result = std::ranges::partition_point(range, pred); + + assert(base(result) == input.data() + partition_point); + assert(std::ranges::all_of(begin, result, pred)); + assert(std::ranges::all_of(result, end, neg_pred)); + } +} + +template +constexpr void test_iterators_2() { + auto is_odd = [](int x) { return x % 2 != 0; }; + + // Empty sequence. + test_one({}, is_odd, 0); + // 1-element sequence, the element satisfies the predicate. + test_one({1}, is_odd, 1); + // 1-element sequence, the element doesn't satisfy the predicate. + test_one({2}, is_odd, 0); + // 2-element sequence. + test_one({1, 2}, is_odd, 1); + // 3-element sequence. + test_one({3, 1, 2}, is_odd, 2); + // Longer sequence. + test_one({1, 3, 11, 5, 6, 2, 8, 4}, is_odd, 4); + // Longer sequence with duplicates. + test_one({1, 3, 3, 4, 6, 2, 8, 2}, is_odd, 3); + // All elements are the same and satisfy the predicate. + test_one({1, 1, 1}, is_odd, 3); + // All elements are the same and don't satisfy the predicate. + test_one({2, 2, 2}, is_odd, 0); + // All non-satisfying and all satisfying elements are the same. + test_one({1, 1, 1, 2, 2, 2}, is_odd, 3); + + auto is_negative = [](int x) { return x < 0; }; + // Different comparator. + test_one({-3, -6, 5, 7, 2}, is_negative, 2); +} + +template +constexpr void test_iterators_1() { + test_iterators_2(); + test_iterators_2>(); +} + +constexpr void test_iterators() { + test_iterators_1>(); + test_iterators_1>(); + test_iterators_1>(); + test_iterators_1>(); + test_iterators_1(); +} constexpr bool test() { - // TODO: main tests. - // TODO: A custom comparator works. - // TODO: A custom projection works. + test_iterators(); + + { // A custom projection works. + const std::array in = {1, 3, 4, 6, 8}; + auto is_odd = [](int x) { return x % 2 != 0; }; + auto x2 = [](int x) { return x * 2; }; + auto expected_no_proj = in.begin() + 2; + auto expected_with_proj = in.begin(); + + { // (iterator, sentinel) overload. + auto result_no_proj = std::ranges::partition_point(in.begin(), in.end(), is_odd); + assert(result_no_proj == expected_no_proj); + auto result_with_proj = std::ranges::partition_point(in.begin(), in.end(), is_odd, x2); + assert(result_with_proj == expected_with_proj); + } + + { // (range) overload. + auto result_no_proj = std::ranges::partition_point(in, is_odd); + assert(result_no_proj == expected_no_proj); + auto result_with_proj = std::ranges::partition_point(in, is_odd, x2); + assert(result_with_proj == expected_with_proj); + } + } return true; } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_stable_partition.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_stable_partition.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_stable_partition.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_stable_partition.pass.cpp @@ -151,6 +151,10 @@ test_one({4, 6, 8, 1, 3, 5}, is_odd, 3, {1, 3, 5, 4, 6, 8}); // Repeating pattern. test_one({1, 2, 1, 2, 1, 2}, is_odd, 3, {1, 1, 1, 2, 2, 2}); + + auto is_negative = [](int x) { return x < 0; }; + // Different comparator. + test_one({-3, 5, 7, -6, 2}, is_negative, 2, {-3, -6, 5, 7, 2}); } template diff --git a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp --- a/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_result_alias_declarations.compile.pass.cpp @@ -47,11 +47,11 @@ static_assert(std::is_same_v, binary_transform_result>); static_assert(std::is_same_v, merge_result>); -// static_assert(std::is_same_v, set_symmetric_difference_result>); -// static_assert(std::is_same_v, set_union_result>); -// static_assert(std::is_same_v, set_intersection_result>); +static_assert(std::is_same_v, set_symmetric_difference_result>); +static_assert(std::is_same_v, set_union_result>); +static_assert(std::is_same_v, set_intersection_result>); -// static_assert(std::is_same_v, partition_copy_result>); +static_assert(std::is_same_v, partition_copy_result>); static_assert(std::is_same_v, minmax_result>); static_assert(std::is_same_v, minmax_element_result>); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp @@ -84,7 +84,7 @@ std::array output = {4, 5, 6}; auto out = output.begin(); - //auto out2 = output.begin() + 1; + auto out2 = output.begin() + 1; int x = 2; int count = 1; @@ -99,7 +99,7 @@ in2_pred(std::ranges::mismatch, in, in2, binary_pred); in2_pred(std::ranges::equal, in, in2, binary_pred); in2_pred(std::ranges::lexicographical_compare, in, in2, binary_pred); - //in_pred(std::ranges::partition_point, unary_pred); + in_pred(std::ranges::partition_point, in, unary_pred); in_val_pred(std::ranges::lower_bound, in, x, binary_pred); in_val_pred(std::ranges::upper_bound, in, x, binary_pred); //in_val_pred(std::ranges::equal_range, in, x, binary_pred); @@ -146,8 +146,8 @@ //in_out_pred(std::ranges::unique_copy, in, out, binary_pred); // partition_copy - //std::ranges::partition_copy(in.begin(), in.end(), out, out2, unary_pred); - //std::ranges::partition_copy(in, out, out2, unary_pred); + std::ranges::partition_copy(in.begin(), in.end(), out, out2, unary_pred); + std::ranges::partition_copy(in, out, out2, unary_pred); //in2_pred(std::ranges::partial_sort_copy, in, in2, binary_pred); in2_out_pred(std::ranges::merge, in, in2, out, binary_pred); in2_out_pred(std::ranges::set_difference, in, in2, out, binary_pred); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp @@ -92,7 +92,7 @@ std::array output = {Bar{Foo{4}}, Bar{Foo{5}}, Bar{Foo{6}}}; auto out = output.begin(); - //auto out2 = output.begin() + 1; + auto out2 = output.begin() + 1; Bar a{Foo{1}}; Bar b{Foo{2}}; @@ -112,7 +112,7 @@ in2_pred(std::ranges::mismatch, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); in2_pred(std::ranges::equal, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); in2_pred(std::ranges::lexicographical_compare, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val); - //in_pred(std::ranges::partition_point, in, &Foo::unary_pred, &Bar::val); + in_pred(std::ranges::partition_point, in, &Foo::unary_pred, &Bar::val); in_val_pred(std::ranges::lower_bound, in, x, &Foo::binary_pred, &Bar::val); in_val_pred(std::ranges::upper_bound, in, x, &Foo::binary_pred, &Bar::val); //in_val_pred(std::ranges::equal_range, in, x, &Foo::binary_pred, &Bar::val); @@ -187,8 +187,8 @@ // `sample` has no requirement that the given generator be invoked via `std::invoke`. //in_out_pred(std::ranges::unique_copy, in, out, &Foo::binary_pred, &Bar::val); // partition_copy - //std::ranges::partition_copy(in.begin(), in.end(), out, out2, &Foo::unary_pred, &Bar::val); - //std::ranges::partition_copy(in, out, out2, &Foo::unary_pred, &Bar::val); + std::ranges::partition_copy(in.begin(), in.end(), out, out2, &Foo::unary_pred, &Bar::val); + std::ranges::partition_copy(in, out, out2, &Foo::unary_pred, &Bar::val); //in2_pred(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val); in2_out_pred(std::ranges::merge, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val); in2_out_pred(std::ranges::set_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val); diff --git a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp --- a/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp +++ b/libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp @@ -56,7 +56,7 @@ std::array output = {T{4}, T{5}, T{6}, T{7}, T{8}, T{9}}; ProxyIterator out{output.begin()}; - //auto out2 = output.begin() + 1; + ProxyIterator out2{output.begin() + 1}; T num{2}; Proxy x{num}; @@ -79,7 +79,7 @@ test(std::ranges::mismatch, in, in2); test(std::ranges::equal, in, in2); test(std::ranges::lexicographical_compare, in, in2); - //test(std::ranges::partition_point, unary_pred); + test(std::ranges::partition_point, in, unary_pred); test(std::ranges::lower_bound, in, x); test(std::ranges::upper_bound, in, x); //test(std::ranges::equal_range, in, x); @@ -133,7 +133,7 @@ test(std::ranges::reverse_copy, in, out); test_mid(std::ranges::rotate_copy, in, mid, out); //test(std::ranges::unique_copy, in, out); - //test(std::ranges::partition_copy, in, out, out2, unary_pred); + test(std::ranges::partition_copy, in, out, out2, unary_pred); //test_mid(std::ranges::partial_sort_copy, in, in2); test(std::ranges::merge, in, in2, out); test(std::ranges::set_difference, in, in2, out); 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 @@ -113,8 +113,8 @@ //static_assert(test(std::ranges::partial_sort, a, a+5)); //static_assert(test(std::ranges::partial_sort_copy, a, a)); static_assert(test(std::ranges::partition, a, odd)); -//static_assert(test(std::ranges::partition_copy, a, a, a, odd)); -//static_assert(test(std::ranges::partition_point, a, odd)); +static_assert(test(std::ranges::partition_copy, a, a, a, odd)); +static_assert(test(std::ranges::partition_point, a, odd)); static_assert(test(std::ranges::pop_heap, a)); //static_assert(test(std::ranges::prev_permutation, a)); static_assert(test(std::ranges::push_heap, a)); diff --git a/libcxx/test/support/counting_predicates.h b/libcxx/test/support/counting_predicates.h --- a/libcxx/test/support/counting_predicates.h +++ b/libcxx/test/support/counting_predicates.h @@ -10,6 +10,7 @@ #define TEST_SUPPORT_COUNTING_PREDICATES_H #include +#include template struct unary_counting_predicate { @@ -49,4 +50,27 @@ mutable size_t count_; }; +#if TEST_STD_VER > 14 + +template +class counting_predicate { + Predicate pred_; + int* count_ = nullptr; + +public: + constexpr counting_predicate() = default; + constexpr counting_predicate(Predicate pred, int& count) : pred_(std::move(pred)), count_(&count) {} + + template + constexpr decltype(auto) operator()(Args&& ...args) const { + ++(*count_); + return pred_(std::forward(args)...); + } +}; + +template +counting_predicate(Predicate pred, int& count) -> counting_predicate; + +#endif // TEST_STD_VER > 14 + #endif // TEST_SUPPORT_COUNTING_PREDICATES_H diff --git a/libcxx/test/support/counting_projection.h b/libcxx/test/support/counting_projection.h new file mode 100644 --- /dev/null +++ b/libcxx/test/support/counting_projection.h @@ -0,0 +1,40 @@ +//===----------------------------------------------------------------------===// +// +// 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 TEST_SUPPORT_COUNTING_PROJECTION_H +#define TEST_SUPPORT_COUNTING_PROJECTION_H + +#include +#include + +#if TEST_STD_VER > 14 + +template +class counting_projection { + Proj proj_; + int* count_ = nullptr; + +public: + constexpr counting_projection() = default; + constexpr counting_projection(int& count) : count_(&count) {} + constexpr counting_projection(Proj proj, int& count) : proj_(std::move(proj)), count_(&count) {} + + template + constexpr decltype(auto) operator()(T&& value) const { + ++(*count_); + return proj_(std::forward(value)); + } +}; + +counting_projection(int& count) -> counting_projection; +template +counting_projection(Proj proj, int& count) -> counting_projection; + +#endif // TEST_STD_VER > 14 + +#endif // TEST_SUPPORT_COUNTING_PROJECTION_H