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