libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search.pass.cpp

   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
  13 // template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
  14 //          sentinel_for<I2> S2, class Pred = ranges::equal_to,
  15 //          class Proj1 = identity, class Proj2 = identity>
  16 //   requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
  17 //   constexpr subrange<I1>
  18 //     ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
  19 //                    Proj1 proj1 = {}, Proj2 proj2 = {});
  20 // template<forward_range R1, forward_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 borrowed_subrange_t<R1>
  24 //     ranges::search(R1&& r1, R2&& r2, Pred pred = {},
  25 //                    Proj1 proj1 = {}, Proj2 proj2 = {});
  26
  27 #include <algorithm>
  28 #include <array>
  29 #include <ranges>
  30
  31 #include "almost_satisfies_types.h"
  32 #include "test_iterators.h"
  33
  34 template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2>
  35 concept HasSearchIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
  36   std::ranges::search(first1, last1, first2, last2);
  37 };
  38
  39 static_assert(HasSearchIt<int*>);
  40 static_assert(!HasSearchIt<ForwardIteratorNotDerivedFrom>);
  41 static_assert(!HasSearchIt<ForwardIteratorNotIncrementable>);
  42 static_assert(!HasSearchIt<int*, SentinelForNotSemiregular>);
  43 static_assert(!HasSearchIt<int*, int*, int**>); // not indirectly comparable
  44 static_assert(!HasSearchIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
  45 static_assert(!HasSearchIt<int*, int*, ForwardIteratorNotDerivedFrom>);
  46 static_assert(!HasSearchIt<int*, int*, ForwardIteratorNotIncrementable>);
  47 static_assert(!HasSearchIt<int*, int*, int*, SentinelForNotSemiregular>);
  48 static_assert(!HasSearchIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
  49
  50 template <class Range1, class Range2 = UncheckedRange<int*>>
  51 concept HasSearchR = requires (Range1 range1, Range2 range2) {
  52   std::ranges::search(range1, range2);
  53 };
  54
  55 static_assert(HasSearchR<UncheckedRange<int*>>);
  56 static_assert(!HasSearchR<ForwardRangeNotDerivedFrom>);
  57 static_assert(!HasSearchR<ForwardIteratorNotIncrementable>);
  58 static_assert(!HasSearchR<ForwardRangeNotSentinelSemiregular>);
  59 static_assert(!HasSearchR<ForwardRangeNotSentinelEqualityComparableWith>);
  60 static_assert(!HasSearchR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable
  61 static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);
  62 static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);
  63 static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);
  64 static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);
  65
  66 template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>
  67 constexpr void test_iterators() {
  68   { // simple test
  69     {
  70       int a[] = {1, 2, 3, 4, 5, 6};
  71       int p[] = {3, 4};
  72       std::same_as<std::ranges::subrange<Iter1, Iter1>> decltype(auto) ret =
  73           std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 2)));
  74       assert(base(ret.begin()) == a + 2);
  75       assert(base(ret.end()) == a + 4);
  76     }
  77     {
  78       int a[] = {1, 2, 3, 4, 5, 6};
  79       int p[] = {3, 4};
  80       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
  81       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));
  82       std::same_as<std::ranges::subrange<Iter1, Iter1>> decltype(auto) ret = std::ranges::search(range1, range2);
  83       assert(base(ret.begin()) == a + 2);
  84       assert(base(ret.end()) == a + 4);
  85     }
  86   }
  87
  88   { // matching part begins at the front
  89     {
  90       int a[] = {7, 5, 3, 7, 3, 6};
  91       int p[] = {7, 5, 3};
  92       auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)), Iter2(p), Sent2(Iter2(p + 3)));
  93       assert(base(ret.begin()) == a);
  94       assert(base(ret.end()) == a + 3);
  95     }
  96     {
  97       int a[] = {7, 5, 3, 7, 3, 6};
  98       int p[] = {7, 5, 3};
  99       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
 100       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
 101       auto ret = std::ranges::search(range1, range2);
 102       assert(base(ret.begin()) == a);
 103       assert(base(ret.end()) == a + 3);
 104     }
 105   }
 106
 107   { // matching part ends at the back
 108     {
 109       int a[] = {9, 3, 6, 4, 8};
 110       int p[] = {4, 8};
 111       auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 2)));
 112       assert(base(ret.begin()) == a + 3);
 113       assert(base(ret.end()) == a + 5);
 114     }
 115     {
 116       int a[] = {9, 3, 6, 4, 8};
 117       int p[] = {4, 8};
 118       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
 119       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));
 120       auto ret = std::ranges::search(range1, range2);
 121       assert(base(ret.begin()) == a + 3);
 122       assert(base(ret.end()) == a + 5);
 123     }
 124   }
 125
 126   { // pattern does not match
 127     {
 128       int a[] = {9, 3, 6, 4, 8};
 129       int p[] = {1};
 130       auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 5)), Iter2(p), Sent2(Iter2(p + 1)));
 131       assert(base(ret.begin()) == a + 5);
 132       assert(base(ret.end()) == a + 5);
 133     }
 134     {
 135       int a[] = {9, 3, 6, 4, 8};
 136       int p[] = {1};
 137       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));
 138       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1)));
 139       auto ret = std::ranges::search(range1, range2);
 140       assert(base(ret.begin()) == a + 5);
 141       assert(base(ret.end()) == a + 5);
 142     }
 143   }
 144
 145   { // range and pattern are identical
 146     {
 147       int a[] = {6, 7, 8, 9};
 148       int p[] = {6, 7, 8, 9};
 149       auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 4)), Iter2(p), Sent2(Iter2(p + 4)));
 150       assert(base(ret.begin()) == a);
 151       assert(base(ret.end()) == a + 4);
 152     }
 153     {
 154       int a[] = {6, 7, 8, 9};
 155       int p[] = {6, 7, 8, 9};
 156       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4)));
 157       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4)));
 158       auto ret = std::ranges::search(range1, range2);
 159       assert(base(ret.begin()) == a);
 160       assert(base(ret.end()) == a + 4);
 161     }
 162   }
 163
 164   { // pattern is longer than range
 165     {
 166       int a[] = {6, 7, 8};
 167       int p[] = {6, 7, 8, 9};
 168       auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p + 4)));
 169       assert(base(ret.begin()) == a + 3);
 170       assert(base(ret.end()) == a + 3);
 171     }
 172     {
 173       int a[] = {6, 7, 8};
 174       int p[] = {6, 7, 8, 9};
 175       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3)));
 176       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4)));
 177       auto ret = std::ranges::search(range1, range2);
 178       assert(base(ret.begin()) == a + 3);
 179       assert(base(ret.end()) == a + 3);
 180     }
 181   }
 182
 183   { // pattern has zero length
 184     {
 185       int a[] = {6, 7, 8};
 186       int p[] = {};
 187       auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p), Sent2(Iter2(p)));
 188       assert(base(ret.begin()) == a);
 189       assert(base(ret.end()) == a);
 190     }
 191     {
 192       int a[] = {6, 7, 8};
 193       int p[] = {};
 194       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3)));
 195       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p)));
 196       auto ret = std::ranges::search(range1, range2);
 197       assert(base(ret.begin()) == a);
 198       assert(base(ret.end()) == a);
 199     }
 200   }
 201
 202   { // range has zero length
 203     {
 204       int a[] = {};
 205       int p[] = {6, 7, 8};
 206       auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a)), Iter2(p), Sent2(Iter2(p + 3)));
 207       assert(base(ret.begin()) == a);
 208       assert(base(ret.end()) == a);
 209     }
 210     {
 211       int a[] = {};
 212       int p[] = {6, 7, 8};
 213       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a)));
 214       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
 215       auto ret = std::ranges::search(range1, range2);
 216       assert(base(ret.begin()) == a);
 217       assert(base(ret.end()) == a);
 218     }
 219   }
 220
 221   { // check that the first match is returned
 222     {
 223       int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8};
 224       int p[] = {6, 7, 8};
 225       auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 9)), Iter2(p), Sent2(Iter2(p + 3)));
 226       assert(base(ret.begin()) == a);
 227       assert(base(ret.end()) == a + 3);
 228     }
 229     {
 230       int a[] = {6, 7, 8, 6, 7, 8, 6, 7, 8};
 231       int p[] = {6, 7, 8};
 232       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 9)));
 233       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
 234       auto ret = std::ranges::search(range1, range2);
 235       assert(base(ret.begin()) == a);
 236       assert(base(ret.end()) == a + 3);
 237     }
 238   }
 239
 240   { // check that the predicate is used
 241     {
 242       int a[] = {1, 2, 8, 1, 5, 6};
 243       int p[] = {7, 0, 4};
 244       auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)),
 245                                      Iter2(p), Sent2(Iter2(p + 3)),
 246                                      [](int l, int r) { return l > r; });
 247       assert(base(ret.begin()) == a + 2);
 248       assert(base(ret.end()) == a + 5);
 249     }
 250     {
 251       int a[] = {1, 2, 8, 1, 5, 6};
 252       int p[] = {7, 0, 4};
 253       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
 254       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
 255       auto ret = std::ranges::search(range1, range2, [](int l, int r) { return l > r; });
 256       assert(base(ret.begin()) == a + 2);
 257       assert(base(ret.end()) == a + 5);
 258     }
 259   }
 260
 261   { // check that the projections are used
 262     {
 263       int a[] = {1, 3, 5, 1, 5, 6};
 264       int p[] = {2, 3, 4};
 265       auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 6)),
 266                                      Iter2(p), Sent2(Iter2(p + 3)),
 267                                      {},
 268                                      [](int i) { return i + 3; },
 269                                      [](int i) { return i * 2; });
 270       assert(base(ret.begin()) == a);
 271       assert(base(ret.end()) == a + 3);
 272     }
 273     {
 274       int a[] = {1, 3, 5, 1, 5, 6};
 275       int p[] = {2, 3, 4};
 276       auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));
 277       auto range2 = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));
 278       auto ret = std::ranges::search(range1,
 279                                      range2,
 280                                      {},
 281                                      [](int i) { return i + 3; },
 282                                      [](int i) { return i * 2; });
 283       assert(base(ret.begin()) == a);
 284       assert(base(ret.end()) == a + 3);
 285     }
 286   }
 287 }
 288
 289 template <class Iter1, class Sent1 = Iter1>
 290 constexpr void test_iterators2() {
 291   test_iterators<Iter1, Sent1, forward_iterator<int*>>();
 292   test_iterators<Iter1, Sent1, forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
 293   test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>();
 294   test_iterators<Iter1, Sent1, bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
 295   test_iterators<Iter1, Sent1, random_access_iterator<int*>>();
 296   test_iterators<Iter1, Sent1, random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
 297   test_iterators<Iter1, Sent1, contiguous_iterator<int*>>();
 298   test_iterators<Iter1, Sent1, contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
 299   test_iterators<Iter1, Sent1, int*>();
 300 }
 301
 302 constexpr bool test() {
 303   test_iterators2<forward_iterator<int*>>();
 304   test_iterators2<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
 305   test_iterators2<bidirectional_iterator<int*>>();
 306   test_iterators2<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
 307   test_iterators2<random_access_iterator<int*>>();
 308   test_iterators2<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
 309   test_iterators2<contiguous_iterator<int*>>();
 310   test_iterators2<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
 311   test_iterators2<int*>();
 312
 313   { // check that std::invoke is used
 314     struct S {
 315       int i;
 316
 317       constexpr S identity() {
 318         return *this;
 319       }
 320
 321       constexpr bool compare(const S& s) {
 322         return i == s.i;
 323       }
 324     };
 325     {
 326       S a[] = {{1}, {2}, {3}, {4}};
 327       S p[] = {{2}, {3}};
 328       auto ret = std::ranges::search(a, a + 4, p, p + 2, &S::compare, &S::identity, &S::identity);
 329       assert(ret.begin() == a + 1);
 330       assert(ret.end() == a + 3);
 331     }
 332     {
 333       S a[] = {{1}, {2}, {3}, {4}};
 334       S p[] = {{2}, {3}};
 335       auto ret = std::ranges::search(a, p, &S::compare, &S::identity, &S::identity);
 336       assert(ret.begin() == a + 1);
 337       assert(ret.end() == a + 3);
 338     }
 339   }
 340
 341   { // check that std::ranges::dangling is returned
 342     [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
 343         std::ranges::search(std::array {1, 2, 3, 4}, std::array {2, 3});
 344   }
 345
 346   return true;
 347 }
 348
 349 int main(int, char**) {
 350   test();
 351   static_assert(test());
 352
 353   return 0;
 354 }