209 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<permutable I, sentinel_for<I> S, class Proj = identity,14// indirect_unary_predicate<projected<I, Proj>> Pred>15// constexpr subrange<I> ranges::remove_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// requires permutable<iterator_t<R>>19// constexpr borrowed_subrange_t<R>20// ranges::remove_if(R&& r, Pred pred, Proj proj = {});21 22#include <algorithm>23#include <array>24#include <cassert>25#include <ranges>26 27#include "almost_satisfies_types.h"28#include "test_iterators.h"29 30struct FalsePredicate {31 bool operator()(int) { return false; }32};33 34template <class Iter, class Sent = sentinel_wrapper<Iter>>35concept HasRemoveIfIt = requires(Iter first, Sent last) { std::ranges::remove_if(first, last, FalsePredicate{}); };36 37static_assert(HasRemoveIfIt<int*>);38static_assert(!HasRemoveIfIt<PermutableNotForwardIterator>);39static_assert(!HasRemoveIfIt<PermutableNotSwappable>);40static_assert(!HasRemoveIfIt<int*, SentinelForNotSemiregular>);41static_assert(!HasRemoveIfIt<int*, SentinelForNotWeaklyEqualityComparableWith>);42static_assert(!HasRemoveIfIt<int**>); // not indirect_unary_predicate43 44template <class Range>45concept HasRemoveIfR = requires(Range range) { std::ranges::remove_if(range, FalsePredicate{}); };46 47static_assert(HasRemoveIfR<UncheckedRange<int*>>);48static_assert(!HasRemoveIfR<PermutableRangeNotForwardIterator>);49static_assert(!HasRemoveIfR<PermutableRangeNotSwappable>);50static_assert(!HasRemoveIfR<SentinelForNotSemiregular>);51static_assert(!HasRemoveIfR<SentinelForNotWeaklyEqualityComparableWith>);52static_assert(!HasRemoveIfR<UncheckedRange<int**>>); // not indirect_unary_predicate53 54template <int N, int M>55struct Data {56 std::array<int, N> input;57 std::array<int, M> expected;58 int cutoff;59};60 61template <class Iter, class Sent, int N, int M>62constexpr void test(Data<N, M> d) {63 { // iterator overload64 auto input = d.input;65 66 auto first = Iter(input.data());67 auto last = Sent(Iter(input.data() + input.size()));68 69 std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret =70 std::ranges::remove_if(std::move(first), std::move(last), [&](int i) { return i < d.cutoff; });71 72 assert(base(ret.begin()) == input.data() + M);73 assert(base(ret.end()) == input.data() + N);74 assert(std::ranges::equal(input.data(), base(ret.begin()), d.expected.begin(), d.expected.end()));75 }76 77 { // range overload78 auto input = d.input;79 auto range = std::ranges::subrange(Iter(input.data()), Sent(Iter(input.data() + input.size())));80 81 std::same_as<std::ranges::subrange<Iter>> decltype(auto) ret = std::ranges::remove_if(range, [&](int i) {82 return i < d.cutoff;83 });84 85 assert(base(ret.begin()) == input.data() + M);86 assert(base(ret.end()) == input.data() + N);87 assert(std::ranges::equal(input.data(), base(ret.begin()), d.expected.begin(), d.expected.end()));88 }89}90 91template <class Iter, class Sent>92constexpr void tests() {93 // simple test94 test<Iter, Sent, 6, 2>({.input = {1, 2, 3, 4, 5, 6}, .expected = {5, 6}, .cutoff = 5});95 // empty range96 test<Iter, Sent, 0, 0>({});97 // single element range - no match98 test<Iter, Sent, 1, 1>({.input = {1}, .expected = {1}, .cutoff = 1});99 // single element range - match100 test<Iter, Sent, 1, 0>({.input = {1}, .expected = {}, .cutoff = 2});101 // two element range102 test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {2}, .cutoff = 2});103 // all elements match104 test<Iter, Sent, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .cutoff = 2});105 // no elements match106 test<Iter, Sent, 5, 5>({.input = {1, 1, 1, 1, 1}, .expected = {1, 1, 1, 1, 1}, .cutoff = 0});107 // the relative order of elements isn't changed108 test<Iter, Sent, 8, 7>({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {2, 3, 2, 3, 4, 2, 5}, .cutoff = 2});109 // multiple matches in a row110 test<Iter, Sent, 5, 3>({.input = {1, 2, 2, 2, 1}, .expected = {2, 2, 2}, .cutoff = 2});111 // only the last element matches112 test<Iter, Sent, 3, 2>({.input = {2, 2, 1}, .expected = {2, 2}, .cutoff = 2});113 // only the last element doesn't match114 test<Iter, Sent, 3, 1>({.input = {1, 1, 2}, .expected = {2}, .cutoff = 2});115}116 117template <class Iter>118constexpr void test_sentinels() {119 tests<Iter, Iter>();120 tests<Iter, sentinel_wrapper<Iter>>();121 tests<Iter, sized_sentinel<Iter>>();122}123 124constexpr void test_iterators() {125 test_sentinels<forward_iterator<int*>>();126 test_sentinels<bidirectional_iterator<int*>>();127 test_sentinels<random_access_iterator<int*>>();128 test_sentinels<contiguous_iterator<int*>>();129 test_sentinels<int*>();130}131 132constexpr bool test() {133 test_iterators();134 135 { // check that ranges::dangling is returned136 [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) ret =137 std::ranges::remove_if(std::array{1, 2, 3, 4}, [](int i) { return i < 0; });138 }139 140 {// check complexity requirements141 142 // This is https://llvm.org/PR56382 - clang-format behaves weird if function-local structs are used143 // clang-format off144 {145 int comp_count = 0;146 auto comp = [&](int i) {147 ++comp_count;148 return i == 0;149 };150 int proj_count = 0;151 auto proj = [&](int i) {152 ++proj_count;153 return i;154 };155 int a[] = {1, 2, 3, 4};156 auto ret = std::ranges::remove_if(std::begin(a), std::end(a), comp, proj);157 assert(ret.begin() == std::end(a) && ret.end() == std::end(a));158 assert(comp_count == 4);159 assert(proj_count == 4);160 }161 {162 int comp_count = 0;163 auto comp = [&](int i) {164 ++comp_count;165 return i == 0;166 };167 int proj_count = 0;168 auto proj = [&](int i) {169 ++proj_count;170 return i;171 };172 int a[] = {1, 2, 3, 4};173 auto ret = std::ranges::remove_if(a, comp, proj);174 assert(ret.begin() == std::end(a) && ret.end() == std::end(a));175 assert(comp_count == 4);176 assert(proj_count == 4);177 }178 }179 180 { // check that std::invoke is used181 struct S {182 constexpr S& identity() { return *this; }183 constexpr bool predicate() const { return true; }184 };185 {186 S a[4] = {};187 auto ret = std::ranges::remove_if(std::begin(a), std::end(a), &S::predicate, &S::identity);188 assert(ret.begin() == std::begin(a));189 assert(ret.end() == std::end(a));190 }191 {192 S a[4] = {};193 auto ret = std::ranges::remove_if(a, &S::predicate, &S::identity);194 assert(ret.begin() == std::begin(a));195 assert(ret.end() == std::end(a));196 }197 }198 199 return true;200}201// clang-format on202 203int main(int, char**) {204 test();205 static_assert(test());206 207 return 0;208}209