1 // Range v3 library
2 //
3 // Copyright Eric Niebler 2014-present
4 //
5 // Use, modification and distribution is subject to the
6 // Boost Software License, Version 1.0. (See accompanying
7 // file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9 //
10 // Project home: https://github.com/ericniebler/range-v3
11 //
12 // Copyright 2005 - 2007 Adobe Systems Incorporated
13 // Distributed under the MIT License(see accompanying file LICENSE_1_0_0.txt
14 // or a copy at http://stlab.adobe.com/licenses.html)
15
16 //===----------------------------------------------------------------------===//
17 //
18 // The LLVM Compiler Infrastructure
19 //
20 // This file is dual licensed under the MIT and the University of Illinois Open
21 // Source Licenses. See LICENSE.TXT for details.
22 //
23 //===----------------------------------------------------------------------===//
24
25 // Implementation based on the code in libc++
26 // http://http://libcxx.llvm.org/
27
28 #include <cstring>
29 #include <vector>
30 #include <range/v3/core.hpp>
31 #include <range/v3/algorithm/unique_copy.hpp>
32 #include "../simple_test.hpp"
33 #include "../test_utils.hpp"
34 #include "../test_iterators.hpp"
35
36 struct count_equal
37 {
38 static unsigned count;
39 template<class T>
operator ()count_equal40 bool operator()(const T& x, const T& y)
41 {++count; return x == y;}
42 };
43
44 unsigned count_equal::count = 0;
45
46 template<class InIter, class OutIter, typename Sent = InIter>
47 void
test_iter()48 test_iter()
49 {
50 const int ia[] = {0};
51 const unsigned sa = sizeof(ia)/sizeof(ia[0]);
52 int ja[sa] = {-1};
53 count_equal::count = 0;
54 ranges::unique_copy_result<InIter, OutIter> r = ranges::unique_copy(InIter(ia), Sent(ia+sa), OutIter(ja), count_equal());
55 CHECK(base(r.in) == ia + sa);
56 CHECK(base(r.out) == ja + sa);
57 CHECK(ja[0] == 0);
58 CHECK(count_equal::count == sa-1);
59
60 const int ib[] = {0, 1};
61 const unsigned sb = sizeof(ib)/sizeof(ib[0]);
62 int jb[sb] = {-1};
63 count_equal::count = 0;
64 r = ranges::unique_copy(InIter(ib), Sent(ib+sb), OutIter(jb), count_equal());
65 CHECK(base(r.in) == ib + sb);
66 CHECK(base(r.out) == jb + sb);
67 CHECK(jb[0] == 0);
68 CHECK(jb[1] == 1);
69 CHECK(count_equal::count == sb-1);
70
71 const int ic[] = {0, 0};
72 const unsigned sc = sizeof(ic)/sizeof(ic[0]);
73 int jc[sc] = {-1};
74 count_equal::count = 0;
75 r = ranges::unique_copy(InIter(ic), Sent(ic+sc), OutIter(jc), count_equal());
76 CHECK(base(r.in) == ic + sc);
77 CHECK(base(r.out) == jc + 1);
78 CHECK(jc[0] == 0);
79 CHECK(count_equal::count == sc-1);
80
81 const int id[] = {0, 0, 1};
82 const unsigned sd = sizeof(id)/sizeof(id[0]);
83 int jd[sd] = {-1};
84 count_equal::count = 0;
85 r = ranges::unique_copy(InIter(id), Sent(id+sd), OutIter(jd), count_equal());
86 CHECK(base(r.in) == id + sd);
87 CHECK(base(r.out) == jd + 2);
88 CHECK(jd[0] == 0);
89 CHECK(jd[1] == 1);
90 CHECK(count_equal::count == sd-1);
91
92 const int ie[] = {0, 0, 1, 0};
93 const unsigned se = sizeof(ie)/sizeof(ie[0]);
94 int je[se] = {-1};
95 count_equal::count = 0;
96 r = ranges::unique_copy(InIter(ie), Sent(ie+se), OutIter(je), count_equal());
97 CHECK(base(r.in) == ie + se);
98 CHECK(base(r.out) == je + 3);
99 CHECK(je[0] == 0);
100 CHECK(je[1] == 1);
101 CHECK(je[2] == 0);
102 CHECK(count_equal::count == se-1);
103
104 const int ig[] = {0, 0, 1, 1};
105 const unsigned sg = sizeof(ig)/sizeof(ig[0]);
106 int jg[sg] = {-1};
107 count_equal::count = 0;
108 r = ranges::unique_copy(InIter(ig), Sent(ig+sg), OutIter(jg), count_equal());
109 CHECK(base(r.in) == ig + sg);
110 CHECK(base(r.out) == jg + 2);
111 CHECK(jg[0] == 0);
112 CHECK(jg[1] == 1);
113 CHECK(count_equal::count == sg-1);
114
115 const int ih[] = {0, 1, 1};
116 const unsigned sh = sizeof(ih)/sizeof(ih[0]);
117 int jh[sh] = {-1};
118 count_equal::count = 0;
119 r = ranges::unique_copy(InIter(ih), Sent(ih+sh), OutIter(jh), count_equal());
120 CHECK(base(r.in) == ih + sh);
121 CHECK(base(r.out) == jh + 2);
122 CHECK(jh[0] == 0);
123 CHECK(jh[1] == 1);
124 CHECK(count_equal::count == sh-1);
125
126 const int ii[] = {0, 1, 1, 1, 2, 2, 2};
127 const unsigned si = sizeof(ii)/sizeof(ii[0]);
128 int ji[si] = {-1};
129 count_equal::count = 0;
130 r = ranges::unique_copy(InIter(ii), Sent(ii+si), OutIter(ji), count_equal());
131 CHECK(base(r.in) == ii + si);
132 CHECK(base(r.out) == ji + 3);
133 CHECK(ji[0] == 0);
134 CHECK(ji[1] == 1);
135 CHECK(ji[2] == 2);
136 CHECK(count_equal::count == si-1);
137 }
138
139 template<class InIter, class OutIter, typename Sent = InIter>
140 void
test_range()141 test_range()
142 {
143 const int ia[] = {0};
144 const unsigned sa = sizeof(ia)/sizeof(ia[0]);
145 int ja[sa] = {-1};
146 count_equal::count = 0;
147 ranges::unique_copy_result<InIter, OutIter> r = ranges::unique_copy(::as_lvalue(ranges::make_subrange(InIter(ia), Sent(ia+sa))), OutIter(ja), count_equal());
148 CHECK(base(r.in) == ia + sa);
149 CHECK(base(r.out) == ja + sa);
150 CHECK(ja[0] == 0);
151 CHECK(count_equal::count == sa-1);
152
153 const int ib[] = {0, 1};
154 const unsigned sb = sizeof(ib)/sizeof(ib[0]);
155 int jb[sb] = {-1};
156 count_equal::count = 0;
157 r = ranges::unique_copy(::as_lvalue(ranges::make_subrange(InIter(ib), Sent(ib+sb))), OutIter(jb), count_equal());
158 CHECK(base(r.in) == ib + sb);
159 CHECK(base(r.out) == jb + sb);
160 CHECK(jb[0] == 0);
161 CHECK(jb[1] == 1);
162 CHECK(count_equal::count == sb-1);
163
164 const int ic[] = {0, 0};
165 const unsigned sc = sizeof(ic)/sizeof(ic[0]);
166 int jc[sc] = {-1};
167 count_equal::count = 0;
168 r = ranges::unique_copy(::as_lvalue(ranges::make_subrange(InIter(ic), Sent(ic+sc))), OutIter(jc), count_equal());
169 CHECK(base(r.in) == ic + sc);
170 CHECK(base(r.out) == jc + 1);
171 CHECK(jc[0] == 0);
172 CHECK(count_equal::count == sc-1);
173
174 const int id[] = {0, 0, 1};
175 const unsigned sd = sizeof(id)/sizeof(id[0]);
176 int jd[sd] = {-1};
177 count_equal::count = 0;
178 r = ranges::unique_copy(::as_lvalue(ranges::make_subrange(InIter(id), Sent(id+sd))), OutIter(jd), count_equal());
179 CHECK(base(r.in) == id + sd);
180 CHECK(base(r.out) == jd + 2);
181 CHECK(jd[0] == 0);
182 CHECK(jd[1] == 1);
183 CHECK(count_equal::count == sd-1);
184
185 const int ie[] = {0, 0, 1, 0};
186 const unsigned se = sizeof(ie)/sizeof(ie[0]);
187 int je[se] = {-1};
188 count_equal::count = 0;
189 r = ranges::unique_copy(::as_lvalue(ranges::make_subrange(InIter(ie), Sent(ie+se))), OutIter(je), count_equal());
190 CHECK(base(r.in) == ie + se);
191 CHECK(base(r.out) == je + 3);
192 CHECK(je[0] == 0);
193 CHECK(je[1] == 1);
194 CHECK(je[2] == 0);
195 CHECK(count_equal::count == se-1);
196
197 const int ig[] = {0, 0, 1, 1};
198 const unsigned sg = sizeof(ig)/sizeof(ig[0]);
199 int jg[sg] = {-1};
200 count_equal::count = 0;
201 r = ranges::unique_copy(::as_lvalue(ranges::make_subrange(InIter(ig), Sent(ig+sg))), OutIter(jg), count_equal());
202 CHECK(base(r.in) == ig + sg);
203 CHECK(base(r.out) == jg + 2);
204 CHECK(jg[0] == 0);
205 CHECK(jg[1] == 1);
206 CHECK(count_equal::count == sg-1);
207
208 const int ih[] = {0, 1, 1};
209 const unsigned sh = sizeof(ih)/sizeof(ih[0]);
210 int jh[sh] = {-1};
211 count_equal::count = 0;
212 r = ranges::unique_copy(::as_lvalue(ranges::make_subrange(InIter(ih), Sent(ih+sh))), OutIter(jh), count_equal());
213 CHECK(base(r.in) == ih + sh);
214 CHECK(base(r.out) == jh + 2);
215 CHECK(jh[0] == 0);
216 CHECK(jh[1] == 1);
217 CHECK(count_equal::count == sh-1);
218
219 const int ii[] = {0, 1, 1, 1, 2, 2, 2};
220 const unsigned si = sizeof(ii)/sizeof(ii[0]);
221 int ji[si] = {-1};
222 count_equal::count = 0;
223 r = ranges::unique_copy(::as_lvalue(ranges::make_subrange(InIter(ii), Sent(ii+si))), OutIter(ji), count_equal());
224 CHECK(base(r.in) == ii + si);
225 CHECK(base(r.out) == ji + 3);
226 CHECK(ji[0] == 0);
227 CHECK(ji[1] == 1);
228 CHECK(ji[2] == 2);
229 CHECK(count_equal::count == si-1);
230 }
231
232 template<class InIter, class OutIter>
test()233 void test()
234 {
235 using Sent = typename sentinel_type<InIter>::type;
236 test_iter<InIter, OutIter>();
237 test_iter<InIter, OutIter, Sent>();
238
239 test_range<InIter, OutIter>();
240 test_range<InIter, OutIter, Sent>();
241 }
242
243 struct S
244 {
245 int i,j;
246 };
247
operator ==(S l,S r)248 bool operator==(S l, S r)
249 {
250 return l.i == r.i && l.j == r.j;
251 }
252
main()253 int main()
254 {
255 test<InputIterator<const int*>, OutputIterator<int*> >();
256 test<InputIterator<const int*>, ForwardIterator<int*> >();
257 test<InputIterator<const int*>, BidirectionalIterator<int*> >();
258 test<InputIterator<const int*>, RandomAccessIterator<int*> >();
259 test<InputIterator<const int*>, int*>();
260
261 test<ForwardIterator<const int*>, OutputIterator<int*> >();
262 test<ForwardIterator<const int*>, ForwardIterator<int*> >();
263 test<ForwardIterator<const int*>, BidirectionalIterator<int*> >();
264 test<ForwardIterator<const int*>, RandomAccessIterator<int*> >();
265 test<ForwardIterator<const int*>, int*>();
266
267 test<BidirectionalIterator<const int*>, OutputIterator<int*> >();
268 test<BidirectionalIterator<const int*>, ForwardIterator<int*> >();
269 test<BidirectionalIterator<const int*>, BidirectionalIterator<int*> >();
270 test<BidirectionalIterator<const int*>, RandomAccessIterator<int*> >();
271 test<BidirectionalIterator<const int*>, int*>();
272
273 test<RandomAccessIterator<const int*>, OutputIterator<int*> >();
274 test<RandomAccessIterator<const int*>, ForwardIterator<int*> >();
275 test<RandomAccessIterator<const int*>, BidirectionalIterator<int*> >();
276 test<RandomAccessIterator<const int*>, RandomAccessIterator<int*> >();
277 test<RandomAccessIterator<const int*>, int*>();
278
279 test<const int*, OutputIterator<int*> >();
280 test<const int*, ForwardIterator<int*> >();
281 test<const int*, BidirectionalIterator<int*> >();
282 test<const int*, RandomAccessIterator<int*> >();
283 test<const int*, int*>();
284
285 // Test projections:
286 {
287 S const ia[] = {{1,1},{2,2},{3,3},{3,4},{4,5},{5,6},{5,7},{5,8},{6,9},{7,10}};
288 S ib[ranges::size(ia)];
289 ranges::unique_copy_result<S const *, S *> r = ranges::unique_copy(ia, ib, ranges::equal_to(), &S::i);
290 CHECK(r.in == ranges::end(ia));
291 CHECK(r.out == ib + 7);
292 check_equal(ranges::make_subrange(ib, ib+7), {S{1,1},S{2,2},S{3,3},S{4,5},S{5,6},S{6,9},S{7,10}});
293 }
294
295 // Test rvalue ranges:
296 {
297 S const ia[] = {{1,1},{2,2},{3,3},{3,4},{4,5},{5,6},{5,7},{5,8},{6,9},{7,10}};
298 S ib[ranges::size(ia)];
299 auto r = ranges::unique_copy(ranges::views::all(ia), ib, ranges::equal_to(), &S::i);
300 CHECK(r.in == ranges::end(ia));
301 CHECK(r.out == ib + 7);
302 check_equal(ranges::make_subrange(ib, ib+7), {S{1,1},S{2,2},S{3,3},S{4,5},S{5,6},S{6,9},S{7,10}});
303 }
304 #ifndef RANGES_WORKAROUND_MSVC_573728
305 {
306 S const ia[] = {{1,1},{2,2},{3,3},{3,4},{4,5},{5,6},{5,7},{5,8},{6,9},{7,10}};
307 S ib[ranges::size(ia)];
308 auto r = ranges::unique_copy(std::move(ia), ib, ranges::equal_to(), &S::i);
309 CHECK(::is_dangling(r.in));
310 CHECK(r.out == ib + 7);
311 check_equal(ranges::make_subrange(ib, ib+7), {S{1,1},S{2,2},S{3,3},S{4,5},S{5,6},S{6,9},S{7,10}});
312 }
313 #endif // RANGES_WORKAROUND_MSVC_573728
314 {
315 std::vector<S> const ia{{1,1},{2,2},{3,3},{3,4},{4,5},{5,6},{5,7},{5,8},{6,9},{7,10}};
316 S ib[10];
317 RANGES_ENSURE(ranges::size(ia) == ranges::size(ib));
318 auto r = ranges::unique_copy(std::move(ia), ib, ranges::equal_to(), &S::i);
319 CHECK(::is_dangling(r.in));
320 CHECK(r.out == ib + 7);
321 check_equal(ranges::make_subrange(ib, ib+7), {S{1,1},S{2,2},S{3,3},S{4,5},S{5,6},S{6,9},S{7,10}});
322 }
323
324 return ::test_result();
325 }
326