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_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
15 // constexpr ranges::minmax_element_result<I> ranges::minmax_element(I first, S last, Comp comp = {}, Proj proj = {});
16 //
17 // template<forward_range R, class Proj = identity,
18 // indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
19 // constexpr ranges::minmax_element_result<borrowed_iterator_t<R>>
20 // ranges::minmax_element(R&& r, Comp comp = {}, Proj proj = {});
21
22 #include <algorithm>
23 #include <array>
24 #include <cassert>
25 #include <functional>
26 #include <ranges>
27
28 #include "almost_satisfies_types.h"
29 #include "test_iterators.h"
30
31 template <class T>
32 concept HasMinMaxElementR = requires(T t) { std::ranges::minmax_element(t); };
33
34 struct NoLessThanOp {};
35 struct NotTotallyOrdered {
36 int i;
operator <NotTotallyOrdered37 bool operator<(const NotTotallyOrdered& o) const { return i < o.i; }
38 };
39
40 static_assert(HasMinMaxElementR<int (&)[10]>); // make sure HasMinMaxElementR works with an array
41 static_assert(!HasMinMaxElementR<NoLessThanOp (&)[10]>);
42 static_assert(!HasMinMaxElementR<NotTotallyOrdered (&)[10]>);
43
44 static_assert(HasMinMaxElementR<std::initializer_list<int>>); // make sure HasMinMaxElementR works with an initializer_list
45 static_assert(!HasMinMaxElementR<std::initializer_list<NoLessThanOp>>);
46 static_assert(!HasMinMaxElementR<std::initializer_list<NotTotallyOrdered>>);
47 static_assert(!HasMinMaxElementR<InputRangeNotDerivedFrom>);
48 static_assert(!HasMinMaxElementR<InputRangeNotIndirectlyReadable>);
49 static_assert(!HasMinMaxElementR<InputRangeNotInputOrOutputIterator>);
50 static_assert(!HasMinMaxElementR<InputRangeNotSentinelSemiregular>);
51 static_assert(!HasMinMaxElementR<InputRangeNotSentinelEqualityComparableWith>);
52
53 template <class It, class Sent = sentinel_wrapper<It>>
54 concept HasMinMaxElementIt = requires(It it, Sent sent) { std::ranges::minmax_element(it, sent); };
55 static_assert(HasMinMaxElementIt<int*>); // make sure HasMinMaxElementIt works
56 static_assert(!HasMinMaxElementIt<InputIteratorNotDerivedFrom>);
57 static_assert(!HasMinMaxElementIt<InputIteratorNotIndirectlyReadable>);
58 static_assert(!HasMinMaxElementIt<InputIteratorNotInputOrOutputIterator>);
59 static_assert(!HasMinMaxElementIt<int*, SentinelForNotSemiregular>);
60 static_assert(!HasMinMaxElementIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
61
62 static_assert(std::is_same_v<std::ranges::minmax_element_result<int>, std::ranges::min_max_result<int>>);
63
64 template <class It>
test_iterators(std::initializer_list<int> a,int expectedMin,int expectedMax)65 constexpr void test_iterators(std::initializer_list<int> a, int expectedMin, int expectedMax) {
66 using Expected = std::ranges::minmax_element_result<It>;
67 const int* first = a.begin();
68 const int* last = a.end();
69 {
70 std::same_as<Expected> auto it = std::ranges::minmax_element(It(first), It(last));
71 assert(base(it.min) == first + expectedMin);
72 assert(base(it.max) == first + expectedMax);
73 }
74 {
75 using Sent = sentinel_wrapper<It>;
76 std::same_as<Expected> auto it = std::ranges::minmax_element(It(first), Sent(It(last)));
77 assert(base(it.min) == first + expectedMin);
78 assert(base(it.max) == first + expectedMax);
79 }
80 {
81 auto range = std::ranges::subrange(It(first), It(last));
82 std::same_as<Expected> auto it = std::ranges::minmax_element(range);
83 assert(base(it.min) == first + expectedMin);
84 assert(base(it.max) == first + expectedMax);
85 }
86 {
87 using Sent = sentinel_wrapper<It>;
88 auto range = std::ranges::subrange(It(first), Sent(It(last)));
89 std::same_as<Expected> auto it = std::ranges::minmax_element(range);
90 assert(base(it.min) == first + expectedMin);
91 assert(base(it.max) == first + expectedMax);
92 }
93 }
94
95 template <class It>
test_iterators()96 constexpr bool test_iterators() {
97 test_iterators<It>({}, 0, 0);
98 test_iterators<It>({1}, 0, 0);
99 test_iterators<It>({1, 2}, 0, 1);
100 test_iterators<It>({2, 1}, 1, 0);
101 test_iterators<It>({2, 1, 2}, 1, 2);
102 test_iterators<It>({2, 1, 1}, 1, 0);
103 test_iterators<It>({2, 2, 1}, 2, 1);
104
105 return true;
106 }
107
test_borrowed_range_and_sentinel()108 constexpr void test_borrowed_range_and_sentinel() {
109 int a[] = {7, 6, 1, 3, 5, 1, 2, 4};
110
111 std::ranges::minmax_element_result<int*> ret = std::ranges::minmax_element(std::views::all(a));
112 assert(ret.min == a + 2);
113 assert(ret.max == a + 0);
114 assert(*ret.min == 1);
115 assert(*ret.max == 7);
116 }
117
test_comparator()118 constexpr void test_comparator() {
119 int a[] = {7, 6, 9, 3, 5, 1, 2, 4};
120 std::ranges::minmax_element_result<int*> ret = std::ranges::minmax_element(a, std::ranges::greater{});
121 assert(ret.min == a + 2);
122 assert(ret.max == a + 5);
123 assert(*ret.min == 9);
124 assert(*ret.max == 1);
125 }
126
test_projection()127 constexpr void test_projection() {
128 {
129 int a[] = {7, 6, 9, 3, 5, 1, 2, 4};
130 std::ranges::minmax_element_result<int*> ret =
131 std::ranges::minmax_element(a, std::ranges::less{}, [](int i) { return i == 5 ? -100 : i; });
132 assert(ret.min == a + 4);
133 assert(ret.max == a + 2);
134 assert(*ret.min == 5);
135 assert(*ret.max == 9);
136 }
137 {
138 int a[] = {7, 6, 9, 3, 5, 1, 2, 4};
139 std::ranges::minmax_element_result<int*> ret =
140 std::ranges::minmax_element(a, std::less<int*>{}, [](int& i) { return &i; });
141 assert(ret.min == a + 0);
142 assert(ret.max == a + 7);
143 assert(*ret.min == 7);
144 assert(*ret.max == 4);
145 }
146 }
147
148 struct Immobile {
149 int i;
150
ImmobileImmobile151 constexpr Immobile(int i_) : i(i_) {}
152 Immobile(const Immobile&) = delete;
153 Immobile(Immobile&&) = delete;
154
155 auto operator<=>(const Immobile&) const = default;
156 };
157
test_immobile()158 constexpr void test_immobile() {
159 {
160 Immobile arr[]{1, 2, 3};
161 auto ret = std::ranges::minmax_element(arr);
162 assert(ret.min == arr + 0);
163 assert(ret.max == arr + 2);
164 }
165 {
166 Immobile arr[]{1, 2, 3};
167 auto ret = std::ranges::minmax_element(arr, arr + 3);
168 assert(ret.min == arr + 0);
169 assert(ret.max == arr + 2);
170 }
171 }
172
test_dangling()173 constexpr void test_dangling() {
174 int compares = 0;
175 int projections = 0;
176 auto comparator = [&](int a, int b) {
177 ++compares;
178 return a < b;
179 };
180 auto projection = [&](int a) {
181 ++projections;
182 return a;
183 };
184 [[maybe_unused]] std::same_as<std::ranges::minmax_element_result<std::ranges::dangling>> auto ret =
185 std::ranges::minmax_element(std::array{1, 2, 3}, comparator, projection);
186 assert(compares == 3);
187 assert(projections == 6);
188 }
189
test()190 constexpr bool test() {
191 test_iterators<forward_iterator<const int*>>();
192 test_iterators<bidirectional_iterator<const int*>>();
193 test_iterators<random_access_iterator<const int*>>();
194 test_iterators<contiguous_iterator<const int*>>();
195 test_iterators<const int*>();
196 test_iterators<int*>();
197
198 test_borrowed_range_and_sentinel();
199 test_comparator();
200 test_projection();
201 test_dangling();
202
203 { // check that std::invoke is used
204 {
205 struct S {
206 int i;
207 };
208 S b[3] = {S{2}, S{1}, S{3}};
209 std::same_as<std::ranges::minmax_element_result<S*>> auto ret = std::ranges::minmax_element(b, {}, &S::i);
210 assert(ret.min->i == 1);
211 assert(ret.max->i == 3);
212 assert(ret.min == b + 1);
213 assert(ret.max == b + 2);
214 }
215 {
216 struct S {
217 int i;
218 };
219 S b[3] = {S{2}, S{1}, S{3}};
220 std::same_as<std::ranges::minmax_element_result<S*>> auto ret = std::ranges::minmax_element(b, b + 3, {}, &S::i);
221 assert(ret.min->i == 1);
222 assert(ret.max->i == 3);
223 assert(ret.min == b + 1);
224 assert(ret.max == b + 2);
225 }
226 }
227
228 { // check that the leftmost value for min an rightmost for max are returned
229 {
230 struct S {
231 int comp;
232 int other;
233 };
234 S a[] = { {0, 0}, {0, 2}, {0, 1} };
235 auto ret = std::ranges::minmax_element(a, a + 3, {}, &S::comp);
236 assert(ret.min->comp == 0);
237 assert(ret.max->comp == 0);
238 assert(ret.min->other == 0);
239 assert(ret.max->other == 1);
240 }
241 {
242 struct S {
243 int comp;
244 int other;
245 };
246 S a[] = { {0, 0}, {0, 2}, {0, 1} };
247 auto ret = std::ranges::minmax_element(a, {}, &S::comp);
248 assert(ret.min->comp == 0);
249 assert(ret.max->comp == 0);
250 assert(ret.min->other == 0);
251 assert(ret.max->other == 1);
252 }
253 }
254
255 { // check that an empty range works
256 {
257 std::array<int, 0> a = {};
258 auto ret = std::ranges::minmax_element(a.begin(), a.end());
259 assert(ret.min == a.begin());
260 assert(ret.max == a.begin());
261 }
262 {
263 std::array<int, 0> a = {};
264 auto ret = std::ranges::minmax_element(a);
265 assert(ret.min == a.begin());
266 assert(ret.max == a.begin());
267 }
268 }
269
270 { // check in ascending order
271 {
272 int a[] = {1, 2, 3};
273 auto ret = std::ranges::minmax_element(a, a + 3);
274 assert(ret.min == a + 0);
275 assert(ret.max == a + 2);
276 assert(*ret.min == 1);
277 assert(*ret.max == 3);
278 }
279 {
280 int a[] = {1, 2, 3};
281 auto ret = std::ranges::minmax_element(a);
282 assert(ret.min == a + 0);
283 assert(ret.max == a + 2);
284 assert(*ret.min == 1);
285 assert(*ret.max == 3);
286 }
287 }
288
289 { // check in descending order
290 {
291 int a[] = {3, 2, 1};
292 auto ret = std::ranges::minmax_element(a, a + 3);
293 assert(ret.min == a + 2);
294 assert(ret.max == a + 0);
295 assert(*ret.min == 1);
296 assert(*ret.max == 3);
297 }
298 {
299 int a[] = {3, 2, 1};
300 auto ret = std::ranges::minmax_element(a);
301 assert(ret.min == a + 2);
302 assert(ret.max == a + 0);
303 assert(*ret.min == 1);
304 assert(*ret.max == 3);
305 }
306 }
307
308 return true;
309 }
310
main(int,char **)311 int main(int, char**) {
312 test();
313 static_assert(test());
314
315 return 0;
316 }
317