262 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<forward_iterator I, sentinel_for<I> S, class Proj = identity,14// indirect_unary_predicate<projected<I, Proj>> Pred>15// constexpr subrange<I> ranges::find_last_if(I first, S last, Pred pred, Proj proj = {});16// template<forward_range R, class Proj = identity,17// indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>18// constexpr borrowed_subrange_t<R> ranges::find_last_if(R&& r, Pred pred, Proj proj = {});19 20#include <algorithm>21#include <array>22#include <cassert>23#include <ranges>24 25#include "almost_satisfies_types.h"26#include "test_iterators.h"27 28struct Predicate {29 bool operator()(int);30};31 32template <class It, class Sent = It>33concept HasFindLastIfIt = requires(It it, Sent sent) { std::ranges::find_last_if(it, sent, Predicate{}); };34static_assert(HasFindLastIfIt<int*>);35static_assert(HasFindLastIfIt<forward_iterator<int*>>);36static_assert(!HasFindLastIfIt<cpp20_input_iterator<int*>>);37static_assert(!HasFindLastIfIt<ForwardIteratorNotDerivedFrom>);38static_assert(!HasFindLastIfIt<ForwardIteratorNotIncrementable>);39static_assert(!HasFindLastIfIt<forward_iterator<int*>, SentinelForNotSemiregular>);40static_assert(!HasFindLastIfIt<forward_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);41 42static_assert(!HasFindLastIfIt<int*, int>);43static_assert(!HasFindLastIfIt<int, int*>);44 45template <class Pred>46concept HasFindLastIfPred = requires(int* it, Pred pred) { std::ranges::find_last_if(it, it, pred); };47 48static_assert(!HasFindLastIfPred<IndirectUnaryPredicateNotCopyConstructible>);49static_assert(!HasFindLastIfPred<IndirectUnaryPredicateNotPredicate>);50 51template <class R>52concept HasFindLastIfR = requires(R r) { std::ranges::find_last_if(r, Predicate{}); };53static_assert(HasFindLastIfR<std::array<int, 0>>);54static_assert(!HasFindLastIfR<int>);55static_assert(!HasFindLastIfR<ForwardRangeNotDerivedFrom>);56static_assert(!HasFindLastIfR<ForwardRangeNotIncrementable>);57static_assert(!HasFindLastIfR<ForwardRangeNotSentinelSemiregular>);58static_assert(!HasFindLastIfR<ForwardRangeNotSentinelEqualityComparableWith>);59 60template <class It, class Sent>61constexpr auto make_range(auto& a) {62 return std::ranges::subrange(It(std::ranges::begin(a)), Sent(It(std::ranges::end(a))));63}64 65template <template <class> class IteratorT, template <class> class SentinelT>66constexpr void test_iterator_classes() {67 {68 using it = IteratorT<int*>;69 using sent = SentinelT<it>;70 71 {72 int a[] = {1, 2, 3, 4};73 std::same_as<std::ranges::subrange<it>> auto ret =74 std::ranges::find_last_if(it(a), sent(it(a + 4)), [](int x) { return x == 4; });75 assert(base(ret.begin()) == a + 3);76 assert(*ret.begin() == 4);77 }78 {79 int a[] = {1, 2, 3, 4};80 81 std::same_as<std::ranges::subrange<it>> auto ret =82 std::ranges::find_last_if(make_range<it, sent>(a), [](int x) { return x == 4; });83 assert(ret.begin() == it(a + 3));84 assert(*ret.begin() == 4);85 }86 }87 88 { // check that an empty range works89 using it = IteratorT<std::ranges::iterator_t<std::array<int, 0>&>>;90 using sent = SentinelT<it>;91 92 {93 std::array<int, 0> a = {};94 95 auto ret = std::ranges::find_last_if(it(a.begin()), sent(it(a.end())), [](auto&&) { return true; }).begin();96 assert(ret == it(a.end()));97 }98 {99 std::array<int, 0> a = {};100 101 auto ret = std::ranges::find_last_if(make_range<it, sent>(a), [](auto&&) { return true; }).begin();102 assert(ret == it(a.end()));103 }104 }105 106 { // check that last is returned with no match107 using it = IteratorT<int*>;108 using sent = SentinelT<it>;109 110 {111 int a[] = {1, 1, 1};112 113 auto ret = std::ranges::find_last_if(it(a), sent(it(a + 3)), [](auto&&) { return false; }).begin();114 assert(ret == it(a + 3));115 }116 {117 int a[] = {1, 1, 1};118 119 auto ret = std::ranges::find_last_if(make_range<it, sent>(a), [](auto&&) { return false; }).begin();120 assert(ret == it(a + 3));121 }122 }123 124 { // check that the last element is returned125 struct S {126 int comp;127 int other;128 };129 using it = IteratorT<S*>;130 using sent = SentinelT<it>;131 132 S a[] = {{0, 0}, {0, 2}, {0, 1}};133 134 auto ret = std::ranges::find_last_if(135 it(std::begin(a)), sent(it(std::end(a))), [](int c) { return c == 0; }, &S::comp)136 .begin();137 assert(ret == it(a + 2));138 assert((*ret).comp == 0);139 assert((*ret).other == 1);140 }141 142 {143 // count projection and predicate invocation count144 {145 int a[] = {1, 2, 3, 4};146 int predicate_count = 0;147 int projection_count = 0;148 149 using it = IteratorT<int*>;150 using sent = SentinelT<it>;151 152 auto ret =153 std::ranges::find_last_if(154 it(a),155 sent(it(a + 4)),156 [&](int i) {157 ++predicate_count;158 return i == 2;159 },160 [&](int i) {161 ++projection_count;162 return i;163 })164 .begin();165 assert(ret == it(a + 1));166 assert(*ret == 2);167 168 if constexpr (std::bidirectional_iterator<it>) {169 assert(predicate_count == 3);170 assert(projection_count == 3);171 } else {172 assert(predicate_count == 4);173 assert(projection_count == 4);174 }175 }176 }177}178 179struct NonConstComparable {180 friend constexpr bool operator==(const NonConstComparable&, const NonConstComparable&) { return false; }181 friend constexpr bool operator==(NonConstComparable&, NonConstComparable&) { return false; }182 friend constexpr bool operator==(const NonConstComparable&, NonConstComparable&) { return false; }183 friend constexpr bool operator==(NonConstComparable&, const NonConstComparable&) { return true; }184};185 186// TODO: this should really use `std::const_iterator`187template <class T>188struct add_const_to_ptr {189 using type = T;190};191template <class T>192struct add_const_to_ptr<T*> {193 using type = const T*;194};195template <class T>196using add_const_to_ptr_t = typename add_const_to_ptr<T>::type;197 198constexpr bool test() {199 test_iterator_classes<std::type_identity_t, std::type_identity_t>();200 test_iterator_classes<add_const_to_ptr_t, std::type_identity_t>();201 test_iterator_classes<contiguous_iterator, std::type_identity_t>();202 test_iterator_classes<random_access_iterator, std::type_identity_t>();203 test_iterator_classes<bidirectional_iterator, std::type_identity_t>();204 test_iterator_classes<forward_iterator, std::type_identity_t>();205 test_iterator_classes<forward_iterator, sentinel_wrapper>();206 207 {208 // check that projections are used properly and that they are called with the iterator directly209 {210 int a[] = {1, 2, 3, 4};211 auto ret =212 std::ranges::find_last_if(a, a + 4, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; }).begin();213 assert(ret == a + 3);214 }215 {216 int a[] = {1, 2, 3, 4};217 auto ret = std::ranges::find_last_if(a, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; }).begin();218 assert(ret == a + 3);219 }220 }221 222 {223 // check that ranges::dangling is returned224 [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret =225 std::ranges::find_last_if(std::array{1, 2}, [](int) { return false; });226 }227 228 {229 // check that a subrange is returned with a borrowing range230 int a[] = {1, 2, 3, 4};231 std::same_as<std::ranges::subrange<int*>> auto ret =232 std::ranges::find_last_if(std::views::all(a), [](int) { return true; });233 assert(ret.begin() == a + 3);234 assert(*ret.begin() == 4);235 }236 237 {238 // check that the return type of `iter::operator*` doesn't change239 {240 NonConstComparable a[] = {NonConstComparable{}};241 242 auto ret = std::ranges::find_last_if(a, a + 1, [](auto&& e) { return e == NonConstComparable{}; }).begin();243 assert(ret == a);244 }245 {246 NonConstComparable a[] = {NonConstComparable{}};247 248 auto ret = std::ranges::find_last_if(a, [](auto&& e) { return e == NonConstComparable{}; }).begin();249 assert(ret == a);250 }251 }252 253 return true;254}255 256int main(int, char**) {257 test();258 static_assert(test());259 260 return 0;261}262