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
34template <class Iter = int*, class Sent = int*, class Comp = std::ranges::equal_to, class Proj = std::identity>
35concept 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
41static_assert(HasUniqueIter<int*, int*>);
42
43// !permutable<I>
44static_assert(!HasUniqueIter<PermutableNotForwardIterator>);
45static_assert(!HasUniqueIter<PermutableNotSwappable>);
46
47// !sentinel_for<S, I>
48static_assert(!HasUniqueIter<int*, SentinelForNotSemiregular>);
49
50// !indirect_equivalence_relation<Comp, projected<I, Proj>>
51static_assert(!HasUniqueIter<int*, int*, ComparatorNotCopyable<int>>);
52
53template <class Range, class Comp = std::ranges::equal_to, class Proj = std::identity>
54concept 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
59template <class T>
60using R = UncheckedRange<T>;
61
62static_assert(HasUniqueRange<R<int*>>);
63
64// !forward_range<R>
65static_assert(!HasUniqueRange<ForwardRangeNotDerivedFrom>);
66static_assert(!HasUniqueRange<ForwardRangeNotIncrementable>);
67
68// permutable<ranges::iterator_t<R>>
69static_assert(!HasUniqueRange<R<PermutableNotForwardIterator>>);
70static_assert(!HasUniqueRange<R<PermutableNotSwappable>>);
71
72// !indirect_equivalence_relation<Comp, projected<ranges::iterator_t<R>, Proj>>
73static_assert(!HasUniqueRange<R<int*>, ComparatorNotCopyable<int>>);
74
75template <class Iter, template <class> class SentWrapper, std::size_t N1, std::size_t N2>
76constexpr 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
98template <class Iter, template <class> class SentWrapper>
99constexpr 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
141template <template <class> class SentWrapper>
142constexpr 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
150constexpr 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{.data: 4}, Data{.data: 8}, Data{.data: 8}, Data{.data: 8}};
161 std::array expected{Data{.data: 4}, Data{.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{.data: 4}, Data{.data: 8}, Data{.data: 8}, Data{.data: 8}};
184 std::array expected{Data{.data: 4}, Data{.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
242int main(int, char**) {
243 test();
244 static_assert(test());
245
246 return 0;
247}
248

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