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// UNSUPPORTED: c++03, c++11, c++14, c++17
10
11// <algorithm>
12
13// template<input_iterator I, sentinel_for<I> S, weakly_incrementable O,
14// class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
15// requires indirectly_copyable<I, O>
16// constexpr remove_copy_if_result<I, O>
17// remove_copy_if(I first, S last, O result, Pred pred, Proj proj = {}); // Since C++20
18//
19// template<input_range R, weakly_incrementable O, class Proj = identity,
20// indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
21// requires indirectly_copyable<iterator_t<R>, O>
22// constexpr remove_copy_if_result<borrowed_iterator_t<R>, O>
23// remove_copy_if(R&& r, O result, Pred pred, Proj proj = {}); // Since C++20
24
25#include <algorithm>
26#include <array>
27#include <concepts>
28#include <functional>
29#include <ranges>
30#include <type_traits>
31#include <utility>
32
33#include "almost_satisfies_types.h"
34#include "counting_predicates.h"
35#include "counting_projection.h"
36#include "test_iterators.h"
37
38struct AlwaysTrue {
39 constexpr bool operator()(auto&&...) const { return true; }
40};
41
42template <
43 class I,
44 class S = sentinel_wrapper<std::decay_t<I>>,
45 class O = int*,
46 class Pred = AlwaysTrue>
47concept HasRemoveCopyIfIter =
48 requires(I&& iter, S&& sent, O&& out, Pred&& pred) {
49 std::ranges::remove_copy_if(std::forward<I>(iter), std::forward<S>(sent),
50 std::forward<O>(out), std::forward<Pred>(pred));
51};
52
53static_assert(HasRemoveCopyIfIter<int*, int*, int*>);
54
55// !input_iterator<I>
56static_assert(!HasRemoveCopyIfIter<InputIteratorNotDerivedFrom>);
57static_assert(!HasRemoveCopyIfIter<cpp20_output_iterator<int*>>);
58
59// !sentinel_for<S, I>
60static_assert(!HasRemoveCopyIfIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
61static_assert(!HasRemoveCopyIfIter<int*, SentinelForNotSemiregular>);
62
63// !weakly_incrementable<O>
64static_assert(!HasRemoveCopyIfIter<int*, int*, WeaklyIncrementableNotMovable>);
65
66// !indirect_unary_predicate<Pred, projected<I, Proj>>
67static_assert(!HasRemoveCopyIfIter<int*, int*, int*, IndirectUnaryPredicateNotPredicate>);
68static_assert(!HasRemoveCopyIfIter<int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
69
70// !indirectly_copyable<I, O>
71static_assert(!HasRemoveCopyIfIter<int*, int*, OutputIteratorNotIndirectlyWritable>);
72static_assert(!HasRemoveCopyIfIter<const int*, const int*, const int*>);
73
74template < class R, class O = int*, class Pred = AlwaysTrue, class Proj = std::identity>
75concept HasRemoveCopyIfRange =
76 requires(R&& r, O&& out, Pred&& pred, Proj&& proj) {
77 std::ranges::remove_copy_if(
78 std::forward<R>(r), std::forward<O>(out), std::forward<Pred>(pred), std::forward<Proj>(proj));
79 };
80
81template <class T>
82using R = UncheckedRange<T>;
83
84static_assert(HasRemoveCopyIfRange<R<int*>>);
85
86// !input_range<R>
87static_assert(!HasRemoveCopyIfRange<R<InputIteratorNotDerivedFrom>>);
88static_assert(!HasRemoveCopyIfRange<R<cpp20_output_iterator<int*>>>);
89
90// !weakly_incrementable<O>
91static_assert(!HasRemoveCopyIfRange<R<int*>, WeaklyIncrementableNotMovable>);
92
93// !indirect_unary_predicate<Pred, projected<iterator_t<R>, Proj>>
94static_assert(!HasRemoveCopyIfRange<R<int*>, int*, IndirectUnaryPredicateNotPredicate>);
95static_assert(!HasRemoveCopyIfRange<R<int*>, int*, IndirectUnaryPredicateNotCopyConstructible>);
96
97// !indirectly_copyable<iterator_t<R>, O>
98static_assert(!HasRemoveCopyIfRange<R<int*>, OutputIteratorNotIndirectlyWritable>);
99static_assert(!HasRemoveCopyIfRange<R<const int*>, const int*>);
100
101template <class InIter, class OutIter, template <class> class SentWrapper, std::size_t N1, std::size_t N2, class Pred>
102constexpr void testRemoveCopyIfImpl(std::array<int, N1> in, std::array<int, N2> expected, Pred pred) {
103 using Sent = SentWrapper<InIter>;
104 using Result = std::ranges::remove_copy_if_result<InIter, OutIter>;
105
106 // iterator overload
107 {
108 std::array<int, N2> out;
109 std::same_as<Result> decltype(auto) result =
110 std::ranges::remove_copy_if(InIter{in.data()}, Sent{InIter{in.data() + in.size()}}, OutIter{out.data()}, pred);
111 assert(std::ranges::equal(out, expected));
112 assert(base(result.in) == in.data() + in.size());
113 assert(base(result.out) == out.data() + out.size());
114 }
115
116 // range overload
117 {
118 std::array<int, N2> out;
119 std::ranges::subrange r{InIter{in.data()}, Sent{InIter{in.data() + in.size()}}};
120 std::same_as<Result> decltype(auto) result =
121 std::ranges::remove_copy_if(r, OutIter{out.data()}, pred);
122 assert(std::ranges::equal(out, expected));
123 assert(base(result.in) == in.data() + in.size());
124 assert(base(result.out) == out.data() + out.size());
125 }
126}
127
128template <class InIter, class OutIter, template <class> class SentWrapper>
129constexpr void testImpl() {
130 // remove multiple elements
131 {
132 std::array in{1, 2, 3, 2, 1};
133 std::array expected{1, 3, 1};
134 auto pred = [](int i) { return i == 2; };
135 testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
136 }
137
138 // remove single elements
139 {
140 std::array in{1, 2, 3, 2, 1};
141 std::array expected{1, 2, 2, 1};
142 auto pred = [](int i) { return i == 3; };
143 testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
144 }
145
146 // nothing removed
147 {
148 std::array in{1, 2, 3, 2, 1};
149 std::array expected{1, 2, 3, 2, 1};
150 auto pred = [](int) { return false; };
151 testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
152 }
153
154 // all removed
155 {
156 std::array in{1, 2, 3, 2, 1};
157 std::array<int, 0> expected{};
158 auto pred = [](int) { return true; };
159 testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
160 }
161
162 // remove first
163 {
164 std::array in{1, 2, 3, 2};
165 std::array expected{2, 3, 2};
166 auto pred = [](int i) { return i < 2; };
167 testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
168 }
169
170 // remove last
171 {
172 std::array in{1, 2, 3, 2, 5};
173 std::array expected{1, 2, 3, 2};
174 auto pred = [](int i) { return i > 3; };
175 testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
176 }
177
178 // stable
179 {
180 std::array in{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
181 std::array expected{6, 7, 8, 9, 10};
182 auto pred = [](int i) { return i < 6; };
183 testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
184 }
185
186 // empty range
187 {
188 std::array<int, 0> in{};
189 std::array<int, 0> expected{};
190 auto pred = [](int) { return false; };
191 testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
192 }
193
194 // one element range
195 {
196 std::array in{1};
197 std::array<int, 0> expected{};
198 auto pred = [](int i) { return i == 1; };
199 testRemoveCopyIfImpl<InIter, OutIter, SentWrapper>(in, expected, pred);
200 }
201}
202
203template <class OutIter, template <class> class SentWrapper>
204constexpr void withAllPermutationsOfInIter() {
205 testImpl<cpp20_input_iterator<int*>, OutIter, sentinel_wrapper>();
206 testImpl<forward_iterator<int*>, OutIter, SentWrapper>();
207 testImpl<bidirectional_iterator<int*>, OutIter, SentWrapper>();
208 testImpl<random_access_iterator<int*>, OutIter, SentWrapper>();
209 testImpl<contiguous_iterator<int*>, OutIter, SentWrapper>();
210 testImpl<int*, OutIter, SentWrapper>();
211}
212
213template <template <class> class SentWrapper>
214constexpr void withAllPermutationsOfInIterOutIter() {
215 withAllPermutationsOfInIter<cpp20_output_iterator<int*>, SentWrapper>();
216 withAllPermutationsOfInIter<int*, SentWrapper>();
217}
218
219constexpr bool test() {
220 withAllPermutationsOfInIterOutIter<std::type_identity_t>();
221 withAllPermutationsOfInIterOutIter<sentinel_wrapper>();
222
223 // Test custom projection
224 {
225 struct Data {
226 int data;
227 };
228
229 std::array in{Data{.data: 4}, Data{.data: 8}, Data{.data: 12}, Data{.data: 12}};
230 std::array expected{Data{.data: 4}, Data{.data: 12}, Data{.data: 12}};
231
232 const auto proj = &Data::data;
233 const auto pred = [](int i) { return i == 8; };
234
235 const auto equals = [](const Data& x, const Data& y) { return x.data == y.data; };
236 // iterator overload
237 {
238 std::array<Data, 3> out;
239 auto result = std::ranges::remove_copy_if(in.begin(), in.end(), out.begin(), pred, proj);
240 assert(std::ranges::equal(out, expected, equals));
241 assert(result.in == in.end());
242 assert(result.out == out.end());
243 }
244
245 // range overload
246 {
247 std::array<Data, 3> out;
248 auto result = std::ranges::remove_copy_if(in, out.begin(), pred, proj);
249 assert(std::ranges::equal(out, expected, equals));
250 assert(result.in == in.end());
251 assert(result.out == out.end());
252 }
253 }
254
255 // Complexity: Exactly last - first applications of the corresponding predicate and any projection.
256 {
257 std::array in{4, 4, 5, 6};
258 std::array expected{5, 6};
259
260 const auto pred = [](int i) { return i == 4; };
261
262 // iterator overload
263 {
264 int numberOfPred = 0;
265 int numberOfProj = 0;
266 std::array<int, 2> out;
267 std::ranges::remove_copy_if(
268 in.begin(), in.end(), out.begin(), counting_predicate(pred, numberOfPred), counting_projection(numberOfProj));
269
270 assert(numberOfPred == static_cast<int>(in.size()));
271 assert(numberOfProj == static_cast<int>(in.size()));
272
273 assert(std::ranges::equal(out, expected));
274 }
275
276 // range overload
277 {
278 int numberOfPred = 0;
279 int numberOfProj = 0;
280 std::array<int, 2> out;
281 std::ranges::remove_copy_if(
282 in, out.begin(), counting_predicate(pred, numberOfPred), counting_projection(numberOfProj));
283 assert(numberOfPred == static_cast<int>(in.size()));
284 assert(numberOfProj == static_cast<int>(in.size()));
285 assert(std::ranges::equal(out, expected));
286 }
287 }
288
289 return true;
290}
291
292int main(int, char**) {
293 test();
294 static_assert(test());
295
296 return 0;
297}
298

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