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