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<permutable I, sentinel_for<I> S, class Proj = identity,
15 // indirect_unary_predicate<projected<I, Proj>> Pred>
16 // constexpr subrange<I>
17 // partition(I first, S last, Pred pred, Proj proj = {}); // Since C++20
18 //
19 // template<forward_range R, class Proj = identity,
20 // indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
21 // requires permutable<iterator_t<R>>
22 // constexpr borrowed_subrange_t<R>
23 // partition(R&& r, Pred pred, Proj proj = {}); // Since C++20
24
25 #include <algorithm>
26 #include <array>
27 #include <concepts>
28 #include <functional>
29 #include <ranges>
30
31 #include "almost_satisfies_types.h"
32 #include "test_iterators.h"
33
34 struct UnaryPred { bool operator()(int) const; };
35
36 // Test constraints of the (iterator, sentinel) overload.
37 // ======================================================
38
39 template <class Iter = int*, class Sent = int*, class Pred = UnaryPred>
40 concept HasPartitionIter =
41 requires(Iter&& iter, Sent&& sent, Pred&& pred) {
42 std::ranges::partition(std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Pred>(pred));
43 };
44
45 static_assert(HasPartitionIter<int*, int*, UnaryPred>);
46
47 // !permutable<I>
48 static_assert(!HasPartitionIter<PermutableNotForwardIterator>);
49 static_assert(!HasPartitionIter<PermutableNotSwappable>);
50
51 // !sentinel_for<S, I>
52 static_assert(!HasPartitionIter<int*, SentinelForNotSemiregular>);
53 static_assert(!HasPartitionIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
54
55 // !indirect_unary_predicate<projected<I, Proj>>
56 static_assert(!HasPartitionIter<int*, int*, IndirectUnaryPredicateNotPredicate>);
57 static_assert(!HasPartitionIter<int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
58
59 // Test constraints of the (range) overload.
60 // =========================================
61
62 template <class Range, class Pred>
63 concept HasPartitionRange =
64 requires(Range&& range, Pred&& pred) {
65 std::ranges::partition(std::forward<Range>(range), std::forward<Pred>(pred));
66 };
67
68 template <class T>
69 using R = UncheckedRange<T>;
70
71 static_assert(HasPartitionRange<R<int*>, UnaryPred>);
72
73 // !forward_range<R>
74 static_assert(!HasPartitionRange<ForwardRangeNotDerivedFrom, UnaryPred>);
75 static_assert(!HasPartitionRange<ForwardRangeNotIncrementable, UnaryPred>);
76
77 // !indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
78 static_assert(!HasPartitionRange<R<int*>, IndirectUnaryPredicateNotPredicate>);
79 static_assert(!HasPartitionRange<R<int*>, IndirectUnaryPredicateNotCopyConstructible>);
80
81 // !permutable<iterator_t<R>>
82 static_assert(!HasPartitionRange<R<PermutableNotForwardIterator>, UnaryPred>);
83 static_assert(!HasPartitionRange<R<PermutableNotSwappable>, UnaryPred>);
84
85 // `partition` isn't a stable algorithm so this function cannot test the exact output.
86 template <class Iter, class Sent, size_t N, class Pred>
test_one(std::array<int,N> input,Pred pred,size_t partition_point)87 constexpr void test_one(std::array<int, N> input, Pred pred, size_t partition_point) {
88 auto neg_pred = [&](int x) { return !pred(x); };
89
90 { // (iterator, sentinel) overload.
91 auto partitioned = input;
92 auto b = Iter(partitioned.data());
93 auto e = Sent(Iter(partitioned.data() + partitioned.size()));
94
95 std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::partition(b, e, pred);
96
97 assert(base(result.begin()) == partitioned.data() + partition_point);
98 assert(base(result.end()) == partitioned.data() + partitioned.size());
99
100 assert(std::ranges::all_of(b, result.begin(), pred));
101 assert(std::ranges::all_of(result.begin(), e, neg_pred));
102 }
103
104 { // (range) overload.
105 auto partitioned = input;
106 auto b = Iter(partitioned.data());
107 auto e = Sent(Iter(partitioned.data() + partitioned.size()));
108 auto range = std::ranges::subrange(b, e);
109
110 std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::partition(range, pred);
111
112 assert(base(result.begin()) == partitioned.data() + partition_point);
113 assert(base(result.end()) == partitioned.data() + partitioned.size());
114
115 assert(std::ranges::all_of(b, result.begin(), pred));
116 assert(std::ranges::all_of(result.begin(), e, neg_pred));
117 }
118 }
119
120 template <class Iter, class Sent>
test_iterators_2()121 constexpr void test_iterators_2() {
122 auto is_odd = [](int x) { return x % 2 != 0; };
123
124 // Empty sequence.
125 test_one<Iter, Sent, 0>({}, is_odd, 0);
126 // 1-element sequence, the element satisfies the predicate.
127 test_one<Iter, Sent, 1>({1}, is_odd, 1);
128 // 1-element sequence, the element doesn't satisfy the predicate.
129 test_one<Iter, Sent, 1>({2}, is_odd, 0);
130 // 2-element sequence, not in order.
131 test_one<Iter, Sent, 2>({2, 1}, is_odd, 1);
132 // 2-element sequence, already in order.
133 test_one<Iter, Sent, 2>({1, 2}, is_odd, 1);
134 // 3-element sequence.
135 test_one<Iter, Sent, 3>({2, 1, 3}, is_odd, 2);
136 // Longer sequence.
137 test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, is_odd, 4);
138 // Longer sequence with duplicates.
139 test_one<Iter, Sent, 8>({2, 1, 3, 6, 2, 8, 1, 6}, is_odd, 3);
140 // All elements are the same and satisfy the predicate.
141 test_one<Iter, Sent, 3>({1, 1, 1}, is_odd, 3);
142 // All elements are the same and don't satisfy the predicate.
143 test_one<Iter, Sent, 3>({2, 2, 2}, is_odd, 0);
144 // Already partitioned.
145 test_one<Iter, Sent, 6>({1, 3, 5, 4, 6, 8}, is_odd, 3);
146 // Reverse-partitioned.
147 test_one<Iter, Sent, 6>({4, 6, 8, 1, 3, 5}, is_odd, 3);
148 // Repeating pattern.
149 test_one<Iter, Sent, 6>({1, 2, 1, 2, 1, 2}, is_odd, 3);
150
151 auto is_negative = [](int x) { return x < 0; };
152 // Different comparator.
153 test_one<Iter, Sent, 5>({-3, 5, 7, -6, 2}, is_negative, 2);
154 }
155
156 template <class Iter>
test_iterators_1()157 constexpr void test_iterators_1() {
158 test_iterators_2<Iter, Iter>();
159 test_iterators_2<Iter, sentinel_wrapper<Iter>>();
160 }
161
test_iterators()162 constexpr void test_iterators() {
163 test_iterators_1<forward_iterator<int*>>();
164 test_iterators_1<bidirectional_iterator<int*>>();
165 test_iterators_1<random_access_iterator<int*>>();
166 test_iterators_1<contiguous_iterator<int*>>();
167 test_iterators_1<int*>();
168 }
169
test()170 constexpr bool test() {
171 test_iterators();
172
173 { // A custom projection works.
174 const std::array input = {1, -1};
175 auto is_negative = [](int x) { return x < 0; };
176 auto negate = [](int x) { return -x; };
177 const std::array expected_no_proj = {-1, 1};
178 const std::array expected_with_proj = {1, -1};
179
180 { // (iterator, sentinel) overload.
181 {
182 auto in = input;
183 std::ranges::partition(in.begin(), in.end(), is_negative);
184 assert(in == expected_no_proj);
185 }
186 {
187 auto in = input;
188 std::ranges::partition(in.begin(), in.end(), is_negative, negate);
189 assert(in == expected_with_proj);
190 }
191 }
192
193 { // (range) overload.
194 {
195 auto in = input;
196 std::ranges::partition(in, is_negative);
197 assert(in == expected_no_proj);
198 }
199 {
200 auto in = input;
201 std::ranges::partition(in, is_negative, negate);
202 assert(in == expected_with_proj);
203 }
204 }
205 }
206
207 return true;
208 }
209
main(int,char **)210 int main(int, char**) {
211 test();
212 static_assert(test());
213
214 return 0;
215 }
216