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>
test(Data<N,M> d)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>
tests()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>
test_output_iterators()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>
test_sentinels()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
test()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
main(int,char **)254 int main(int, char**) {
255 test();
256 static_assert(test());
257
258 return 0;
259 }
260