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 
41 struct UnaryPred { bool operator()(int) const; };
42 
43 // Test constraints of the (iterator, sentinel) overload.
44 // ======================================================
45 
46 template <class InIter = int*, class Sent = int*, class Output1 = int*, class Output2 = int*, class Pred = UnaryPred>
47 concept 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 
53 static_assert(HasPartitionCopyIter<int*, int*, int*, int*, UnaryPred>);
54 
55 // !input_iterator<I>
56 static_assert(!HasPartitionCopyIter<InputIteratorNotDerivedFrom>);
57 static_assert(!HasPartitionCopyIter<InputIteratorNotIndirectlyReadable>);
58 static_assert(!HasPartitionCopyIter<InputIteratorNotInputOrOutputIterator>);
59 
60 // !sentinel_for<S, I>
61 static_assert(!HasPartitionCopyIter<int*, SentinelForNotSemiregular>);
62 static_assert(!HasPartitionCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
63 
64 // !weakly_incrementable<O1>
65 static_assert(!HasPartitionCopyIter<int*, int*, WeaklyIncrementableNotMovable>);
66 
67 // !weakly_incrementable<O2>
68 static_assert(!HasPartitionCopyIter<int*, int*, int*, WeaklyIncrementableNotMovable>);
69 
70 // !indirect_unary_predicate<projected<I, Proj>>
71 static_assert(!HasPartitionCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotPredicate>);
72 static_assert(!HasPartitionCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
73 
74 struct Uncopyable {
75   Uncopyable(int&&);
76   Uncopyable(const int&) = delete;
77 };
78 // !indirectly_copyable<I, O1>
79 static_assert(!HasPartitionCopyIter<int*, int*, Uncopyable*>);
80 // !indirectly_copyable<I, O2>
81 static_assert(!HasPartitionCopyIter<int*, int*, int*, Uncopyable*>);
82 
83 // Test constraints of the (range) overload.
84 // =========================================
85 
86 template <class InputRange, class Output1 = int*, class Output2 = int*, class Pred = UnaryPred>
87 concept 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 
93 template <class T>
94 using R = UncheckedRange<T>;
95 
96 static_assert(HasPartitionCopyRange<R<int*>, int*, int*, UnaryPred>);
97 
98 // !input_iterator<I>
99 static_assert(!HasPartitionCopyRange<InputRangeNotDerivedFrom>);
100 static_assert(!HasPartitionCopyRange<InputRangeNotIndirectlyReadable>);
101 static_assert(!HasPartitionCopyRange<InputRangeNotInputOrOutputIterator>);
102 
103 // !weakly_incrementable<O1>
104 static_assert(!HasPartitionCopyRange<R<int*>, WeaklyIncrementableNotMovable>);
105 
106 // !weakly_incrementable<O2>
107 static_assert(!HasPartitionCopyRange<R<int*>, int*, WeaklyIncrementableNotMovable>);
108 
109 // !indirect_unary_predicate<projected<I, Proj>>
110 static_assert(!HasPartitionCopyRange<R<int*>, int*, int*, IndirectUnaryPredicateNotPredicate>);
111 static_assert(!HasPartitionCopyRange<R<int*>, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
112 
113 // !indirectly_copyable<I, O1>
114 static_assert(!HasPartitionCopyRange<R<int*>, Uncopyable*>);
115 // !indirectly_copyable<I, O2>
116 static_assert(!HasPartitionCopyRange<R<int*>, int*, Uncopyable*>);
117 
118 static_assert(std::is_same_v<std::ranges::partition_copy_result<int, int, int>,
119     std::ranges::in_out_out_result<int, int, int>>);
120 
121 template <class Iter, class Sent, class OutIter1, class OutIter2, size_t N1, size_t N2, size_t N3, class Pred>
122 constexpr 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.begin()), OutIter2(out2.begin()), 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.begin()), OutIter2(out2.begin()), 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 
162 template <class InIter, class Sent, class Out1, class Out2>
163 constexpr 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 
198 template <class InIter, class Sent, class Out1>
199 constexpr 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 
205 template <class InIter, class Sent>
206 constexpr 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 
213 template <class InIter>
214 constexpr 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 
221 constexpr 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 
228 constexpr 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 
300 int main(int, char**) {
301   test();
302   static_assert(test());
303 
304   return 0;
305 }
306