libcxx/test/std/algorithms/alg.nonmodifying/alg.search/ranges.search_n.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 I, sentinel_for<I> S, class T,
  14 //          class Pred = ranges::equal_to, class Proj = identity>
  15 //   requires indirectly_comparable<I, const T*, Pred, Proj>
  16 //   constexpr subrange<I>
  17 //     ranges::search_n(I first, S last, iter_difference_t<I> count,
  18 //                      const T& value, Pred pred = {}, Proj proj = {});
  19 // template<forward_range R, class T, class Pred = ranges::equal_to,
  20 //          class Proj = identity>
  21 //   requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
  22 //   constexpr borrowed_subrange_t<R>
  23 //     ranges::search_n(R&& r, range_difference_t<R> count,
  24 //                      const T& value, Pred pred = {}, Proj proj = {});
  25
  26 #include <algorithm>
  27 #include <array>
  28 #include <ranges>
  29
  30 #include "almost_satisfies_types.h"
  31 #include "test_iterators.h"
  32
  33 template <class Iter1, class Sent1 = Iter1>
  34 concept HasSearchNIt = requires (Iter1 first1, Sent1 last1) {
  35   std::ranges::search_n(first1, last1, 0, 0);
  36 };
  37
  38 static_assert(HasSearchNIt<int*>);
  39 static_assert(!HasSearchNIt<ForwardIteratorNotDerivedFrom>);
  40 static_assert(!HasSearchNIt<ForwardIteratorNotIncrementable>);
  41 static_assert(!HasSearchNIt<int*, SentinelForNotSemiregular>);
  42 static_assert(!HasSearchNIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
  43 static_assert(!HasSearchNIt<int**, int**>); // not indirectly comparable
  44
  45 template <class Range1, class Range2 = UncheckedRange<int*>>
  46 concept HasSearchNR = requires (Range1 range) {
  47   std::ranges::search_n(range, 0, 0);
  48 };
  49
  50 static_assert(HasSearchNR<UncheckedRange<int*>>);
  51 static_assert(!HasSearchNR<ForwardRangeNotDerivedFrom>);
  52 static_assert(!HasSearchNR<ForwardIteratorNotIncrementable>);
  53 static_assert(!HasSearchNR<ForwardRangeNotSentinelSemiregular>);
  54 static_assert(!HasSearchNR<ForwardRangeNotSentinelEqualityComparableWith>);
  55 static_assert(!HasSearchNR<UncheckedRange<int**>>); // not indirectly comparable
  56
  57 template <class Iter, class Sent = Iter>
  58 constexpr void test_iterators() {
  59   { // simple test
  60     {
  61       int a[] = {1, 2, 3, 4, 5, 6};
  62       std::same_as<std::ranges::subrange<Iter, Iter>> decltype(auto) ret =
  63           std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), 1, 3);
  64       assert(base(ret.begin()) == a + 2);
  65       assert(base(ret.end()) == a + 3);
  66     }
  67     {
  68       int a[] = {1, 2, 3, 4, 5, 6};
  69       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
  70       std::same_as<std::ranges::subrange<Iter, Iter>> decltype(auto) ret = std::ranges::search_n(range, 1, 3);
  71       assert(base(ret.begin()) == a + 2);
  72       assert(base(ret.end()) == a + 3);
  73     }
  74   }
  75
  76   { // matching part begins at the front
  77     {
  78       int a[] = {7, 7, 3, 7, 3, 6};
  79       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)), 2, 7);
  80       assert(base(ret.begin()) == a);
  81       assert(base(ret.end()) == a + 2);
  82     }
  83     {
  84       int a[] = {7, 7, 3, 7, 3, 6};
  85       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
  86       auto ret = std::ranges::search_n(range, 2, 7);
  87       assert(base(ret.begin()) == a);
  88       assert(base(ret.end()) == a + 2);
  89     }
  90   }
  91
  92   { // matching part ends at the back
  93     {
  94       int a[] = {9, 3, 6, 4, 4};
  95       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 5)), 2, 4);
  96       assert(base(ret.begin()) == a + 3);
  97       assert(base(ret.end()) == a + 5);
  98     }
  99     {
 100       int a[] = {9, 3, 6, 4, 4};
 101       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5)));
 102       auto ret = std::ranges::search_n(range, 2, 4);
 103       assert(base(ret.begin()) == a + 3);
 104       assert(base(ret.end()) == a + 5);
 105     }
 106   }
 107
 108   { // pattern does not match
 109     {
 110       int a[] = {9, 3, 6, 4, 8};
 111       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 5)), 1, 1);
 112       assert(base(ret.begin()) == a + 5);
 113       assert(base(ret.end()) == a + 5);
 114     }
 115     {
 116       int a[] = {9, 3, 6, 4, 8};
 117       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5)));
 118       auto ret = std::ranges::search_n(range, 1, 1);
 119       assert(base(ret.begin()) == a + 5);
 120       assert(base(ret.end()) == a + 5);
 121     }
 122   }
 123
 124   { // range and pattern are identical
 125     {
 126       int a[] = {1, 1, 1, 1};
 127       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 4)), 4, 1);
 128       assert(base(ret.begin()) == a);
 129       assert(base(ret.end()) == a + 4);
 130     }
 131     {
 132       int a[] = {1, 1, 1, 1};
 133       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 4)));
 134       auto ret = std::ranges::search_n(range, 4, 1);
 135       assert(base(ret.begin()) == a);
 136       assert(base(ret.end()) == a + 4);
 137     }
 138   }
 139
 140   { // pattern is longer than range
 141     {
 142       int a[] = {3, 3, 3};
 143       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 3)), 4, 3);
 144       assert(base(ret.begin()) == a + 3);
 145       assert(base(ret.end()) == a + 3);
 146     }
 147     {
 148       int a[] = {3, 3, 3};
 149       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
 150       auto ret = std::ranges::search_n(range, 4, 3);
 151       assert(base(ret.begin()) == a + 3);
 152       assert(base(ret.end()) == a + 3);
 153     }
 154   }
 155
 156   { // pattern has zero length
 157     {
 158       int a[] = {6, 7, 8};
 159       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 3)), 0, 7);
 160       assert(base(ret.begin()) == a);
 161       assert(base(ret.end()) == a);
 162     }
 163     {
 164       int a[] = {6, 7, 8};
 165       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 3)));
 166       auto ret = std::ranges::search_n(range, 0, 7);
 167       assert(base(ret.begin()) == a);
 168       assert(base(ret.end()) == a);
 169     }
 170   }
 171
 172   { // range has zero length
 173     {
 174       std::array<int, 0> a = {};
 175       auto ret             = std::ranges::search_n(Iter(a.data()), Sent(Iter(a.data())), 1, 1);
 176       assert(base(ret.begin()) == a.data());
 177       assert(base(ret.end()) == a.data());
 178     }
 179     {
 180       std::array<int, 0> a = {};
 181       auto range           = std::ranges::subrange(Iter(a.data()), Sent(Iter(a.data())));
 182       auto ret = std::ranges::search_n(range, 1, 1);
 183       assert(base(ret.begin()) == a.data());
 184       assert(base(ret.end()) == a.data());
 185     }
 186   }
 187
 188   { // check that the first match is returned
 189     {
 190       int a[] = {6, 6, 8, 6, 6, 8, 6, 6, 8};
 191       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 9)), 2, 6);
 192       assert(base(ret.begin()) == a);
 193       assert(base(ret.end()) == a + 2);
 194     }
 195     {
 196       int a[] = {6, 6, 8, 6, 6, 8, 6, 6, 8};
 197       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 9)));
 198       auto ret = std::ranges::search_n(range, 2, 6);
 199       assert(base(ret.begin()) == a);
 200       assert(base(ret.end()) == a + 2);
 201     }
 202   }
 203
 204   { // check that the predicate is used
 205     {
 206       int a[] = {1, 4, 4, 3, 6, 1};
 207       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)),
 208                                        3,
 209                                        4,
 210                                        [](int l, int r) { return l == r || l == 1; });
 211       assert(base(ret.begin()) == a);
 212       assert(base(ret.end()) == a + 3);
 213     }
 214     {
 215       int a[] = {1, 4, 4, 3, 6, 1};
 216       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
 217       auto ret = std::ranges::search_n(range, 3, 4, [](int l, int r) { return l == r || l == 1; });
 218       assert(base(ret.begin()) == a);
 219       assert(base(ret.end()) == a + 3);
 220     }
 221   }
 222
 223   { // check that the projections are used
 224     {
 225       int a[] = {1, 3, 1, 6, 5, 6};
 226       auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a + 6)),
 227                                        3,
 228                                        6,
 229                                        {},
 230                                        [](int i) { return i % 2 == 0 ? i : i + 1; });
 231       assert(base(ret.begin()) == a + 3);
 232       assert(base(ret.end()) == a + 6);
 233     }
 234     {
 235       int a[] = {1, 3, 1, 6, 5, 6};
 236       auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
 237       auto ret = std::ranges::search_n(range,
 238                                        3,
 239                                        6,
 240                                        {},
 241                                        [](int i) { return i % 2 == 0 ? i : i + 1; });
 242       assert(base(ret.begin()) == a + 3);
 243       assert(base(ret.end()) == a + 6);
 244     }
 245   }
 246 }
 247 constexpr bool test() {
 248   test_iterators<forward_iterator<int*>>();
 249   test_iterators<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
 250   test_iterators<bidirectional_iterator<int*>>();
 251   test_iterators<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
 252   test_iterators<random_access_iterator<int*>>();
 253   test_iterators<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
 254   test_iterators<contiguous_iterator<int*>>();
 255   test_iterators<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
 256   test_iterators<int*>();
 257
 258   { // check that std::invoke is used
 259     struct S {
 260       int i;
 261
 262       constexpr S identity() {
 263         return *this;
 264       }
 265
 266       constexpr bool compare(int o) {
 267         return i == o;
 268       }
 269     };
 270     {
 271       S a[] = {{1}, {2}, {3}, {4}};
 272       auto ret = std::ranges::search_n(a, a + 4, 1, 2, &S::compare, &S::identity);
 273       assert(ret.begin() == a + 1);
 274       assert(ret.end() == a + 2);
 275     }
 276     {
 277       S a[] = {{1}, {2}, {3}, {4}};
 278       auto ret = std::ranges::search_n(a, 1, 2, &S::compare, &S::identity);
 279       assert(ret.begin() == a + 1);
 280       assert(ret.end() == a + 2);
 281     }
 282   }
 283
 284   { // check that std::ranges::dangling is returned
 285     [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =
 286         std::ranges::search_n(std::array {1, 2, 3, 4}, 1, 0);
 287   }
 288
 289   return true;
 290 }
 291
 292 int main(int, char**) {
 293   test();
 294   static_assert(test());
 295
 296   return 0;
 297 }