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 use `std::invoke` to call the given projection(s) (and predicates, where applicable).
14
15#include <algorithm>
16
17#include <array>
18#include <concepts>
19#include <initializer_list>
20#include <iterator>
21#include <ranges>
22#include <type_traits>
23
24#include "test_macros.h"
25
26struct Foo {
27 int val;
28 constexpr bool unary_pred() const { return val > 0; }
29 constexpr bool binary_pred(const Foo& rhs) const { return val < rhs.val; }
30 constexpr auto operator<=>(const Foo&) const = default;
31};
32
33struct Bar {
34 Foo val;
35 Bar create() const { return Bar(); }
36};
37
38// Invokes both the (iterator, sentinel, ...) and the (range, ...) overloads of the given algorithm function object.
39
40// (in, ...)
41template <class Func, std::ranges::range Input, class... Args>
42constexpr void test(Func&& func, Input& in, Args&&... args) {
43 (void)func(in.begin(), in.end(), std::forward<Args>(args)...);
44 (void)func(in, std::forward<Args>(args)...);
45}
46
47// (in1, in2, ...)
48template <class Func, std::ranges::range Input, class... Args>
49constexpr void test(Func&& func, Input& in1, Input& in2, Args&&... args) {
50 (void)func(in1.begin(), in1.end(), in2.begin(), in2.end(), std::forward<Args>(args)...);
51 (void)func(in1, in2, std::forward<Args>(args)...);
52}
53
54// (in, mid, ...)
55template <class Func, std::ranges::range Input, class... Args>
56constexpr void test_mid(Func&& func, Input& in, std::ranges::iterator_t<Input> mid, Args&&... args) {
57 (void)func(in.begin(), mid, in.end(), std::forward<Args>(args)...);
58 (void)func(in, mid, std::forward<Args>(args)...);
59}
60
61constexpr bool test_all() {
62 std::array in = {Bar{.val: Foo{.val: 1}}, Bar{.val: Foo{.val: 2}}, Bar{.val: Foo{.val: 3}}};
63 std::array in2 = {Bar{.val: Foo{.val: 4}}, Bar{.val: Foo{.val: 5}}, Bar{.val: Foo{.val: 6}}};
64 auto mid = in.begin() + 1;
65
66 std::array output = {Bar{.val: Foo{.val: 7}}, Bar{.val: Foo{.val: 8}}, Bar{.val: Foo{.val: 9}}, Bar{.val: Foo{.val: 10}}, Bar{.val: Foo{.val: 11}}, Bar{.val: Foo{.val: 12}}};
67 auto out = output.begin();
68 auto out2 = output.begin() + 1;
69
70 Bar a{.val: Foo{.val: 1}};
71 Bar b{.val: Foo{.val: 2}};
72 Bar c{.val: Foo{.val: 3}};
73
74 Foo x{.val: 2};
75 std::size_t count = 1;
76
77 test(std::ranges::any_of, in, &Foo::unary_pred, &Bar::val);
78 test(std::ranges::all_of, in, &Foo::unary_pred, &Bar::val);
79#if TEST_STD_VER >= 23
80 test(std::ranges::contains, in, x, &Bar::val);
81 test(std::ranges::ends_with, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
82#endif
83 test(std::ranges::none_of, in, &Foo::unary_pred, &Bar::val);
84 test(std::ranges::find, in, x, &Bar::val);
85 test(std::ranges::find_if, in, &Foo::unary_pred, &Bar::val);
86 test(std::ranges::find_if_not, in, &Foo::unary_pred, &Bar::val);
87 test(std::ranges::find_first_of, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
88 test(std::ranges::adjacent_find, in, &Foo::binary_pred, &Bar::val);
89 test(std::ranges::mismatch, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
90 test(std::ranges::equal, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
91 test(std::ranges::lexicographical_compare, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
92 test(std::ranges::partition_point, in, &Foo::unary_pred, &Bar::val);
93 test(std::ranges::lower_bound, in, x, &Foo::binary_pred, &Bar::val);
94 test(std::ranges::upper_bound, in, x, &Foo::binary_pred, &Bar::val);
95 test(std::ranges::equal_range, in, x, &Foo::binary_pred, &Bar::val);
96 test(std::ranges::binary_search, in, x, &Foo::binary_pred, &Bar::val);
97
98 // min
99 (void)std::ranges::min(a, b, &Foo::binary_pred, &Bar::val);
100 (void)std::ranges::min(std::initializer_list<Bar>{a, b}, &Foo::binary_pred, &Bar::val);
101 (void)std::ranges::min(in, &Foo::binary_pred, &Bar::val);
102 // max
103 (void)std::ranges::max(a, b, &Foo::binary_pred, &Bar::val);
104 (void)std::ranges::max(std::initializer_list<Bar>{a, b}, &Foo::binary_pred, &Bar::val);
105 (void)std::ranges::max(in, &Foo::binary_pred, &Bar::val);
106 // minmax
107 (void)std::ranges::minmax(a, b, &Foo::binary_pred, &Bar::val);
108 (void)std::ranges::minmax(std::initializer_list<Bar>{a, b}, &Foo::binary_pred, &Bar::val);
109 (void)std::ranges::minmax(in, &Foo::binary_pred, &Bar::val);
110
111 test(std::ranges::min_element, in, &Foo::binary_pred, &Bar::val);
112 test(std::ranges::max_element, in, &Foo::binary_pred, &Bar::val);
113 test(std::ranges::minmax_element, in, &Foo::binary_pred, &Bar::val);
114 test(std::ranges::count, in, x, &Bar::val);
115 test(std::ranges::count_if, in, &Foo::unary_pred, &Bar::val);
116 test(std::ranges::search, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
117 test(std::ranges::search_n, in, count, x, &Foo::binary_pred, &Bar::val);
118 test(std::ranges::find_end, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
119 test(std::ranges::is_partitioned, in, &Foo::unary_pred, &Bar::val);
120 test(std::ranges::is_sorted, in, &Foo::binary_pred, &Bar::val);
121 test(std::ranges::is_sorted_until, in, &Foo::binary_pred, &Bar::val);
122 test(std::ranges::includes, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
123 test(std::ranges::is_heap, in, &Foo::binary_pred, &Bar::val);
124 test(std::ranges::is_heap_until, in, &Foo::binary_pred, &Bar::val);
125 (void)std::ranges::clamp(b, a, c, &Foo::binary_pred, &Bar::val);
126 test(std::ranges::is_permutation, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
127 test(std::ranges::for_each, in, &Foo::unary_pred, &Bar::val);
128 std::ranges::for_each_n(in.begin(), count, &Foo::unary_pred, &Bar::val);
129 // `copy`, `copy_n` and `copy_backward` have neither a projection nor a predicate.
130 test(std::ranges::copy_if, in, out, &Foo::unary_pred, &Bar::val);
131 // `move` and `move_backward` have neither a projection nor a predicate.
132 // `fill` and `fill_n` have neither a projection nor a predicate.
133 {
134 std::array out_transform = {false, true, true};
135 test(std::ranges::transform, in, out_transform.begin(), &Foo::unary_pred, &Bar::val);
136 }
137 // Whether `ranges::generate{,_n}` invokes `gen` via `std::invoke` is not observable.
138 test(std::ranges::remove_copy, in, out, x, &Bar::val);
139 test(std::ranges::remove_copy_if, in, out, &Foo::unary_pred, &Bar::val);
140 // `replace*` algorithms only use the projection to compare the elements, not to write them.
141 test(std::ranges::replace, in, x, a, &Bar::val);
142 test(std::ranges::replace_if, in, &Foo::unary_pred, a, &Bar::val);
143 test(std::ranges::replace_copy, in, out, x, a, &Bar::val);
144 test(std::ranges::replace_copy_if, in, out, &Foo::unary_pred, a, &Bar::val);
145 // `swap_ranges` has neither a projection nor a predicate.
146 // `reverse_copy` has neither a projection nor a predicate.
147 // `rotate_copy` has neither a projection nor a predicate.
148 // For `sample`, whether the given generator is invoked via `std::invoke` is not observable.
149 test(std::ranges::unique_copy, in, out, &Foo::binary_pred, &Bar::val);
150 test(std::ranges::partition_copy, in, out, out2, &Foo::unary_pred, &Bar::val);
151 test(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
152 test(std::ranges::merge, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
153#if TEST_STD_VER > 20
154 test(std::ranges::starts_with, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
155#endif
156 test(std::ranges::set_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
157 test(std::ranges::set_intersection, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
158 test(std::ranges::set_symmetric_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
159 test(std::ranges::set_union, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
160 test(std::ranges::remove, in, x, &Bar::val);
161 test(std::ranges::remove_if, in, &Foo::unary_pred, &Bar::val);
162 // `reverse` has neither a projection nor a predicate.
163 // `rotate` has neither a projection nor a predicate.
164 // For `shuffle`, whether the given generator is invoked via `std::invoke` is not observable.
165 test(std::ranges::unique, in, &Foo::binary_pred, &Bar::val);
166 test(std::ranges::partition, in, &Foo::unary_pred, &Bar::val);
167 if (TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED) {
168 test(std::ranges::stable_partition, in, &Foo::unary_pred, &Bar::val);
169 }
170 test(std::ranges::sort, in, &Foo::binary_pred, &Bar::val);
171 if (TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED) {
172 test(std::ranges::stable_sort, in, &Foo::binary_pred, &Bar::val);
173 }
174 test_mid(std::ranges::partial_sort, in, mid, &Foo::binary_pred, &Bar::val);
175 test_mid(std::ranges::nth_element, in, mid, &Foo::binary_pred, &Bar::val);
176 if (TEST_STD_AT_LEAST_26_OR_RUNTIME_EVALUATED) {
177 test_mid(std::ranges::inplace_merge, in, mid, &Foo::binary_pred, &Bar::val);
178 }
179 test(std::ranges::make_heap, in, &Foo::binary_pred, &Bar::val);
180 test(std::ranges::push_heap, in, &Foo::binary_pred, &Bar::val);
181 test(std::ranges::pop_heap, in, &Foo::binary_pred, &Bar::val);
182 test(std::ranges::sort_heap, in, &Foo::binary_pred, &Bar::val);
183 test(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val);
184 test(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val);
185
186 return true;
187}
188
189int main(int, char**) {
190 test_all();
191 static_assert(test_all());
192
193 return 0;
194}
195

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