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 
38 struct AlwaysTrue {
operator ()AlwaysTrue39   constexpr bool operator()(auto&&...) const { return true; }
40 };
41 
42 template <
43     class I,
44     class S    = sentinel_wrapper<std::decay_t<I>>,
45     class O    = int*,
46     class Pred = AlwaysTrue>
47 concept 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 
53 static_assert(HasRemoveCopyIfIter<int*, int*, int*>);
54 
55 // !input_iterator<I>
56 static_assert(!HasRemoveCopyIfIter<InputIteratorNotDerivedFrom>);
57 static_assert(!HasRemoveCopyIfIter<cpp20_output_iterator<int*>>);
58 
59 // !sentinel_for<S, I>
60 static_assert(!HasRemoveCopyIfIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
61 static_assert(!HasRemoveCopyIfIter<int*, SentinelForNotSemiregular>);
62 
63 // !weakly_incrementable<O>
64 static_assert(!HasRemoveCopyIfIter<int*, int*, WeaklyIncrementableNotMovable>);
65 
66 // !indirect_unary_predicate<Pred, projected<I, Proj>>
67 static_assert(!HasRemoveCopyIfIter<int*, int*, int*, IndirectUnaryPredicateNotPredicate>);
68 static_assert(!HasRemoveCopyIfIter<int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
69 
70 // !indirectly_copyable<I, O>
71 static_assert(!HasRemoveCopyIfIter<int*, int*, OutputIteratorNotIndirectlyWritable>);
72 static_assert(!HasRemoveCopyIfIter<const int*, const int*, const int*>);
73 
74 template < class R, class O = int*, class Pred = AlwaysTrue, class Proj = std::identity>
75 concept 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 
81 template <class T>
82 using R = UncheckedRange<T>;
83 
84 static_assert(HasRemoveCopyIfRange<R<int*>>);
85 
86 // !input_range<R>
87 static_assert(!HasRemoveCopyIfRange<R<InputIteratorNotDerivedFrom>>);
88 static_assert(!HasRemoveCopyIfRange<R<cpp20_output_iterator<int*>>>);
89 
90 // !weakly_incrementable<O>
91 static_assert(!HasRemoveCopyIfRange<R<int*>, WeaklyIncrementableNotMovable>);
92 
93 // !indirect_unary_predicate<Pred, projected<iterator_t<R>, Proj>>
94 static_assert(!HasRemoveCopyIfRange<R<int*>, int*, IndirectUnaryPredicateNotPredicate>);
95 static_assert(!HasRemoveCopyIfRange<R<int*>, int*, IndirectUnaryPredicateNotCopyConstructible>);
96 
97 // !indirectly_copyable<iterator_t<R>, O>
98 static_assert(!HasRemoveCopyIfRange<R<int*>, OutputIteratorNotIndirectlyWritable>);
99 static_assert(!HasRemoveCopyIfRange<R<const int*>, const int*>);
100 
101 template <class InIter, class OutIter, template <class> class SentWrapper, std::size_t N1, std::size_t N2, class Pred>
testRemoveCopyIfImpl(std::array<int,N1> in,std::array<int,N2> expected,Pred pred)102 constexpr 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 
128 template <class InIter, class OutIter, template <class> class SentWrapper>
testImpl()129 constexpr 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 
203 template <class OutIter, template <class> class SentWrapper>
withAllPermutationsOfInIter()204 constexpr 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 
213 template <template <class> class SentWrapper>
withAllPermutationsOfInIterOutIter()214 constexpr void withAllPermutationsOfInIterOutIter() {
215   withAllPermutationsOfInIter<cpp20_output_iterator<int*>, SentWrapper>();
216   withAllPermutationsOfInIter<int*, SentWrapper>();
217 }
218 
test()219 constexpr 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{4}, Data{8}, Data{12}, Data{12}};
230     std::array expected{Data{4}, Data{12}, 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 
main(int,char **)292 int main(int, char**) {
293   test();
294   static_assert(test());
295 
296   return 0;
297 }
298