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