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 int a[] = {}; 175 auto ret = std::ranges::search_n(Iter(a), Sent(Iter(a)), 1, 1); 176 assert(base(ret.begin()) == a); 177 assert(base(ret.end()) == a); 178 } 179 { 180 int a[] = {}; 181 auto range = std::ranges::subrange(Iter(a), Sent(Iter(a))); 182 auto ret = std::ranges::search_n(range, 1, 1); 183 assert(base(ret.begin()) == a); 184 assert(base(ret.end()) == a); 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 } 298