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// UNSUPPORTED: c++03, c++11, c++14, c++17
10
11// template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
12// indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
13// constexpr I ranges::lower_bound(I first, S last, const T& value, Comp comp = {},
14// Proj proj = {});
15// template<forward_range R, class T, class Proj = identity,
16// indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
17// ranges::less>
18// constexpr borrowed_iterator_t<R>
19// ranges::lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
20
21#include <algorithm>
22#include <array>
23#include <cassert>
24#include <functional>
25#include <ranges>
26
27#include "almost_satisfies_types.h"
28#include "test_iterators.h"
29
30struct NotLessThanComparable {};
31
32template <class It, class Sent = It>
33concept HasLowerBoundIt = requires(It it, Sent sent) { std::ranges::lower_bound(it, sent, 1); };
34
35static_assert(HasLowerBoundIt<int*>);
36static_assert(!HasLowerBoundIt<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>);
37static_assert(!HasLowerBoundIt<ForwardIteratorNotDerivedFrom>);
38static_assert(!HasLowerBoundIt<ForwardIteratorNotIncrementable>);
39static_assert(!HasLowerBoundIt<NotLessThanComparable*>);
40
41template <class Range>
42concept HasLowerBoundR = requires(Range range) { std::ranges::lower_bound(range, 1); };
43
44static_assert(HasLowerBoundR<std::array<int, 1>>);
45static_assert(!HasLowerBoundR<ForwardRangeNotDerivedFrom>);
46static_assert(!HasLowerBoundR<ForwardRangeNotIncrementable>);
47static_assert(!HasLowerBoundR<UncheckedRange<NotLessThanComparable*>>);
48
49template <class Pred>
50concept HasLowerBoundPred = requires(int* it, Pred pred) {std::ranges::lower_bound(it, it, 1, pred); };
51
52static_assert(HasLowerBoundPred<std::ranges::less>);
53static_assert(!HasLowerBoundPred<IndirectUnaryPredicateNotCopyConstructible>);
54static_assert(!HasLowerBoundPred<IndirectUnaryPredicateNotPredicate>);
55
56template <class It>
57constexpr void test_iterators() {
58 { // simple test
59 {
60 int a[] = {1, 2, 3, 4, 5, 6};
61 std::same_as<It> auto ret = std::ranges::lower_bound(It(a), It(a + 6), 3);
62 assert(base(ret) == a + 2);
63 }
64 {
65 int a[] = {1, 2, 3, 4, 5, 6};
66 auto range = std::ranges::subrange(It(a), It(a + 6));
67 std::same_as<It> auto ret = std::ranges::lower_bound(range, 3);
68 assert(base(ret) == a + 2);
69 }
70 }
71
72 { // check that the predicate is used
73 {
74 int a[] = {6, 5, 4, 3, 2, 1};
75 auto ret = std::ranges::lower_bound(It(a), It(a + 6), 2, std::ranges::greater{});
76 assert(base(ret) == a + 4);
77 }
78 {
79 int a[] = {6, 5, 4, 3, 2, 1};
80 auto range = std::ranges::subrange(It(a), It(a + 6));
81 auto ret = std::ranges::lower_bound(range, 2, std::ranges::greater{});
82 assert(base(ret) == a + 4);
83 }
84 }
85
86 { // check that the projection is used
87 {
88 int a[] = {1, 2, 3, 4, 5, 6};
89 auto ret = std::ranges::lower_bound(It(a), It(a + 6), 0, {}, [](int i) { return i - 3; });
90 assert(base(ret) == a + 2);
91 }
92 {
93 int a[] = {1, 2, 3, 4, 5, 6};
94 auto range = std::ranges::subrange(It(a), It(a + 6));
95 auto ret = std::ranges::lower_bound(range, 0, {}, [](int i) { return i - 3; });
96 assert(base(ret) == a + 2);
97 }
98 }
99
100 { // check that the last lower bound is returned
101 {
102 int a[] = {1, 2, 2, 2, 3};
103 auto ret = std::ranges::lower_bound(It(a), It(a + 5), 2);
104 assert(base(ret) == a + 1);
105 }
106 {
107 int a[] = {1, 2, 2, 2, 3};
108 auto range = std::ranges::subrange(It(a), It(a + 5));
109 auto ret = std::ranges::lower_bound(range, 2);
110 assert(base(ret) == a + 1);
111 }
112 }
113
114 { // check that end is returned if all elements compare less than
115 {
116 int a[] = {1, 2, 3, 4};
117 auto ret = std::ranges::lower_bound(It(a), It(a + 4), 5);
118 assert(base(ret) == a + 4);
119 }
120 {
121 int a[] = {1, 2, 3, 4};
122 auto range = std::ranges::subrange(It(a), It(a + 4));
123 auto ret = std::ranges::lower_bound(range, 5);
124 assert(base(ret) == a + 4);
125 }
126 }
127
128 { // check that the first element is returned if no element compares less than
129 {
130 int a[] = {1, 2, 3, 4};
131 auto ret = std::ranges::lower_bound(It(a), It(a + 4), 0);
132 assert(base(ret) == a);
133 }
134 {
135 int a[] = {1, 2, 3, 4};
136 auto range = std::ranges::subrange(It(a), It(a + 4));
137 auto ret = std::ranges::lower_bound(range, 0);
138 assert(base(ret) == a);
139 }
140 }
141
142 { // check that a single element works
143 {
144 int a[] = {1};
145 auto ret = std::ranges::lower_bound(It(a), It(a + 1), 1);
146 assert(base(ret) == a);
147 }
148 {
149 int a[] = {1};
150 auto range = std::ranges::subrange(It(a), It(a + 1));
151 auto ret = std::ranges::lower_bound(range, 1);
152 assert(base(ret) == a);
153 }
154 }
155
156 { // check that an even number of elements works
157 {
158 int a[] = {1, 3, 6, 6, 7, 8};
159 auto ret = std::ranges::lower_bound(It(a), It(a + 6), 6);
160 assert(base(ret) == a + 2);
161 }
162 {
163 int a[] = {1, 3, 6, 6, 7, 8};
164 auto range = std::ranges::subrange(It(a), It(a + 6));
165 auto ret = std::ranges::lower_bound(range, 6);
166 assert(base(ret) == a + 2);
167 }
168 }
169
170 { // check that an odd number of elements works
171 {
172 int a[] = {1, 3, 6, 6, 7};
173 auto ret = std::ranges::lower_bound(It(a), It(a + 5), 6);
174 assert(base(ret) == a + 2);
175 }
176 {
177 int a[] = {1, 3, 6, 6, 7};
178 auto range = std::ranges::subrange(It(a), It(a + 5));
179 auto ret = std::ranges::lower_bound(range, 6);
180 assert(base(ret) == a + 2);
181 }
182 }
183
184 { // check that it works when all but the searched for element are equal
185 {
186 int a[] = {1, 6, 6, 6, 6, 6};
187 auto ret = std::ranges::lower_bound(It(a), It(a + 6), 1);
188 assert(base(ret) == a);
189 }
190 {
191 int a[] = {1, 6, 6, 6, 6, 6};
192 auto range = std::ranges::subrange(It(a), It(a + 6));
193 auto ret = std::ranges::lower_bound(range, 1);
194 assert(base(ret) == a);
195 }
196 }
197
198 { // check that the middle of a range is returned when there are smaller and larger elements
199 {
200 int a[] = {1, 2, 3, 4, 6, 7, 8};
201 auto ret = std::ranges::lower_bound(It(a), It(a + 7), 5);
202 assert(base(ret) == a + 4);
203 assert(*ret == 6);
204 }
205 {
206 int a[] = {1, 2, 3, 4, 6, 7, 8};
207 auto range = std::ranges::subrange(It(a), It(a + 7));
208 auto ret = std::ranges::lower_bound(range, 5);
209 assert(base(ret) == a + 4);
210 assert(*ret == 6);
211 }
212 }
213}
214
215constexpr bool test() {
216 test_iterators<int*>();
217 test_iterators<forward_iterator<int*>>();
218 test_iterators<bidirectional_iterator<int*>>();
219 test_iterators<random_access_iterator<int*>>();
220 test_iterators<contiguous_iterator<int*>>();
221
222 { // check that std::invoke is used for the projections
223 {
224 struct S { int check; int other; };
225 S a[] = {{.check: 1, .other: 6}, {.check: 2, .other: 5}, {.check: 3, .other: 4}, {.check: 4, .other: 3}, {.check: 5, .other: 2}, {.check: 6, .other: 1}};
226 auto ret = std::ranges::lower_bound(a, a + 6, 4, {}, &S::check);
227 assert(ret == a + 3);
228 }
229 {
230 struct S { int check; int other; };
231 S a[] = {{.check: 1, .other: 6}, {.check: 2, .other: 5}, {.check: 3, .other: 4}, {.check: 4, .other: 3}, {.check: 5, .other: 2}, {.check: 6, .other: 1}};
232 auto ret = std::ranges::lower_bound(a, 4, {}, &S::check);
233 assert(ret == a + 3);
234 }
235 }
236
237 { // check that std::invoke is used for the predicate
238 struct S {
239 int check;
240 int other;
241
242 constexpr bool compare(const S& s) const {
243 return check < s.check;
244 }
245 };
246 {
247 S a[] = {{.check: 1, .other: 6}, {.check: 2, .other: 5}, {.check: 3, .other: 4}, {.check: 4, .other: 3}, {.check: 5, .other: 2}, {.check: 6, .other: 1}};
248 auto ret = std::ranges::lower_bound(a, a + 6, S{4, 0}, &S::compare);
249 assert(ret == a + 3);
250 }
251 {
252 S a[] = {{.check: 1, .other: 6}, {.check: 2, .other: 5}, {.check: 3, .other: 4}, {.check: 4, .other: 3}, {.check: 5, .other: 2}, {.check: 6, .other: 1}};
253 auto ret = std::ranges::lower_bound(a, S{4, 0}, &S::compare);
254 assert(ret == a + 3);
255 }
256 }
257
258 { // check that an empty range works
259 {
260 std::array<int, 0> a;
261 auto ret = std::ranges::lower_bound(a.begin(), a.end(), 1);
262 assert(ret == a.end());
263 }
264 {
265 std::array<int, 0> a;
266 auto ret = std::ranges::lower_bound(a, 1);
267 assert(ret == a.end());
268 }
269 }
270
271 { // check that ranges::dangling is returned
272 [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret = std::ranges::lower_bound(std::array{1, 2}, 1);
273 }
274
275 { // check that an iterator is returned with a borrowing range
276 int a[] = {1, 2, 3};
277 std::same_as<int*> auto ret = std::ranges::lower_bound(std::views::all(a), 1);
278 assert(ret == a);
279 }
280
281 return true;
282}
283
284int main(int, char**) {
285 test();
286 static_assert(test());
287
288 return 0;
289}
290

source code of libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges.lower_bound.pass.cpp