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>
test_iterators()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 {
operator ==(const NonConstComparableLValue &,const NonConstComparableLValue &)79 friend constexpr bool operator==(const NonConstComparableLValue&, const NonConstComparableLValue&) { return false; }
operator ==(NonConstComparableLValue &,NonConstComparableLValue &)80 friend constexpr bool operator==(NonConstComparableLValue&, NonConstComparableLValue&) { return false; }
operator ==(const NonConstComparableLValue &,NonConstComparableLValue &)81 friend constexpr bool operator==(const NonConstComparableLValue&, NonConstComparableLValue&) { return false; }
operator ==(NonConstComparableLValue &,const NonConstComparableLValue &)82 friend constexpr bool operator==(NonConstComparableLValue&, const NonConstComparableLValue&) { return true; }
83 };
84
test()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[] = { {0, 0}, {0, 2}, {0, 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[] = { {0, 0}, {0, 2}, {0, 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{1}, S{3}, S{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
main(int,char **)223 int main(int, char**) {
224 test();
225 static_assert(test());
226
227 return 0;
228 }
229