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