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