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 bool ranges::binary_search(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 bool ranges::binary_search(R&& r, const T& value, Comp comp = {},
19// 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::binary_search(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::binary_search(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::binary_search(it, it, 1, pred); };
51
52static_assert(HasLowerBoundPred<std::ranges::less>);
53static_assert(!HasLowerBoundPred<IndirectUnaryPredicateNotCopyConstructible>);
54static_assert(!HasLowerBoundPred<IndirectUnaryPredicateNotPredicate>);
55
56template <class It, class Sent = It>
57constexpr void test_iterators() {
58 { // simple test
59 {
60 int a[] = {1, 2, 3, 4, 5, 6};
61 std::same_as<bool> auto ret = std::ranges::binary_search(It(a), Sent(It(a + 6)), 3);
62 assert(ret);
63 }
64 {
65 int a[] = {1, 2, 3, 4, 5, 6};
66 auto range = std::ranges::subrange(It(a), Sent(It(a + 6)));
67 std::same_as<bool> auto ret = std::ranges::binary_search(range, 3);
68 assert(ret);
69 }
70 }
71
72 { // check that the predicate is used
73 int a[] = {6, 5, 4, 3, 2, 1};
74 assert(std::ranges::binary_search(It(a), Sent(It(a + 6)), 2, std::ranges::greater{}));
75 auto range = std::ranges::subrange(It(a), Sent(It(a + 6)));
76 assert(std::ranges::binary_search(range, 2, std::ranges::greater{}));
77 }
78
79 { // check that the projection is used
80 int a[] = {1, 2, 3, 4, 5, 6};
81 assert(std::ranges::binary_search(It(a), Sent(It(a + 6)), 0, {}, [](int i) { return i - 3; }));
82 auto range = std::ranges::subrange(It(a), Sent(It(a + 6)));
83 assert(std::ranges::binary_search(range, 0, {}, [](int i) { return i - 3; }));
84 }
85
86 { // check that true is returned with multiple matches
87 int a[] = {1, 2, 2, 2, 3};
88 assert(std::ranges::binary_search(It(a), Sent(It(a + 5)), 2));
89 auto range = std::ranges::subrange(It(a), Sent(It(a + 5)));
90 assert(std::ranges::binary_search(range, 2));
91 }
92
93 { // check that false is returned if all elements compare less than
94 int a[] = {1, 2, 3, 4};
95 assert(!std::ranges::binary_search(It(a), Sent(It(a + 4)), 5));
96 auto range = std::ranges::subrange(It(a), Sent(It(a + 4)));
97 assert(!std::ranges::binary_search(range, 5));
98 }
99
100 { // check that false is returned if no element compares less than
101 int a[] = {1, 2, 3, 4};
102 assert(!std::ranges::binary_search(It(a), Sent(It(a + 4)), 0));
103 auto range = std::ranges::subrange(It(a), Sent(It(a + 4)));
104 assert(!std::ranges::binary_search(range, 0));
105 }
106
107 { // check that a single element works
108 int a[] = {1};
109 assert(std::ranges::binary_search(It(a), Sent(It(a + 1)), 1));
110 auto range = std::ranges::subrange(It(a), Sent(It(a + 1)));
111 assert(std::ranges::binary_search(range, 1));
112 }
113
114 { // check that an even number of elements works and that searching for the first element works
115 int a[] = {1, 2, 7, 8, 10, 11};
116 assert(std::ranges::binary_search(It(a), Sent(It(a + 6)), 1));
117 auto range = std::ranges::subrange(It(a), Sent(It(a + 6)));
118 assert(std::ranges::binary_search(range, 1));
119 }
120
121 { // check that an odd number of elements works and that searching for the last element works
122 int a[] = {1, 2, 7, 10, 11};
123 assert(std::ranges::binary_search(It(a), Sent(It(a + 5)), 11));
124 auto range = std::ranges::subrange(It(a), Sent(It(a + 5)));
125 assert(std::ranges::binary_search(range, 11));
126 }
127
128 { // check that it works when all but the searched for elements are equal
129 int a[] = {1, 2, 2, 2, 2};
130 assert(std::ranges::binary_search(It(a), Sent(It(a + 5)), 1));
131 auto range = std::ranges::subrange(It(a), Sent(It(a + 5)));
132 assert(std::ranges::binary_search(range, 1));
133 }
134
135 { // check that false is returned when the element doesn't exist, but an element with a greater value is in the range
136 int a[] = {1, 2, 4};
137 assert(!std::ranges::binary_search(It(a), Sent(It(a + 3)), 3));
138 auto range = std::ranges::subrange(It(a), Sent(It(a + 3)));
139 assert(!std::ranges::binary_search(range, 3));
140 }
141}
142
143constexpr bool test() {
144 test_iterators<int*>();
145 test_iterators<forward_iterator<int*>>();
146 test_iterators<forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();
147 test_iterators<bidirectional_iterator<int*>>();
148 test_iterators<random_access_iterator<int*>>();
149 test_iterators<contiguous_iterator<int*>>();
150 test_iterators<contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>>();
151
152 { // check that std::invoke is used
153 struct S { int check; int other; };
154 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}};
155 assert(std::ranges::binary_search(a, a + 6, 4, {}, &S::check));
156 assert(std::ranges::binary_search(a, 4, {}, &S::check));
157 }
158
159 { // check that an empty range works
160 std::array<int, 0> a;
161 assert(!std::ranges::binary_search(a.begin(), a.end(), 1));
162 assert(!std::ranges::binary_search(a, 1));
163 }
164
165 { // check that a non-const operator() works
166 struct Func {
167 constexpr bool operator()(const int& i, const int& j) { return i < j; }
168 };
169 int a[] = {1, 6, 9, 10, 23};
170 assert(std::ranges::binary_search(a, 6, Func{}));
171 assert(std::ranges::binary_search(a, a + 5, 6, Func{}));
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.sorting/alg.binary.search/binary.search/ranges.binary_search.pass.cpp