1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// UNSUPPORTED: c++03, c++11, c++14, c++17
10
11// <algorithm>
12
13// template<input_iterator I, sentinel_for<I> S,
14// weakly_incrementable O1, weakly_incrementable O2,
15// class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
16// requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2>
17// constexpr partition_copy_result<I, O1, O2>
18// partition_copy(I first, S last, O1 out_true, O2 out_false, Pred pred,
19// Proj proj = {}); // Since C++20
20//
21// template<input_range R, weakly_incrementable O1, weakly_incrementable O2,
22// class Proj = identity,
23// indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
24// requires indirectly_copyable<iterator_t<R>, O1> &&
25// indirectly_copyable<iterator_t<R>, O2>
26// constexpr partition_copy_result<borrowed_iterator_t<R>, O1, O2>
27// partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {}); // Since C++20
28
29#include <algorithm>
30#include <array>
31#include <concepts>
32#include <functional>
33#include <ranges>
34#include <utility>
35
36#include "almost_satisfies_types.h"
37#include "counting_predicates.h"
38#include "counting_projection.h"
39#include "test_iterators.h"
40
41struct UnaryPred { bool operator()(int) const; };
42
43// Test constraints of the (iterator, sentinel) overload.
44// ======================================================
45
46template <class InIter = int*, class Sent = int*, class Output1 = int*, class Output2 = int*, class Pred = UnaryPred>
47concept HasPartitionCopyIter =
48 requires(InIter&& input, Sent&& sent, Output1&& output1, Output2&& output2, Pred&& pred) {
49 std::ranges::partition_copy(std::forward<InIter>(input), std::forward<Sent>(sent),
50 std::forward<Output1>(output1), std::forward<Output2>(output2), std::forward<Pred>(pred));
51 };
52
53static_assert(HasPartitionCopyIter<int*, int*, int*, int*, UnaryPred>);
54
55// !input_iterator<I>
56static_assert(!HasPartitionCopyIter<InputIteratorNotDerivedFrom>);
57static_assert(!HasPartitionCopyIter<InputIteratorNotIndirectlyReadable>);
58static_assert(!HasPartitionCopyIter<InputIteratorNotInputOrOutputIterator>);
59
60// !sentinel_for<S, I>
61static_assert(!HasPartitionCopyIter<int*, SentinelForNotSemiregular>);
62static_assert(!HasPartitionCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
63
64// !weakly_incrementable<O1>
65static_assert(!HasPartitionCopyIter<int*, int*, WeaklyIncrementableNotMovable>);
66
67// !weakly_incrementable<O2>
68static_assert(!HasPartitionCopyIter<int*, int*, int*, WeaklyIncrementableNotMovable>);
69
70// !indirect_unary_predicate<projected<I, Proj>>
71static_assert(!HasPartitionCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotPredicate>);
72static_assert(!HasPartitionCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
73
74struct Uncopyable {
75 Uncopyable(int&&);
76 Uncopyable(const int&) = delete;
77};
78// !indirectly_copyable<I, O1>
79static_assert(!HasPartitionCopyIter<int*, int*, Uncopyable*>);
80// !indirectly_copyable<I, O2>
81static_assert(!HasPartitionCopyIter<int*, int*, int*, Uncopyable*>);
82
83// Test constraints of the (range) overload.
84// =========================================
85
86template <class InputRange, class Output1 = int*, class Output2 = int*, class Pred = UnaryPred>
87concept HasPartitionCopyRange =
88 requires(InputRange&& input, Output1&& output1, Output2&& output2, Pred&& pred) {
89 std::ranges::partition_copy(std::forward<InputRange>(input),
90 std::forward<Output1>(output1), std::forward<Output2>(output2), std::forward<Pred>(pred));
91 };
92
93template <class T>
94using R = UncheckedRange<T>;
95
96static_assert(HasPartitionCopyRange<R<int*>, int*, int*, UnaryPred>);
97
98// !input_iterator<I>
99static_assert(!HasPartitionCopyRange<InputRangeNotDerivedFrom>);
100static_assert(!HasPartitionCopyRange<InputRangeNotIndirectlyReadable>);
101static_assert(!HasPartitionCopyRange<InputRangeNotInputOrOutputIterator>);
102
103// !weakly_incrementable<O1>
104static_assert(!HasPartitionCopyRange<R<int*>, WeaklyIncrementableNotMovable>);
105
106// !weakly_incrementable<O2>
107static_assert(!HasPartitionCopyRange<R<int*>, int*, WeaklyIncrementableNotMovable>);
108
109// !indirect_unary_predicate<projected<I, Proj>>
110static_assert(!HasPartitionCopyRange<R<int*>, int*, int*, IndirectUnaryPredicateNotPredicate>);
111static_assert(!HasPartitionCopyRange<R<int*>, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
112
113// !indirectly_copyable<I, O1>
114static_assert(!HasPartitionCopyRange<R<int*>, Uncopyable*>);
115// !indirectly_copyable<I, O2>
116static_assert(!HasPartitionCopyRange<R<int*>, int*, Uncopyable*>);
117
118static_assert(std::is_same_v<std::ranges::partition_copy_result<int, int, int>,
119 std::ranges::in_out_out_result<int, int, int>>);
120
121template <class Iter, class Sent, class OutIter1, class OutIter2, std::size_t N1, size_t N2, size_t N3, class Pred>
122constexpr void test_one(std::array<int, N1> input, Pred pred, std::array<int, N2> expected_true,
123 std::array<int, N3> expected_false) {
124 static_assert(N2 + N3 == N1);
125 using ResultT = std::ranges::partition_copy_result<Iter, OutIter1, OutIter2>;
126
127 auto begin = input.data();
128 auto end = input.data() + input.size();
129
130 { // (iterator, sentinel) overload.
131 std::array<int, N2> out1;
132 std::array<int, N3> out2;
133
134 std::same_as<ResultT> decltype(auto) result = std::ranges::partition_copy(
135 Iter(begin), Sent(Iter(end)), OutIter1(out1.data()), OutIter2(out2.data()), pred);
136
137 assert(base(result.in) == input.data() + input.size());
138 assert(base(result.out1) == out1.data() + expected_true.size());
139 assert(base(result.out2) == out2.data() + expected_false.size());
140
141 assert(std::ranges::equal(out1, expected_true));
142 assert(std::ranges::equal(out2, expected_false));
143 }
144
145 { // (range) overload.
146 std::ranges::subrange range{Iter(begin), Sent(Iter(end))};
147 std::array<int, N2> out1;
148 std::array<int, N3> out2;
149
150 std::same_as<ResultT> decltype(auto) result = std::ranges::partition_copy(
151 range, OutIter1(out1.data()), OutIter2(out2.data()), pred);
152
153 assert(base(result.in) == input.data() + input.size());
154 assert(base(result.out1) == out1.data() + expected_true.size());
155 assert(base(result.out2) == out2.data() + expected_false.size());
156
157 assert(std::ranges::equal(out1, expected_true));
158 assert(std::ranges::equal(out2, expected_false));
159 }
160}
161
162template <class InIter, class Sent, class Out1, class Out2>
163constexpr void test_iterators_in_sent_out1_out2() {
164 auto is_odd = [](int x) { return x % 2 != 0; };
165
166 // Empty sequence.
167 test_one<InIter, Sent, Out1, Out2, 0, 0, 0>({}, is_odd, {}, {});
168 // 1-element sequence, the element satisfies the predicate.
169 test_one<InIter, Sent, Out1, Out2, 1, 1, 0>({1}, is_odd, {1}, {});
170 // 1-element sequence, the element doesn't satisfy the predicate.
171 test_one<InIter, Sent, Out1, Out2, 1, 0, 1>({2}, is_odd, {}, {2});
172 // 2-element sequence, not in order.
173 test_one<InIter, Sent, Out1, Out2, 2, 1, 1>({2, 1}, is_odd, {1}, {2});
174 // 2-element sequence, already in order.
175 test_one<InIter, Sent, Out1, Out2, 2, 1, 1>({1, 2}, is_odd, {1}, {2});
176 // 3-element sequence.
177 test_one<InIter, Sent, Out1, Out2, 3, 2, 1>({2, 1, 3}, is_odd, {1, 3}, {2});
178 // Longer sequence.
179 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});
180 // Longer sequence with duplicates.
181 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});
182 // All elements are the same and satisfy the predicate.
183 test_one<InIter, Sent, Out1, Out2, 3, 3, 0>({1, 1, 1}, is_odd, {1, 1, 1}, {});
184 // All elements are the same and don't satisfy the predicate.
185 test_one<InIter, Sent, Out1, Out2, 3, 0, 3>({2, 2, 2}, is_odd, {}, {2, 2, 2});
186 // Already partitioned.
187 test_one<InIter, Sent, Out1, Out2, 6, 3, 3>({1, 3, 5, 4, 6, 8}, is_odd, {1, 3, 5}, {4, 6, 8});
188 // Reverse-partitioned.
189 test_one<InIter, Sent, Out1, Out2, 6, 3, 3>({4, 6, 8, 1, 3, 5}, is_odd, {1, 3, 5}, {4, 6, 8});
190 // Repeating pattern.
191 test_one<InIter, Sent, Out1, Out2, 6, 3, 3>({1, 2, 1, 2, 1, 2}, is_odd, {1, 1, 1}, {2, 2, 2});
192
193 auto is_negative = [](int x) { return x < 0; };
194 // Different comparator.
195 test_one<InIter, Sent, Out1, Out2, 5, 2, 3>({-3, 5, 7, -6, 2}, is_negative, {-3, -6}, {5, 7, 2});
196}
197
198template <class InIter, class Sent, class Out1>
199constexpr void test_iterators_in_sent_out1() {
200 test_iterators_in_sent_out1_out2<InIter, Sent, Out1, cpp20_output_iterator<int*>>();
201 test_iterators_in_sent_out1_out2<InIter, Sent, Out1, random_access_iterator<int*>>();
202 test_iterators_in_sent_out1_out2<InIter, Sent, Out1, int*>();
203}
204
205template <class InIter, class Sent>
206constexpr void test_iterators_in_sent() {
207 test_iterators_in_sent_out1<InIter, Sent, cpp17_output_iterator<int*>>();
208 test_iterators_in_sent_out1<InIter, Sent, cpp20_output_iterator<int*>>();
209 test_iterators_in_sent_out1<InIter, Sent, random_access_iterator<int*>>();
210 test_iterators_in_sent_out1<InIter, Sent, int*>();
211}
212
213template <class InIter>
214constexpr void test_iterators_in() {
215 if constexpr (std::sentinel_for<InIter, InIter>) {
216 test_iterators_in_sent<InIter, InIter>();
217 }
218 test_iterators_in_sent<InIter, sentinel_wrapper<InIter>>();
219}
220
221constexpr void test_iterators() {
222 // Note: deliberately testing with only the weakest and "strongest" iterator types to minimize combinatorial
223 // explosion.
224 test_iterators_in<cpp20_input_iterator<int*>>();
225 test_iterators_in<int*>();
226}
227
228constexpr bool test() {
229 test_iterators();
230
231 { // A custom projection works.
232 const std::array in = {1, 3, 9, -2, -5, -8};
233 auto is_negative = [](int x) { return x < 0; };
234 auto negate = [](int x) { return -x; };
235 const std::array expected_negative = {-2, -5, -8};
236 const std::array expected_positive = {1, 3, 9};
237
238 { // (iterator, sentinel) overload.
239 {
240 std::array<int, 3> out1, out2;
241 std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), is_negative);
242 assert(out1 == expected_negative);
243 assert(out2 == expected_positive);
244 }
245 {
246 std::array<int, 3> out1, out2;
247 std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), is_negative, negate);
248 assert(out1 == expected_positive);
249 assert(out2 == expected_negative);
250 }
251 }
252
253 { // (range) overload.
254 {
255 std::array<int, 3> out1, out2;
256 std::ranges::partition_copy(in, out1.begin(), out2.begin(), is_negative);
257 assert(out1 == expected_negative);
258 assert(out2 == expected_positive);
259 }
260 {
261 std::array<int, 3> out1, out2;
262 std::ranges::partition_copy(in, out1.begin(), out2.begin(), is_negative, negate);
263 assert(out1 == expected_positive);
264 assert(out2 == expected_negative);
265 }
266 }
267 }
268
269 { // Complexity: Exactly `last - first` applications of `pred` and `proj`.
270 {
271 const std::array in = {-2, -5, -8, -11, -10, -5, 1, 3, 9, 6, 8, 2, 4, 2};
272 auto is_negative = [](int x) { return x < 0; };
273 std::array<int, 6> out1;
274 std::array<int, 8> out2;
275
276 int pred_count = 0, proj_count = 0;
277 counting_predicate pred(is_negative, pred_count);
278 counting_projection proj(proj_count);
279 auto expected = static_cast<int>(in.size());
280
281 {
282 std::ranges::partition_copy(in.begin(), in.end(), out1.begin(), out2.begin(), pred, proj);
283 assert(pred_count == expected);
284 assert(proj_count == expected);
285 pred_count = proj_count = 0;
286 }
287
288 {
289 std::ranges::partition_copy(in, out1.begin(), out2.begin(), pred, proj);
290 assert(pred_count == expected);
291 assert(proj_count == expected);
292 pred_count = proj_count = 0;
293 }
294 }
295 }
296
297 return true;
298}
299
300int main(int, char**) {
301 test();
302 static_assert(test());
303
304 return 0;
305}
306

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_copy.pass.cpp