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-exception
6//
7//===----------------------------------------------------------------------===//
8
9// <algorithm>
10
11// UNSUPPORTED: c++03, c++11, c++14, c++17
12
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_predicate
43
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_predicate
53
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 overload
64 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 overload
78 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 test
94 test<Iter, Sent, 6, 2>({.input = {1, 2, 3, 4, 5, 6}, .expected = {5, 6}, .cutoff = 5});
95 // empty range
96 test<Iter, Sent, 0, 0>({});
97 // single element range - no match
98 test<Iter, Sent, 1, 1>({.input = {1}, .expected = {1}, .cutoff = 1});
99 // single element range - match
100 test<Iter, Sent, 1, 0>({.input = {1}, .expected = {}, .cutoff = 2});
101 // two element range
102 test<Iter, Sent, 2, 1>({.input = {1, 2}, .expected = {2}, .cutoff = 2});
103 // all elements match
104 test<Iter, Sent, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .cutoff = 2});
105 // no elements match
106 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 changed
108 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 row
110 test<Iter, Sent, 5, 3>({.input = {1, 2, 2, 2, 1}, .expected = {2, 2, 2}, .cutoff = 2});
111 // only the last element matches
112 test<Iter, Sent, 3, 2>({.input = {2, 2, 1}, .expected = {2, 2}, .cutoff = 2});
113 // only the last element doesn't match
114 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 returned
136 [[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 requirements
141
142 // This is https://llvm.org/PR56382 - clang-format behaves weird if function-local structs are used
143 // clang-format off
144 {
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 used
181 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 on
202
203int main(int, char**) {
204 test();
205 static_assert(test());
206
207 return 0;
208}
209

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges.remove_if.pass.cpp