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 // UNSUPPORTED: libcpp-has-no-incomplete-ranges
13
14 // template<class T, class Proj = identity,
15 // indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
16 // constexpr ranges::minmax_result<const T&>
17 // ranges::minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {});
18 // template<copyable T, class Proj = identity,
19 // indirect_strict_weak_order<projected<const T*, Proj>> Comp = ranges::less>
20 // constexpr ranges::minmax_result<T>
21 // ranges::minmax(initializer_list<T> r, Comp comp = {}, Proj proj = {});
22 // template<input_range R, class Proj = identity,
23 // indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
24 // requires indirectly_copyable_storable<iterator_t<R>, range_value_t<R>*>
25 // constexpr ranges::minmax_result<range_value_t<R>>
26 // ranges::minmax(R&& r, Comp comp = {}, Proj proj = {});
27
28 #include <algorithm>
29 #include <array>
30 #include <cassert>
31 #include <functional>
32 #include <ranges>
33
34 #include "test_iterators.h"
35
36 template <class T>
37 concept HasMinMax = requires { std::ranges::minmax(std::declval<T>()); };
38
39 struct NoLessThanOp {};
40 struct NotTotallyOrdered {
41 int i;
operator <NotTotallyOrdered42 bool operator<(const NotTotallyOrdered& o) const { return i < o.i; }
43 };
44 struct MoveOnly {
45 MoveOnly(MoveOnly&&) = default;
46 MoveOnly& operator=(MoveOnly&&) = default;
47 MoveOnly(const MoveOnly&) = delete;
48 };
49
50 static_assert(!HasMinMax<int>);
51
52 static_assert(HasMinMax<int (&)[10]>); // make sure HasMinMax works with an array
53 static_assert(!HasMinMax<NoLessThanOp (&)[10]>);
54 static_assert(!HasMinMax<NotTotallyOrdered (&)[10]>);
55 static_assert(!HasMinMax<MoveOnly (&)[10]>);
56
57 static_assert(HasMinMax<std::initializer_list<int>>); // make sure HasMinMax works with an initializer_list
58 static_assert(!HasMinMax<std::initializer_list<NoLessThanOp>>);
59 static_assert(!HasMinMax<std::initializer_list<NotTotallyOrdered>>);
60 static_assert(!HasMinMax<std::initializer_list<MoveOnly>>);
61
62 static_assert(std::is_same_v<std::ranges::minmax_result<int>, std::ranges::min_max_result<int>>);
63
64 static_assert(std::is_same_v<decltype(std::ranges::minmax(1, 2)), std::ranges::minmax_result<const int&>>);
65
test_2_arguments()66 constexpr void test_2_arguments() {
67 const int one = 1;
68 const int two = 2;
69 {
70 auto result = std::ranges::minmax(one, two);
71 assert(result.min == 1);
72 assert(result.max == 2);
73 }
74
75 {
76 auto result = std::ranges::minmax(two, one);
77 assert(result.min == 1);
78 assert(result.max == 2);
79 }
80
81 {
82 // test comparator
83 auto result = std::ranges::minmax(one, two, std::ranges::greater{});
84 assert(result.min == 2);
85 assert(result.max == 1);
86 }
87
88 {
89 // test projection
90 auto result = std::ranges::minmax(one, two, std::ranges::less{}, [](int i) { return i == 1 ? 10 : i; });
91 assert(result.min == 2);
92 assert(result.max == 1);
93 }
94
95 {
96 // test if std::invoke is used for the predicate
97 struct S {
98 int i;
99 };
100 S a[3] = {S{2}, S{1}, S{3}};
101 std::same_as<std::ranges::minmax_result<const S&>> auto ret = std::ranges::minmax(a[0], a[1], {}, &S::i);
102 assert(&ret.min == &a[1]);
103 assert(&ret.max == &a[0]);
104 assert(ret.min.i == 1);
105 assert(ret.max.i == 2);
106 }
107
108 {
109 // check that std::invoke is used for the comparator
110 struct S {
111 int i;
112 constexpr bool comp(S rhs) const { return i < rhs.i; }
113 };
114 S a[] = {{2}, {5}};
115 auto ret = std::ranges::minmax(a[0], a[1], &S::comp);
116 assert(ret.min.i == 2);
117 assert(ret.max.i == 5);
118 }
119
120 {
121 // make sure that {a, b} is returned if b is not less than a
122 auto r = std::ranges::minmax(one, two);
123 assert(&r.min == &one);
124 assert(&r.max == &two);
125 }
126 }
127
test_initializer_list()128 constexpr void test_initializer_list() {
129 {
130 // test projection
131 auto proj = [](int i) { return i == 5 ? -100 : i; };
132 auto ret = std::ranges::minmax({7, 6, 9, 3, 5, 1, 2, 4}, std::ranges::less{}, proj);
133 assert(ret.min == 5);
134 assert(ret.max == 9);
135 }
136
137 {
138 // test comparator
139 auto ret = std::ranges::minmax({7, 6, 9, 3, 5, 1, 2, 4}, std::ranges::greater{});
140 assert(ret.min == 9);
141 assert(ret.max == 1);
142 }
143
144 {
145 // check predicate and projection call counts
146 int compares = 0;
147 int projections = 0;
148 auto comparator = [&](int a, int b) {
149 ++compares;
150 return a < b;
151 };
152 auto projection = [&](int a) {
153 ++projections;
154 return a;
155 };
156 std::same_as<std::ranges::minmax_result<int>> auto ret = std::ranges::minmax({1, 2, 3}, comparator, projection);
157 assert(ret.min == 1);
158 assert(ret.max == 3);
159 assert(compares == 3);
160 assert(projections == 6);
161 }
162
163 {
164 // check that std::invoke is used for the predicate
165 struct S {
166 int i;
167 };
168 std::same_as<std::ranges::minmax_result<S>> auto ret = std::ranges::minmax({S{2}, S{1}, S{3}}, {}, &S::i);
169 assert(ret.min.i == 1);
170 assert(ret.max.i == 3);
171 }
172
173 {
174 // check that std::invoke is used for the comparator
175 struct S {
176 int i;
177 constexpr bool comp(S rhs) const { return i < rhs.i; }
178 };
179 auto ret = std::ranges::minmax({S {1}, S {2}, S {3}, S {4}}, &S::comp);
180 assert(ret.min.i == 1);
181 assert(ret.max.i == 4);
182 }
183
184 {
185 // check that a single element works
186 auto ret = std::ranges::minmax({ 1 });
187 assert(ret.min == 1);
188 assert(ret.max == 1);
189 }
190
191 {
192 // check in ascending order
193 auto ret = std::ranges::minmax({1, 2, 3});
194 assert(ret.min == 1);
195 assert(ret.max == 3);
196 }
197
198 {
199 // check in descending order
200 auto ret = std::ranges::minmax({3, 2, 1});
201 assert(ret.min == 1);
202 assert(ret.max == 3);
203 }
204 }
205
206 template <class Iter, class Sent = Iter>
test_range_types()207 constexpr void test_range_types() {
208 {
209 // test projection
210 int a[] = {7, 6, 9, 3, 5, 1, 2, 4};
211 auto proj = [](int& i) { return i == 5 ? -100 : i; };
212 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 8)));
213 auto ret = std::ranges::minmax(range, std::ranges::less{}, proj);
214 assert(ret.min == 5);
215 assert(ret.max == 9);
216 }
217
218 {
219 // test comparator
220 int a[] = {7, 6, 9, 3, 5, 1, 2, 4};
221 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 8)));
222 auto ret = std::ranges::minmax(range, std::ranges::greater{});
223 assert(ret.min == 9);
224 assert(ret.max == 1);
225 }
226
227 {
228 // check that complexity requirements are met
229 int compares = 0;
230 int projections = 0;
231 auto comparator = [&](int x, int y) {
232 ++compares;
233 return x < y;
234 };
235 auto projection = [&](int x) {
236 ++projections;
237 return x;
238 };
239 int a[] = {1, 2, 3};
240 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
241 std::same_as<std::ranges::minmax_result<int>> auto ret = std::ranges::minmax(range, comparator, projection);
242 assert(ret.min == 1);
243 assert(ret.max == 3);
244 assert(compares == 3);
245 assert(projections == 6);
246 }
247
248 {
249 // check that a single element works
250 int a[] = { 1 };
251 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 1)));
252 auto ret = std::ranges::minmax(range);
253 assert(ret.min == 1);
254 assert(ret.max == 1);
255 }
256
257 {
258 // check in ascending order
259 int a[] = {1, 2, 3};
260 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
261 auto ret = std::ranges::minmax(range);
262 assert(ret.min == 1);
263 assert(ret.max == 3);
264 }
265
266 {
267 // check in descending order
268 int a[] = {3, 2, 1};
269 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
270 auto ret = std::ranges::minmax(range);
271 assert(ret.min == 1);
272 assert(ret.max == 3);
273 }
274 }
275
test_range()276 constexpr void test_range() {
277 test_range_types<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
278 test_range_types<forward_iterator<int*>>();
279 test_range_types<bidirectional_iterator<int*>>();
280 test_range_types<random_access_iterator<int*>>();
281 test_range_types<contiguous_iterator<int*>>();
282
283 {
284 // check that std::invoke is used for the predicate
285 struct S {
286 int i;
287 };
288 S b[3] = {S{2}, S{1}, S{3}};
289 std::same_as<std::ranges::minmax_result<S>> auto ret = std::ranges::minmax(b, {}, &S::i);
290 assert(ret.min.i == 1);
291 assert(ret.max.i == 3);
292 }
293
294 {
295 // check that std::invoke is used for the comparator
296 struct S {
297 int i;
298 constexpr bool comp(S rhs) const { return i < rhs.i; }
299 };
300 S a[] = {{1}, {2}, {3}, {4}};
301 auto ret = std::ranges::minmax(a, &S::comp);
302 assert(ret.min.i == 1);
303 assert(ret.max.i == 4);
304 }
305
306 {
307 // check that the leftmost value for min an rightmost for max are returned
308 struct S {
309 int comp;
310 int other;
311 };
312 S a[] = { {0, 0}, {0, 2}, {0, 1} };
313 auto ret = std::ranges::minmax(a, {}, &S::comp);
314 assert(ret.min.comp == 0);
315 assert(ret.max.comp == 0);
316 assert(ret.min.other == 0);
317 assert(ret.max.other == 1);
318 }
319
320 {
321 // check that an rvalue array works
322 int a[] = {1, 2, 3, 4};
323 auto ret = std::ranges::minmax(std::move(a));
324 assert(ret.min == 1);
325 assert(ret.max == 4);
326 }
327 }
328
test()329 constexpr bool test() {
330 test_2_arguments();
331 test_initializer_list();
332 test_range();
333
334 return true;
335 }
336
main(int,char **)337 int main(int, char**) {
338 test();
339 static_assert(test());
340
341 {
342 // check that the iterator isn't moved from multiple times
343 std::shared_ptr<int> a[] = { std::make_shared<int>(42) };
344 auto range = std::ranges::subrange(std::move_iterator(a), std::move_iterator(a + 1));
345 auto [min, max] = std::ranges::minmax(range);
346 assert(a[0] == nullptr);
347 assert(min != nullptr);
348 assert(max == min);
349 }
350
351 return 0;
352 }
353