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