1 | /* |
2 | * Copyright 2016-present Facebook, Inc. |
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 <map> |
18 | |
19 | #include <folly/container/Array.h> |
20 | #include <folly/detail/Iterators.h> |
21 | #include <folly/portability/GTest.h> |
22 | |
23 | using namespace folly::detail; |
24 | using namespace folly; |
25 | |
26 | namespace { |
27 | struct IntArrayIterator |
28 | : IteratorFacade<IntArrayIterator, int const, std::forward_iterator_tag> { |
29 | explicit IntArrayIterator(int const* a) : a_(a) {} |
30 | void increment() { |
31 | ++a_; |
32 | } |
33 | int const& dereference() const { |
34 | return *a_; |
35 | } |
36 | bool equal(IntArrayIterator const& rhs) const { |
37 | return rhs.a_ == a_; |
38 | } |
39 | int const* a_; |
40 | }; |
41 | } // namespace |
42 | |
43 | TEST(IteratorsTest, IterFacadeHasCorrectTraits) { |
44 | using TR = std::iterator_traits<IntArrayIterator>; |
45 | static_assert(std::is_same<TR::value_type, int const>::value, "" ); |
46 | static_assert(std::is_same<TR::reference, int const&>::value, "" ); |
47 | static_assert(std::is_same<TR::pointer, int const*>::value, "" ); |
48 | static_assert( |
49 | std::is_same<TR::iterator_category, std::forward_iterator_tag>::value, |
50 | "" ); |
51 | static_assert(std::is_same<TR::difference_type, ssize_t>::value, "" ); |
52 | } |
53 | |
54 | TEST(IteratorsTest, SimpleIteratorFacade) { |
55 | static const auto kArray = folly::make_array(42, 43, 44); |
56 | IntArrayIterator end(kArray.data() + kArray.size()); |
57 | IntArrayIterator iter(kArray.data()); |
58 | EXPECT_NE(iter, end); |
59 | EXPECT_EQ(42, *iter); |
60 | ++iter; |
61 | EXPECT_NE(iter, end); |
62 | EXPECT_EQ(43, *iter); |
63 | ++iter; |
64 | EXPECT_NE(iter, end); |
65 | EXPECT_EQ(44, *iter); |
66 | ++iter; |
67 | EXPECT_EQ(iter, end); |
68 | } |
69 | |
70 | namespace { |
71 | // Simple iterator adaptor: wraps an int pointer. |
72 | struct IntPointerIter : IteratorAdaptor< |
73 | IntPointerIter, |
74 | int const*, |
75 | int const, |
76 | std::forward_iterator_tag> { |
77 | using Super = IteratorAdaptor< |
78 | IntPointerIter, |
79 | int const*, |
80 | int const, |
81 | std::forward_iterator_tag>; |
82 | explicit IntPointerIter(int const* ptr) : Super(ptr) {} |
83 | }; |
84 | } // namespace |
85 | |
86 | TEST(IteratorsTest, IterAdaptorHasCorrectTraits) { |
87 | using TR = std::iterator_traits<IntPointerIter>; |
88 | static_assert(std::is_same<TR::value_type, int const>::value, "" ); |
89 | static_assert(std::is_same<TR::reference, int const&>::value, "" ); |
90 | static_assert(std::is_same<TR::pointer, int const*>::value, "" ); |
91 | static_assert( |
92 | std::is_same<TR::iterator_category, std::forward_iterator_tag>::value, |
93 | "" ); |
94 | static_assert(std::is_same<TR::difference_type, ssize_t>::value, "" ); |
95 | } |
96 | |
97 | TEST(IteratorsTest, IterAdaptorWithPointer) { |
98 | static const auto kArray = folly::make_array(42, 43, 44); |
99 | IntPointerIter end(kArray.data() + kArray.size()); |
100 | IntPointerIter iter(kArray.data()); |
101 | EXPECT_NE(iter, end); |
102 | EXPECT_EQ(42, *iter); |
103 | ++iter; |
104 | EXPECT_NE(iter, end); |
105 | EXPECT_EQ(43, *iter); |
106 | ++iter; |
107 | EXPECT_NE(iter, end); |
108 | EXPECT_EQ(44, *iter); |
109 | ++iter; |
110 | EXPECT_EQ(iter, end); |
111 | } |
112 | |
113 | namespace { |
114 | // More complex case: wrap a map iterator, but these provide either the key or |
115 | // value. |
116 | struct IntMapKeyIter : IteratorAdaptor< |
117 | IntMapKeyIter, |
118 | std::map<int, int>::iterator, |
119 | int const, |
120 | std::forward_iterator_tag> { |
121 | using Super = IteratorAdaptor< |
122 | IntMapKeyIter, |
123 | std::map<int, int>::iterator, |
124 | int const, |
125 | std::forward_iterator_tag>; |
126 | explicit IntMapKeyIter(std::map<int, int>::iterator iter) : Super(iter) {} |
127 | int const& dereference() const { |
128 | return base()->first; |
129 | } |
130 | }; |
131 | |
132 | struct IntMapValueIter : IteratorAdaptor< |
133 | IntMapValueIter, |
134 | std::map<int, int>::iterator, |
135 | int, |
136 | std::forward_iterator_tag> { |
137 | using Super = IteratorAdaptor< |
138 | IntMapValueIter, |
139 | std::map<int, int>::iterator, |
140 | int, |
141 | std::forward_iterator_tag>; |
142 | explicit IntMapValueIter(std::map<int, int>::iterator iter) : Super(iter) {} |
143 | int& dereference() const { |
144 | return base()->second; |
145 | } |
146 | }; |
147 | |
148 | } // namespace |
149 | |
150 | TEST(IteratorsTest, IterAdaptorOfOtherIter) { |
151 | std::map<int, int> m{{2, 42}, {3, 43}, {4, 44}}; |
152 | |
153 | IntMapKeyIter keyEnd(m.end()); |
154 | IntMapKeyIter keyIter(m.begin()); |
155 | EXPECT_NE(keyIter, keyEnd); |
156 | EXPECT_EQ(2, *keyIter); |
157 | ++keyIter; |
158 | EXPECT_NE(keyIter, keyEnd); |
159 | EXPECT_EQ(3, *keyIter); |
160 | ++keyIter; |
161 | EXPECT_NE(keyIter, keyEnd); |
162 | EXPECT_EQ(4, *keyIter); |
163 | ++keyIter; |
164 | EXPECT_EQ(keyIter, keyEnd); |
165 | |
166 | IntMapValueIter valueEnd(m.end()); |
167 | IntMapValueIter valueIter(m.begin()); |
168 | EXPECT_NE(valueIter, valueEnd); |
169 | EXPECT_EQ(42, *valueIter); |
170 | ++valueIter; |
171 | EXPECT_NE(valueIter, valueEnd); |
172 | EXPECT_EQ(43, *valueIter); |
173 | ++valueIter; |
174 | EXPECT_NE(valueIter, valueEnd); |
175 | EXPECT_EQ(44, *valueIter); |
176 | ++valueIter; |
177 | EXPECT_EQ(valueIter, valueEnd); |
178 | } |
179 | |
180 | namespace { |
181 | struct IntMapValueIterConst : IteratorAdaptor< |
182 | IntMapValueIterConst, |
183 | std::map<int, int>::const_iterator, |
184 | int const, |
185 | std::forward_iterator_tag> { |
186 | using Super = IteratorAdaptor< |
187 | IntMapValueIterConst, |
188 | std::map<int, int>::const_iterator, |
189 | int const, |
190 | std::forward_iterator_tag>; |
191 | explicit IntMapValueIterConst(std::map<int, int>::const_iterator iter) |
192 | : Super(iter) {} |
193 | /* implicit */ IntMapValueIterConst(IntMapValueIter const& rhs) |
194 | : IntMapValueIterConst(rhs.base()) {} |
195 | int const& dereference() const { |
196 | return base()->second; |
197 | } |
198 | }; |
199 | } // namespace |
200 | |
201 | TEST(IteratorsTest, MixedConstAndNonconstIters) { |
202 | std::map<int, int> m{{2, 42}, {3, 43}, {4, 44}}; |
203 | IntMapValueIterConst cend(m.cend()); |
204 | IntMapValueIter valueIter(m.begin()); |
205 | EXPECT_NE(valueIter, cend); |
206 | ++valueIter; |
207 | ++valueIter; |
208 | ++valueIter; |
209 | EXPECT_EQ(valueIter, cend); |
210 | } |
211 | |