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
31template <class Iter, class Sent = Iter>
32concept HasAdjacentFindIt = requires (Iter iter, Sent sent) { std::ranges::adjacent_find(iter, sent); };
33
34struct NotComparable {};
35
36static_assert(HasAdjacentFindIt<int*>);
37static_assert(!HasAdjacentFindIt<ForwardIteratorNotDerivedFrom>);
38static_assert(!HasAdjacentFindIt<ForwardIteratorNotIncrementable>);
39static_assert(!HasAdjacentFindIt<int*, SentinelForNotSemiregular>);
40static_assert(!HasAdjacentFindIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
41static_assert(!HasAdjacentFindIt<NotComparable*>);
42
43template <class Range>
44concept HasAdjacentFindR = requires (Range range) { std::ranges::adjacent_find(range); };
45
46static_assert(HasAdjacentFindR<UncheckedRange<int*>>);
47static_assert(!HasAdjacentFindR<ForwardRangeNotDerivedFrom>);
48static_assert(!HasAdjacentFindR<ForwardRangeNotIncrementable>);
49static_assert(!HasAdjacentFindR<ForwardRangeNotSentinelSemiregular>);
50static_assert(!HasAdjacentFindR<ForwardRangeNotSentinelEqualityComparableWith>);
51static_assert(!HasAdjacentFindR<UncheckedRange<NotComparable>>);
52
53template <std::size_t N>
54struct Data {
55 std::array<int, N> input;
56 int expected;
57};
58
59template <class Iter, class Sent, std::size_t N>
60constexpr 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
73template <class Iter, class Sent = Iter>
74constexpr 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
91constexpr 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
177int main(int, char**) {
178 test();
179 static_assert(test());
180
181 return 0;
182}
183

source code of libcxx/test/std/algorithms/alg.nonmodifying/alg.adjacent.find/ranges.adjacent_find.pass.cpp