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 // UNSUPPORTED: libcpp-has-no-incomplete-ranges
13 
14 // template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
15 //          indirect_binary_predicate<projected<I, Proj>,
16 //                                    projected<I, Proj>> Pred = ranges::equal_to>
17 //   constexpr I ranges::adjacent_find(I first, S last, Pred pred = {}, Proj proj = {});
18 // template<forward_range R, class Proj = identity,
19 //          indirect_binary_predicate<projected<iterator_t<R>, Proj>,
20 //                                    projected<iterator_t<R>, Proj>> Pred = ranges::equal_to>
21 //   constexpr borrowed_iterator_t<R> ranges::adjacent_find(R&& r, Pred pred = {}, Proj proj = {});
22 
23 #include <algorithm>
24 #include <array>
25 #include <cassert>
26 #include <cstddef>
27 #include <ranges>
28 
29 #include "almost_satisfies_types.h"
30 #include "boolean_testable.h"
31 #include "test_iterators.h"
32 
33 template <class Iter, class Sent = Iter>
34 concept HasAdjacentFindIt = requires (Iter iter, Sent sent) { std::ranges::adjacent_find(iter, sent); };
35 
36 struct NotComparable {};
37 
38 static_assert(HasAdjacentFindIt<int*>);
39 static_assert(!HasAdjacentFindIt<ForwardIteratorNotDerivedFrom>);
40 static_assert(!HasAdjacentFindIt<ForwardIteratorNotIncrementable>);
41 static_assert(!HasAdjacentFindIt<int*, SentinelForNotSemiregular>);
42 static_assert(!HasAdjacentFindIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
43 static_assert(!HasAdjacentFindIt<NotComparable*>);
44 
45 template <class Range>
46 concept HasAdjacentFindR = requires (Range range) { std::ranges::adjacent_find(range); };
47 
48 static_assert(HasAdjacentFindR<UncheckedRange<int*>>);
49 static_assert(!HasAdjacentFindR<ForwardRangeNotDerivedFrom>);
50 static_assert(!HasAdjacentFindR<ForwardRangeNotIncrementable>);
51 static_assert(!HasAdjacentFindR<ForwardRangeNotSentinelSemiregular>);
52 static_assert(!HasAdjacentFindR<ForwardRangeNotSentinelEqualityComparableWith>);
53 static_assert(!HasAdjacentFindR<UncheckedRange<NotComparable>>);
54 
55 template <size_t N>
56 struct Data {
57   std::array<int, N> input;
58   int expected;
59 };
60 
61 template <class Iter, class Sent, size_t N>
62 constexpr void test(Data<N> d) {
63   {
64     std::same_as<Iter> decltype(auto) ret =
65         std::ranges::adjacent_find(Iter(d.input.data()), Sent(Iter(d.input.data() + d.input.size())));
66     assert(base(ret) == d.input.data() + d.expected);
67   }
68   {
69     auto range = std::ranges::subrange(Iter(d.input.data()), Sent(Iter(d.input.data() + d.input.size())));
70     std::same_as<Iter> decltype(auto) ret = std::ranges::adjacent_find(range);
71     assert(base(ret) == d.input.data() + d.expected);
72   }
73 }
74 
75 template <class Iter, class Sent = Iter>
76 constexpr void test_iterators() {
77   // simple test
78   test<Iter, Sent, 4>({.input = {1, 2, 2, 4}, .expected = 1});
79   // last is returned with no match
80   test<Iter, Sent, 4>({.input = {1, 2, 3, 4}, .expected = 4});
81   // first elements match
82   test<Iter, Sent, 4>({.input = {1, 1, 3, 4}, .expected = 0});
83   // the first match is returned
84   test<Iter, Sent, 7>({.input = {1, 1, 3, 4, 4, 4, 4}, .expected = 0});
85   // two element range works
86   test<Iter, Sent, 2>({.input = {3, 3}, .expected = 0});
87   // single element range works
88   test<Iter, Sent, 1>({.input = {1}, .expected = 1});
89   // empty range works
90   test<Iter, Sent, 0>({.input = {}, .expected = 0});
91 }
92 
93 constexpr bool test() {
94   test_iterators<forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();
95   test_iterators<forward_iterator<int*>>();
96   test_iterators<bidirectional_iterator<int*>>();
97   test_iterators<random_access_iterator<int*>>();
98   test_iterators<contiguous_iterator<int*>>();
99   test_iterators<int*>();
100   test_iterators<const int*>();
101 
102   { // check that ranges::dangling is returned
103     [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
104         std::ranges::adjacent_find(std::array{1, 2, 3, 4});
105   }
106 
107   { // check that the complexity requirements are met with no match
108     {
109       int predicateCount = 0;
110       auto pred = [&](int, int) { ++predicateCount; return false; };
111       auto projectionCount = 0;
112       auto proj = [&](int i) { ++projectionCount; return i; };
113       int a[] = {1, 2, 3, 4, 5};
114       auto ret = std::ranges::adjacent_find(a, a + 5, pred, proj);
115       assert(ret == a + 5);
116       assert(predicateCount == 4);
117       assert(projectionCount == 8);
118     }
119     {
120       int predicateCount = 0;
121       auto pred = [&](int, int) { ++predicateCount; return false; };
122       auto projectionCount = 0;
123       auto proj = [&](int i) { ++projectionCount; return i; };
124       int a[] = {1, 2, 3, 4, 5};
125       auto ret = std::ranges::adjacent_find(a, pred, proj);
126       assert(ret == a + 5);
127       assert(predicateCount == 4);
128       assert(projectionCount == 8);
129     }
130   }
131 
132   { // check that the complexity requirements are met with a match
133     {
134       int predicateCount = 0;
135       auto pred = [&](int i, int j) { ++predicateCount; return i == j; };
136       auto projectionCount = 0;
137       auto proj = [&](int i) { ++projectionCount; return i; };
138       int a[] = {1, 2, 4, 4, 5};
139       auto ret = std::ranges::adjacent_find(a, a + 5, pred, proj);
140       assert(ret == a + 2);
141       assert(predicateCount == 3);
142       assert(projectionCount == 6);
143     }
144     {
145       int predicateCount = 0;
146       auto pred = [&](int i, int j) { ++predicateCount; return i == j; };
147       auto projectionCount = 0;
148       auto proj = [&](int i) { ++projectionCount; return i; };
149       int a[] = {1, 2, 4, 4, 5};
150       auto ret = std::ranges::adjacent_find(a, pred, proj);
151       assert(ret == a + 2);
152       assert(predicateCount == 3);
153       assert(projectionCount == 6);
154     }
155   }
156 
157   { // check that std::invoke is used
158     struct S {
159       constexpr S(int i_) : i(i_) {}
160       constexpr bool compare(const S& j) const { return j.i == i; }
161       constexpr const S& identity() const { return *this; }
162       int i;
163     };
164     {
165       S a[] = {1, 2, 3, 4};
166       auto ret = std::ranges::adjacent_find(std::begin(a), std::end(a), &S::compare, &S::identity);
167       assert(ret == a + 4);
168     }
169     {
170       S a[] = {1, 2, 3, 4};
171       auto ret = std::ranges::adjacent_find(a, &S::compare, &S::identity);
172       assert(ret == a + 4);
173     }
174   }
175 
176   { // check that the implicit conversion to bool works
177     {
178       int a[] = {1, 2, 2, 4};
179       auto ret = std::ranges::adjacent_find(a, a + 4, [](int i, int j) { return BooleanTestable{i == j}; });
180       assert(ret == a + 1);
181     }
182     {
183       int a[] = {1, 2, 2, 4};
184       auto ret = std::ranges::adjacent_find(a, [](int i, int j) { return BooleanTestable{i == j}; });
185       assert(ret == a + 1);
186     }
187   }
188 
189   return true;
190 }
191 
192 int main(int, char**) {
193   test();
194   static_assert(test());
195 
196   return 0;
197 }
198