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