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, c++20
12 
13 // template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
14 //          indirect_unary_predicate<projected<I, Proj>> Pred>
15 //   constexpr subrange<I> ranges::find_last_if_not(I first, S last, Pred pred, Proj proj = {});
16 // template<forward_range R, class Proj = identity,
17 //          indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
18 //   constexpr borrowed_subrange_t<R> ranges::find_last_if_not(R&& r, Pred pred, Proj proj = {});
19 
20 #include <algorithm>
21 #include <array>
22 #include <cassert>
23 #include <ranges>
24 
25 #include "almost_satisfies_types.h"
26 #include "test_iterators.h"
27 
28 struct Predicate {
29   bool operator()(int);
30 };
31 
32 template <class It, class Sent = It>
33 concept HasFindLastIfIt = requires(It it, Sent sent) { std::ranges::find_last_if_not(it, sent, Predicate{}); };
34 static_assert(HasFindLastIfIt<int*>);
35 static_assert(HasFindLastIfIt<forward_iterator<int*>>);
36 static_assert(!HasFindLastIfIt<cpp20_input_iterator<int*>>);
37 static_assert(!HasFindLastIfIt<ForwardIteratorNotDerivedFrom>);
38 static_assert(!HasFindLastIfIt<ForwardIteratorNotIncrementable>);
39 static_assert(!HasFindLastIfIt<forward_iterator<int*>, SentinelForNotSemiregular>);
40 static_assert(!HasFindLastIfIt<forward_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);
41 
42 static_assert(!HasFindLastIfIt<int*, int>);
43 static_assert(!HasFindLastIfIt<int, int*>);
44 
45 template <class Pred>
46 concept HasFindLastIfPred = requires(int* it, Pred pred) { std::ranges::find_last_if_not(it, it, pred); };
47 
48 static_assert(!HasFindLastIfPred<IndirectUnaryPredicateNotCopyConstructible>);
49 static_assert(!HasFindLastIfPred<IndirectUnaryPredicateNotPredicate>);
50 
51 template <class R>
52 concept HasFindLastIfR = requires(R r) { std::ranges::find_last_if_not(r, Predicate{}); };
53 static_assert(HasFindLastIfR<std::array<int, 0>>);
54 static_assert(!HasFindLastIfR<int>);
55 static_assert(!HasFindLastIfR<ForwardRangeNotDerivedFrom>);
56 static_assert(!HasFindLastIfR<ForwardRangeNotIncrementable>);
57 static_assert(!HasFindLastIfR<ForwardRangeNotSentinelSemiregular>);
58 static_assert(!HasFindLastIfR<ForwardRangeNotSentinelEqualityComparableWith>);
59 
60 template <class It, class Sent>
61 constexpr auto make_range(auto& a) {
62   return std::ranges::subrange(It(std::ranges::begin(a)), Sent(It(std::ranges::end(a))));
63 }
64 
65 template <template <class> class IteratorT, template <class> class SentinelT>
66 constexpr void test_iterator_classes() {
67   {
68     using it   = IteratorT<int*>;
69     using sent = SentinelT<it>;
70 
71     {
72       int a[] = {1, 2, 3, 4};
73       std::same_as<std::ranges::subrange<it>> auto ret =
74           std::ranges::find_last_if_not(it(a), sent(it(a + 4)), [](int x) { return x != 4; });
75       assert(base(ret.begin()) == a + 3);
76       assert(*ret.begin() == 4);
77     }
78     {
79       int a[] = {1, 2, 3, 4};
80 
81       std::same_as<std::ranges::subrange<it>> auto ret =
82           std::ranges::find_last_if_not(make_range<it, sent>(a), [](int x) { return x != 4; });
83       assert(ret.begin() == it(a + 3));
84       assert(*ret.begin() == 4);
85     }
86   }
87 
88   { // check that an empty range works
89     using it   = IteratorT<std::ranges::iterator_t<std::array<int, 0>&>>;
90     using sent = SentinelT<it>;
91 
92     {
93       std::array<int, 0> a = {};
94 
95       auto ret = std::ranges::find_last_if_not(it(a.begin()), sent(it(a.end())), [](auto&&) { return false; }).begin();
96       assert(ret == it(a.end()));
97     }
98     {
99       std::array<int, 0> a = {};
100 
101       auto ret = std::ranges::find_last_if_not(make_range<it, sent>(a), [](auto&&) { return false; }).begin();
102       assert(ret == it(a.end()));
103     }
104   }
105 
106   { // check that last is returned with no match
107     using it   = IteratorT<int*>;
108     using sent = SentinelT<it>;
109 
110     {
111       int a[] = {1, 1, 1};
112 
113       auto ret = std::ranges::find_last_if_not(it(a), sent(it(a + 3)), [](auto&&) { return true; }).begin();
114       assert(ret == it(a + 3));
115     }
116     {
117       int a[] = {1, 1, 1};
118 
119       auto ret = std::ranges::find_last_if_not(make_range<it, sent>(a), [](auto&&) { return true; }).begin();
120       assert(ret == it(a + 3));
121     }
122   }
123 
124   { // check that the last element is returned
125     struct S {
126       int comp;
127       int other;
128     };
129     using it   = IteratorT<S*>;
130     using sent = SentinelT<it>;
131 
132     S a[] = {{0, 0}, {0, 2}, {0, 1}};
133 
134     auto ret = std::ranges::find_last_if_not(
135                    it(std::begin(a)), sent(it(std::end(a))), [](int c) { return c != 0; }, &S::comp)
136                    .begin();
137     assert(ret == it(a + 2));
138     assert((*ret).comp == 0);
139     assert((*ret).other == 1);
140   }
141 
142   {
143     // count projection and predicate invocation count
144     {
145       int a[]              = {1, 2, 3, 4};
146       int predicate_count  = 0;
147       int projection_count = 0;
148 
149       using it   = IteratorT<int*>;
150       using sent = SentinelT<it>;
151 
152       auto ret =
153           std::ranges::find_last_if_not(
154               it(a),
155               sent(it(a + 4)),
156               [&](int i) {
157                 ++predicate_count;
158                 return i != 2;
159               },
160               [&](int i) {
161                 ++projection_count;
162                 return i;
163               })
164               .begin();
165       assert(ret == it(a + 1));
166       assert(*ret == 2);
167 
168       if constexpr (std::bidirectional_iterator<it>) {
169         assert(predicate_count == 3);
170         assert(projection_count == 3);
171       } else {
172         assert(predicate_count == 4);
173         assert(projection_count == 4);
174       }
175     }
176   }
177 }
178 
179 struct NonConstComparable {
180   friend constexpr bool operator!=(const NonConstComparable&, const NonConstComparable&) { return true; }
181   friend constexpr bool operator!=(NonConstComparable&, NonConstComparable&) { return true; }
182   friend constexpr bool operator!=(const NonConstComparable&, NonConstComparable&) { return true; }
183   friend constexpr bool operator!=(NonConstComparable&, const NonConstComparable&) { return false; }
184 };
185 
186 // TODO: this should really use `std::const_iterator`
187 template <class T>
188 struct add_const_to_ptr {
189   using type = T;
190 };
191 template <class T>
192 struct add_const_to_ptr<T*> {
193   using type = const T*;
194 };
195 template <class T>
196 using add_const_to_ptr_t = typename add_const_to_ptr<T>::type;
197 
198 constexpr bool test() {
199   test_iterator_classes<std::type_identity_t, std::type_identity_t>();
200   test_iterator_classes<add_const_to_ptr_t, std::type_identity_t>();
201   test_iterator_classes<contiguous_iterator, std::type_identity_t>();
202   test_iterator_classes<random_access_iterator, std::type_identity_t>();
203   test_iterator_classes<bidirectional_iterator, std::type_identity_t>();
204   test_iterator_classes<forward_iterator, std::type_identity_t>();
205   test_iterator_classes<forward_iterator, sentinel_wrapper>();
206 
207   {
208     // check that projections are used properly and that they are called with the iterator directly
209     {
210       int a[]  = {1, 2, 3, 4};
211       auto ret = std::ranges::find_last_if_not(
212                      a, a + 4, [&](int* i) { return i != a + 3; }, [](int& i) { return &i; })
213                      .begin();
214       assert(ret == a + 3);
215     }
216     {
217       int a[] = {1, 2, 3, 4};
218       auto ret =
219           std::ranges::find_last_if_not(a, [&](int* i) { return i != a + 3; }, [](int& i) { return &i; }).begin();
220       assert(ret == a + 3);
221     }
222   }
223 
224   {
225     // check that ranges::dangling is returned
226     [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret =
227         std::ranges::find_last_if_not(std::array{1, 2}, [](int) { return false; });
228   }
229 
230   {
231     // check that a subrange is returned with a borrowing range
232     int a[] = {1, 2, 3, 4};
233     std::same_as<std::ranges::subrange<int*>> auto ret =
234         std::ranges::find_last_if_not(std::views::all(a), [](int) { return false; });
235     assert(ret.begin() == a + 3);
236     assert(*ret.begin() == 4);
237   }
238 
239   {
240     // check that the return type of `iter::operator*` doesn't change
241     {
242       NonConstComparable a[] = {NonConstComparable{}};
243 
244       auto ret = std::ranges::find_last_if_not(a, a + 1, [](auto&& e) { return e != NonConstComparable{}; }).begin();
245       assert(ret == a);
246     }
247     {
248       NonConstComparable a[] = {NonConstComparable{}};
249 
250       auto ret = std::ranges::find_last_if_not(a, [](auto&& e) { return e != NonConstComparable{}; }).begin();
251       assert(ret == a);
252     }
253   }
254 
255   return true;
256 }
257 
258 int main(int, char**) {
259   test();
260   static_assert(test());
261 
262   return 0;
263 }
264