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 | // UNSUPPORTED: c++03, c++11, c++14, c++17 |
10 | |
11 | // <algorithm> |
12 | // |
13 | // Range algorithms should work with proxy iterators. For example, the implementations should use `iter_swap` (which is |
14 | // a customization point) rather than plain `swap` (which might not work with certain valid iterators). |
15 | |
16 | #include <algorithm> |
17 | #include <numeric> |
18 | |
19 | #include <array> |
20 | #include <concepts> |
21 | #include <initializer_list> |
22 | #include <iterator> |
23 | #include <memory> |
24 | #include <random> |
25 | #include <ranges> |
26 | |
27 | #include "MoveOnly.h" |
28 | #include "test_iterators.h" |
29 | #include "test_macros.h" |
30 | |
31 | // (in, ...) |
32 | template <class Func, std::ranges::range Input, class... Args> |
33 | constexpr void test(Func&& func, Input& in, Args&&... args) { |
34 | (void)func(in.begin(), in.end(), std::forward<Args>(args)...); |
35 | (void)func(in, std::forward<Args>(args)...); |
36 | } |
37 | |
38 | // (in1, in2, ...) |
39 | template <class Func, std::ranges::range Range1, std::ranges::range Range2, class... Args> |
40 | constexpr void test(Func&& func, Range1& r1, Range2& r2, Args&&... args) { |
41 | (void)func(r1.begin(), r1.end(), r2.begin(), r2.end(), std::forward<Args>(args)...); |
42 | (void)func(r1, r2, std::forward<Args>(args)...); |
43 | } |
44 | |
45 | // (in, mid, ...) |
46 | template <class Func, std::ranges::range Input, class... Args> |
47 | constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t<Input> mid, Args&&... args) { |
48 | (void)func(in.begin(), mid, in.end(), std::forward<Args>(args)...); |
49 | (void)func(in, mid, std::forward<Args>(args)...); |
50 | } |
51 | |
52 | std::mt19937 rand_gen() { return std::mt19937(); } |
53 | |
54 | template <class T> |
55 | constexpr void run_tests() { |
56 | std::array input = {T{1}, T{2}, T{3}}; |
57 | ProxyRange in{input}; |
58 | std::array input2 = {T{4}, T{5}, T{6}}; |
59 | ProxyRange in2{input2}; |
60 | |
61 | auto mid = in.begin() + 1; |
62 | |
63 | std::array output = {T{4}, T{5}, T{6}, T{7}, T{8}, T{9}}; |
64 | ProxyIterator out{output.begin()}; |
65 | ProxyIterator out2{output.begin() + 1}; |
66 | ProxyIterator out_end{output.end()}; |
67 | |
68 | T num{2}; |
69 | Proxy<T&> x{num}; |
70 | int count = 1; |
71 | |
72 | auto unary_pred = [](const Proxy<T&>&) { return true; }; |
73 | auto binary_func = [](const Proxy<T>&, const Proxy<T>&) -> Proxy<T> { return Proxy<T>(T()); }; |
74 | auto gen = [] { return Proxy<T>(T{42}); }; |
75 | |
76 | test(std::ranges::any_of, in, unary_pred); |
77 | test(std::ranges::all_of, in, unary_pred); |
78 | #if TEST_STD_VER >= 23 |
79 | test(std::ranges::contains, in, x); |
80 | test(std::ranges::ends_with, in, in2); |
81 | #endif |
82 | test(std::ranges::none_of, in, unary_pred); |
83 | test(std::ranges::find, in, x); |
84 | test(std::ranges::find_if, in, unary_pred); |
85 | test(std::ranges::find_if_not, in, unary_pred); |
86 | #if TEST_STD_VER >= 23 |
87 | test(std::ranges::find_last, in, x); |
88 | test(std::ranges::find_last_if, in, unary_pred); |
89 | test(std::ranges::find_last_if_not, in, unary_pred); |
90 | #endif |
91 | test(std::ranges::find_first_of, in, in2); |
92 | test(std::ranges::adjacent_find, in); |
93 | test(std::ranges::mismatch, in, in2); |
94 | test(std::ranges::equal, in, in2); |
95 | test(std::ranges::lexicographical_compare, in, in2); |
96 | test(std::ranges::partition_point, in, unary_pred); |
97 | test(std::ranges::lower_bound, in, x); |
98 | test(std::ranges::upper_bound, in, x); |
99 | test(std::ranges::equal_range, in, x); |
100 | test(std::ranges::binary_search, in, x); |
101 | |
102 | test(std::ranges::min_element, in); |
103 | test(std::ranges::max_element, in); |
104 | test(std::ranges::minmax_element, in); |
105 | test(std::ranges::count, in, x); |
106 | test(std::ranges::count_if, in, unary_pred); |
107 | test(std::ranges::search, in, in2); |
108 | test(std::ranges::search_n, in, count, x); |
109 | test(std::ranges::find_end, in, in2); |
110 | #if TEST_STD_VER >= 23 |
111 | if constexpr (std::weakly_incrementable<T>) { |
112 | test(std::ranges::iota, in, x); |
113 | } |
114 | #endif |
115 | test(std::ranges::is_partitioned, in, unary_pred); |
116 | test(std::ranges::is_sorted, in); |
117 | test(std::ranges::is_sorted_until, in); |
118 | test(std::ranges::includes, in, in2); |
119 | test(std::ranges::is_heap, in); |
120 | test(std::ranges::is_heap_until, in); |
121 | test(std::ranges::is_permutation, in, in2); |
122 | test(std::ranges::for_each, in, std::identity{}); |
123 | std::ranges::for_each_n(in.begin(), count, std::identity{}); |
124 | if constexpr (std::copyable<T>) { |
125 | test(std::ranges::copy, in, out); |
126 | std::ranges::copy_n(in.begin(), count, out); |
127 | test(std::ranges::copy_if, in, out, unary_pred); |
128 | test(std::ranges::copy_backward, in, out_end); |
129 | } |
130 | test(std::ranges::move, in, out); |
131 | test(std::ranges::move_backward, in, out_end); |
132 | if constexpr (std::copyable<T>) { |
133 | test(std::ranges::fill, in, x); |
134 | std::ranges::fill_n(in.begin(), count, x); |
135 | test(std::ranges::transform, in, out, std::identity{}); |
136 | test(std::ranges::transform, in, in2, out, binary_func); |
137 | } |
138 | test(std::ranges::generate, in, gen); |
139 | std::ranges::generate_n(in.begin(), count, gen); |
140 | if constexpr (std::copyable<T>) { |
141 | test(std::ranges::remove_copy, in, out, x); |
142 | test(std::ranges::remove_copy_if, in, out, unary_pred); |
143 | test(std::ranges::replace, in, x, x); |
144 | test(std::ranges::replace_if, in, unary_pred, x); |
145 | test(std::ranges::replace_copy, in, out, x, x); |
146 | test(std::ranges::replace_copy_if, in, out, unary_pred, x); |
147 | } |
148 | #if TEST_STD_VER > 20 |
149 | test(std::ranges::starts_with, in, in2); |
150 | #endif |
151 | test(std::ranges::swap_ranges, in, in2); |
152 | if constexpr (std::copyable<T>) { |
153 | test(std::ranges::reverse_copy, in, out); |
154 | test_mid(std::ranges::rotate_copy, in, mid, out); |
155 | test(std::ranges::unique_copy, in, out); |
156 | test(std::ranges::partition_copy, in, out, out2, unary_pred); |
157 | test(std::ranges::partial_sort_copy, in, in2); |
158 | test(std::ranges::merge, in, in2, out); |
159 | test(std::ranges::set_difference, in, in2, out); |
160 | test(std::ranges::set_intersection, in, in2, out); |
161 | test(std::ranges::set_symmetric_difference, in, in2, out); |
162 | test(std::ranges::set_union, in, in2, out); |
163 | } |
164 | test(std::ranges::remove, in, x); |
165 | test(std::ranges::remove_if, in, unary_pred); |
166 | test(std::ranges::reverse, in); |
167 | test_mid(std::ranges::rotate, in, mid); |
168 | if (!std::is_constant_evaluated()) // `shuffle` isn't `constexpr`. |
169 | test(std::ranges::shuffle, in, rand_gen()); |
170 | if (!std::is_constant_evaluated()) { |
171 | if constexpr (std::copyable<T>) |
172 | test(std::ranges::sample, in, out, count, rand_gen()); |
173 | } |
174 | test(std::ranges::unique, in); |
175 | test(std::ranges::partition, in, unary_pred); |
176 | if (TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED) { |
177 | test(std::ranges::stable_partition, in, unary_pred); |
178 | } |
179 | test(std::ranges::sort, in); |
180 | if (TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED) { |
181 | test(std::ranges::stable_sort, in); |
182 | } |
183 | test_mid(std::ranges::partial_sort, in, mid); |
184 | test_mid(std::ranges::nth_element, in, mid); |
185 | if (TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED) { |
186 | test_mid(std::ranges::inplace_merge, in, mid); |
187 | } |
188 | test(std::ranges::make_heap, in); |
189 | test(std::ranges::push_heap, in); |
190 | test(std::ranges::pop_heap, in); |
191 | test(std::ranges::sort_heap, in); |
192 | test(std::ranges::prev_permutation, in); |
193 | test(std::ranges::next_permutation, in); |
194 | |
195 | // The algorithms that work on uninitialized memory have constraints that prevent proxy iterators from being used with |
196 | // them. |
197 | } |
198 | |
199 | constexpr bool test_all() { |
200 | run_tests<int>(); |
201 | run_tests<MoveOnly>(); |
202 | |
203 | return true; |
204 | } |
205 | |
206 | int main(int, char**) { |
207 | test_all(); |
208 | static_assert(test_all()); |
209 | |
210 | return 0; |
211 | } |
212 | |