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 
43 template <
44     class InIter  = int*,
45     class Sent    = int*,
46     class OutIter = int*,
47     class Comp    = std::ranges::equal_to,
48     class Proj    = std::identity>
49 concept 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 
59 static_assert(HasUniqueCopyIter<int*, int*, int*>);
60 
61 // !input_iterator<I>
62 static_assert(!HasUniqueCopyIter<InputIteratorNotDerivedFrom, sentinel_wrapper<InputIteratorNotDerivedFrom>>);
63 
64 // !sentinel_for<S, I>
65 static_assert(!HasUniqueCopyIter<int*, SentinelForNotSemiregular>);
66 
67 // !weakly_incrementable<O>
68 static_assert(!HasUniqueCopyIter<int*, int*, WeaklyIncrementableNotMovable>);
69 
70 // !indirect_equivalence_relation<Comp, projected<I, Proj>>
71 static_assert(!HasUniqueCopyIter<int*, int*, int*, ComparatorNotCopyable<int>>);
72 
73 // !indirectly_copyable<I, O>
74 static_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>
79 struct AssignableFromMoveOnly {
80   int data;
operator =AssignableFromMoveOnly81   constexpr AssignableFromMoveOnly& operator=(MoveOnly const& m) {
82     data = m.get();
83     return *this;
84   }
85 };
86 static_assert(HasUniqueCopyIter<MoveOnly*, MoveOnly*, AssignableFromMoveOnly*>);
87 // because:
88 static_assert(std::forward_iterator<MoveOnly*>);
89 static_assert(!std::same_as<std::iter_value_t<MoveOnly*>, std::iter_value_t<AssignableFromMoveOnly*>>);
90 static_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>
95 struct CopyAssignableNotCopyConstructible {
96   int data;
CopyAssignableNotCopyConstructibleCopyAssignableNotCopyConstructible97   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 
104 using InputAndOutputIterator = cpp17_input_iterator<CopyAssignableNotCopyConstructible*>;
105 static_assert(std::input_iterator<InputAndOutputIterator>);
106 static_assert(std::output_iterator<InputAndOutputIterator, CopyAssignableNotCopyConstructible>);
107 
108 static_assert(
109     HasUniqueCopyIter<
110         cpp20_input_iterator<CopyAssignableNotCopyConstructible*>,
111         sentinel_wrapper<cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>,
112         InputAndOutputIterator>);
113 // because:
114 static_assert(!std::forward_iterator< cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>);
115 static_assert(
116     std::input_iterator<InputAndOutputIterator> &&
117     std::same_as<std::iter_value_t<cpp20_input_iterator<CopyAssignableNotCopyConstructible*>>,
118                  std::iter_value_t<InputAndOutputIterator>>);
119 static_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>
127 static_assert(
128     HasUniqueCopyIter<
129         cpp20_input_iterator<int*>,
130         sentinel_wrapper<cpp20_input_iterator<int*>>,
131         cpp20_output_iterator<int*>>);
132 // because:
133 static_assert(!std::forward_iterator<cpp20_input_iterator<int*>>);
134 static_assert(!std::input_iterator<cpp20_output_iterator<int*>>);
135 static_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>
140 static_assert(
141     !HasUniqueCopyIter<
142         cpp20_input_iterator<MoveOnly*>,
143         sentinel_wrapper<cpp20_input_iterator<MoveOnly*>>,
144         cpp20_output_iterator<AssignableFromMoveOnly*>>);
145 // because:
146 static_assert(!std::forward_iterator<cpp20_input_iterator<MoveOnly*>>);
147 static_assert(!std::input_iterator<cpp20_output_iterator<MoveOnly*>>);
148 static_assert(
149     !std::
150         indirectly_copyable_storable<cpp20_input_iterator<MoveOnly*>, cpp20_output_iterator<AssignableFromMoveOnly*>>);
151 
152 template < class Range, class OutIter = int*, class Comp = std::ranges::equal_to, class Proj = std::identity>
153 concept 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 
159 template <class T>
160 using R = UncheckedRange<T>;
161 
162 static_assert(HasUniqueCopyRange<R<int*>, int*>);
163 
164 // !input_range<R>
165 static_assert(!HasUniqueCopyRange<R<InputIteratorNotDerivedFrom>>);
166 
167 // !weakly_incrementable<O>
168 static_assert(!HasUniqueCopyIter<R<int*>, WeaklyIncrementableNotMovable>);
169 
170 // !indirect_equivalence_relation<Comp, projected<I, Proj>>
171 static_assert(!HasUniqueCopyIter<R<int*>, int*, ComparatorNotCopyable<int>>);
172 
173 // !indirectly_copyable<I, O>
174 static_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>
179 static_assert(!HasUniqueCopyIter< R<cpp20_input_iterator<MoveOnly*>>, cpp20_output_iterator<AssignableFromMoveOnly*>>);
180 
181 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)182 constexpr 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 
207 template <class InIter, class OutIter, template <class> class SentWrapper>
testImpl()208 constexpr 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 
245 template <class OutIter, template <class> class SentWrapper>
withAllPermutationsOfInIter()246 constexpr 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 
255 template <template <class> class SentWrapper>
withAllPermutationsOfInIterAndOutIter()256 constexpr 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 
test()265 constexpr 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{4}, Data{8}, Data{8}, Data{8}};
354     std::array expected{Data{4}, 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{4}, Data{8}, Data{8}, Data{8}};
379     std::array expected{Data{4}, 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 
main(int,char **)444 int main(int, char**) {
445   test();
446   static_assert(test());
447 
448   return 0;
449 }
450