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<forward_iterator I, sentinel_for<I> S, class Proj = identity,
15 // indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
16 // constexpr I ranges::min_element(I first, S last, Comp comp = {}, Proj proj = {});
17 //
18 // template<forward_range R, class Proj = identity,
19 // indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
20 // constexpr borrowed_iterator_t<R> ranges::min_element(R&& r, Comp comp = {}, Proj proj = {});
21
22 #include <algorithm>
23 #include <array>
24 #include <cassert>
25 #include <functional>
26 #include <random>
27 #include <ranges>
28
29 #include "test_macros.h"
30 #include "test_iterators.h"
31
32 template <class T>
33 concept HasMinElement = requires (T t) { std::ranges::min_element(t); };
34
35 struct NoLessThanOp {};
36 struct NotTotallyOrdered {
37 int i;
operator <NotTotallyOrdered38 bool operator<(const NotTotallyOrdered& o) const { return i < o.i; }
39 };
40
41 static_assert(HasMinElement<std::array<int, 0>>);
42 static_assert(!HasMinElement<int>);
43 static_assert(!HasMinElement<NoLessThanOp>);
44 static_assert(!HasMinElement<NotTotallyOrdered>);
45
46 template <class Iter>
test_iterators(Iter first,Iter last)47 constexpr void test_iterators(Iter first, Iter last) {
48 std::same_as<Iter> auto it = std::ranges::min_element(first, last);
49 if (first != last) {
50 for (Iter j = first; j != last; ++j)
51 assert(!(*j < *it));
52 } else {
53 assert(it == first);
54 }
55 }
56
57 template <class Range, class Iter>
test_range(Range && rng,Iter begin,Iter end)58 constexpr void test_range(Range&& rng, Iter begin, Iter end) {
59 std::same_as<Iter> auto it = std::ranges::min_element(std::forward<Range>(rng));
60 if (begin != end) {
61 for (Iter j = begin; j != end; ++j)
62 assert(!(*j < *it));
63 } else {
64 assert(it == begin);
65 }
66 }
67
68 template <class It>
test(std::initializer_list<int> a,int expected)69 constexpr void test(std::initializer_list<int> a, int expected) {
70 const int* first = a.begin();
71 const int* last = a.end();
72 {
73 std::same_as<It> auto it = std::ranges::min_element(It(first), It(last));
74 assert(base(it) == first + expected);
75 }
76 {
77 using Sent = sentinel_wrapper<It>;
78 std::same_as<It> auto it = std::ranges::min_element(It(first), Sent(It(last)));
79 assert(base(it) == first + expected);
80 }
81 {
82 auto range = std::ranges::subrange(It(first), It(last));
83 std::same_as<It> auto it = std::ranges::min_element(range);
84 assert(base(it) == first + expected);
85 }
86 {
87 using Sent = sentinel_wrapper<It>;
88 auto range = std::ranges::subrange(It(first), Sent(It(last)));
89 std::same_as<It> auto it = std::ranges::min_element(range);
90 assert(base(it) == first + expected);
91 }
92 }
93
94 template <class It>
test()95 constexpr bool test() {
96 test<It>({}, 0);
97 test<It>({1}, 0);
98 test<It>({1, 2}, 0);
99 test<It>({2, 1}, 1);
100 test<It>({2, 1, 2}, 1);
101 test<It>({2, 1, 1}, 1);
102
103 return true;
104 }
105
test_borrowed_range_and_sentinel()106 constexpr void test_borrowed_range_and_sentinel() {
107 int a[] = {7, 6, 1, 3, 5, 1, 2, 4};
108
109 int* ret = std::ranges::min_element(std::views::all(a));
110 assert(ret == a + 2);
111 assert(*ret == 1);
112 }
113
test_comparator()114 constexpr void test_comparator() {
115 int a[] = {7, 6, 9, 3, 5, 1, 2, 4};
116 int* ret = std::ranges::min_element(a, std::ranges::greater{});
117 assert(ret == a + 2);
118 assert(*ret == 9);
119 }
120
test_projection()121 constexpr void test_projection() {
122 int a[] = {7, 6, 9, 3, 5, 1, 2, 4};
123 {
124 int* ret = std::ranges::min_element(a, std::ranges::less{}, [](int i) { return i == 5 ? -100 : i; });
125 assert(ret == a + 4);
126 assert(*ret == 5);
127 }
128 {
129 int* ret = std::ranges::min_element(a, std::less<int*>{}, [](int& i) { return &i; });
130 assert(ret == a);
131 assert(*ret == 7);
132 }
133 }
134
135 struct Immobile {
136 int i;
137
ImmobileImmobile138 constexpr Immobile(int i_) : i(i_) {}
139 Immobile(const Immobile&) = delete;
140 Immobile(Immobile&&) = delete;
141
142 auto operator<=>(const Immobile&) const = default;
143 };
144
test_immobile()145 constexpr void test_immobile() {
146
147 Immobile arr[] {1, 2, 3};
148 assert(std::ranges::min_element(arr) == arr);
149 assert(std::ranges::min_element(arr, arr + 3) == arr);
150 }
151
test_dangling()152 constexpr void test_dangling() {
153 int compares = 0;
154 int projections = 0;
155 auto comparator = [&](int a, int b) {
156 ++compares;
157 return a < b;
158 };
159 auto projection = [&](int a) {
160 ++projections;
161 return a;
162 };
163 [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret =
164 std::ranges::min_element(std::array{1, 2, 3}, comparator, projection);
165 assert(compares == 2);
166 assert(projections == 4);
167 }
168
test()169 constexpr bool test() {
170
171 test<forward_iterator<const int*>>();
172 test<bidirectional_iterator<const int*>>();
173 test<random_access_iterator<const int*>>();
174 test<const int*>();
175
176 int a[] = {7, 6, 5, 3, 4, 2, 1, 8};
177 test_iterators(a, a + 8);
178 int a2[] = {7, 6, 5, 3, 4, 2, 1, 8};
179 test_range(a2, a2, a2 + 8);
180
181 test_borrowed_range_and_sentinel();
182 test_comparator();
183 test_projection();
184 test_dangling();
185
186 return true;
187 }
188
main(int,char **)189 int main(int, char**) {
190 test();
191 static_assert(test());
192
193 return 0;
194 }
195