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