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, ...)
32template <class Func, std::ranges::range Input, class... Args>
33constexpr 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, ...)
39template <class Func, std::ranges::range Range1, std::ranges::range Range2, class... Args>
40constexpr 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, ...)
46template <class Func, std::ranges::range Input, class... Args>
47constexpr 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
52std::mt19937 rand_gen() { return std::mt19937(); }
53
54template <class T>
55constexpr 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
199constexpr bool test_all() {
200 run_tests<int>();
201 run_tests<MoveOnly>();
202
203 return true;
204}
205
206int main(int, char**) {
207 test_all();
208 static_assert(test_all());
209
210 return 0;
211}
212

source code of libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp