1 /*
2  * Copyright (C) 2016 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include <algorithm>
18 #include <forward_list>
19 #include <list>
20 #include <type_traits>
21 #include <vector>
22 
23 #include "gtest/gtest.h"
24 #include "transform_iterator.h"
25 
26 namespace art {
27 
28 namespace {  // anonymous namespace
29 
30 struct ValueHolder {
31   // Deliberately not explicit.
32   ValueHolder(int v) : value(v) { }  // NOLINT
33   int value;
34 };
35 
36 bool operator==(const ValueHolder& lhs, const ValueHolder& rhs) {
37   return lhs.value == rhs.value;
38 }
39 
40 }  // anonymous namespace
41 
42 TEST(TransformIterator, VectorAdd1) {
43   auto add1 = [](const ValueHolder& h) { return h.value + 1; };
44   std::vector<ValueHolder> input({ 1, 7, 3, 8 });
45   std::vector<int> output;
46 
47   using vector_titer = decltype(MakeTransformIterator(input.begin(), add1));
48   static_assert(std::is_same<std::random_access_iterator_tag,
49                              vector_titer::iterator_category>::value, "category");
50   static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type");
51   static_assert(std::is_same<vector_titer, vector_titer::pointer>::value, "pointer");
52   static_assert(std::is_same<int, vector_titer::reference>::value, "reference");
53 
54   using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), add1));
55   static_assert(std::is_same<std::random_access_iterator_tag,
56                              vector_ctiter::iterator_category>::value, "category");
57   static_assert(std::is_same<int, vector_ctiter::value_type>::value, "value_type");
58   static_assert(std::is_same<vector_ctiter, vector_ctiter::pointer>::value, "pointer");
59   static_assert(std::is_same<int, vector_ctiter::reference>::value, "reference");
60 
61   using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), add1));
62   static_assert(std::is_same<std::random_access_iterator_tag,
63                              vector_rtiter::iterator_category>::value, "category");
64   static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type");
65   static_assert(std::is_same<vector_rtiter, vector_rtiter::pointer>::value, "pointer");
66   static_assert(std::is_same<int, vector_rtiter::reference>::value, "reference");
67 
68   using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), add1));
69   static_assert(std::is_same<std::random_access_iterator_tag,
70                              vector_crtiter::iterator_category>::value, "category");
71   static_assert(std::is_same<int, vector_crtiter::value_type>::value, "value_type");
72   static_assert(std::is_same<vector_crtiter, vector_crtiter::pointer>::value, "pointer");
73   static_assert(std::is_same<int, vector_crtiter::reference>::value, "reference");
74 
75   std::copy(MakeTransformIterator(input.begin(), add1),
76             MakeTransformIterator(input.end(), add1),
77             std::back_inserter(output));
78   ASSERT_EQ(std::vector<int>({ 2, 8, 4, 9 }), output);
79   output.clear();
80 
81   std::copy(MakeTransformIterator(input.cbegin(), add1),
82             MakeTransformIterator(input.cend(), add1),
83             std::back_inserter(output));
84   ASSERT_EQ(std::vector<int>({ 2, 8, 4, 9 }), output);
85   output.clear();
86 
87   std::copy(MakeTransformIterator(input.rbegin(), add1),
88             MakeTransformIterator(input.rend(), add1),
89             std::back_inserter(output));
90   ASSERT_EQ(std::vector<int>({ 9, 4, 8, 2 }), output);
91   output.clear();
92 
93   std::copy(MakeTransformIterator(input.crbegin(), add1),
94             MakeTransformIterator(input.crend(), add1),
95             std::back_inserter(output));
96   ASSERT_EQ(std::vector<int>({ 9, 4, 8, 2 }), output);
97   output.clear();
98 
99   for (size_t i = 0; i != input.size(); ++i) {
100     ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.begin(), add1)[i]);
101     ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.cbegin(), add1)[i]);
102     ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u);
103     ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.rbegin(), add1)[index_from_rbegin]);
104     ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.crbegin(), add1)[index_from_rbegin]);
105     ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i);
106     ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.end(), add1)[index_from_end]);
107     ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.cend(), add1)[index_from_end]);
108     ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i);
109     ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.rend(), add1)[index_from_rend]);
110     ASSERT_EQ(input[i].value + 1, MakeTransformIterator(input.crend(), add1)[index_from_rend]);
111 
112     ASSERT_EQ(MakeTransformIterator(input.begin(), add1) + i,
113               MakeTransformIterator(input.begin() + i, add1));
114     ASSERT_EQ(MakeTransformIterator(input.cbegin(), add1) + i,
115               MakeTransformIterator(input.cbegin() + i, add1));
116     ASSERT_EQ(MakeTransformIterator(input.rbegin(), add1) + i,
117               MakeTransformIterator(input.rbegin() + i, add1));
118     ASSERT_EQ(MakeTransformIterator(input.crbegin(), add1) + i,
119               MakeTransformIterator(input.crbegin() + i, add1));
120     ASSERT_EQ(MakeTransformIterator(input.end(), add1) - i,
121               MakeTransformIterator(input.end() - i, add1));
122     ASSERT_EQ(MakeTransformIterator(input.cend(), add1) - i,
123               MakeTransformIterator(input.cend() - i, add1));
124     ASSERT_EQ(MakeTransformIterator(input.rend(), add1) - i,
125               MakeTransformIterator(input.rend() - i, add1));
126     ASSERT_EQ(MakeTransformIterator(input.crend(), add1) - i,
127               MakeTransformIterator(input.crend() - i, add1));
128   }
129   ASSERT_EQ(input.end(),
130             (MakeTransformIterator(input.begin(), add1) + input.size()).base());
131   ASSERT_EQ(MakeTransformIterator(input.end(), add1) - MakeTransformIterator(input.begin(), add1),
132             static_cast<ptrdiff_t>(input.size()));
133 
134   // Test iterator->const_iterator conversion and comparison.
135   auto it = MakeTransformIterator(input.begin(), add1);
136   decltype(MakeTransformIterator(input.cbegin(), add1)) cit = it;
137   static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different");
138   ASSERT_EQ(it, cit);
139   auto rit = MakeTransformIterator(input.rbegin(), add1);
140   decltype(MakeTransformIterator(input.crbegin(), add1)) crit(rit);
141   static_assert(!std::is_same<decltype(rit), decltype(crit)>::value, "Types must be different");
142   ASSERT_EQ(rit, crit);
143 }
144 
145 TEST(TransformIterator, ListSub1) {
146   auto sub1 = [](const ValueHolder& h) { return h.value - 1; };
147   std::list<ValueHolder> input({ 2, 3, 5, 7, 11 });
148   std::vector<int> output;
149 
150   using list_titer = decltype(MakeTransformIterator(input.begin(), sub1));
151   static_assert(std::is_same<std::bidirectional_iterator_tag,
152                              list_titer::iterator_category>::value, "category");
153   static_assert(std::is_same<int, list_titer::value_type>::value, "value_type");
154   static_assert(std::is_same<list_titer, list_titer::pointer>::value, "pointer");
155   static_assert(std::is_same<int, list_titer::reference>::value, "reference");
156 
157   using list_ctiter = decltype(MakeTransformIterator(input.cbegin(), sub1));
158   static_assert(std::is_same<std::bidirectional_iterator_tag,
159                              list_ctiter::iterator_category>::value, "category");
160   static_assert(std::is_same<int, list_ctiter::value_type>::value, "value_type");
161   static_assert(std::is_same<list_ctiter, list_ctiter::pointer>::value, "pointer");
162   static_assert(std::is_same<int, list_ctiter::reference>::value, "reference");
163 
164   using list_rtiter = decltype(MakeTransformIterator(input.rbegin(), sub1));
165   static_assert(std::is_same<std::bidirectional_iterator_tag,
166                              list_rtiter::iterator_category>::value, "category");
167   static_assert(std::is_same<int, list_rtiter::value_type>::value, "value_type");
168   static_assert(std::is_same<list_rtiter, list_rtiter::pointer>::value, "pointer");
169   static_assert(std::is_same<int, list_rtiter::reference>::value, "reference");
170 
171   using list_crtiter = decltype(MakeTransformIterator(input.crbegin(), sub1));
172   static_assert(std::is_same<std::bidirectional_iterator_tag,
173                              list_crtiter::iterator_category>::value, "category");
174   static_assert(std::is_same<int, list_crtiter::value_type>::value, "value_type");
175   static_assert(std::is_same<list_crtiter, list_crtiter::pointer>::value, "pointer");
176   static_assert(std::is_same<int, list_crtiter::reference>::value, "reference");
177 
178   std::copy(MakeTransformIterator(input.begin(), sub1),
179             MakeTransformIterator(input.end(), sub1),
180             std::back_inserter(output));
181   ASSERT_EQ(std::vector<int>({ 1, 2, 4, 6, 10 }), output);
182   output.clear();
183 
184   std::copy(MakeTransformIterator(input.cbegin(), sub1),
185             MakeTransformIterator(input.cend(), sub1),
186             std::back_inserter(output));
187   ASSERT_EQ(std::vector<int>({ 1, 2, 4, 6, 10 }), output);
188   output.clear();
189 
190   std::copy(MakeTransformIterator(input.rbegin(), sub1),
191             MakeTransformIterator(input.rend(), sub1),
192             std::back_inserter(output));
193   ASSERT_EQ(std::vector<int>({ 10, 6, 4, 2, 1 }), output);
194   output.clear();
195 
196   std::copy(MakeTransformIterator(input.crbegin(), sub1),
197             MakeTransformIterator(input.crend(), sub1),
198             std::back_inserter(output));
199   ASSERT_EQ(std::vector<int>({ 10, 6, 4, 2, 1  }), output);
200   output.clear();
201 
202   // Test iterator->const_iterator conversion and comparison.
203   auto it = MakeTransformIterator(input.begin(), sub1);
204   decltype(MakeTransformIterator(input.cbegin(), sub1)) cit = it;
205   static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different");
206   ASSERT_EQ(it, cit);
207 }
208 
209 TEST(TransformIterator, ForwardListSub1) {
210   auto mul3 = [](const ValueHolder& h) { return h.value * 3; };
211   std::forward_list<ValueHolder> input({ 1, 1, 2, 3, 5, 8 });
212   std::vector<int> output;
213 
214   using flist_titer = decltype(MakeTransformIterator(input.begin(), mul3));
215   static_assert(std::is_same<std::forward_iterator_tag,
216                              flist_titer::iterator_category>::value, "category");
217   static_assert(std::is_same<int, flist_titer::value_type>::value, "value_type");
218   static_assert(std::is_same<flist_titer, flist_titer::pointer>::value, "pointer");
219   static_assert(std::is_same<int, flist_titer::reference>::value, "reference");
220 
221   using flist_ctiter = decltype(MakeTransformIterator(input.cbegin(), mul3));
222   static_assert(std::is_same<std::forward_iterator_tag,
223                              flist_ctiter::iterator_category>::value, "category");
224   static_assert(std::is_same<int, flist_ctiter::value_type>::value, "value_type");
225   static_assert(std::is_same<flist_ctiter, flist_ctiter::pointer>::value, "pointer");
226   static_assert(std::is_same<int, flist_ctiter::reference>::value, "reference");
227 
228   std::copy(MakeTransformIterator(input.begin(), mul3),
229             MakeTransformIterator(input.end(), mul3),
230             std::back_inserter(output));
231   ASSERT_EQ(std::vector<int>({ 3, 3, 6, 9, 15, 24 }), output);
232   output.clear();
233 
234   std::copy(MakeTransformIterator(input.cbegin(), mul3),
235             MakeTransformIterator(input.cend(), mul3),
236             std::back_inserter(output));
237   ASSERT_EQ(std::vector<int>({ 3, 3, 6, 9, 15, 24 }), output);
238   output.clear();
239 
240   // Test iterator->const_iterator conversion and comparison.
241   auto it = MakeTransformIterator(input.begin(), mul3);
242   decltype(MakeTransformIterator(input.cbegin(), mul3)) cit = it;
243   static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different");
244   ASSERT_EQ(it, cit);
245 }
246 
247 TEST(TransformIterator, VectorConstReference) {
248   auto ref = [](const ValueHolder& h) -> const int& { return h.value; };
249   std::vector<ValueHolder> input({ 7, 3, 1, 2, 4, 8 });
250   std::vector<int> output;
251 
252   using vector_titer = decltype(MakeTransformIterator(input.begin(), ref));
253   static_assert(std::is_same<std::random_access_iterator_tag,
254                              vector_titer::iterator_category>::value, "category");
255   static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type");
256   static_assert(std::is_same<const int*, vector_titer::pointer>::value, "pointer");
257   static_assert(std::is_same<const int&, vector_titer::reference>::value, "reference");
258 
259   using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), ref));
260   static_assert(std::is_same<std::random_access_iterator_tag,
261                              vector_ctiter::iterator_category>::value, "category");
262   static_assert(std::is_same<int, vector_ctiter::value_type>::value, "value_type");
263   static_assert(std::is_same<const int*, vector_ctiter::pointer>::value, "pointer");
264   static_assert(std::is_same<const int&, vector_ctiter::reference>::value, "reference");
265 
266   using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref));
267   static_assert(std::is_same<std::random_access_iterator_tag,
268                              vector_rtiter::iterator_category>::value, "category");
269   static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type");
270   static_assert(std::is_same<const int*, vector_rtiter::pointer>::value, "pointer");
271   static_assert(std::is_same<const int&, vector_rtiter::reference>::value, "reference");
272 
273   using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), ref));
274   static_assert(std::is_same<std::random_access_iterator_tag,
275                              vector_crtiter::iterator_category>::value, "category");
276   static_assert(std::is_same<int, vector_crtiter::value_type>::value, "value_type");
277   static_assert(std::is_same<const int*, vector_crtiter::pointer>::value, "pointer");
278   static_assert(std::is_same<const int&, vector_crtiter::reference>::value, "reference");
279 
280   std::copy(MakeTransformIterator(input.begin(), ref),
281             MakeTransformIterator(input.end(), ref),
282             std::back_inserter(output));
283   ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
284   output.clear();
285 
286   std::copy(MakeTransformIterator(input.cbegin(), ref),
287             MakeTransformIterator(input.cend(), ref),
288             std::back_inserter(output));
289   ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
290   output.clear();
291 
292   std::copy(MakeTransformIterator(input.rbegin(), ref),
293             MakeTransformIterator(input.rend(), ref),
294             std::back_inserter(output));
295   ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
296   output.clear();
297 
298   std::copy(MakeTransformIterator(input.crbegin(), ref),
299             MakeTransformIterator(input.crend(), ref),
300             std::back_inserter(output));
301   ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
302   output.clear();
303 
304   for (size_t i = 0; i != input.size(); ++i) {
305     ASSERT_EQ(input[i].value, MakeTransformIterator(input.begin(), ref)[i]);
306     ASSERT_EQ(input[i].value, MakeTransformIterator(input.cbegin(), ref)[i]);
307     ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u);
308     ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]);
309     ASSERT_EQ(input[i].value, MakeTransformIterator(input.crbegin(), ref)[index_from_rbegin]);
310     ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i);
311     ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]);
312     ASSERT_EQ(input[i].value, MakeTransformIterator(input.cend(), ref)[index_from_end]);
313     ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i);
314     ASSERT_EQ(input[i].value, MakeTransformIterator(input.rend(), ref)[index_from_rend]);
315     ASSERT_EQ(input[i].value, MakeTransformIterator(input.crend(), ref)[index_from_rend]);
316 
317     ASSERT_EQ(MakeTransformIterator(input.begin(), ref) + i,
318               MakeTransformIterator(input.begin() + i, ref));
319     ASSERT_EQ(MakeTransformIterator(input.cbegin(), ref) + i,
320               MakeTransformIterator(input.cbegin() + i, ref));
321     ASSERT_EQ(MakeTransformIterator(input.rbegin(), ref) + i,
322               MakeTransformIterator(input.rbegin() + i, ref));
323     ASSERT_EQ(MakeTransformIterator(input.crbegin(), ref) + i,
324               MakeTransformIterator(input.crbegin() + i, ref));
325     ASSERT_EQ(MakeTransformIterator(input.end(), ref) - i,
326               MakeTransformIterator(input.end() - i, ref));
327     ASSERT_EQ(MakeTransformIterator(input.cend(), ref) - i,
328               MakeTransformIterator(input.cend() - i, ref));
329     ASSERT_EQ(MakeTransformIterator(input.rend(), ref) - i,
330               MakeTransformIterator(input.rend() - i, ref));
331     ASSERT_EQ(MakeTransformIterator(input.crend(), ref) - i,
332               MakeTransformIterator(input.crend() - i, ref));
333   }
334   ASSERT_EQ(input.end(),
335             (MakeTransformIterator(input.begin(), ref) + input.size()).base());
336   ASSERT_EQ(MakeTransformIterator(input.end(), ref) - MakeTransformIterator(input.begin(), ref),
337             static_cast<ptrdiff_t>(input.size()));
338 }
339 
340 TEST(TransformIterator, VectorNonConstReference) {
341   auto ref = [](ValueHolder& h) -> int& { return h.value; };
342   std::vector<ValueHolder> input({ 7, 3, 1, 2, 4, 8 });
343   std::vector<int> output;
344 
345   using vector_titer = decltype(MakeTransformIterator(input.begin(), ref));
346   static_assert(std::is_same<std::random_access_iterator_tag,
347                              vector_titer::iterator_category>::value, "category");
348   static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type");
349   static_assert(std::is_same<int*, vector_titer::pointer>::value, "pointer");
350   static_assert(std::is_same<int&, vector_titer::reference>::value, "reference");
351 
352   using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref));
353   static_assert(std::is_same<std::random_access_iterator_tag,
354                              vector_rtiter::iterator_category>::value, "category");
355   static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type");
356   static_assert(std::is_same<int*, vector_rtiter::pointer>::value, "pointer");
357   static_assert(std::is_same<int&, vector_rtiter::reference>::value, "reference");
358 
359   std::copy(MakeTransformIterator(input.begin(), ref),
360             MakeTransformIterator(input.end(), ref),
361             std::back_inserter(output));
362   ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
363   output.clear();
364 
365   std::copy(MakeTransformIterator(input.rbegin(), ref),
366             MakeTransformIterator(input.rend(), ref),
367             std::back_inserter(output));
368   ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
369   output.clear();
370 
371   for (size_t i = 0; i != input.size(); ++i) {
372     ASSERT_EQ(input[i].value, MakeTransformIterator(input.begin(), ref)[i]);
373     ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u);
374     ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]);
375     ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i);
376     ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]);
377     ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i);
378     ASSERT_EQ(input[i].value, MakeTransformIterator(input.rend(), ref)[index_from_rend]);
379 
380     ASSERT_EQ(MakeTransformIterator(input.begin(), ref) + i,
381               MakeTransformIterator(input.begin() + i, ref));
382     ASSERT_EQ(MakeTransformIterator(input.rbegin(), ref) + i,
383               MakeTransformIterator(input.rbegin() + i, ref));
384     ASSERT_EQ(MakeTransformIterator(input.end(), ref) - i,
385               MakeTransformIterator(input.end() - i, ref));
386     ASSERT_EQ(MakeTransformIterator(input.rend(), ref) - i,
387               MakeTransformIterator(input.rend() - i, ref));
388   }
389   ASSERT_EQ(input.end(),
390             (MakeTransformIterator(input.begin(), ref) + input.size()).base());
391   ASSERT_EQ(MakeTransformIterator(input.end(), ref) - MakeTransformIterator(input.begin(), ref),
392             static_cast<ptrdiff_t>(input.size()));
393 
394   // Test writing through the transform iterator.
395   std::list<int> transform_input({ 1, -1, 2, -2, 3, -3 });
396   std::vector<ValueHolder> transformed(transform_input.size(), 0);
397   std::transform(transform_input.begin(),
398                  transform_input.end(),
399                  MakeTransformIterator(transformed.begin(), ref),
400                  [](int v) { return -2 * v; });
401   ASSERT_EQ(std::vector<ValueHolder>({ -2, 2, -4, 4, -6, 6 }), transformed);
402 }
403 
404 TEST(TransformIterator, VectorConstAndNonConstReference) {
405   struct Ref {
406     int& operator()(ValueHolder& h) const { return h.value; }
407     const int& operator()(const ValueHolder& h) const { return h.value; }
408   };
409   Ref ref;
410   std::vector<ValueHolder> input({ 7, 3, 1, 2, 4, 8 });
411   std::vector<int> output;
412 
413   using vector_titer = decltype(MakeTransformIterator(input.begin(), ref));
414   static_assert(std::is_same<std::random_access_iterator_tag,
415                              vector_titer::iterator_category>::value, "category");
416   static_assert(std::is_same<int, vector_titer::value_type>::value, "value_type");
417   static_assert(std::is_same<int*, vector_titer::pointer>::value, "pointer");
418   static_assert(std::is_same<int&, vector_titer::reference>::value, "reference");
419 
420   using vector_ctiter = decltype(MakeTransformIterator(input.cbegin(), ref));
421   static_assert(std::is_same<std::random_access_iterator_tag,
422                              vector_ctiter::iterator_category>::value, "category");
423   // static_assert(std::is_same<int, vector_ctiter::value_type>::value, "value_type");
424   static_assert(std::is_same<const int*, vector_ctiter::pointer>::value, "pointer");
425   static_assert(std::is_same<const int&, vector_ctiter::reference>::value, "reference");
426 
427   using vector_rtiter = decltype(MakeTransformIterator(input.rbegin(), ref));
428   static_assert(std::is_same<std::random_access_iterator_tag,
429                              vector_rtiter::iterator_category>::value, "category");
430   static_assert(std::is_same<int, vector_rtiter::value_type>::value, "value_type");
431   static_assert(std::is_same<int*, vector_rtiter::pointer>::value, "pointer");
432   static_assert(std::is_same<int&, vector_rtiter::reference>::value, "reference");
433 
434   using vector_crtiter = decltype(MakeTransformIterator(input.crbegin(), ref));
435   static_assert(std::is_same<std::random_access_iterator_tag,
436                              vector_crtiter::iterator_category>::value, "category");
437   // static_assert(std::is_same<int, vector_crtiter::value_type>::value, "value_type");
438   static_assert(std::is_same<const int*, vector_crtiter::pointer>::value, "pointer");
439   static_assert(std::is_same<const int&, vector_crtiter::reference>::value, "reference");
440 
441   std::copy(MakeTransformIterator(input.begin(), ref),
442             MakeTransformIterator(input.end(), ref),
443             std::back_inserter(output));
444   ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
445   output.clear();
446 
447   std::copy(MakeTransformIterator(input.cbegin(), ref),
448             MakeTransformIterator(input.cend(), ref),
449             std::back_inserter(output));
450   ASSERT_EQ(std::vector<int>({ 7, 3, 1, 2, 4, 8 }), output);
451   output.clear();
452 
453   std::copy(MakeTransformIterator(input.rbegin(), ref),
454             MakeTransformIterator(input.rend(), ref),
455             std::back_inserter(output));
456   ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
457   output.clear();
458 
459   std::copy(MakeTransformIterator(input.crbegin(), ref),
460             MakeTransformIterator(input.crend(), ref),
461             std::back_inserter(output));
462   ASSERT_EQ(std::vector<int>({ 8, 4, 2, 1, 3, 7 }), output);
463   output.clear();
464 
465   for (size_t i = 0; i != input.size(); ++i) {
466     ASSERT_EQ(input[i].value, MakeTransformIterator(input.begin(), ref)[i]);
467     ASSERT_EQ(input[i].value, MakeTransformIterator(input.cbegin(), ref)[i]);
468     ptrdiff_t index_from_rbegin = static_cast<ptrdiff_t>(input.size() - i - 1u);
469     ASSERT_EQ(input[i].value, MakeTransformIterator(input.rbegin(), ref)[index_from_rbegin]);
470     ASSERT_EQ(input[i].value, MakeTransformIterator(input.crbegin(), ref)[index_from_rbegin]);
471     ptrdiff_t index_from_end = -static_cast<ptrdiff_t>(input.size() - i);
472     ASSERT_EQ(input[i].value, MakeTransformIterator(input.end(), ref)[index_from_end]);
473     ASSERT_EQ(input[i].value, MakeTransformIterator(input.cend(), ref)[index_from_end]);
474     ptrdiff_t index_from_rend = -1 - static_cast<ptrdiff_t>(i);
475     ASSERT_EQ(input[i].value, MakeTransformIterator(input.rend(), ref)[index_from_rend]);
476     ASSERT_EQ(input[i].value, MakeTransformIterator(input.crend(), ref)[index_from_rend]);
477 
478     ASSERT_EQ(MakeTransformIterator(input.begin(), ref) + i,
479               MakeTransformIterator(input.begin() + i, ref));
480     ASSERT_EQ(MakeTransformIterator(input.cbegin(), ref) + i,
481               MakeTransformIterator(input.cbegin() + i, ref));
482     ASSERT_EQ(MakeTransformIterator(input.rbegin(), ref) + i,
483               MakeTransformIterator(input.rbegin() + i, ref));
484     ASSERT_EQ(MakeTransformIterator(input.crbegin(), ref) + i,
485               MakeTransformIterator(input.crbegin() + i, ref));
486     ASSERT_EQ(MakeTransformIterator(input.end(), ref) - i,
487               MakeTransformIterator(input.end() - i, ref));
488     ASSERT_EQ(MakeTransformIterator(input.cend(), ref) - i,
489               MakeTransformIterator(input.cend() - i, ref));
490     ASSERT_EQ(MakeTransformIterator(input.rend(), ref) - i,
491               MakeTransformIterator(input.rend() - i, ref));
492     ASSERT_EQ(MakeTransformIterator(input.crend(), ref) - i,
493               MakeTransformIterator(input.crend() - i, ref));
494   }
495   ASSERT_EQ(input.end(),
496             (MakeTransformIterator(input.begin(), ref) + input.size()).base());
497   ASSERT_EQ(MakeTransformIterator(input.end(), ref) - MakeTransformIterator(input.begin(), ref),
498             static_cast<ptrdiff_t>(input.size()));
499 
500   // Test iterator->const_iterator conversion and comparison.
501   auto it = MakeTransformIterator(input.begin(), ref);
502   decltype(MakeTransformIterator(input.cbegin(), ref)) cit = it;
503   static_assert(!std::is_same<decltype(it), decltype(cit)>::value, "Types must be different");
504   ASSERT_EQ(it, cit);
505   auto rit = MakeTransformIterator(input.rbegin(), ref);
506   decltype(MakeTransformIterator(input.crbegin(), ref)) crit(rit);
507   static_assert(!std::is_same<decltype(rit), decltype(crit)>::value, "Types must be different");
508   ASSERT_EQ(rit, crit);
509 
510   // Test writing through the transform iterator.
511   std::list<int> transform_input({ 42, 73, 11, 17 });
512   std::vector<ValueHolder> transformed(transform_input.size(), 0);
513   std::transform(transform_input.begin(),
514                  transform_input.end(),
515                  MakeTransformIterator(transformed.begin(), ref),
516                  [](int v) { return -v; });
517   ASSERT_EQ(std::vector<ValueHolder>({ -42, -73, -11, -17 }), transformed);
518 }
519 
520 TEST(TransformIterator, TransformRange) {
521   auto ref = [](ValueHolder& h) -> int& { return h.value; };
522   std::vector<ValueHolder> data({ 1, 0, 1, 3, 1, 0 });
523 
524   for (int& v : MakeTransformRange(data, ref)) {
525     v += 11;
526   }
527   ASSERT_EQ(std::vector<ValueHolder>({ 12, 11, 12, 14, 12, 11 }), data);
528 }
529 
530 }  // namespace art
531