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