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 26 struct 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 33 struct 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 niebloid. 39 40 // (in, ...) 41 template <class Func, std::ranges::range Input, class... Args> 42 constexpr 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, ...) 48 template <class Func, std::ranges::range Input, class... Args> 49 constexpr 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, ...) 55 template <class Func, std::ranges::range Input, class... Args> 56 constexpr 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 61 constexpr bool test_all() { 62 std::array in = {Bar{Foo{1}}, Bar{Foo{2}}, Bar{Foo{3}}}; 63 std::array in2 = {Bar{Foo{4}}, Bar{Foo{5}}, Bar{Foo{6}}}; 64 auto mid = in.begin() + 1; 65 66 std::array output = {Bar{Foo{7}}, Bar{Foo{8}}, Bar{Foo{9}}, Bar{Foo{10}}, Bar{Foo{11}}, Bar{Foo{12}}}; 67 auto out = output.begin(); 68 auto out2 = output.begin() + 1; 69 70 Bar a{Foo{1}}; 71 Bar b{Foo{2}}; 72 Bar c{Foo{3}}; 73 74 Foo x{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 (!std::is_constant_evaluated()) 168 test(std::ranges::stable_partition, in, &Foo::unary_pred, &Bar::val); 169 test(std::ranges::sort, in, &Foo::binary_pred, &Bar::val); 170 if (!std::is_constant_evaluated()) 171 test(std::ranges::stable_sort, in, &Foo::binary_pred, &Bar::val); 172 test_mid(std::ranges::partial_sort, in, mid, &Foo::binary_pred, &Bar::val); 173 test_mid(std::ranges::nth_element, in, mid, &Foo::binary_pred, &Bar::val); 174 if (!std::is_constant_evaluated()) 175 test_mid(std::ranges::inplace_merge, in, mid, &Foo::binary_pred, &Bar::val); 176 test(std::ranges::make_heap, in, &Foo::binary_pred, &Bar::val); 177 test(std::ranges::push_heap, in, &Foo::binary_pred, &Bar::val); 178 test(std::ranges::pop_heap, in, &Foo::binary_pred, &Bar::val); 179 test(std::ranges::sort_heap, in, &Foo::binary_pred, &Bar::val); 180 test(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val); 181 test(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val); 182 183 return true; 184 } 185 186 int main(int, char**) { 187 test_all(); 188 static_assert(test_all()); 189 190 return 0; 191 } 192