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, class T,
15 //          class Proj = identity>
16 //   requires indirectly_copyable<I, O> &&
17 //            indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
18 //   constexpr remove_copy_result<I, O>
19 //     remove_copy(I first, S last, O result, const T& value, Proj proj = {});                      // Since C++20
20 //
21 // template<input_range R, weakly_incrementable O, class T, class Proj = identity>
22 //   requires indirectly_copyable<iterator_t<R>, O> &&
23 //            indirect_binary_predicate<ranges::equal_to,
24 //                                      projected<iterator_t<R>, Proj>, const T*>
25 //   constexpr remove_copy_result<borrowed_iterator_t<R>, O>
26 //     remove_copy(R&& r, O result, const T& value, Proj proj = {});                                // Since C++20
27 
28 #include <algorithm>
29 #include <array>
30 #include <concepts>
31 #include <functional>
32 #include <ranges>
33 #include <utility>
34 
35 #include "almost_satisfies_types.h"
36 #include "counting_projection.h"
37 #include "test_iterators.h"
38 
39 struct ToPtr {
40   int* operator()(int) const;
41 };
42 
43 template <class Iter = int*, class Sent = int*, class OutIter = int*, class Proj = std::identity>
44 concept HasRemoveCopyIter =
45   requires(Iter&& iter, Sent&& sent, OutIter&& out, Proj&& proj) {
46     std::ranges::remove_copy(
47         std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<OutIter>(out), 0, std::forward<Proj>(proj));
48 };
49 
50 static_assert(HasRemoveCopyIter<int*>);
51 
52 // !input_iterator<I>
53 static_assert(!HasRemoveCopyIter<InputIteratorNotDerivedFrom>);
54 static_assert(!HasRemoveCopyIter<cpp20_output_iterator<int*>>);
55 
56 // !sentinel_for<S, I>
57 static_assert(!HasRemoveCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
58 static_assert(!HasRemoveCopyIter<int*, SentinelForNotSemiregular>);
59 
60 // !weakly_incrementable<O>
61 static_assert(!HasRemoveCopyIter<int*, int*, WeaklyIncrementableNotMovable>);
62 
63 // !indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
64 static_assert(!HasRemoveCopyIter<int*, int*, int*, ToPtr>);
65 
66 // !indirectly_copyable<I, O>
67 static_assert(!HasRemoveCopyIter<int*, int*, OutputIteratorNotIndirectlyWritable>);
68 static_assert(!HasRemoveCopyIter<const int*, const int*, const int*>);
69 
70 template <class Range, class OutIter = int*, class Proj = std::identity>
71 concept HasRemoveCopyRange =
72   requires(Range&& range, OutIter&& out, Proj&& proj) {
73     std::ranges::remove_copy(
74         std::forward<Range>(range), std::forward<OutIter>(out), 0, std::forward<Proj>(proj));
75 };
76 
77 template <class T>
78 using R = UncheckedRange<T>;
79 
80 static_assert(HasRemoveCopyRange<R<int*>>);
81 
82 // !input_range<R>
83 static_assert(!HasRemoveCopyRange<InputRangeNotDerivedFrom>);
84 static_assert(!HasRemoveCopyRange<InputRangeNotIndirectlyReadable>);
85 static_assert(!HasRemoveCopyRange<InputRangeNotInputOrOutputIterator>);
86 static_assert(!HasRemoveCopyRange<InputRangeNotSentinelSemiregular>);
87 static_assert(!HasRemoveCopyRange<InputRangeNotSentinelEqualityComparableWith>);
88 
89 // !weakly_incrementable<O>
90 static_assert(!HasRemoveCopyRange<R<int*>, WeaklyIncrementableNotMovable>);
91 
92 // !indirect_binary_predicate<ranges::equal_to, projected<iterator_t<I>, Proj>, const T*>
93 static_assert(!HasRemoveCopyRange<R<int*>, int*, ToPtr>);
94 
95 // !indirectly_copyable<I, O>
96 static_assert(!HasRemoveCopyRange<R<int*>, int*, OutputIteratorNotIndirectlyWritable>);
97 static_assert(!HasRemoveCopyRange<const int*, const int*, const int*>);
98 
99 template <int N, int M>
100 struct Data {
101   std::array<int, N> input;
102   std::array<int, M> expected;
103   int val;
104 };
105 
106 template <class InIter, class Sent, class OutIter, int N, int M>
107 constexpr void test(Data<N, M> d) {
108   using Result = std::ranges::remove_copy_result<InIter, OutIter>;
109 
110   { // iterator overload
111     std::array<int, M> output;
112 
113     std::same_as<Result> decltype(auto) ret = std::ranges::remove_copy(
114         InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size())), OutIter(output.data()), d.val);
115 
116     assert(base(ret.in) == d.input.data() + N);
117     assert(base(ret.out) == output.data() + M);
118     assert(d.expected == output);
119   }
120 
121   { // range overload
122     std::array<int, M> output;
123     auto range = std::ranges::subrange(InIter(d.input.data()), Sent(InIter(d.input.data() + d.input.size())));
124 
125     std::same_as<Result> decltype(auto) ret =
126         std::ranges::remove_copy(range, OutIter(output.data()), d.val);
127 
128     assert(base(ret.in) == d.input.data() + N);
129     assert(base(ret.out) == output.data() + M);
130     assert(d.expected == output);
131   }
132 }
133 
134 template <class Iter, class Sent, class OutIter>
135 constexpr void tests() {
136   // simple test
137   test<Iter, Sent, OutIter, 6, 5>({.input = {1, 2, 3, 4, 5, 6}, .expected = {1, 2, 3, 4, 6}, .val = 5});
138   // empty range
139   test<Iter, Sent, OutIter, 0, 0>({});
140   // single element range - match
141   test<Iter, Sent, OutIter, 1, 0>({.input = {1}, .expected = {}, .val = 1});
142   // single element range - no match
143   test<Iter, Sent, OutIter, 1, 1>({.input = {1}, .expected = {1}, .val = 2});
144   // two element range - same order
145   test<Iter, Sent, OutIter, 2, 1>({.input = {1, 2}, .expected = {1}, .val = 2});
146   // two element range - reversed order
147   test<Iter, Sent, OutIter, 2, 1>({.input = {1, 2}, .expected = {2}, .val = 1});
148   // all elements match
149   test<Iter, Sent, OutIter, 5, 0>({.input = {1, 1, 1, 1, 1}, .expected = {}, .val = 1});
150   // the relative order of elements isn't changed
151   test<Iter, Sent, OutIter, 8, 5>({.input = {1, 2, 3, 2, 3, 4, 2, 5}, .expected = {1, 3, 3, 4, 5}, .val = 2});
152 }
153 
154 template <class InIter, class Sent>
155 constexpr void test_output_iterators() {
156   tests<InIter, Sent, cpp17_output_iterator<int*>>();
157   tests<InIter, Sent, forward_iterator<int*>>();
158   tests<InIter, Sent, bidirectional_iterator<int*>>();
159   tests<InIter, Sent, random_access_iterator<int*>>();
160   tests<InIter, Sent, contiguous_iterator<int*>>();
161   tests<InIter, Sent, int*>();
162 }
163 
164 template <class Iter>
165 constexpr void test_sentinels() {
166   test_output_iterators<Iter, Iter>();
167   test_output_iterators<Iter, sentinel_wrapper<Iter>>();
168   test_output_iterators<Iter, sized_sentinel<Iter>>();
169 }
170 
171 constexpr bool test() {
172   test_output_iterators<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
173   test_output_iterators<cpp17_input_iterator<int*>, sized_sentinel<cpp17_input_iterator<int*>>>();
174   test_output_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
175   test_output_iterators<cpp20_input_iterator<int*>, sized_sentinel<cpp20_input_iterator<int*>>>();
176   test_sentinels<forward_iterator<int*>>();
177   test_sentinels<bidirectional_iterator<int*>>();
178   test_sentinels<random_access_iterator<int*>>();
179   test_sentinels<contiguous_iterator<int*>>();
180   test_sentinels<int*>();
181 
182   { // check that passing a different type works
183     struct S {
184       constexpr operator int() const { return 3; }
185     };
186 
187     { // iterator overload
188       int a[] = {1, 2, 3, 4};
189       int b[3];
190       std::ranges::remove_copy(std::begin(a), std::end(a), std::begin(b), S{});
191     }
192 
193     { // range overload
194       int a[] = {1, 2, 3, 4};
195       int b[3];
196       std::ranges::remove_copy(a, std::begin(b), S{});
197     }
198   }
199 
200   { // check that a custom projection works
201     struct S {
202       constexpr operator int() const { return 3; }
203     };
204 
205     { // iterator overload
206       int a[] = {1, 2, 3, 4};
207       int b[3];
208       std::ranges::remove_copy(std::begin(a), std::end(a), std::begin(b), S{});
209 
210     }
211     { // range overload
212       int a[] = {1, 2, 3, 4};
213       int b[3];
214       std::ranges::remove_copy(a, std::begin(b), S{});
215     }
216   }
217 
218   // Complexity: Exactly last - first applications of the corresponding predicate and any projection.
219 
220   {
221     std::array in{4, 4, 5, 6};
222     std::array expected{5, 6};
223 
224     // iterator overload
225     {
226       int numberOfProj = 0;
227       std::array<int, 2> out;
228       std::ranges::remove_copy(
229           in.begin(),
230           in.end(),
231           out.begin(),
232           4,
233           counting_projection(numberOfProj));
234 
235       assert(numberOfProj == static_cast<int>(in.size()));
236 
237       assert(std::ranges::equal(out, expected));
238     }
239 
240     // range overload
241     {
242       int numberOfProj = 0;
243       std::array<int, 2> out;
244       std::ranges::remove_copy(
245           in, out.begin(), 4, counting_projection(numberOfProj));
246       assert(numberOfProj == static_cast<int>(in.size()));
247       assert(std::ranges::equal(out, expected));
248     }
249   }
250 
251   return true;
252 }
253 
254 int main(int, char**) {
255   test();
256   static_assert(test());
257 
258   return 0;
259 }
260