306 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++17, c++2012 13// template<input_iterator I1, sentinel_for<I1> S1, input_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 bool ranges::ends_with(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},17// Proj1 proj1 = {}, Proj2 proj2 = {});18// template<input_range R1, input_range R2, class Pred = ranges::equal_to, class Proj1 = identity,19// class Proj2 = identity>20// requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>21// constexpr bool ranges::ends_with(R1&& r1, R2&& r2, Pred pred = {},22// Proj1 proj1 = {}, Proj2 proj2 = {});23 24#include <algorithm>25#include <array>26#include <chrono>27#include <ranges>28 29#include "almost_satisfies_types.h"30#include "test_iterators.h"31#include "type_algorithms.h"32 33using namespace std::chrono;34 35template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2>36concept HasEndsWithIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {37 std::ranges::ends_with(first1, last1, first2, last2);38};39 40static_assert(HasEndsWithIt<int*>);41static_assert(!HasEndsWithIt<ForwardIteratorNotDerivedFrom>);42static_assert(!HasEndsWithIt<ForwardIteratorNotIncrementable>);43static_assert(HasEndsWithIt<int*, int*>);44static_assert(!HasEndsWithIt<int*, SentinelForNotSemiregular>);45static_assert(!HasEndsWithIt<int*, int*, int**>); // not indirectly comparable46static_assert(!HasEndsWithIt<int*, SentinelForNotWeaklyEqualityComparableWith>);47static_assert(!HasEndsWithIt<int*, int*, ForwardIteratorNotDerivedFrom>);48static_assert(!HasEndsWithIt<int*, int*, ForwardIteratorNotIncrementable>);49static_assert(!HasEndsWithIt<int*, int*, int*, SentinelForNotSemiregular>);50static_assert(!HasEndsWithIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);51 52template <class Range1, class Range2 = UncheckedRange<int*>>53concept HasEndsWithR = requires(Range1&& range1, Range2&& range2) {54 std::ranges::ends_with(std::forward<Range1>(range1), std::forward<Range2>(range2));55};56 57static_assert(HasEndsWithR<UncheckedRange<int*>>);58static_assert(!HasEndsWithR<ForwardRangeNotDerivedFrom>);59static_assert(!HasEndsWithR<ForwardIteratorNotIncrementable>);60static_assert(!HasEndsWithR<ForwardRangeNotSentinelSemiregular>);61static_assert(!HasEndsWithR<ForwardRangeNotSentinelEqualityComparableWith>);62static_assert(HasEndsWithR<UncheckedRange<int*>, UncheckedRange<int*>>);63static_assert(!HasEndsWithR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable64static_assert(!HasEndsWithR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);65static_assert(!HasEndsWithR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);66 67template <class Iter1, class Sent1 = Iter1, class Iter2, class Sent2 = Iter2>68constexpr void test_iterators() {69 { // simple tests70 int a[] = {1, 2, 3, 4, 5, 6};71 int p[] = {4, 5, 6};72 {73 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));74 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));75 [[maybe_unused]] std::same_as<bool> decltype(auto) ret =76 std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());77 assert(ret);78 }79 {80 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));81 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));82 [[maybe_unused]] std::same_as<bool> decltype(auto) ret = std::ranges::ends_with(whole, suffix);83 assert(ret);84 }85 }86 87 { // suffix doesn't match88 int a[] = {1, 2, 3, 4, 5, 6};89 int p[] = {1, 2, 3};90 {91 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));92 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));93 bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());94 assert(!ret);95 }96 {97 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));98 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));99 bool ret = std::ranges::ends_with(whole, suffix);100 assert(!ret);101 }102 }103 104 { // range consists of just one element105 int a[] = {1};106 int p[] = {1};107 {108 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 1)));109 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1)));110 bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());111 assert(ret);112 }113 {114 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 1)));115 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1)));116 bool ret = std::ranges::ends_with(whole, suffix);117 assert(ret);118 }119 }120 121 { // suffix consists of just one element122 int a[] = {5, 1, 2, 4, 3};123 int p[] = {3};124 {125 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));126 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1)));127 bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());128 assert(ret);129 }130 {131 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));132 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 1)));133 bool ret = std::ranges::ends_with(whole, suffix);134 assert(ret);135 }136 }137 138 { // range and suffix are identical139 int a[] = {1, 2, 3, 4, 5, 6};140 int p[] = {1, 2, 3, 4, 5, 6};141 {142 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));143 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 6)));144 bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());145 assert(ret);146 }147 {148 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));149 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 6)));150 bool ret = std::ranges::ends_with(whole, suffix);151 assert(ret);152 }153 }154 155 { // suffix is longer than range156 int a[] = {3, 4, 5, 6, 7, 8};157 int p[] = {1, 2, 3, 4, 5, 6, 7, 8};158 {159 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));160 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8)));161 bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());162 assert(!ret);163 }164 {165 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));166 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8)));167 bool ret = std::ranges::ends_with(whole, suffix);168 assert(!ret);169 }170 }171 172 { // suffix has zero length173 int a[] = {1, 2, 3, 4, 5, 6};174 std::array<int, 0> p = {};175 {176 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));177 auto suffix = std::ranges::subrange(Iter2(p.data()), Sent2(Iter2(p.data())));178 bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());179 assert(ret);180 }181 {182 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));183 auto suffix = std::ranges::subrange(Iter2(p.data()), Sent2(Iter2(p.data())));184 bool ret = std::ranges::ends_with(whole, suffix);185 assert(ret);186 }187 }188 189 { // range has zero length190 std::array<int, 0> a = {};191 int p[] = {1, 2, 3, 4, 5, 6, 7, 8};192 {193 auto whole = std::ranges::subrange(Iter1(a.data()), Sent1(Iter1(a.data())));194 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8)));195 bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());196 assert(!ret);197 }198 {199 auto whole = std::ranges::subrange(Iter1(a.data()), Sent1(Iter1(a.data())));200 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 8)));201 bool ret = std::ranges::ends_with(whole, suffix);202 assert(!ret);203 }204 }205 206 { // subarray207 int a[] = {0, 3, 5, 10, 7, 3, 5, 89, 3, 5, 2, 1, 8, 6};208 int p[] = {3, 5};209 {210 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 13)));211 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));212 bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());213 assert(!ret);214 }215 {216 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 13)));217 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));218 bool ret = std::ranges::ends_with(whole, suffix);219 assert(!ret);220 }221 }222 223 { // repeated suffix224 int a[] = {8, 6, 3, 5, 1, 2};225 int p[] = {1, 2, 1, 2};226 {227 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));228 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4)));229 bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end());230 assert(!ret);231 }232 {233 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));234 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 4)));235 bool ret = std::ranges::ends_with(whole, suffix);236 assert(!ret);237 }238 }239 240 { // check that the predicate is used241 int a[] = {5, 1, 3, 2, 7};242 int p[] = {-2, -7};243 auto pred = [](int l, int r) { return l * -1 == r; };244 {245 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));246 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));247 bool ret = std::ranges::ends_with(whole.begin(), whole.end(), suffix.begin(), suffix.end(), pred);248 assert(ret);249 }250 {251 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5)));252 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 2)));253 bool ret = std::ranges::ends_with(whole, suffix, pred);254 assert(ret);255 }256 }257 258 { // check that the projections are used259 int a[] = {1, 3, 15, 1, 2, 1};260 int p[] = {2, 1, 2};261 {262 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));263 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));264 bool ret = std::ranges::ends_with(265 whole.begin(),266 whole.end(),267 suffix.begin(),268 suffix.end(),269 {},270 [](int i) { return i - 3; },271 [](int i) { return i * -1; });272 assert(ret);273 }274 {275 auto whole = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 6)));276 auto suffix = std::ranges::subrange(Iter2(p), Sent2(Iter2(p + 3)));277 bool ret = std::ranges::ends_with(whole, suffix, {}, [](int i) { return i - 3; }, [](int i) { return i * -1; });278 assert(ret);279 }280 }281}282 283constexpr bool test() {284 // This is to test (forward_iterator<_Iter1> || sized_sentinel_for<_Sent1, _Iter1>) condition.285 types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter2>() {286 types::for_each(types::cpp20_input_iterator_list<int*>{}, []<class Iter1>() {287 if constexpr (std::forward_iterator<Iter1> && std::forward_iterator<Iter2>)288 test_iterators<Iter1, Iter1, Iter2, Iter2>();289 if constexpr (std::forward_iterator<Iter2>)290 test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, Iter2>();291 if constexpr (std::forward_iterator<Iter1>)292 test_iterators<Iter1, Iter1, Iter2, sized_sentinel<Iter2>>();293 test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, sized_sentinel<Iter2>>();294 });295 });296 297 return true;298}299 300int main(int, char**) {301 test();302 static_assert(test());303 304 return 0;305}306