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 // UNSUPPORTED: c++03, c++11, c++14, c++17 12 // UNSUPPORTED: libcpp-has-no-incomplete-ranges 13 14 // template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, 15 // class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> 16 // requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> 17 // constexpr bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2, 18 // Pred pred = {}, 19 // Proj1 proj1 = {}, Proj2 proj2 = {}); 20 // template<input_range R1, input_range R2, class Pred = ranges::equal_to, 21 // class Proj1 = identity, class Proj2 = identity> 22 // requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> 23 // constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {}, 24 // Proj1 proj1 = {}, Proj2 proj2 = {}); 25 26 #include <algorithm> 27 #include <cassert> 28 #include <concepts> 29 #include <functional> 30 #include <ranges> 31 32 #include "almost_satisfies_types.h" 33 #include "test_iterators.h" 34 35 template <class Iter1, class Sent1 = sentinel_wrapper<Iter1>, 36 class Iter2 = Iter1, class Sent2 = sentinel_wrapper<Iter2>> 37 concept HasEqualIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) { 38 std::ranges::equal(first1, last1, first2, last2); 39 }; 40 41 static_assert(HasEqualIt<int*>); 42 static_assert(!HasEqualIt<InputIteratorNotDerivedFrom>); 43 static_assert(!HasEqualIt<InputIteratorNotIndirectlyReadable>); 44 static_assert(!HasEqualIt<InputIteratorNotInputOrOutputIterator>); 45 static_assert(!HasEqualIt<int*, int*, InputIteratorNotDerivedFrom>); 46 static_assert(!HasEqualIt<int*, int*, InputIteratorNotIndirectlyReadable>); 47 static_assert(!HasEqualIt<int*, int*, InputIteratorNotInputOrOutputIterator>); 48 static_assert(!HasEqualIt<int*, SentinelForNotSemiregular>); 49 static_assert(!HasEqualIt<int*, SentinelForNotWeaklyEqualityComparableWith>); 50 static_assert(!HasEqualIt<int*, int*, int*, SentinelForNotSemiregular>); 51 static_assert(!HasEqualIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>); 52 static_assert(!HasEqualIt<int*, int*, int**>); 53 54 template <class Range1, class Range2> 55 concept HasEqualR = requires (Range1 range1, Range2 range2) { 56 std::ranges::equal(range1, range2); 57 }; 58 59 static_assert(HasEqualR<UncheckedRange<int*>, UncheckedRange<int*>>); 60 static_assert(!HasEqualR<InputRangeNotDerivedFrom, UncheckedRange<int*>>); 61 static_assert(!HasEqualR<InputRangeNotIndirectlyReadable, UncheckedRange<int*>>); 62 static_assert(!HasEqualR<InputRangeNotInputOrOutputIterator, UncheckedRange<int*>>); 63 static_assert(!HasEqualR<InputRangeNotSentinelSemiregular, UncheckedRange<int*>>); 64 static_assert(!HasEqualR<InputRangeNotSentinelEqualityComparableWith, UncheckedRange<int*>>); 65 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotDerivedFrom>); 66 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotIndirectlyReadable>); 67 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotInputOrOutputIterator>); 68 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotSentinelSemiregular>); 69 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotSentinelEqualityComparableWith>); 70 static_assert(!HasEqualR<UncheckedRange<int*>, UncheckedRange<int**>>); 71 72 template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2> 73 constexpr void test_iterators() { 74 { // simple test 75 { 76 int a[] = {1, 2, 3, 4}; 77 int b[] = {1, 2, 3, 4}; 78 std::same_as<bool> decltype(auto) ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), 79 Iter2(b), Sent2(Iter2(b + 4))); 80 assert(ret); 81 } 82 { 83 int a[] = {1, 2, 3, 4}; 84 int b[] = {1, 2, 3, 4}; 85 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); 86 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); 87 std::same_as<bool> decltype(auto) ret = std::ranges::equal(range1, range2); 88 assert(ret); 89 } 90 } 91 92 { // check that the predicate is used (return true) 93 { 94 int a[] = {1, 2, 3, 4}; 95 int b[] = {2, 3, 4, 5}; 96 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)), 97 [](int l, int r) { return l != r; }); 98 assert(ret); 99 } 100 { 101 int a[] = {1, 2, 3, 4}; 102 int b[] = {2, 3, 4, 5}; 103 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); 104 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); 105 auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; }); 106 assert(ret); 107 } 108 } 109 110 { // check that the predicate is used (return false) 111 { 112 int a[] = {1, 2, 3, 4}; 113 int b[] = {2, 3, 3, 5}; 114 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)), 115 [](int l, int r) { return l != r; }); 116 assert(!ret); 117 } 118 { 119 int a[] = {1, 2, 3, 4}; 120 int b[] = {2, 3, 3, 5}; 121 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); 122 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); 123 auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; }); 124 assert(!ret); 125 } 126 } 127 128 { // check that the projections are used 129 { 130 int a[] = {1, 2, 3, 4, 5}; 131 int b[] = {6, 10, 14, 18, 22}; 132 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)), 133 Iter2(b), Sent2(Iter2(b + 5)), 134 {}, 135 [](int i) { return i * 4; }, 136 [](int i) { return i - 2; }); 137 assert(ret); 138 } 139 { 140 int a[] = {1, 2, 3, 4, 5}; 141 int b[] = {6, 10, 14, 18, 22}; 142 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); 143 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5))); 144 auto ret = std::ranges::equal(range1, 145 range2, 146 {}, 147 [](int i) { return i * 4; }, 148 [](int i) { return i - 2; }); 149 assert(ret); 150 } 151 } 152 153 { // check that different sized ranges work 154 { 155 int a[] = {4, 3, 2, 1}; 156 int b[] = {4, 3, 2, 1, 5, 6, 7}; 157 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 7))); 158 assert(!ret); 159 } 160 { 161 int a[] = {4, 3, 2, 1}; 162 int b[] = {4, 3, 2, 1, 5, 6, 7}; 163 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); 164 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 7))); 165 auto ret = std::ranges::equal(range1, range2); 166 assert(!ret); 167 } 168 } 169 170 { // check that two ranges with the same size but different values are different 171 { 172 int a[] = {4, 6, 34, 76, 5}; 173 int b[] = {4, 6, 34, 67, 5}; 174 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)), Iter2(b), Sent2(Iter2(b + 5))); 175 assert(!ret); 176 } 177 { 178 int a[] = {4, 6, 34, 76, 5}; 179 int b[] = {4, 6, 34, 67, 5}; 180 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); 181 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5))); 182 auto ret = std::ranges::equal(range1, range2); 183 assert(!ret); 184 } 185 } 186 187 { // check that two empty ranges work 188 { 189 int a[] = {}; 190 int b[] = {}; 191 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a)), Iter2(b), Sent2(Iter2(b))); 192 assert(ret); 193 } 194 { 195 int a[] = {}; 196 int b[] = {}; 197 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); 198 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b))); 199 auto ret = std::ranges::equal(range1, range2); 200 assert(ret); 201 } 202 } 203 204 { // check that it works with the first range empty 205 { 206 int a[] = {}; 207 int b[] = {1, 2}; 208 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a)), Iter2(b), Sent2(Iter2(b + 2))); 209 assert(!ret); 210 } 211 { 212 int a[] = {}; 213 int b[] = {1, 2}; 214 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); 215 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 2))); 216 auto ret = std::ranges::equal(range1, range2); 217 assert(!ret); 218 } 219 } 220 221 { // check that it works with the second range empty 222 { 223 int a[] = {1, 2}; 224 int b[] = {}; 225 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 2)), Iter2(b), Sent2(Iter2(b))); 226 assert(!ret); 227 } 228 { 229 int a[] = {1, 2}; 230 int b[] = {}; 231 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 2))); 232 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b))); 233 auto ret = std::ranges::equal(range1, range2); 234 assert(!ret); 235 } 236 } 237 } 238 239 template<class Iter1, class Sent1 = Iter1> 240 constexpr void test_iterators2() { 241 test_iterators<Iter1, Sent1, cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>(); 242 test_iterators<Iter1, Sent1, cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>(); 243 test_iterators<Iter1, Sent1, forward_iterator<int*>>(); 244 test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>(); 245 test_iterators<Iter1, Sent1, random_access_iterator<int*>>(); 246 test_iterators<Iter1, Sent1, contiguous_iterator<int*>>(); 247 test_iterators<Iter1, Sent1, int*>(); 248 test_iterators<Iter1, Sent1, const int*>(); 249 } 250 251 constexpr bool test() { 252 test_iterators2<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>(); 253 test_iterators2<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>(); 254 test_iterators2<forward_iterator<int*>>(); 255 test_iterators2<bidirectional_iterator<int*>>(); 256 test_iterators2<random_access_iterator<int*>>(); 257 test_iterators2<contiguous_iterator<int*>>(); 258 test_iterators2<int*>(); 259 test_iterators2<const int*>(); 260 261 { // check that std::invoke is used 262 struct S { 263 constexpr S(int i_) : i(i_) {} 264 constexpr bool equal(int o) { return i == o; } 265 constexpr S& identity() { return *this; } 266 int i; 267 }; 268 { 269 S a[] = {7, 8, 9}; 270 S b[] = {7, 8, 9}; 271 auto ret = std::ranges::equal(a, a + 3, b, b + 3, &S::equal, &S::identity, &S::i); 272 assert(ret); 273 } 274 { 275 S a[] = {7, 8, 9}; 276 S b[] = {7, 8, 9}; 277 auto ret = std::ranges::equal(a, b, &S::equal, &S::identity, &S::i); 278 assert(ret); 279 } 280 } 281 282 { // check that the complexity requirements are met 283 { // different size 284 { 285 int a[] = {1, 2, 3}; 286 int b[] = {1, 2, 3, 4}; 287 int predCount = 0; 288 int projCount = 0; 289 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 290 auto proj = [&](int i) { ++projCount; return i; }; 291 auto ret = std::ranges::equal(a, a + 3, b, b + 4, pred, proj, proj); 292 assert(!ret); 293 assert(predCount == 0); 294 assert(projCount == 0); 295 } 296 { 297 int a[] = {1, 2, 3}; 298 int b[] = {1, 2, 3, 4}; 299 int predCount = 0; 300 int projCount = 0; 301 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 302 auto proj = [&](int i) { ++projCount; return i; }; 303 auto ret = std::ranges::equal(a, b, pred, proj, proj); 304 assert(!ret); 305 assert(predCount == 0); 306 assert(projCount == 0); 307 } 308 } 309 310 { // not a sized sentinel 311 { 312 int a[] = {1, 2, 3}; 313 int b[] = {1, 2, 3, 4}; 314 int predCount = 0; 315 int projCount = 0; 316 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 317 auto proj = [&](int i) { ++projCount; return i; }; 318 auto ret = std::ranges::equal(a, sentinel_wrapper(a + 3), b, sentinel_wrapper(b + 4), pred, proj, proj); 319 assert(!ret); 320 assert(predCount <= 4); 321 assert(projCount <= 7); 322 } 323 { 324 int a[] = {1, 2, 3}; 325 int b[] = {1, 2, 3, 4}; 326 int predCount = 0; 327 int projCount = 0; 328 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 329 auto proj = [&](int i) { ++projCount; return i; }; 330 auto range1 = std::ranges::subrange(a, sentinel_wrapper(a + 3)); 331 auto range2 = std::ranges::subrange(b, sentinel_wrapper(b + 4)); 332 auto ret = std::ranges::equal(range1, range2, pred, proj, proj); 333 assert(!ret); 334 assert(predCount <= 4); 335 assert(projCount <= 7); 336 } 337 } 338 339 { // same size 340 { 341 int a[] = {1, 2, 3}; 342 int b[] = {1, 2, 3}; 343 int predCount = 0; 344 int projCount = 0; 345 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 346 auto proj = [&](int i) { ++projCount; return i; }; 347 auto ret = std::ranges::equal(a, a + 3, b, b + 3, pred, proj, proj); 348 assert(ret); 349 assert(predCount == 3); 350 assert(projCount == 6); 351 } 352 { 353 int a[] = {1, 2, 3}; 354 int b[] = {1, 2, 3}; 355 int predCount = 0; 356 int projCount = 0; 357 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 358 auto proj = [&](int i) { ++projCount; return i; }; 359 auto ret = std::ranges::equal(a, b, pred, proj, proj); 360 assert(ret); 361 assert(predCount == 3); 362 assert(projCount == 6); 363 } 364 } 365 } 366 367 return true; 368 } 369 370 int main(int, char**) { 371 test(); 372 static_assert(test()); 373 374 return 0; 375 } 376