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
31template <class T>
32concept HasMinMaxElementR = requires(T t) { std::ranges::minmax_element(t); };
33
34struct NoLessThanOp {};
35struct NotTotallyOrdered {
36 int i;
37 bool operator<(const NotTotallyOrdered& o) const { return i < o.i; }
38};
39
40static_assert(HasMinMaxElementR<int (&)[10]>); // make sure HasMinMaxElementR works with an array
41static_assert(!HasMinMaxElementR<NoLessThanOp (&)[10]>);
42static_assert(!HasMinMaxElementR<NotTotallyOrdered (&)[10]>);
43
44static_assert(HasMinMaxElementR<std::initializer_list<int>>); // make sure HasMinMaxElementR works with an initializer_list
45static_assert(!HasMinMaxElementR<std::initializer_list<NoLessThanOp>>);
46static_assert(!HasMinMaxElementR<std::initializer_list<NotTotallyOrdered>>);
47static_assert(!HasMinMaxElementR<InputRangeNotDerivedFrom>);
48static_assert(!HasMinMaxElementR<InputRangeNotIndirectlyReadable>);
49static_assert(!HasMinMaxElementR<InputRangeNotInputOrOutputIterator>);
50static_assert(!HasMinMaxElementR<InputRangeNotSentinelSemiregular>);
51static_assert(!HasMinMaxElementR<InputRangeNotSentinelEqualityComparableWith>);
52
53template <class It, class Sent = sentinel_wrapper<It>>
54concept HasMinMaxElementIt = requires(It it, Sent sent) { std::ranges::minmax_element(it, sent); };
55static_assert(HasMinMaxElementIt<int*>); // make sure HasMinMaxElementIt works
56static_assert(!HasMinMaxElementIt<InputIteratorNotDerivedFrom>);
57static_assert(!HasMinMaxElementIt<InputIteratorNotIndirectlyReadable>);
58static_assert(!HasMinMaxElementIt<InputIteratorNotInputOrOutputIterator>);
59static_assert(!HasMinMaxElementIt<int*, SentinelForNotSemiregular>);
60static_assert(!HasMinMaxElementIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
61
62static_assert(std::is_same_v<std::ranges::minmax_element_result<int>, std::ranges::min_max_result<int>>);
63
64template <class It>
65constexpr 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
95template <class It>
96constexpr 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
108constexpr 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
118constexpr 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
127constexpr 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
148struct Immobile {
149 int i;
150
151 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
158constexpr 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
173constexpr 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
190constexpr 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{.i: 2}, S{.i: 1}, S{.i: 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{.i: 2}, S{.i: 1}, S{.i: 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[] = { {.comp: 0, .other: 0}, {.comp: 0, .other: 2}, {.comp: 0, .other: 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[] = { {.comp: 0, .other: 0}, {.comp: 0, .other: 2}, {.comp: 0, .other: 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
311int main(int, char**) {
312 test();
313 static_assert(test());
314
315 return 0;
316}
317

source code of libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax_element.pass.cpp