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<permutable I, sentinel_for<I> S, class Proj = identity,
15 //          indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
16 //   constexpr subrange<I> unique(I first, S last, C comp = {}, Proj proj = {});                    // Since C++20
17 //
18 // template<forward_range R, class Proj = identity,
19 //          indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
20 //   requires permutable<iterator_t<R>>
21 //   constexpr borrowed_subrange_t<R>
22 //     unique(R&& r, C comp = {}, Proj proj = {});                                                  // Since C++20
23 
24 #include <algorithm>
25 #include <array>
26 #include <concepts>
27 #include <functional>
28 #include <ranges>
29 
30 #include "almost_satisfies_types.h"
31 #include "counting_predicates.h"
32 #include "counting_projection.h"
33 #include "test_iterators.h"
34 
35 template <class Iter = int*, class Sent = int*, class Comp = std::ranges::equal_to, class Proj = std::identity>
36 concept HasUniqueIter =
37     requires(Iter&& iter, Sent&& sent, Comp&& comp, Proj&& proj) {
38       std::ranges::unique(
39           std::forward<Iter>(iter), std::forward<Sent>(sent), std::forward<Comp>(comp), std::forward<Proj>(proj));
40     };
41 
42 static_assert(HasUniqueIter<int*, int*>);
43 
44 // !permutable<I>
45 static_assert(!HasUniqueIter<PermutableNotForwardIterator>);
46 static_assert(!HasUniqueIter<PermutableNotSwappable>);
47 
48 // !sentinel_for<S, I>
49 static_assert(!HasUniqueIter<int*, SentinelForNotSemiregular>);
50 
51 // !indirect_equivalence_relation<Comp, projected<I, Proj>>
52 static_assert(!HasUniqueIter<int*, int*, ComparatorNotCopyable<int>>);
53 
54 template <class Range, class Comp = std::ranges::equal_to, class Proj = std::identity>
55 concept HasUniqueRange =
56     requires(Range&& range, Comp&& comp, Proj&& proj) {
57       std::ranges::unique(std::forward<Range>(range), std::forward<Comp>(comp), std::forward<Proj>(proj));
58     };
59 
60 template <class T>
61 using R = UncheckedRange<T>;
62 
63 static_assert(HasUniqueRange<R<int*>>);
64 
65 // !forward_range<R>
66 static_assert(!HasUniqueRange<ForwardRangeNotDerivedFrom>);
67 static_assert(!HasUniqueRange<ForwardRangeNotIncrementable>);
68 
69 // permutable<ranges::iterator_t<R>>
70 static_assert(!HasUniqueRange<R<PermutableNotForwardIterator>>);
71 static_assert(!HasUniqueRange<R<PermutableNotSwappable>>);
72 
73 // !indirect_equivalence_relation<Comp, projected<ranges::iterator_t<R>, Proj>>
74 static_assert(!HasUniqueRange<R<int*>, ComparatorNotCopyable<int>>);
75 
76 template <class Iter, template <class> class SentWrapper, std::size_t N1, std::size_t N2>
77 constexpr void testUniqueImpl(std::array<int, N1> input, std::array<int, N2> expected) {
78   using Sent = SentWrapper<Iter>;
79 
80   // iterator overload
81   {
82     auto in = input;
83     std::same_as<std::ranges::subrange<Iter>> decltype(auto) result =
84         std::ranges::unique(Iter{in.data()}, Sent{Iter{in.data() + in.size()}});
85     assert(std::ranges::equal(std::ranges::subrange<Iter>{Iter{in.data()}, result.begin()}, expected));
86     assert(base(result.end()) == in.data() + in.size());
87   }
88 
89   // range overload
90   {
91     auto in = input;
92     std::ranges::subrange r{Iter{in.data()}, Sent{Iter{in.data() + in.size()}}};
93     std::same_as<std::ranges::subrange<Iter>> decltype(auto) result = std::ranges::unique(r);
94     assert(std::ranges::equal(std::ranges::subrange<Iter>{Iter{in.data()}, result.begin()}, expected));
95     assert(base(result.end()) == in.data() + in.size());
96   }
97 }
98 
99 template <class Iter, template <class> class SentWrapper>
100 constexpr void testImpl() {
101   // no consecutive elements
102   {
103     std::array in{1, 2, 3, 2, 1};
104     std::array expected{1, 2, 3, 2, 1};
105     testUniqueImpl<Iter, SentWrapper>(in, expected);
106   }
107 
108   // one group of consecutive elements
109   {
110     std::array in{2, 3, 3, 3, 4, 3};
111     std::array expected{2, 3, 4, 3};
112     testUniqueImpl<Iter, SentWrapper>(in, expected);
113   }
114 
115   // multiple groups of consecutive elements
116   {
117     std::array in{2, 3, 3, 3, 4, 3, 3, 5, 5, 5};
118     std::array expected{2, 3, 4, 3, 5};
119     testUniqueImpl<Iter, SentWrapper>(in, expected);
120   }
121 
122   // all the same
123   {
124     std::array in{1, 1, 1, 1, 1, 1};
125     std::array expected{1};
126     testUniqueImpl<Iter, SentWrapper>(in, expected);
127   }
128 
129   // empty range
130   {
131     std::array<int, 0> in{};
132     std::array<int, 0> expected{};
133     testUniqueImpl<Iter, SentWrapper>(in, expected);
134   }
135 
136   // single element range
137     std::array in{1};
138     std::array expected{1};
139     testUniqueImpl<Iter, SentWrapper>(in, expected);
140 }
141 
142 template <template <class> class SentWrapper>
143 constexpr void withAllPermutationsOfIter() {
144   testImpl<forward_iterator<int*>, SentWrapper>();
145   testImpl<bidirectional_iterator<int*>, SentWrapper>();
146   testImpl<random_access_iterator<int*>, SentWrapper>();
147   testImpl<contiguous_iterator<int*>, SentWrapper>();
148   testImpl<int*, SentWrapper>();
149 }
150 
151 constexpr bool test() {
152   withAllPermutationsOfIter<std::type_identity_t>();
153   withAllPermutationsOfIter<sentinel_wrapper>();
154 
155   struct Data {
156     int data;
157   };
158 
159   // Test custom comparator
160   {
161     std::array input{Data{4}, Data{8}, Data{8}, Data{8}};
162     std::array expected{Data{4}, Data{8}};
163     const auto comp = [](const Data& x, const Data& y) { return x.data == y.data; };
164 
165     // iterator overload
166     {
167       auto in     = input;
168       auto result = std::ranges::unique(in.begin(), in.end(), comp);
169       assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), comp));
170       assert(base(result.end()) == in.end());
171     }
172 
173     // range overload
174     {
175       auto in     = input;
176       auto result = std::ranges::unique(in, comp);
177       assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), comp));
178       assert(base(result.end()) == in.end());
179     }
180   }
181 
182   // Test custom projection
183   {
184     std::array input{Data{4}, Data{8}, Data{8}, Data{8}};
185     std::array expected{Data{4}, Data{8}};
186 
187     const auto proj = &Data::data;
188 
189     // iterator overload
190     {
191       auto in     = input;
192       auto result = std::ranges::unique(in.begin(), in.end(), {}, proj);
193       assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), {}, proj, proj));
194       assert(base(result.end()) == in.end());
195     }
196 
197     // range overload
198     {
199       auto in     = input;
200       auto result = std::ranges::unique(in, {}, proj);
201       assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end(), {}, proj, proj));
202       assert(base(result.end()) == in.end());
203     }
204   }
205 
206   // Complexity: For nonempty ranges, exactly (last - first) - 1 applications of the corresponding predicate
207   // and no more than twice as many applications of any projection.
208   {
209     std::array input{1, 2, 3, 3, 3, 4, 3, 3, 5, 5, 6, 6, 1};
210     std::array expected{1, 2, 3, 4, 3, 5, 6, 1};
211     // iterator overload
212     {
213       auto in          = input;
214       int numberOfComp = 0;
215       int numberOfProj = 0;
216       auto result      = std::ranges::unique(
217           in.begin(),
218           in.end(),
219           counting_predicate{std::ranges::equal_to{}, numberOfComp},
220           counting_projection{numberOfProj});
221       assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end()));
222       assert(base(result.end()) == in.end());
223       assert(numberOfComp == in.size() - 1);
224       assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));
225     }
226     // range overload
227     {
228       auto in          = input;
229       int numberOfComp = 0;
230       int numberOfProj = 0;
231       auto result      = std::ranges::unique(
232           in, counting_predicate{std::ranges::equal_to{}, numberOfComp}, counting_projection{numberOfProj});
233       assert(std::ranges::equal(in.begin(), result.begin(), expected.begin(), expected.end()));
234       assert(base(result.end()) == in.end());
235       assert(numberOfComp == in.size() - 1);
236       assert(numberOfProj <= static_cast<int>(2 * (in.size() - 1)));
237     }
238   }
239 
240   return true;
241 }
242 
243 int main(int, char**) {
244   test();
245   static_assert(test());
246 
247   return 0;
248 }
249