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 // <algorithm>
10
11 #include <algorithm>
12 #include <cassert>
13 #include <compare>
14 #include <cstddef>
15
16 #include "test_macros.h"
17
18 template <class T>
19 struct Less {
20 int *copies_;
LessLess21 TEST_CONSTEXPR explicit Less(int *copies) : copies_(copies) {}
LessLess22 TEST_CONSTEXPR_CXX14 Less(const Less& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
23 TEST_CONSTEXPR_CXX14 Less& operator=(const Less&) = default;
operator ()Less24 TEST_CONSTEXPR bool operator()(T, T) const { return false; }
25 };
26
27 template <class T>
28 struct Equal {
29 int *copies_;
EqualEqual30 TEST_CONSTEXPR explicit Equal(int *copies) : copies_(copies) {}
EqualEqual31 TEST_CONSTEXPR_CXX14 Equal(const Equal& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
32 TEST_CONSTEXPR_CXX14 Equal& operator=(const Equal&) = default;
operator ()Equal33 TEST_CONSTEXPR bool operator()(T, T) const { return true; }
34 };
35
36 template <class T>
37 struct UnaryVoid {
38 int *copies_;
UnaryVoidUnaryVoid39 TEST_CONSTEXPR explicit UnaryVoid(int *copies) : copies_(copies) {}
UnaryVoidUnaryVoid40 TEST_CONSTEXPR_CXX14 UnaryVoid(const UnaryVoid& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
41 TEST_CONSTEXPR_CXX14 UnaryVoid& operator=(const UnaryVoid&) = default;
operator ()UnaryVoid42 TEST_CONSTEXPR_CXX14 void operator()(T) const {}
43 };
44
45 template <class T>
46 struct UnaryTrue {
47 int *copies_;
UnaryTrueUnaryTrue48 TEST_CONSTEXPR explicit UnaryTrue(int *copies) : copies_(copies) {}
UnaryTrueUnaryTrue49 TEST_CONSTEXPR_CXX14 UnaryTrue(const UnaryTrue& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
50 TEST_CONSTEXPR_CXX14 UnaryTrue& operator=(const UnaryTrue&) = default;
operator ()UnaryTrue51 TEST_CONSTEXPR bool operator()(T) const { return true; }
52 };
53
54 template <class T>
55 struct NullaryValue {
56 int *copies_;
NullaryValueNullaryValue57 TEST_CONSTEXPR explicit NullaryValue(int *copies) : copies_(copies) {}
NullaryValueNullaryValue58 TEST_CONSTEXPR_CXX14 NullaryValue(const NullaryValue& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
59 TEST_CONSTEXPR_CXX14 NullaryValue& operator=(const NullaryValue&) = default;
operator ()NullaryValue60 TEST_CONSTEXPR T operator()() const { return 0; }
61 };
62
63 template <class T>
64 struct UnaryTransform {
65 int *copies_;
UnaryTransformUnaryTransform66 TEST_CONSTEXPR explicit UnaryTransform(int *copies) : copies_(copies) {}
UnaryTransformUnaryTransform67 TEST_CONSTEXPR_CXX14 UnaryTransform(const UnaryTransform& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
68 TEST_CONSTEXPR_CXX14 UnaryTransform& operator=(const UnaryTransform&) = default;
operator ()UnaryTransform69 TEST_CONSTEXPR T operator()(T) const { return 0; }
70 };
71
72 template <class T>
73 struct BinaryTransform {
74 int *copies_;
BinaryTransformBinaryTransform75 TEST_CONSTEXPR explicit BinaryTransform(int *copies) : copies_(copies) {}
BinaryTransformBinaryTransform76 TEST_CONSTEXPR_CXX14 BinaryTransform(const BinaryTransform& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
77 TEST_CONSTEXPR_CXX14 BinaryTransform& operator=(const BinaryTransform&) = default;
operator ()BinaryTransform78 TEST_CONSTEXPR T operator()(T, T) const { return 0; }
79 };
80
81 #if TEST_STD_VER > 17
82 struct ThreeWay {
83 int *copies_;
ThreeWayThreeWay84 constexpr explicit ThreeWay(int *copies) : copies_(copies) {}
ThreeWayThreeWay85 constexpr ThreeWay(const ThreeWay& rhs) : copies_(rhs.copies_) { *copies_ += 1; }
86 constexpr ThreeWay& operator=(const ThreeWay&) = default;
operator ()ThreeWay87 constexpr std::strong_ordering operator()(void*, void*) const { return std::strong_ordering::equal; }
88 };
89 #endif
90
91 template <class T>
all_the_algorithms()92 TEST_CONSTEXPR_CXX20 bool all_the_algorithms()
93 {
94 T a[10] = {};
95 T b[10] = {};
96 T *first = a;
97 T *mid = a+5;
98 T *last = a+10;
99 T *first2 = b;
100 T *mid2 = b+5;
101 T *last2 = b+10;
102 T value = 0;
103 int count = 1;
104
105 int copies = 0;
106 (void)std::adjacent_find(first, last, Equal<T>(&copies)); assert(copies == 0);
107 #if TEST_STD_VER >= 11
108 (void)std::all_of(first, last, UnaryTrue<T>(&copies)); assert(copies == 0);
109 (void)std::any_of(first, last, UnaryTrue<T>(&copies)); assert(copies == 0);
110 #endif
111 (void)std::binary_search(first, last, value, Less<T>(&copies)); assert(copies == 0);
112 #if TEST_STD_VER > 17
113 (void)std::clamp(value, value, value, Less<T>(&copies)); assert(copies == 0);
114 #endif
115 (void)std::count_if(first, last, UnaryTrue<T>(&copies)); assert(copies == 0);
116 (void)std::copy_if(first, last, first2, UnaryTrue<T>(&copies)); assert(copies == 0);
117 (void)std::equal(first, last, first2, Equal<T>(&copies)); assert(copies == 0);
118 #if TEST_STD_VER > 11
119 (void)std::equal(first, last, first2, last2, Equal<T>(&copies)); assert(copies == 0);
120 #endif
121 (void)std::equal_range(first, last, value, Less<T>(&copies)); assert(copies == 0);
122 (void)std::find_end(first, last, first2, mid2, Equal<T>(&copies)); assert(copies == 0);
123 (void)std::find_first_of(first, last, first2, last2, Equal<T>(&copies)); assert(copies == 0);
124 (void)std::find_if(first, last, UnaryTrue<T>(&copies)); assert(copies == 0);
125 (void)std::find_if_not(first, last, UnaryTrue<T>(&copies)); assert(copies == 0);
126 (void)std::for_each(first, last, UnaryVoid<T>(&copies)); assert(copies == 1); copies = 0;
127 #if TEST_STD_VER > 14
128 (void)std::for_each_n(first, count, UnaryVoid<T>(&copies)); assert(copies == 0);
129 #endif
130 (void)std::generate(first, last, NullaryValue<T>(&copies)); assert(copies == 0);
131 (void)std::generate_n(first, count, NullaryValue<T>(&copies)); assert(copies == 0);
132 (void)std::includes(first, last, first2, last2, Less<T>(&copies)); assert(copies == 0);
133 (void)std::is_heap(first, last, Less<T>(&copies)); assert(copies == 0);
134 (void)std::is_heap_until(first, last, Less<T>(&copies)); assert(copies == 0);
135 (void)std::is_partitioned(first, last, UnaryTrue<T>(&copies)); assert(copies == 0);
136 (void)std::is_permutation(first, last, first2, Equal<T>(&copies)); assert(copies == 0);
137 #if TEST_STD_VER > 11
138 (void)std::is_permutation(first, last, first2, last2, Equal<T>(&copies)); assert(copies == 0);
139 #endif
140 (void)std::is_sorted(first, last, Less<T>(&copies)); assert(copies == 0);
141 (void)std::is_sorted_until(first, last, Less<T>(&copies)); assert(copies == 0);
142 if (!TEST_IS_CONSTANT_EVALUATED) { (void)std::inplace_merge(first, mid, last, Less<T>(&copies)); assert(copies == 0); }
143 (void)std::lexicographical_compare(first, last, first2, last2, Less<T>(&copies)); assert(copies == 0);
144 #if TEST_STD_VER > 17
145 //(void)std::lexicographical_compare_three_way(first, last, first2, last2, ThreeWay(&copies)); assert(copies == 0);
146 #endif
147 (void)std::lower_bound(first, last, value, Less<T>(&copies)); assert(copies == 0);
148 (void)std::make_heap(first, last, Less<T>(&copies)); assert(copies == 0);
149 (void)std::max(value, value, Less<T>(&copies)); assert(copies == 0);
150 #if TEST_STD_VER >= 11
151 (void)std::max({ value, value }, Less<T>(&copies)); assert(copies == 0);
152 #endif
153 (void)std::max_element(first, last, Less<T>(&copies)); assert(copies == 0);
154 (void)std::merge(first, mid, mid, last, first2, Less<T>(&copies)); assert(copies == 0);
155 (void)std::min(value, value, Less<T>(&copies)); assert(copies == 0);
156 #if TEST_STD_VER >= 11
157 (void)std::min({ value, value }, Less<T>(&copies)); assert(copies == 0);
158 #endif
159 (void)std::min_element(first, last, Less<T>(&copies)); assert(copies == 0);
160 (void)std::minmax(value, value, Less<T>(&copies)); assert(copies == 0);
161 #if TEST_STD_VER >= 11
162 (void)std::minmax({ value, value }, Less<T>(&copies)); assert(copies == 0);
163 #endif
164 (void)std::minmax_element(first, last, Less<T>(&copies)); assert(copies == 0);
165 (void)std::mismatch(first, last, first2, Equal<T>(&copies)); assert(copies == 0);
166 #if TEST_STD_VER > 11
167 (void)std::mismatch(first, last, first2, last2, Equal<T>(&copies)); assert(copies == 0);
168 #endif
169 (void)std::next_permutation(first, last, Less<T>(&copies)); assert(copies == 0);
170 #if TEST_STD_VER >= 11
171 (void)std::none_of(first, last, UnaryTrue<T>(&copies)); assert(copies == 0);
172 #endif
173 (void)std::nth_element(first, mid, last, Less<T>(&copies)); assert(copies == 0);
174 (void)std::partial_sort(first, mid, last, Less<T>(&copies)); assert(copies == 0);
175 (void)std::partial_sort_copy(first, last, first2, mid2, Less<T>(&copies)); assert(copies == 0);
176 (void)std::partition(first, last, UnaryTrue<T>(&copies)); assert(copies == 0);
177 (void)std::partition_copy(first, last, first2, last2, UnaryTrue<T>(&copies)); assert(copies == 0);
178 (void)std::partition_point(first, last, UnaryTrue<T>(&copies)); assert(copies == 0);
179 (void)std::pop_heap(first, last, Less<T>(&copies)); assert(copies == 0);
180 (void)std::prev_permutation(first, last, Less<T>(&copies)); assert(copies == 0);
181 (void)std::push_heap(first, last, Less<T>(&copies)); assert(copies == 0);
182 (void)std::remove_copy_if(first, last, first2, UnaryTrue<T>(&copies)); assert(copies == 0);
183 (void)std::remove_if(first, last, UnaryTrue<T>(&copies)); assert(copies == 0);
184 (void)std::replace_copy_if(first, last, first2, UnaryTrue<T>(&copies), value); assert(copies == 0);
185 (void)std::replace_if(first, last, UnaryTrue<T>(&copies), value); assert(copies == 0);
186 (void)std::search(first, last, first2, mid2, Equal<T>(&copies)); assert(copies == 0);
187 (void)std::search_n(first, last, count, value, Equal<T>(&copies)); assert(copies == 0);
188 (void)std::set_difference(first, mid, mid, last, first2, Less<T>(&copies)); assert(copies == 0);
189 (void)std::set_intersection(first, mid, mid, last, first2, Less<T>(&copies)); assert(copies == 0);
190 (void)std::set_symmetric_difference(first, mid, mid, last, first2, Less<T>(&copies)); assert(copies == 0);
191 (void)std::set_union(first, mid, mid, last, first2, Less<T>(&copies)); assert(copies == 0);
192 (void)std::sort(first, first+3, Less<T>(&copies)); assert(copies == 0);
193 (void)std::sort(first, first+4, Less<T>(&copies)); assert(copies == 0);
194 (void)std::sort(first, first+5, Less<T>(&copies)); assert(copies == 0);
195 (void)std::sort(first, last, Less<T>(&copies)); assert(copies == 0);
196 (void)std::sort_heap(first, last, Less<T>(&copies)); assert(copies == 0);
197 if (!TEST_IS_CONSTANT_EVALUATED) { (void)std::stable_partition(first, last, UnaryTrue<T>(&copies)); assert(copies == 0); }
198 if (!TEST_IS_CONSTANT_EVALUATED) { (void)std::stable_sort(first, last, Less<T>(&copies)); assert(copies == 0); }
199 (void)std::transform(first, last, first2, UnaryTransform<T>(&copies)); assert(copies == 0);
200 (void)std::transform(first, mid, mid, first2, BinaryTransform<T>(&copies)); assert(copies == 0);
201 (void)std::unique(first, last, Equal<T>(&copies)); assert(copies == 0);
202 (void)std::unique_copy(first, last, first2, Equal<T>(&copies)); assert(copies == 0);
203 (void)std::upper_bound(first, last, value, Less<T>(&copies)); assert(copies == 0);
204
205 return true;
206 }
207
main(int,char **)208 int main(int, char**)
209 {
210 all_the_algorithms<void*>();
211 all_the_algorithms<int>();
212 #if TEST_STD_VER > 17
213 static_assert(all_the_algorithms<void*>());
214 static_assert(all_the_algorithms<int>());
215 #endif
216
217 return 0;
218 }
219