355 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 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 34template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2>35concept HasSearchIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {36 std::ranges::search(first1, last1, first2, last2);37};38 39static_assert(HasSearchIt<int*>);40static_assert(!HasSearchIt<ForwardIteratorNotDerivedFrom>);41static_assert(!HasSearchIt<ForwardIteratorNotIncrementable>);42static_assert(!HasSearchIt<int*, SentinelForNotSemiregular>);43static_assert(!HasSearchIt<int*, int*, int**>); // not indirectly comparable44static_assert(!HasSearchIt<int*, SentinelForNotWeaklyEqualityComparableWith>);45static_assert(!HasSearchIt<int*, int*, ForwardIteratorNotDerivedFrom>);46static_assert(!HasSearchIt<int*, int*, ForwardIteratorNotIncrementable>);47static_assert(!HasSearchIt<int*, int*, int*, SentinelForNotSemiregular>);48static_assert(!HasSearchIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);49 50template <class Range1, class Range2 = UncheckedRange<int*>>51concept HasSearchR = requires (Range1 range1, Range2 range2) {52 std::ranges::search(range1, range2);53};54 55static_assert(HasSearchR<UncheckedRange<int*>>);56static_assert(!HasSearchR<ForwardRangeNotDerivedFrom>);57static_assert(!HasSearchR<ForwardIteratorNotIncrementable>);58static_assert(!HasSearchR<ForwardRangeNotSentinelSemiregular>);59static_assert(!HasSearchR<ForwardRangeNotSentinelEqualityComparableWith>);60static_assert(!HasSearchR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable61static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);62static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);63static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);64static_assert(!HasSearchR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);65 66template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2>67constexpr void test_iterators() {68 { // simple test69 {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 front89 {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 back108 {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 match127 {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 identical146 {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 range165 {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 length184 {185 int a[] = {6, 7, 8};186 std::array<int, 0> p = {};187 auto ret = std::ranges::search(Iter1(a), Sent1(Iter1(a + 3)), Iter2(p.data()), Sent2(Iter2(p.data())));188 assert(base(ret.begin()) == a);189 assert(base(ret.end()) == a);190 }191 {192 int a[] = {6, 7, 8};193 std::array<int, 0> p = {};194 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 3)));195 auto range2 = std::ranges::subrange(Iter2(p.data()), Sent2(Iter2(p.data())));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 length203 {204 std::array<int, 0> a = {};205 int p[] = {6, 7, 8};206 auto ret = std::ranges::search(Iter1(a.data()), Sent1(Iter1(a.data())), Iter2(p), Sent2(Iter2(p + 3)));207 assert(base(ret.begin()) == a.data());208 assert(base(ret.end()) == a.data());209 }210 {211 std::array<int, 0> a = {};212 int p[] = {6, 7, 8};213 auto range1 = std::ranges::subrange(Iter1(a.data()), Sent1(Iter1(a.data())));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.data());217 assert(base(ret.end()) == a.data());218 }219 }220 221 { // check that the first match is returned222 {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 used241 {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 used262 {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 289template <class Iter1, class Sent1 = Iter1>290constexpr 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 302constexpr 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 used314 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 returned342 [[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 349int main(int, char**) {350 test();351 static_assert(test());352 353 return 0;354}355