| //===----------------------------------------------------------------------===// |
| // |
| // 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 |
| |
| // <algorithm> |
| |
| // template<input_iterator I, sentinel_for<I> S, |
| // weakly_incrementable O1, weakly_incrementable O2, |
| // class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred> |
| // requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2> |
| // constexpr partition_copy_result<I, O1, O2> |
| // partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred, |
| // Proj proj = {}); // Since C++20 |
| // |
| // template<input_range R, weakly_incrementable O1, weakly_incrementable O2, |
| // class Proj = identity, |
| // indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred> |
| // requires indirectly_copyable<iterator_t<R>, O1> && |
| // indirectly_copyable<iterator_t<R>, O2> |
| // constexpr partition_copy_result<borrowed_iterator_t<R>, O1, O2> |
| // partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {}); // Since C++20 |
| |
| #include <algorithm> |
| #include <array> |
| #include <concepts> |
| #include <functional> |
| #include <ranges> |
| #include <utility> |
| |
| #include "almost_satisfies_types.h" |
| #include "counting_predicates.h" |
| #include "counting_projection.h" |
| #include "test_iterators.h" |
| |
| struct UnaryPred { bool operator()(int) const; }; |
| |
| // Test constraints of the (iterator, sentinel) overload. |
| // ====================================================== |
| |
| template <class InIter = int*, class Sent = int*, class Output1 = int*, class Output2 = int*, class Pred = UnaryPred> |
| concept HasPartitionCopyIter = |
| requires(InIter&& input, Sent&& sent, Output1&& output1, Output2&& output2, Pred&& pred) { |
| std::ranges::partition_copy(std::forward<InIter>(input), std::forward<Sent>(sent), |
| std::forward<Output1>(output1), std::forward<Output2>(output2), std::forward<Pred>(pred)); |
| }; |
| |
| static_assert(HasPartitionCopyIter<int*, int*, int*, int*, UnaryPred>); |
| |
| // !input_iterator<I> |
| static_assert(!HasPartitionCopyIter<InputIteratorNotDerivedFrom>); |
| static_assert(!HasPartitionCopyIter<InputIteratorNotIndirectlyReadable>); |
| static_assert(!HasPartitionCopyIter<InputIteratorNotInputOrOutputIterator>); |
| |
| // !sentinel_for<S, I> |
| static_assert(!HasPartitionCopyIter<int*, SentinelForNotSemiregular>); |
| static_assert(!HasPartitionCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>); |
| |
| // !weakly_incrementable<O1> |
| static_assert(!HasPartitionCopyIter<int*, int*, WeaklyIncrementableNotMovable>); |
| |
| // !weakly_incrementable<O2> |
| static_assert(!HasPartitionCopyIter<int*, int*, int*, WeaklyIncrementableNotMovable>); |
| |
| // !indirect_unary_predicate<projected<I, Proj>> |
| static_assert(!HasPartitionCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotPredicate>); |
| static_assert(!HasPartitionCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>); |
| |
| struct Uncopyable { |
| Uncopyable(int&&); |
| Uncopyable(const int&) = delete; |
| }; |
| // !indirectly_copyable<I, O1> |
| static_assert(!HasPartitionCopyIter<int*, int*, Uncopyable*>); |
| // !indirectly_copyable<I, O2> |
| static_assert(!HasPartitionCopyIter<int*, int*, int*, Uncopyable*>); |
| |
| // Test constraints of the (range) overload. |
| // ========================================= |
| |
| template <class InputRange, class Output1 = int*, class Output2 = int*, class Pred = UnaryPred> |
| concept HasPartitionCopyRange = |
| requires(InputRange&& input, Output1&& output1, Output2&& output2, Pred&& pred) { |
| std::ranges::partition_copy(std::forward<InputRange>(input), |
| std::forward<Output1>(output1), std::forward<Output2>(output2), std::forward<Pred>(pred)); |
| }; |
| |
| template <class T> |
| using R = UncheckedRange<T>; |
| |
| static_assert(HasPartitionCopyRange<R<int*>, int*, int*, UnaryPred>); |
| |
| // !input_iterator<I> |
| static_assert(!HasPartitionCopyRange<InputRangeNotDerivedFrom>); |
| static_assert(!HasPartitionCopyRange<InputRangeNotIndirectlyReadable>); |
| static_assert(!HasPartitionCopyRange<InputRangeNotInputOrOutputIterator>); |
| |
| // !weakly_incrementable<O1> |
| static_assert(!HasPartitionCopyRange<R<int*>, WeaklyIncrementableNotMovable>); |
| |
| // !weakly_incrementable<O2> |
| static_assert(!HasPartitionCopyRange<R<int*>, int*, WeaklyIncrementableNotMovable>); |
| |
| // !indirect_unary_predicate<projected<I, Proj>> |
| static_assert(!HasPartitionCopyRange<R<int*>, int*, int*, IndirectUnaryPredicateNotPredicate>); |
| static_assert(!HasPartitionCopyRange<R<int*>, int*, int*, IndirectUnaryPredicateNotCopyConstructible>); |
| |
| // !indirectly_copyable<I, O1> |
| static_assert(!HasPartitionCopyRange<R<int*>, Uncopyable*>); |
| // !indirectly_copyable<I, O2> |
| static_assert(!HasPartitionCopyRange<R<int*>, int*, Uncopyable*>); |
| |
| static_assert(std::is_same_v<std::ranges::partition_copy_result<int, int, int>, |
| std::ranges::in_out_out_result<int, int, int>>); |
| |
| template <class Iter, class Sent, class OutIter1, class OutIter2, std::size_t N1, size_t N2, size_t N3, class Pred> |
| constexpr void test_one(std::array<int, N1> input, Pred pred, std::array<int, N2> expected_true, |
| std::array<int, N3> expected_false) { |
| static_assert(N2 + N3 == N1); |
| using ResultT = std::ranges::partition_copy_result<Iter, OutIter1, OutIter2>; |
| |
| auto begin = input.data(); |
| auto end = input.data() + input.size(); |
| |
| { // (iterator, sentinel) overload. |
| std::array<int, N2> out1; |
| std::array<int, N3> out2; |
| |
| std::same_as<ResultT> 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::equal(out1, expected_true)); |
| assert(std::ranges::equal(out2, expected_false)); |
| } |
| |
| { // (range) overload. |
| std::ranges::subrange range{Iter(begin), Sent(Iter(end))}; |
| std::array<int, N2> out1; |
| std::array<int, N3> out2; |
| |
| std::same_as<ResultT> 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::equal(out1, expected_true)); |
| assert(std::ranges::equal(out2, expected_false)); |
| } |
| } |
| |
| template <class InIter, class Sent, class Out1, class Out2> |
| constexpr void test_iterators_in_sent_out1_out2() { |
| auto is_odd = [](int x) { return x % 2 != 0; }; |
| |
| // Empty sequence. |
| test_one<InIter, Sent, Out1, Out2, 0, 0, 0>({}, is_odd, {}, {}); |
| // 1-element sequence, the element satisfies the predicate. |
| test_one<InIter, Sent, Out1, Out2, 1, 1, 0>({1}, is_odd, {1}, {}); |
| // 1-element sequence, the element doesn't satisfy the predicate. |
| test_one<InIter, Sent, Out1, Out2, 1, 0, 1>({2}, is_odd, {}, {2}); |
| // 2-element sequence, not in order. |
| test_one<InIter, Sent, Out1, Out2, 2, 1, 1>({2, 1}, is_odd, {1}, {2}); |
| // 2-element sequence, already in order. |
| test_one<InIter, Sent, Out1, Out2, 2, 1, 1>({1, 2}, is_odd, {1}, {2}); |
| // 3-element sequence. |
| test_one<InIter, Sent, Out1, Out2, 3, 2, 1>({2, 1, 3}, is_odd, {1, 3}, {2}); |
| // Longer sequence. |
| test_one<InIter, Sent, Out1, Out2, 8, 4, 4>({2, 1, 3, 6, 8, 4, 11, 5}, is_odd, {1, 3, 11, 5}, {2, 6, 8, 4}); |
| // Longer sequence with duplicates. |
| test_one<InIter, Sent, Out1, Out2, 8, 3, 5>({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<InIter, Sent, Out1, Out2, 3, 3, 0>({1, 1, 1}, is_odd, {1, 1, 1}, {}); |
| // All elements are the same and don't satisfy the predicate. |
| test_one<InIter, Sent, Out1, Out2, 3, 0, 3>({2, 2, 2}, is_odd, {}, {2, 2, 2}); |
| // Already partitioned. |
| test_one<InIter, Sent, Out1, Out2, 6, 3, 3>({1, 3, 5, 4, 6, 8}, is_odd, {1, 3, 5}, {4, 6, 8}); |
| // Reverse-partitioned. |
| test_one<InIter, Sent, Out1, Out2, 6, 3, 3>({4, 6, 8, 1, 3, 5}, is_odd, {1, 3, 5}, {4, 6, 8}); |
| // Repeating pattern. |
| test_one<InIter, Sent, Out1, Out2, 6, 3, 3>({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<InIter, Sent, Out1, Out2, 5, 2, 3>({-3, 5, 7, -6, 2}, is_negative, {-3, -6}, {5, 7, 2}); |
| } |
| |
| template <class InIter, class Sent, class Out1> |
| constexpr void test_iterators_in_sent_out1() { |
| test_iterators_in_sent_out1_out2<InIter, Sent, Out1, cpp20_output_iterator<int*>>(); |
| test_iterators_in_sent_out1_out2<InIter, Sent, Out1, random_access_iterator<int*>>(); |
| test_iterators_in_sent_out1_out2<InIter, Sent, Out1, int*>(); |
| } |
| |
| template <class InIter, class Sent> |
| constexpr void test_iterators_in_sent() { |
| test_iterators_in_sent_out1<InIter, Sent, cpp17_output_iterator<int*>>(); |
| test_iterators_in_sent_out1<InIter, Sent, cpp20_output_iterator<int*>>(); |
| test_iterators_in_sent_out1<InIter, Sent, random_access_iterator<int*>>(); |
| test_iterators_in_sent_out1<InIter, Sent, int*>(); |
| } |
| |
| template <class InIter> |
| constexpr void test_iterators_in() { |
| if constexpr (std::sentinel_for<InIter, InIter>) { |
| test_iterators_in_sent<InIter, InIter>(); |
| } |
| test_iterators_in_sent<InIter, sentinel_wrapper<InIter>>(); |
| } |
| |
| constexpr void test_iterators() { |
| // Note: deliberately testing with only the weakest and "strongest" iterator types to minimize combinatorial |
| // explosion. |
| test_iterators_in<cpp20_input_iterator<int*>>(); |
| test_iterators_in<int*>(); |
| } |
| |
| constexpr bool test() { |
| 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<int, 3> 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<int, 3> 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<int, 3> out1, out2; |
| std::ranges::partition_copy(in, out1.begin(), out2.begin(), is_negative); |
| assert(out1 == expected_negative); |
| assert(out2 == expected_positive); |
| } |
| { |
| std::array<int, 3> 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<int, 6> out1; |
| std::array<int, 8> out2; |
| |
| int pred_count = 0, proj_count = 0; |
| counting_predicate pred(is_negative, pred_count); |
| counting_projection proj(proj_count); |
| auto expected = static_cast<int>(in.size()); |
| |
| { |
| std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), pred, proj); |
| assert(pred_count == expected); |
| assert(proj_count == expected); |
| pred_count = proj_count = 0; |
| } |
| |
| { |
| std::ranges::partition_copy(in, out1.begin(), out2.begin(), pred, proj); |
| assert(pred_count == expected); |
| assert(proj_count == expected); |
| pred_count = proj_count = 0; |
| } |
| } |
| } |
| |
| return true; |
| } |
| |
| int main(int, char**) { |
| test(); |
| static_assert(test()); |
| |
| return 0; |
| } |