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 Proj = identity,
14// indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
15// requires indirectly_copyable<I, O> &&
16// (forward_iterator<I> ||
17// (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) ||
18// indirectly_copyable_storable<I, O>)
19// constexpr unique_copy_result<I, O>
20// unique_copy(I first, S last, O result, C comp = {}, Proj proj = {}); // Since C++20
21//
22// template<input_range R, weakly_incrementable O, class Proj = identity,
23// indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
24// requires indirectly_copyable<iterator_t<R>, O> &&
25// (forward_iterator<iterator_t<R>> ||
26// (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||
27// indirectly_copyable_storable<iterator_t<R>, O>)
28// constexpr unique_copy_result<borrowed_iterator_t<R>, O>
29// unique_copy(R&& r, O result, C comp = {}, Proj proj = {}); // Since C++20
30
31#include <algorithm>
32#include <array>
33#include <concepts>
34#include <functional>
35#include <ranges>
36
37#include "almost_satisfies_types.h"
38#include "counting_predicates.h"
39#include "counting_projection.h"
40#include "MoveOnly.h"
41#include "test_iterators.h"
42
43template <
44 class InIter = int*,
45 class Sent = int*,
46 class OutIter = int*,
47 class Comp = std::ranges::equal_to,
48 class Proj = std::identity>
49concept HasUniqueCopyIter =
50 requires(InIter&& in, Sent&& sent, OutIter&& out, Comp&& comp, Proj&& proj) {
51 std::ranges::unique_copy(
52 std::forward<InIter>(in),
53 std::forward<Sent>(sent),
54 std::forward<OutIter>(out),
55 std::forward<Comp>(comp),
56 std::forward<Proj>(proj));
57 };
58
59static_assert(HasUniqueCopyIter<int*, int*, int*>);
60
61// !input_iterator<I>
62static_assert(!HasUniqueCopyIter<InputIteratorNotDerivedFrom, sentinel_wrapper<InputIteratorNotDerivedFrom>>);
63
64// !sentinel_for<S, I>
65static_assert(!HasUniqueCopyIter<int*, SentinelForNotSemiregular>);
66
67// !weakly_incrementable<O>
68static_assert(!HasUniqueCopyIter<int*, int*, WeaklyIncrementableNotMovable>);
69
70// !indirect_equivalence_relation<Comp, projected<I, Proj>>
71static_assert(!HasUniqueCopyIter<int*, int*, int*, ComparatorNotCopyable<int>>);
72
73// !indirectly_copyable<I, O>
74static_assert(!HasUniqueCopyIter<const int*, const int*, const int*>);
75
76// forward_iterator<I>
77// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
78// !indirectly_copyable_storable<I, O>
79struct AssignableFromMoveOnly {
80 int data;
81 constexpr AssignableFromMoveOnly& operator=(MoveOnly const& m) {
82 data = m.get();
83 return *this;
84 }
85};
86static_assert(HasUniqueCopyIter<MoveOnly*, MoveOnly*, AssignableFromMoveOnly*>);
87// because:
88static_assert(std::forward_iterator<MoveOnly*>);
89static_assert(!std::same_as<std::iter_value_t<MoveOnly*>, std::iter_value_t<AssignableFromMoveOnly*>>);
90static_assert(!std::indirectly_copyable_storable<MoveOnly*, AssignableFromMoveOnly*>);
91
92// !forward_iterator<I>
93// (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
94// !indirectly_copyable_storable<I, O>
95struct CopyAssignableNotCopyConstructible {
96 int data;
97 constexpr CopyAssignableNotCopyConstructible(int i = 0) : data(i) {}
98 CopyAssignableNotCopyConstructible(const CopyAssignableNotCopyConstructible&) = delete;
99 CopyAssignableNotCopyConstructible& operator=(const CopyAssignableNotCopyConstructible&) = default;
100 friend constexpr bool
101 operator==(CopyAssignableNotCopyConstructible const&, CopyAssignableNotCopyConstructible const&) = default;
102};
103
104using InputAndOutputIterator = cpp17_input_iterator<CopyAssignableNotCopyConstructible*>;
105static_assert(std::input_iterator<InputAndOutputIterator>);
106static_assert(std::output_iterator<InputAndOutputIterator, CopyAssignableNotCopyConstructible>);
107
108static_assert(
109 HasUniqueCopyIter<
110 cpp20_input_iterator<CopyAssignableNotCopyConstructible*>,
111 sentinel_wrapper<cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>,
112 InputAndOutputIterator>);
113// because:
114static_assert(!std::forward_iterator< cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>);
115static_assert(
116 std::input_iterator<InputAndOutputIterator> &&
117 std::same_as<std::iter_value_t<cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>,
118 std::iter_value_t<InputAndOutputIterator>>);
119static_assert(
120 !std::indirectly_copyable_storable<
121 cpp20_input_iterator<CopyAssignableNotCopyConstructible*>,
122 InputAndOutputIterator>);
123
124// !forward_iterator<I>
125// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
126// indirectly_copyable_storable<I, O>
127static_assert(
128 HasUniqueCopyIter<
129 cpp20_input_iterator<int*>,
130 sentinel_wrapper<cpp20_input_iterator<int*>>,
131 cpp20_output_iterator<int*>>);
132// because:
133static_assert(!std::forward_iterator<cpp20_input_iterator<int*>>);
134static_assert(!std::input_iterator<cpp20_output_iterator<int*>>);
135static_assert(std::indirectly_copyable_storable<cpp20_input_iterator<int*>, cpp20_output_iterator<int*>>);
136
137// !forward_iterator<I>
138// !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
139// !indirectly_copyable_storable<I, O>
140static_assert(
141 !HasUniqueCopyIter<
142 cpp20_input_iterator<MoveOnly*>,
143 sentinel_wrapper<cpp20_input_iterator<MoveOnly*>>,
144 cpp20_output_iterator<AssignableFromMoveOnly*>>);
145// because:
146static_assert(!std::forward_iterator<cpp20_input_iterator<MoveOnly*>>);
147static_assert(!std::input_iterator<cpp20_output_iterator<MoveOnly*>>);
148static_assert(
149 !std::
150 indirectly_copyable_storable<cpp20_input_iterator<MoveOnly*>, cpp20_output_iterator<AssignableFromMoveOnly*>>);
151
152template < class Range, class OutIter = int*, class Comp = std::ranges::equal_to, class Proj = std::identity>
153concept HasUniqueCopyRange =
154 requires(Range&& range, OutIter&& out, Comp&& comp, Proj&& proj) {
155 std::ranges::unique_copy(
156 std::forward<Range>(range), std::forward<OutIter>(out), std::forward<Comp>(comp), std::forward<Proj>(proj));
157 };
158
159template <class T>
160using R = UncheckedRange<T>;
161
162static_assert(HasUniqueCopyRange<R<int*>, int*>);
163
164// !input_range<R>
165static_assert(!HasUniqueCopyRange<R<InputIteratorNotDerivedFrom>>);
166
167// !weakly_incrementable<O>
168static_assert(!HasUniqueCopyIter<R<int*>, WeaklyIncrementableNotMovable>);
169
170// !indirect_equivalence_relation<Comp, projected<I, Proj>>
171static_assert(!HasUniqueCopyIter<R<int*>, int*, ComparatorNotCopyable<int>>);
172
173// !indirectly_copyable<I, O>
174static_assert(!HasUniqueCopyIter<R<const int*>, const int*>);
175
176// !forward_iterator<iterator_t<R>>
177// !(input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>)
178// !indirectly_copyable_storable<iterator_t<R>, O>
179static_assert(!HasUniqueCopyIter< R<cpp20_input_iterator<MoveOnly*>>, cpp20_output_iterator<AssignableFromMoveOnly*>>);
180
181template <class InIter, class OutIter, template <class> class SentWrapper, std::size_t N1, std::size_t N2>
182constexpr void testUniqueCopyImpl(std::array<int, N1> in, std::array<int, N2> expected) {
183 using Sent = SentWrapper<InIter>;
184
185 // iterator overload
186 {
187 std::array<int, N2> out;
188 std::same_as<std::ranges::unique_copy_result<InIter, OutIter>> decltype(auto) result =
189 std::ranges::unique_copy(InIter{in.data()}, Sent{InIter{in.data() + in.size()}}, OutIter{out.data()});
190 assert(std::ranges::equal(out, expected));
191 assert(base(result.in) == in.data() + in.size());
192 assert(base(result.out) == out.data() + out.size());
193 }
194
195 // range overload
196 {
197 std::array<int, N2> out;
198 std::ranges::subrange r{InIter{in.data()}, Sent{InIter{in.data() + in.size()}}};
199 std::same_as<std::ranges::unique_copy_result<InIter, OutIter>> decltype(auto) result =
200 std::ranges::unique_copy(r, OutIter{out.data()});
201 assert(std::ranges::equal(out, expected));
202 assert(base(result.in) == in.data() + in.size());
203 assert(base(result.out) == out.data() + out.size());
204 }
205}
206
207template <class InIter, class OutIter, template <class> class SentWrapper>
208constexpr void testImpl() {
209 // no consecutive elements
210 {
211 std::array in{1, 2, 3, 2, 1};
212 std::array expected{1, 2, 3, 2, 1};
213 testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
214 }
215
216 // one group of consecutive elements
217 {
218 std::array in{2, 3, 3, 3, 4, 3};
219 std::array expected{2, 3, 4, 3};
220 testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
221 }
222
223 // multiple groups of consecutive elements
224 {
225 std::array in{2, 3, 3, 3, 4, 3, 3, 5, 5, 5};
226 std::array expected{2, 3, 4, 3, 5};
227 testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
228 }
229
230 // all the same
231 {
232 std::array in{1, 1, 1, 1, 1, 1};
233 std::array expected{1};
234 testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
235 }
236
237 // empty range
238 {
239 std::array<int, 0> in{};
240 std::array<int, 0> expected{};
241 testUniqueCopyImpl<InIter, OutIter, SentWrapper>(in, expected);
242 }
243}
244
245template <class OutIter, template <class> class SentWrapper>
246constexpr void withAllPermutationsOfInIter() {
247 testImpl<cpp20_input_iterator<int*>, OutIter, sentinel_wrapper>();
248 testImpl<forward_iterator<int*>, OutIter, SentWrapper>();
249 testImpl<bidirectional_iterator<int*>, OutIter, SentWrapper>();
250 testImpl<random_access_iterator<int*>, OutIter, SentWrapper>();
251 testImpl<contiguous_iterator<int*>, OutIter, SentWrapper>();
252 testImpl<int*, OutIter, SentWrapper>();
253}
254
255template <template <class> class SentWrapper>
256constexpr void withAllPermutationsOfInIterAndOutIter() {
257 withAllPermutationsOfInIter<cpp20_output_iterator<int*>, SentWrapper>();
258 withAllPermutationsOfInIter<forward_iterator<int*>, SentWrapper>();
259 withAllPermutationsOfInIter<bidirectional_iterator<int*>, SentWrapper>();
260 withAllPermutationsOfInIter<random_access_iterator<int*>, SentWrapper>();
261 withAllPermutationsOfInIter<contiguous_iterator<int*>, SentWrapper>();
262 withAllPermutationsOfInIter<int*, SentWrapper>();
263}
264
265constexpr bool test() {
266 withAllPermutationsOfInIterAndOutIter<std::type_identity_t>();
267 withAllPermutationsOfInIterAndOutIter<sentinel_wrapper>();
268
269 // Test the overload that re-reads from the input iterator
270 // forward_iterator<I>
271 // !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
272 // !indirectly_copyable_storable<I, O>
273 {
274 MoveOnly in[5] = {1, 3, 3, 3, 1};
275 // iterator overload
276 {
277 AssignableFromMoveOnly out[3] = {};
278 auto result = std::ranges::unique_copy(in, in + 5, out);
279 assert(std::ranges::equal(out, std::array{1, 3, 1}, {}, &AssignableFromMoveOnly::data));
280 assert(result.in == in + 5);
281 assert(result.out == out + 3);
282 }
283 // range overload
284 {
285 AssignableFromMoveOnly out[3] = {};
286 auto result = std::ranges::unique_copy(std::ranges::subrange{in, in + 5}, out);
287 assert(std::ranges::equal(out, std::array{1, 3, 1}, {}, &AssignableFromMoveOnly::data));
288 assert(result.in == in + 5);
289 assert(result.out == out + 3);
290 }
291 }
292
293 // Test the overload that re-reads from the output iterator
294 // !forward_iterator<I>
295 // (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
296 // !indirectly_copyable_storable<I, O>
297 {
298 using InIter = cpp20_input_iterator<CopyAssignableNotCopyConstructible*>;
299 using Sent = sentinel_wrapper<InIter>;
300 CopyAssignableNotCopyConstructible in[6] = {1, 1, 2, 2, 3, 3};
301 // iterator overload
302 {
303 CopyAssignableNotCopyConstructible out[3];
304 auto result = std::ranges::unique_copy(InIter{in}, Sent{InIter{in + 6}}, InputAndOutputIterator{out});
305 assert(std::ranges::equal(out, std::array{1, 2, 3}, {}, &CopyAssignableNotCopyConstructible::data));
306 assert(base(result.in) == in + 6);
307 assert(base(result.out) == out + 3);
308 }
309 // range overload
310 {
311 CopyAssignableNotCopyConstructible out[3];
312 auto r = std::ranges::subrange(InIter{in}, Sent{InIter{in + 6}});
313 auto result = std::ranges::unique_copy(r, InputAndOutputIterator{out});
314 assert(std::ranges::equal(out, std::array{1, 2, 3}, {}, &CopyAssignableNotCopyConstructible::data));
315 assert(base(result.in) == in + 6);
316 assert(base(result.out) == out + 3);
317 }
318 }
319
320 // Test the overload that reads from the temporary copy of the value
321 // !forward_iterator<I>
322 // !(input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
323 // indirectly_copyable_storable<I, O>
324 {
325 using InIter = cpp20_input_iterator<int*>;
326 using Sent = sentinel_wrapper<InIter>;
327 int in[4] = {1, 1, 1, 2};
328 // iterator overload
329 {
330 int out[2];
331 auto result = std::ranges::unique_copy(InIter{in}, Sent{InIter{in + 4}}, cpp20_output_iterator<int*>{out});
332 assert(std::ranges::equal(out, std::array{1, 2}));
333 assert(base(result.in) == in + 4);
334 assert(base(result.out) == out + 2);
335 }
336 // range overload
337 {
338 int out[2];
339 auto r = std::ranges::subrange(InIter{in}, Sent{InIter{in + 4}});
340 auto result = std::ranges::unique_copy(r, cpp20_output_iterator<int*>{out});
341 assert(std::ranges::equal(out, std::array{1, 2}));
342 assert(base(result.in) == in + 4);
343 assert(base(result.out) == out + 2);
344 }
345 }
346
347 struct Data {
348 int data;
349 };
350
351 // Test custom comparator
352 {
353 std::array in{Data{.data: 4}, Data{.data: 8}, Data{.data: 8}, Data{.data: 8}};
354 std::array expected{Data{.data: 4}, Data{.data: 8}};
355 const auto comp = [](const Data& x, const Data& y) { return x.data == y.data; };
356
357 // iterator overload
358 {
359 std::array<Data, 2> out;
360 auto result = std::ranges::unique_copy(in.begin(), in.end(), out.begin(), comp);
361 assert(std::ranges::equal(out, expected, comp));
362 assert(base(result.in) == in.begin() + 4);
363 assert(base(result.out) == out.begin() + 2);
364 }
365
366 // range overload
367 {
368 std::array<Data, 2> out;
369 auto result = std::ranges::unique_copy(in, out.begin(), comp);
370 assert(std::ranges::equal(out, expected, comp));
371 assert(base(result.in) == in.begin() + 4);
372 assert(base(result.out) == out.begin() + 2);
373 }
374 }
375
376 // Test custom projection
377 {
378 std::array in{Data{.data: 4}, Data{.data: 8}, Data{.data: 8}, Data{.data: 8}};
379 std::array expected{Data{.data: 4}, Data{.data: 8}};
380
381 const auto proj = &Data::data;
382
383 // iterator overload
384 {
385 std::array<Data, 2> out;
386 auto result = std::ranges::unique_copy(in.begin(), in.end(), out.begin(), {}, proj);
387 assert(std::ranges::equal(out, expected, {}, proj, proj));
388 assert(base(result.in) == in.begin() + 4);
389 assert(base(result.out) == out.begin() + 2);
390 }
391
392 // range overload
393 {
394 std::array<Data, 2> out;
395 auto result = std::ranges::unique_copy(in, out.begin(), {}, proj);
396 assert(std::ranges::equal(out, expected, {}, proj, proj));
397 assert(base(result.in) == in.begin() + 4);
398 assert(base(result.out) == out.begin() + 2);
399 }
400 }
401
402 // Exactly last - first - 1 applications of the corresponding predicate and no
403 // more than twice as many applications of any projection.
404 {
405 std::array in{1, 2, 3, 3, 3, 4, 3, 3, 5, 5, 6, 6, 1};
406 std::array expected{1, 2, 3, 4, 3, 5, 6, 1};
407 // iterator overload
408 {
409 std::array<int, 8> out;
410 int numberOfComp = 0;
411 int numberOfProj = 0;
412 auto result = std::ranges::unique_copy(
413 in.begin(),
414 in.end(),
415 out.begin(),
416 counting_predicate{std::ranges::equal_to{}, numberOfComp},
417 counting_projection{numberOfProj});
418 assert(std::ranges::equal(out, expected));
419 assert(base(result.in) == in.end());
420 assert(base(result.out) == out.end());
421 assert(numberOfComp == static_cast<int>(in.size() - 1));
422 assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));
423 }
424 // range overload
425 {
426 std::array<int, 8> out;
427 int numberOfComp = 0;
428 int numberOfProj = 0;
429 auto result = std::ranges::unique_copy(
430 in,
431 out.begin(),
432 counting_predicate{std::ranges::equal_to{}, numberOfComp},
433 counting_projection{numberOfProj});
434 assert(std::ranges::equal(out, expected));
435 assert(base(result.in) == in.end());
436 assert(base(result.out) == out.end());
437 assert(numberOfComp == static_cast<int>(in.size() - 1));
438 assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));
439 }
440 }
441 return true;
442}
443
444int main(int, char**) {
445 test();
446 static_assert(test());
447
448 return 0;
449}
450

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.unique/ranges_unique_copy.pass.cpp