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