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 | // <algorithm> |
10 | |
11 | // UNSUPPORTED: c++03, c++11, c++14, c++17 |
12 | |
13 | // template<input_iterator I, sentinel_for<I> S, class Proj = identity, |
14 | // indirect_unary_predicate<projected<I, Proj>> Pred> |
15 | // constexpr I ranges::find_if_not(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 borrowed_iterator_t<R> |
19 | // ranges::find_if_not(R&& r, Pred pred, Proj proj = {}); |
20 | |
21 | #include <algorithm> |
22 | #include <array> |
23 | #include <cassert> |
24 | #include <ranges> |
25 | |
26 | #include "almost_satisfies_types.h" |
27 | #include "test_iterators.h" |
28 | |
29 | struct Predicate { |
30 | bool operator()(int); |
31 | }; |
32 | |
33 | template <class It, class Sent = It> |
34 | concept HasFindIfNotIt = requires(It it, Sent sent) { std::ranges::find_if_not(it, sent, Predicate{}); }; |
35 | static_assert(HasFindIfNotIt<int*>); |
36 | static_assert(!HasFindIfNotIt<InputIteratorNotDerivedFrom>); |
37 | static_assert(!HasFindIfNotIt<InputIteratorNotIndirectlyReadable>); |
38 | static_assert(!HasFindIfNotIt<InputIteratorNotInputOrOutputIterator>); |
39 | static_assert(!HasFindIfNotIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>); |
40 | static_assert(!HasFindIfNotIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>); |
41 | |
42 | static_assert(!HasFindIfNotIt<int*, int>); |
43 | static_assert(!HasFindIfNotIt<int, int*>); |
44 | |
45 | template <class Pred> |
46 | concept HasFindIfNotPred = requires(int* it, Pred pred) {std::ranges::find_if_not(it, it, pred); }; |
47 | |
48 | static_assert(!HasFindIfNotPred<IndirectUnaryPredicateNotCopyConstructible>); |
49 | static_assert(!HasFindIfNotPred<IndirectUnaryPredicateNotPredicate>); |
50 | |
51 | template <class R> |
52 | concept HasFindIfNotR = requires(R r) { std::ranges::find_if_not(r, Predicate{}); }; |
53 | static_assert(HasFindIfNotR<std::array<int, 0>>); |
54 | static_assert(!HasFindIfNotR<int>); |
55 | static_assert(!HasFindIfNotR<InputRangeNotDerivedFrom>); |
56 | static_assert(!HasFindIfNotR<InputRangeNotIndirectlyReadable>); |
57 | static_assert(!HasFindIfNotR<InputRangeNotInputOrOutputIterator>); |
58 | static_assert(!HasFindIfNotR<InputRangeNotSentinelSemiregular>); |
59 | static_assert(!HasFindIfNotR<InputRangeNotSentinelEqualityComparableWith>); |
60 | |
61 | template <class It, class Sent = It> |
62 | constexpr void test_iterators() { |
63 | { |
64 | int a[] = {1, 2, 3, 4}; |
65 | std::same_as<It> auto ret = std::ranges::find_if_not(It(a), Sent(It(a + 4)), [c = 0](int) mutable { return c++ <= 2; }); |
66 | assert(base(ret) == a + 3); |
67 | assert(*ret == 4); |
68 | } |
69 | { |
70 | int a[] = {1, 2, 3, 4}; |
71 | auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); |
72 | std::same_as<It> auto ret = std::ranges::find_if_not(range, [c = 0](int) mutable { return c++ <= 2; }); |
73 | assert(base(ret) == a + 3); |
74 | assert(*ret == 4); |
75 | } |
76 | } |
77 | |
78 | struct NonConstComparableLValue { |
79 | friend constexpr bool operator==(const NonConstComparableLValue&, const NonConstComparableLValue&) { return false; } |
80 | friend constexpr bool operator==(NonConstComparableLValue&, NonConstComparableLValue&) { return false; } |
81 | friend constexpr bool operator==(const NonConstComparableLValue&, NonConstComparableLValue&) { return false; } |
82 | friend constexpr bool operator==(NonConstComparableLValue&, const NonConstComparableLValue&) { return true; } |
83 | }; |
84 | |
85 | constexpr bool test() { |
86 | test_iterators<int*>(); |
87 | test_iterators<const int*>(); |
88 | test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>(); |
89 | test_iterators<bidirectional_iterator<int*>>(); |
90 | test_iterators<forward_iterator<int*>>(); |
91 | test_iterators<random_access_iterator<int*>>(); |
92 | test_iterators<contiguous_iterator<int*>>(); |
93 | |
94 | { // check that projections are used properly and that they are called with the iterator directly |
95 | { |
96 | int a[] = {1, 2, 3, 4}; |
97 | auto ret = std::ranges::find_if_not(a, a + 4, [&](int* i) { return i != a + 3; }, [](int& i) { return &i; }); |
98 | assert(ret == a + 3); |
99 | } |
100 | { |
101 | int a[] = {1, 2, 3, 4}; |
102 | auto ret = std::ranges::find_if_not(a, [&](int* i) { return i != a + 3; }, [](int& i) { return &i; }); |
103 | assert(ret == a + 3); |
104 | } |
105 | } |
106 | |
107 | { |
108 | // check that the first element is returned |
109 | { |
110 | struct S { |
111 | int comp; |
112 | int other; |
113 | }; |
114 | S a[] = { {.comp: 0, .other: 0}, {.comp: 0, .other: 2}, {.comp: 0, .other: 1} }; |
115 | auto ret = std::ranges::find_if_not(a, [](int i){ return i != 0; }, &S::comp); |
116 | assert(ret == a); |
117 | assert(ret->comp == 0); |
118 | assert(ret->other == 0); |
119 | } |
120 | { |
121 | struct S { |
122 | int comp; |
123 | int other; |
124 | }; |
125 | S a[] = { {.comp: 0, .other: 0}, {.comp: 0, .other: 2}, {.comp: 0, .other: 1} }; |
126 | auto ret = std::ranges::find_if_not(a, a + 3, [](int i) { return i != 0; }, &S::comp); |
127 | assert(ret == a); |
128 | assert(ret->comp == 0); |
129 | assert(ret->other == 0); |
130 | } |
131 | } |
132 | |
133 | { |
134 | // check that end + 1 iterator is returned with no match |
135 | { |
136 | int a[] = {1, 1, 1}; |
137 | auto ret = std::ranges::find_if(a, a + 3, [](int) { return false; }); |
138 | assert(ret == a + 3); |
139 | } |
140 | { |
141 | int a[] = {1, 1, 1}; |
142 | auto ret = std::ranges::find_if(a, [](int){ return false; }); |
143 | assert(ret == a + 3); |
144 | } |
145 | } |
146 | |
147 | { // check that ranges::dangling is returned |
148 | [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret = |
149 | std::ranges::find_if_not(std::array{1, 2}, [](int){ return true; }); |
150 | } |
151 | |
152 | { // check that an iterator is returned with a borrowing range |
153 | int a[] = {1, 2, 3, 4}; |
154 | std::same_as<int*> auto ret = std::ranges::find_if_not(std::views::all(a), [](int){ return false; }); |
155 | assert(ret == a); |
156 | assert(*ret == 1); |
157 | } |
158 | |
159 | { // check that std::invoke is used |
160 | struct S { int i; }; |
161 | S a[] = { S{.i: 1}, S{.i: 3}, S{.i: 2} }; |
162 | std::same_as<S*> auto ret = std::ranges::find_if_not(a, [](int) { return true; }, &S::i); |
163 | assert(ret == a + 3); |
164 | } |
165 | |
166 | { // count projection and predicate invocation count |
167 | { |
168 | int a[] = {1, 2, 3, 4}; |
169 | int predicate_count = 0; |
170 | int projection_count = 0; |
171 | auto ret = std::ranges::find_if_not(a, a + 4, |
172 | [&](int i) { ++predicate_count; return i != 2; }, |
173 | [&](int i) { ++projection_count; return i; }); |
174 | assert(ret == a + 1); |
175 | assert(*ret == 2); |
176 | assert(predicate_count == 2); |
177 | assert(projection_count == 2); |
178 | } |
179 | { |
180 | int a[] = {1, 2, 3, 4}; |
181 | int predicate_count = 0; |
182 | int projection_count = 0; |
183 | auto ret = std::ranges::find_if_not(a, |
184 | [&](int i) { ++predicate_count; return i != 2; }, |
185 | [&](int i) { ++projection_count; return i; }); |
186 | assert(ret == a + 1); |
187 | assert(*ret == 2); |
188 | assert(predicate_count == 2); |
189 | assert(projection_count == 2); |
190 | } |
191 | } |
192 | |
193 | { // check that the return type of `iter::operator*` doesn't change |
194 | { |
195 | NonConstComparableLValue a[] = { NonConstComparableLValue{} }; |
196 | auto ret = std::ranges::find_if_not(a, a + 1, [](auto&& e) { return e != NonConstComparableLValue{}; }); |
197 | assert(ret == a); |
198 | } |
199 | { |
200 | NonConstComparableLValue a[] = { NonConstComparableLValue{} }; |
201 | auto ret = std::ranges::find_if_not(a, [](auto&& e) { return e != NonConstComparableLValue{}; }); |
202 | assert(ret == a); |
203 | } |
204 | } |
205 | |
206 | { |
207 | // check that an empty range works |
208 | { |
209 | std::array<int ,0> a = {}; |
210 | auto ret = std::ranges::find_if_not(a.begin(), a.end(), [](int) { return true; }); |
211 | assert(ret == a.begin()); |
212 | } |
213 | { |
214 | std::array<int, 0> a = {}; |
215 | auto ret = std::ranges::find_if_not(a, [](int) { return true; }); |
216 | assert(ret == a.begin()); |
217 | } |
218 | } |
219 | |
220 | return true; |
221 | } |
222 | |
223 | int main(int, char**) { |
224 | test(); |
225 | static_assert(test()); |
226 | |
227 | return 0; |
228 | } |
229 | |