298 lines · 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-exception6//7//===----------------------------------------------------------------------===//8 9// <algorithm>10 11// UNSUPPORTED: c++03, c++11, c++14, c++1712 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 33template <class Iter1, class Sent1 = Iter1>34concept HasSearchNIt = requires (Iter1 first1, Sent1 last1) {35 std::ranges::search_n(first1, last1, 0, 0);36};37 38static_assert(HasSearchNIt<int*>);39static_assert(!HasSearchNIt<ForwardIteratorNotDerivedFrom>);40static_assert(!HasSearchNIt<ForwardIteratorNotIncrementable>);41static_assert(!HasSearchNIt<int*, SentinelForNotSemiregular>);42static_assert(!HasSearchNIt<int*, SentinelForNotWeaklyEqualityComparableWith>);43static_assert(!HasSearchNIt<int**, int**>); // not indirectly comparable44 45template <class Range1, class Range2 = UncheckedRange<int*>>46concept HasSearchNR = requires (Range1 range) {47 std::ranges::search_n(range, 0, 0);48};49 50static_assert(HasSearchNR<UncheckedRange<int*>>);51static_assert(!HasSearchNR<ForwardRangeNotDerivedFrom>);52static_assert(!HasSearchNR<ForwardIteratorNotIncrementable>);53static_assert(!HasSearchNR<ForwardRangeNotSentinelSemiregular>);54static_assert(!HasSearchNR<ForwardRangeNotSentinelEqualityComparableWith>);55static_assert(!HasSearchNR<UncheckedRange<int**>>); // not indirectly comparable56 57template <class Iter, class Sent = Iter>58constexpr void test_iterators() {59 { // simple test60 {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 front77 {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 back93 {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 match109 {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 identical125 {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 range141 {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 length157 {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 length173 {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 returned189 {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 used205 {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 used224 {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}247constexpr 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 used259 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 returned285 [[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 292int main(int, char**) {293 test();294 static_assert(test());295 296 return 0;297}298