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 | // ADDITIONAL_COMPILE_FLAGS(gcc): -Wno-bool-compare |
10 | // ADDITIONAL_COMPILE_FLAGS(gcc-style-warnings): -Wno-sign-compare |
11 | // MSVC warning C4245: conversion from 'int' to 'wchar_t', signed/unsigned mismatch |
12 | // MSVC warning C4305: truncation from 'int' to 'bool' |
13 | // MSVC warning C4310: cast truncates constant value |
14 | // MSVC warning C4389: '==': signed/unsigned mismatch |
15 | // MSVC warning C4805: '==': unsafe mix of type 'char' and type 'bool' in operation |
16 | // ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4245 /wd4305 /wd4310 /wd4389 /wd4805 |
17 | |
18 | // <algorithm> |
19 | |
20 | // template<InputIterator Iter, class T> |
21 | // requires HasEqualTo<Iter::value_type, T> |
22 | // constexpr Iter // constexpr after C++17 |
23 | // find(Iter first, Iter last, const T& value); |
24 | |
25 | #include <algorithm> |
26 | #include <cassert> |
27 | #include <deque> |
28 | #include <vector> |
29 | #include <type_traits> |
30 | |
31 | #include "test_macros.h" |
32 | #include "test_iterators.h" |
33 | #include "type_algorithms.h" |
34 | |
35 | static std::vector<int> comparable_data; |
36 | |
37 | template <class ArrayT, class CompareT> |
38 | struct Test { |
39 | template <class Iter> |
40 | TEST_CONSTEXPR_CXX20 void operator()() { |
41 | ArrayT arr[] = { |
42 | ArrayT(1), ArrayT(2), ArrayT(3), ArrayT(4), ArrayT(5), ArrayT(6), ArrayT(7), ArrayT(8), ArrayT(9), ArrayT(10)}; |
43 | |
44 | static_assert(std::is_same<decltype(std::find(Iter(arr), Iter(arr), 0)), Iter>::value, "" ); |
45 | |
46 | { // first element matches |
47 | Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(1)); |
48 | assert(*iter == ArrayT(1)); |
49 | assert(base(iter) == arr); |
50 | } |
51 | |
52 | { // range is empty; return last |
53 | Iter iter = std::find(Iter(arr), Iter(arr), CompareT(1)); |
54 | assert(base(iter) == arr); |
55 | } |
56 | |
57 | { // if multiple elements match, return the first match |
58 | ArrayT data[] = { |
59 | ArrayT(1), ArrayT(2), ArrayT(3), ArrayT(4), ArrayT(5), ArrayT(6), ArrayT(7), ArrayT(5), ArrayT(4)}; |
60 | Iter iter = std::find(Iter(std::begin(data)), Iter(std::end(data)), CompareT(5)); |
61 | assert(*iter == ArrayT(5)); |
62 | assert(base(iter) == data + 4); |
63 | } |
64 | |
65 | { // some element matches |
66 | Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(6)); |
67 | assert(*iter == ArrayT(6)); |
68 | assert(base(iter) == arr + 5); |
69 | } |
70 | |
71 | { // last element matches |
72 | Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(10)); |
73 | assert(*iter == ArrayT(10)); |
74 | assert(base(iter) == arr + 9); |
75 | } |
76 | |
77 | { // if no element matches, last is returned |
78 | Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(20)); |
79 | assert(base(iter) == arr + 10); |
80 | } |
81 | |
82 | if (!TEST_IS_CONSTANT_EVALUATED) |
83 | comparable_data.clear(); |
84 | } |
85 | }; |
86 | |
87 | template <class IndexT> |
88 | class Comparable { |
89 | IndexT index_; |
90 | |
91 | static IndexT init_index(IndexT i) { |
92 | IndexT size = static_cast<IndexT>(comparable_data.size()); |
93 | comparable_data.push_back(i); |
94 | return size; |
95 | } |
96 | |
97 | public: |
98 | Comparable(IndexT i) : index_(init_index(i)) {} |
99 | |
100 | friend bool operator==(const Comparable& lhs, const Comparable& rhs) { |
101 | return comparable_data[lhs.index_] == comparable_data[rhs.index_]; |
102 | } |
103 | }; |
104 | |
105 | #if TEST_STD_VER >= 20 |
106 | template <class ElementT> |
107 | class TriviallyComparable { |
108 | ElementT el_; |
109 | |
110 | public: |
111 | explicit constexpr TriviallyComparable(ElementT el) : el_(el) {} |
112 | bool operator==(const TriviallyComparable&) const = default; |
113 | }; |
114 | #endif |
115 | |
116 | template <class CompareT> |
117 | struct TestTypes { |
118 | template <class T> |
119 | TEST_CONSTEXPR_CXX20 void operator()() { |
120 | types::for_each(types::cpp17_input_iterator_list<T*>(), Test<T, CompareT>()); |
121 | } |
122 | }; |
123 | |
124 | void test_deque() { |
125 | { // empty deque |
126 | std::deque<int> data; |
127 | assert(std::find(data.begin(), data.end(), 4) == data.end()); |
128 | } |
129 | |
130 | { // single element - match |
131 | std::deque<int> data; |
132 | data.push_back(x: 4); |
133 | assert(std::find(data.begin(), data.end(), 4) == data.begin()); |
134 | } |
135 | |
136 | { // single element - no match |
137 | std::deque<int> data; |
138 | data.push_back(x: 3); |
139 | assert(std::find(data.begin(), data.end(), 4) == data.end()); |
140 | } |
141 | |
142 | // many elements |
143 | int sizes[] = {2, 3, 1023, 1024, 1025, 2047, 2048, 2049}; |
144 | for (auto size : sizes) { |
145 | { // last element match |
146 | std::deque<int> data; |
147 | data.resize(new_size: size); |
148 | std::fill(first: data.begin(), last: data.end(), value: 3); |
149 | data[size - 1] = 4; |
150 | assert(std::find(data.begin(), data.end(), 4) == data.end() - 1); |
151 | } |
152 | |
153 | { // second-last element match |
154 | std::deque<int> data; |
155 | data.resize(new_size: size); |
156 | std::fill(first: data.begin(), last: data.end(), value: 3); |
157 | data[size - 2] = 4; |
158 | assert(std::find(data.begin(), data.end(), 4) == data.end() - 2); |
159 | } |
160 | |
161 | { // no match |
162 | std::deque<int> data; |
163 | data.resize(new_size: size); |
164 | std::fill(first: data.begin(), last: data.end(), value: 3); |
165 | assert(std::find(data.begin(), data.end(), 4) == data.end()); |
166 | } |
167 | } |
168 | } |
169 | |
170 | template <class T> |
171 | struct TestIntegerPromotions1 { |
172 | template <class U> |
173 | TEST_CONSTEXPR_CXX20 void test(T val, U to_find) { |
174 | bool expect_match = val == to_find; |
175 | assert(std::find(&val, &val + 1, to_find) == (expect_match ? &val : &val + 1)); |
176 | } |
177 | |
178 | template <class U> |
179 | TEST_CONSTEXPR_CXX20 void operator()() { |
180 | test<U>(0, 0); |
181 | test<U>(0, 1); |
182 | test<U>(1, 1); |
183 | test<U>(0, -1); |
184 | test<U>(-1, -1); |
185 | test<U>(0, U(-127)); |
186 | test<U>(T(-127), U(-127)); |
187 | test<U>(T(-128), U(-128)); |
188 | test<U>(T(-129), U(-129)); |
189 | test<U>(T(255), U(255)); |
190 | test<U>(T(256), U(256)); |
191 | test<U>(T(257), U(257)); |
192 | test<U>(0, std::numeric_limits<U>::min()); |
193 | test<U>(T(std::numeric_limits<U>::min()), std::numeric_limits<U>::min()); |
194 | test<U>(0, std::numeric_limits<U>::min() + 1); |
195 | test<U>(T(std::numeric_limits<U>::min() + 1), std::numeric_limits<U>::min() + 1); |
196 | test<U>(0, std::numeric_limits<U>::max()); |
197 | test<U>(T(std::numeric_limits<U>::max()), std::numeric_limits<U>::max()); |
198 | test<U>(T(std::numeric_limits<U>::max() - 1), std::numeric_limits<U>::max() - 1); |
199 | } |
200 | }; |
201 | |
202 | struct TestIntegerPromotions { |
203 | template <class T> |
204 | TEST_CONSTEXPR_CXX20 void operator()() { |
205 | types::for_each(types::integral_types(), TestIntegerPromotions1<T>()); |
206 | } |
207 | }; |
208 | |
209 | TEST_CONSTEXPR_CXX20 bool test() { |
210 | types::for_each(types::integer_types(), TestTypes<char>()); |
211 | types::for_each(types::integer_types(), TestTypes<int>()); |
212 | types::for_each(types::integer_types(), TestTypes<long long>()); |
213 | #if TEST_STD_VER >= 20 |
214 | Test<TriviallyComparable<char>, TriviallyComparable<char>>().operator()<TriviallyComparable<char>*>(); |
215 | Test<TriviallyComparable<wchar_t>, TriviallyComparable<wchar_t>>().operator()<TriviallyComparable<wchar_t>*>(); |
216 | #endif |
217 | |
218 | // TODO: Remove the `_LIBCPP_ENABLE_EXPERIMENTAL` check once we have the FTM guarded or views::join isn't |
219 | // experimental anymore |
220 | #if TEST_STD_VER >= 20 && (!defined(_LIBCPP_VERSION) || defined(_LIBCPP_ENABLE_EXPERIMENTAL)) |
221 | { |
222 | std::vector<std::vector<int>> vec = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; |
223 | auto view = vec | std::views::join; |
224 | assert(std::find(view.begin(), view.end(), 4) == std::next(view.begin(), 3)); |
225 | } |
226 | #endif |
227 | |
228 | types::for_each(types::integral_types(), TestIntegerPromotions()); |
229 | |
230 | return true; |
231 | } |
232 | |
233 | int main(int, char**) { |
234 | test_deque(); |
235 | test(); |
236 | #if TEST_STD_VER >= 20 |
237 | static_assert(test()); |
238 | #endif |
239 | |
240 | Test<Comparable<char>, Comparable<char> >().operator()<Comparable<char>*>(); |
241 | Test<Comparable<wchar_t>, Comparable<wchar_t> >().operator()<Comparable<wchar_t>*>(); |
242 | |
243 | return 0; |
244 | } |
245 | |