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
38struct ToPtr {
39 int* operator()(int) const;
40};
41
42template <class Iter = int*, class Sent = int*, class OutIter = int*, class Proj = std::identity>
43concept 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
49static_assert(HasRemoveCopyIter<int*>);
50
51// !input_iterator<I>
52static_assert(!HasRemoveCopyIter<InputIteratorNotDerivedFrom>);
53static_assert(!HasRemoveCopyIter<cpp20_output_iterator<int*>>);
54
55// !sentinel_for<S, I>
56static_assert(!HasRemoveCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
57static_assert(!HasRemoveCopyIter<int*, SentinelForNotSemiregular>);
58
59// !weakly_incrementable<O>
60static_assert(!HasRemoveCopyIter<int*, int*, WeaklyIncrementableNotMovable>);
61
62// !indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
63static_assert(!HasRemoveCopyIter<int*, int*, int*, ToPtr>);
64
65// !indirectly_copyable<I, O>
66static_assert(!HasRemoveCopyIter<int*, int*, OutputIteratorNotIndirectlyWritable>);
67static_assert(!HasRemoveCopyIter<const int*, const int*, const int*>);
68
69template <class Range, class OutIter = int*, class Proj = std::identity>
70concept 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
76template <class T>
77using R = UncheckedRange<T>;
78
79static_assert(HasRemoveCopyRange<R<int*>>);
80
81// !input_range<R>
82static_assert(!HasRemoveCopyRange<InputRangeNotDerivedFrom>);
83static_assert(!HasRemoveCopyRange<InputRangeNotIndirectlyReadable>);
84static_assert(!HasRemoveCopyRange<InputRangeNotInputOrOutputIterator>);
85static_assert(!HasRemoveCopyRange<InputRangeNotSentinelSemiregular>);
86static_assert(!HasRemoveCopyRange<InputRangeNotSentinelEqualityComparableWith>);
87
88// !weakly_incrementable<O>
89static_assert(!HasRemoveCopyRange<R<int*>, WeaklyIncrementableNotMovable>);
90
91// !indirect_binary_predicate<ranges::equal_to, projected<iterator_t<I>, Proj>, const T*>
92static_assert(!HasRemoveCopyRange<R<int*>, int*, ToPtr>);
93
94// !indirectly_copyable<I, O>
95static_assert(!HasRemoveCopyRange<R<int*>, int*, OutputIteratorNotIndirectlyWritable>);
96static_assert(!HasRemoveCopyRange<const int*, const int*, const int*>);
97
98template <int N, int M>
99struct Data {
100 std::array<int, N> input;
101 std::array<int, M> expected;
102 int val;
103};
104
105template <class InIter, class Sent, class OutIter, int N, int M>
106constexpr 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
133template <class Iter, class Sent, class OutIter>
134constexpr 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
153template <class InIter, class Sent>
154constexpr 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
163template <class Iter>
164constexpr 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
170constexpr 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
253int main(int, char**) {
254 test();
255 static_assert(test());
256
257 return 0;
258}
259

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.remove/ranges_remove_copy.pass.cpp