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