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

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