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, class Proj = identity,
14 // indirect_unary_predicate<projected<I, Proj>> Pred>
15 // constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});
16 // template<input_range R, class Proj = identity,
17 // indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
18 // constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});
19
20
21 #include <algorithm>
22 #include <array>
23 #include <cassert>
24
25 #include "almost_satisfies_types.h"
26 #include "test_iterators.h"
27
28 struct Functor {
29 bool operator()(auto&&);
30 };
31
32 template <class Iter, class Sent = sentinel_wrapper<Iter>>
33 concept HasIsPartitionedIt = requires(Iter iter, Sent sent) {
34 std::ranges::is_partitioned(iter, sent, Functor{});
35 };
36
37 static_assert(HasIsPartitionedIt<int*>);
38 static_assert(!HasIsPartitionedIt<InputIteratorNotDerivedFrom>);
39 static_assert(!HasIsPartitionedIt<InputIteratorNotIndirectlyReadable>);
40 static_assert(!HasIsPartitionedIt<InputIteratorNotInputOrOutputIterator>);
41 static_assert(!HasIsPartitionedIt<int*, SentinelForNotSemiregular>);
42 static_assert(!HasIsPartitionedIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
43
44 template <class Pred>
45 concept HasIsPartitionedItPred = requires(int* first, int* last, Pred pred) {
46 std::ranges::is_partitioned(first, last, pred);
47 };
48
49 static_assert(HasIsPartitionedItPred<Functor>);
50 static_assert(!HasIsPartitionedItPred<IndirectUnaryPredicateNotCopyConstructible>);
51 static_assert(!HasIsPartitionedItPred<IndirectUnaryPredicateNotPredicate>);
52
53 template <class Range>
54 concept HasIsPartitionedR = requires (Range range) {
55 std::ranges::is_partitioned(range, Functor{});
56 };
57
58 static_assert(HasIsPartitionedR<UncheckedRange<int*>>);
59 static_assert(!HasIsPartitionedR<InputRangeNotDerivedFrom>);
60 static_assert(!HasIsPartitionedR<InputRangeNotIndirectlyReadable>);
61 static_assert(!HasIsPartitionedR<InputRangeNotInputOrOutputIterator>);
62 static_assert(!HasIsPartitionedR<InputRangeNotSentinelSemiregular>);
63 static_assert(!HasIsPartitionedR<InputRangeNotSentinelEqualityComparableWith>);
64
65 template <class Pred>
66 concept HasIsPartitionedRPred = requires(Pred pred) {
67 std::ranges::is_partitioned(UncheckedRange<int*>{}, pred);
68 };
69
70 static_assert(HasIsPartitionedRPred<Functor>);
71 static_assert(!HasIsPartitionedRPred<IndirectUnaryPredicateNotCopyConstructible>);
72 static_assert(!HasIsPartitionedRPred<IndirectUnaryPredicateNotPredicate>);
73
74 template <class Iter, class Sent = Iter>
test_iterators()75 constexpr void test_iterators() {
76 { // simple test
77 {
78 int a[] = {1, 2, 3, 4, 5};
79 std::same_as<bool> decltype(auto) ret =
80 std::ranges::is_partitioned(Iter(a), Sent(Iter(a + 5)), [](int i) { return i < 3; });
81 assert(ret);
82 }
83 {
84 int a[] = {1, 2, 3, 4, 5};
85 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5)));
86 std::same_as<bool> decltype(auto) ret = std::ranges::is_partitioned(range, [](int i) { return i < 3; });
87 assert(ret);
88 }
89 }
90
91 { // check that it's partitioned if the predicate is true for all elements
92 {
93 int a[] = {1, 2, 3, 4};
94 auto ret = std::ranges::is_partitioned(Iter(a), Sent(Iter(a + 4)), [](int) { return true; });
95 assert(ret);
96 }
97 {
98 int a[] = {1, 2, 3, 4};
99 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 4)));
100 auto ret = std::ranges::is_partitioned(range, [](int) { return true; });
101 assert(ret);
102 }
103 }
104
105 { // check that it's partitioned if the predicate is false for all elements
106 {
107 int a[] = {1, 2, 3, 4};
108 auto ret = std::ranges::is_partitioned(Iter(a), Sent(Iter(a + 4)), [](int) { return false; });
109 assert(ret);
110 }
111 {
112 int a[] = {1, 2, 3, 4};
113 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 4)));
114 auto ret = std::ranges::is_partitioned(range, [](int) { return false; });
115 assert(ret);
116 }
117 }
118
119 { // check that false is returned if the range isn't partitioned
120 {
121 int a[] = {1, 3, 2, 4};
122 auto ret = std::ranges::is_partitioned(Iter(a), Sent(Iter(a + 4)), [](int i) { return i < 3; });
123 assert(!ret);
124 }
125 {
126 int a[] = {1, 3, 2, 4};
127 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 4)));
128 auto ret = std::ranges::is_partitioned(range, [](int i) { return i < 3; });
129 assert(!ret);
130 }
131 }
132
133 { // check that an empty range is partitioned
134 {
135 std::array<int, 0> a = {};
136 auto ret = std::ranges::is_partitioned(Iter(a.data()), Sent(Iter(a.data())), [](int i) { return i < 3; });
137 assert(ret);
138 }
139 {
140 std::array<int, 0> a = {};
141 auto range = std::ranges::subrange(Iter(a.data()), Sent(Iter(a.data())));
142 auto ret = std::ranges::is_partitioned(range, [](int i) { return i < 3; });
143 assert(ret);
144 }
145 }
146
147 { // check that a single element is partitioned
148 {
149 int a[] = {1};
150 auto ret = std::ranges::is_partitioned(Iter(a), Sent(Iter(a + 1)), [](int i) { return i < 3; });
151 assert(ret);
152 }
153 {
154 int a[] = {1};
155 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 1)));
156 auto ret = std::ranges::is_partitioned(range, [](int i) { return i < 3; });
157 assert(ret);
158 }
159 }
160
161 { // check that it is partitioned when the first element is the partition point
162 {
163 int a[] = {0, 1, 1};
164 auto ret = std::ranges::is_partitioned(Iter(a), Sent(Iter(a + 3)), [](int i) { return i < 1; });
165 assert(ret);
166 }
167 {
168 int a[] = {0, 1, 1};
169 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
170 auto ret = std::ranges::is_partitioned(range, [](int i) { return i < 1; });
171 assert(ret);
172 }
173 }
174
175 { // check that it is partitioned when the last element is the partition point
176 {
177 int a[] = {0, 0, 1};
178 auto ret = std::ranges::is_partitioned(Iter(a), Sent(Iter(a + 3)), [](int i) { return i < 1; });
179 assert(ret);
180 }
181 {
182 int a[] = {0, 0, 1};
183 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
184 auto ret = std::ranges::is_partitioned(range, [](int i) { return i < 1; });
185 assert(ret);
186 }
187 }
188 }
189
test()190 constexpr bool test() {
191 test_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
192 test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
193 test_iterators<forward_iterator<int*>>();
194 test_iterators<bidirectional_iterator<int*>>();
195 test_iterators<random_access_iterator<int*>>();
196 test_iterators<contiguous_iterator<int*>>();
197 test_iterators<int*>();
198 test_iterators<const int*>();
199
200 { // check that std:invoke is used
201 struct S {
202 int check;
203 int other;
204
205 constexpr S& identity() {
206 return *this;
207 }
208 };
209 {
210 S a[] = {{1, 2}, {3, 4}, {5, 6}};
211 auto ret = std::ranges::is_partitioned(a, a + 3, &S::check, &S::identity);
212 assert(ret);
213 }
214 {
215 S a[] = {{1, 2}, {3, 4}, {5, 6}};
216 auto ret = std::ranges::is_partitioned(a, &S::check, &S::identity);
217 assert(ret);
218 }
219 }
220
221 return true;
222 }
223
main(int,char **)224 int main(int, char**) {
225 test();
226 static_assert(test());
227
228 return 0;
229 }
230