1 // Copyright 2020 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_containers/flat_map.h"
16
17 #include <limits>
18
19 #include "pw_polyfill/language_feature_macros.h"
20 #include "pw_unit_test/framework.h"
21
22 namespace pw::containers {
23 namespace {
24
25 using Single = FlatMap<int, char, 1>;
26
27 constexpr FlatMap<int, char, 5> kOddMap({{
28 {-3, 'a'},
29 {0, 'b'},
30 {1, 'c'},
31 {50, 'd'},
32 {100, 'e'},
33 }});
34
35 } // namespace
36
TEST(FlatMap,PairEquality)37 TEST(FlatMap, PairEquality) {
38 Pair<char, int> p1{'a', 1};
39 Pair<char, int> p2{'a', 1};
40 Pair<char, int> p3{'b', 1};
41 Pair<char, int> p4{'a', 2};
42
43 EXPECT_EQ(p1, p2);
44 EXPECT_NE(p1, p3);
45 EXPECT_NE(p1, p4);
46 }
47
TEST(FlatMap,Size)48 TEST(FlatMap, Size) { EXPECT_EQ(kOddMap.size(), static_cast<uint32_t>(5)); }
49
TEST(FlatMap,EmptyFlatMapSize)50 TEST(FlatMap, EmptyFlatMapSize) {
51 PW_CONSTEXPR_CPP20 FlatMap<int, char, 0> kEmpty({{}});
52 EXPECT_EQ(kEmpty.size(), static_cast<uint32_t>(0));
53 }
54
TEST(FlatMap,Empty)55 TEST(FlatMap, Empty) {
56 PW_CONSTEXPR_CPP20 FlatMap<int, char, 0> kEmpty({{}});
57 EXPECT_TRUE(kEmpty.empty());
58 }
59
TEST(FlatMap,NotEmpty)60 TEST(FlatMap, NotEmpty) {
61 PW_CONSTEXPR_CPP20 FlatMap<int, char, 1> kNotEmpty({{}});
62 EXPECT_FALSE(kNotEmpty.empty());
63 }
64
TEST(FlatMap,EmptyFlatMapFind)65 TEST(FlatMap, EmptyFlatMapFind) {
66 PW_CONSTEXPR_CPP20 FlatMap<int, char, 0> kEmpty({{}});
67 EXPECT_EQ(kEmpty.find(0), kEmpty.end());
68 }
69
TEST(FlatMap,EmptyFlatMapLowerBound)70 TEST(FlatMap, EmptyFlatMapLowerBound) {
71 PW_CONSTEXPR_CPP20 FlatMap<int, char, 0> kEmpty({{}});
72 EXPECT_EQ(kEmpty.lower_bound(0), kEmpty.end());
73 }
74
TEST(FlatMap,EmptyFlatMapUpperBound)75 TEST(FlatMap, EmptyFlatMapUpperBound) {
76 PW_CONSTEXPR_CPP20 FlatMap<int, char, 0> kEmpty({{}});
77 EXPECT_EQ(kEmpty.upper_bound(0), kEmpty.end());
78 }
79
TEST(FlatMap,EmptyEqualRange)80 TEST(FlatMap, EmptyEqualRange) {
81 PW_CONSTEXPR_CPP20 FlatMap<int, char, 0> kEmpty({{}});
82 EXPECT_EQ(kEmpty.equal_range(0).first, kEmpty.end());
83 EXPECT_EQ(kEmpty.equal_range(0).second, kEmpty.end());
84 }
85
TEST(FlatMap,ConstAtReturnsCorrectValues)86 TEST(FlatMap, ConstAtReturnsCorrectValues) {
87 for (const auto& [key, value] : kOddMap) {
88 EXPECT_EQ(value, kOddMap.at(key));
89 }
90 }
91
TEST(FlatMap,MutableAtReturnsCorrectMutableValues)92 TEST(FlatMap, MutableAtReturnsCorrectMutableValues) {
93 FlatMap<int, char, 5> mutable_map({{
94 {-4, 'a'},
95 {-1, 'b'},
96 {0, 'c'},
97 {49, 'd'},
98 {99, 'e'},
99 }});
100
101 for (const auto& [key, value] : mutable_map) {
102 const char original_value{value};
103 EXPECT_EQ(original_value, mutable_map.at(key));
104 ++mutable_map.at(key);
105 EXPECT_EQ(original_value + 1, mutable_map.at(key));
106 }
107 }
108
TEST(FlatMap,Contains)109 TEST(FlatMap, Contains) {
110 EXPECT_TRUE(kOddMap.contains(0));
111 EXPECT_FALSE(kOddMap.contains(10));
112 }
113
TEST(FlatMap,Iterate)114 TEST(FlatMap, Iterate) {
115 char value = 'a';
116 for (const auto& item : kOddMap) {
117 EXPECT_EQ(value, item.second);
118 EXPECT_EQ(&item, &(*kOddMap.find(item.first)));
119 value += 1;
120 }
121 }
122
TEST(FlatMap,ForwardsMappedValuesIterationWithDeferenceWorks)123 TEST(FlatMap, ForwardsMappedValuesIterationWithDeferenceWorks) {
124 FlatMap<int, char, 5> map({{
125 {-4, 'a'},
126 {-1, 'b'},
127 {0, 'c'},
128 {49, 'd'},
129 {99, 'e'},
130 }});
131
132 char value = 'a';
133 for (auto it = map.mapped_begin(); it != map.mapped_end(); ++it) {
134 EXPECT_EQ(value, *it);
135 ++value;
136 }
137 }
138
TEST(FlatMap,BackwardsMappedValuesIterationWithDereferenceWorks)139 TEST(FlatMap, BackwardsMappedValuesIterationWithDereferenceWorks) {
140 FlatMap<int, char, 5> map({{
141 {-4, 'a'},
142 {-1, 'b'},
143 {0, 'c'},
144 {49, 'd'},
145 {99, 'e'},
146 }});
147
148 char value = 'e';
149 auto it = map.mapped_end();
150 do {
151 --it;
152 EXPECT_EQ(value, *it);
153 --value;
154 } while (it != map.mapped_begin());
155 }
156
TEST(FlatMap,EqualRange)157 TEST(FlatMap, EqualRange) {
158 auto pair = kOddMap.equal_range(1);
159 EXPECT_EQ(1, pair.first->first);
160 EXPECT_EQ(50, pair.second->first);
161
162 pair = kOddMap.equal_range(75);
163 EXPECT_EQ(100, pair.first->first);
164 EXPECT_EQ(100, pair.second->first);
165 }
166
TEST(FlatMap,Find)167 TEST(FlatMap, Find) {
168 auto it = kOddMap.find(50);
169 EXPECT_EQ(50, it->first);
170 EXPECT_EQ('d', it->second);
171
172 auto not_found = kOddMap.find(-1);
173 EXPECT_EQ(kOddMap.cend(), not_found);
174 }
175
TEST(FlatMap,UpperBoundLessThanSmallestKey)176 TEST(FlatMap, UpperBoundLessThanSmallestKey) {
177 EXPECT_EQ(-3, kOddMap.upper_bound(std::numeric_limits<int>::min())->first);
178 EXPECT_EQ(-3, kOddMap.upper_bound(-123)->first);
179 EXPECT_EQ(-3, kOddMap.upper_bound(-4)->first);
180 }
181
TEST(FlatMap,UpperBoundBetweenTheTwoSmallestKeys)182 TEST(FlatMap, UpperBoundBetweenTheTwoSmallestKeys) {
183 EXPECT_EQ(0, kOddMap.upper_bound(-3)->first);
184 EXPECT_EQ(0, kOddMap.upper_bound(-2)->first);
185 EXPECT_EQ(0, kOddMap.upper_bound(-1)->first);
186 }
187
TEST(FlatMap,UpperBoundIntermediateKeys)188 TEST(FlatMap, UpperBoundIntermediateKeys) {
189 EXPECT_EQ(1, kOddMap.upper_bound(0)->first);
190 EXPECT_EQ('c', kOddMap.upper_bound(0)->second);
191 EXPECT_EQ(50, kOddMap.upper_bound(1)->first);
192 EXPECT_EQ('d', kOddMap.upper_bound(1)->second);
193 EXPECT_EQ(50, kOddMap.upper_bound(2)->first);
194 EXPECT_EQ(50, kOddMap.upper_bound(49)->first);
195 EXPECT_EQ(100, kOddMap.upper_bound(51)->first);
196 }
197
TEST(FlatMap,UpperBoundGreaterThanLargestKey)198 TEST(FlatMap, UpperBoundGreaterThanLargestKey) {
199 EXPECT_EQ(kOddMap.end(), kOddMap.upper_bound(100));
200 EXPECT_EQ(kOddMap.end(), kOddMap.upper_bound(2384924));
201 EXPECT_EQ(kOddMap.end(),
202 kOddMap.upper_bound(std::numeric_limits<int>::max()));
203 }
204
TEST(FlatMap,LowerBoundLessThanSmallestKey)205 TEST(FlatMap, LowerBoundLessThanSmallestKey) {
206 EXPECT_EQ(-3, kOddMap.lower_bound(std::numeric_limits<int>::min())->first);
207 EXPECT_EQ(-3, kOddMap.lower_bound(-123)->first);
208 EXPECT_EQ(-3, kOddMap.lower_bound(-4)->first);
209 }
210
TEST(FlatMap,LowerBoundBetweenTwoSmallestKeys)211 TEST(FlatMap, LowerBoundBetweenTwoSmallestKeys) {
212 EXPECT_EQ(-3, kOddMap.lower_bound(-3)->first);
213 EXPECT_EQ(0, kOddMap.lower_bound(-2)->first);
214 EXPECT_EQ(0, kOddMap.lower_bound(-1)->first);
215 }
216
TEST(FlatMap,LowerBoundIntermediateKeys)217 TEST(FlatMap, LowerBoundIntermediateKeys) {
218 EXPECT_EQ(0, kOddMap.lower_bound(0)->first);
219 EXPECT_EQ('b', kOddMap.lower_bound(0)->second);
220 EXPECT_EQ(1, kOddMap.lower_bound(1)->first);
221 EXPECT_EQ('c', kOddMap.lower_bound(1)->second);
222 EXPECT_EQ(50, kOddMap.lower_bound(2)->first);
223 EXPECT_EQ(50, kOddMap.lower_bound(49)->first);
224 EXPECT_EQ(100, kOddMap.lower_bound(51)->first);
225 }
226
TEST(FlatMap,LowerBoundGreaterThanLargestKey)227 TEST(FlatMap, LowerBoundGreaterThanLargestKey) {
228 EXPECT_EQ(100, kOddMap.lower_bound(100)->first);
229 EXPECT_EQ(kOddMap.end(), kOddMap.lower_bound(2384924));
230 EXPECT_EQ(kOddMap.end(),
231 kOddMap.lower_bound(std::numeric_limits<int>::max()));
232 }
233
TEST(FlatMap,ForEachIteration)234 TEST(FlatMap, ForEachIteration) {
235 for (const auto& item : kOddMap) {
236 EXPECT_NE(item.first, 2);
237 }
238 }
239
TEST(FlatMap,MapsWithUnsortedKeys)240 TEST(FlatMap, MapsWithUnsortedKeys) {
241 constexpr FlatMap<int, const char*, 2> bad_array({{
242 {2, "hello"},
243 {1, "goodbye"},
244 }});
245
246 EXPECT_EQ(bad_array.begin()->first, 1);
247
248 constexpr FlatMap<int, const char*, 2> too_short({{
249 {1, "goodbye"},
250 }});
251 EXPECT_EQ(too_short.begin()->first, 0);
252 }
253
TEST(FlatMap,DontDereferenceEnd)254 TEST(FlatMap, DontDereferenceEnd) {
255 constexpr FlatMap<int, const char*, 2> unsorted_array({{
256 {2, "hello"},
257 {1, "goodbye"},
258 }});
259
260 EXPECT_EQ(unsorted_array.contains(3), false);
261 }
262
TEST(FlatMap,NullMappedIteratorNotEqualToValidOne)263 TEST(FlatMap, NullMappedIteratorNotEqualToValidOne) {
264 Single map({{{-4, 'a'}}});
265
266 EXPECT_NE(Single::mapped_iterator(), map.mapped_begin());
267 }
268
TEST(FlatMap,CopyConstructedMapIteratorEqualToSource)269 TEST(FlatMap, CopyConstructedMapIteratorEqualToSource) {
270 Single map({{{-4, 'a'}}});
271
272 EXPECT_EQ(Single::mapped_iterator(map.mapped_begin()), map.mapped_begin());
273 }
274
TEST(FlatMap,CopyAssignedMapIteratorEqualToSource)275 TEST(FlatMap, CopyAssignedMapIteratorEqualToSource) {
276 Single map({{{-4, 'a'}}});
277
278 Single::mapped_iterator it;
279 EXPECT_NE(it, map.mapped_begin());
280 it = map.mapped_begin();
281 EXPECT_EQ(it, map.mapped_begin());
282 }
283
TEST(FlatMap,MappedIteratorCorrectDereferenceMutation)284 TEST(FlatMap, MappedIteratorCorrectDereferenceMutation) {
285 constexpr int kKey = -4;
286 constexpr char kValue = 'a';
287 Single mutable_map({{{kKey, kValue}}});
288
289 ++*mutable_map.mapped_begin();
290 EXPECT_EQ(kValue + 1, mutable_map.at(kKey));
291 }
292
TEST(FlatMap,MappedIteratorValueCorrectMemberAccess)293 TEST(FlatMap, MappedIteratorValueCorrectMemberAccess) {
294 constexpr int kAValue{5};
295 struct A {
296 int a;
297 };
298 FlatMap<int, A, 1> map({{{-4, A{kAValue}}}});
299
300 EXPECT_EQ(kAValue, map.mapped_begin()->a);
301 }
302
TEST(FlatMap,MappedIteratorValueCorrectMemberMutation)303 TEST(FlatMap, MappedIteratorValueCorrectMemberMutation) {
304 constexpr int kAValue{5};
305 struct A {
306 int a;
307 };
308 FlatMap<int, A, 1> map({{{-4, A{kAValue}}}});
309
310 ++map.mapped_begin()->a;
311 EXPECT_EQ(kAValue + 1, map.mapped_begin()->a);
312 }
313
TEST(FlatMap,MappedIteratorPrefixIncrementCorrectReturnAndSideEffect)314 TEST(FlatMap, MappedIteratorPrefixIncrementCorrectReturnAndSideEffect) {
315 Single map({{{-4, 'a'}}});
316
317 auto it = map.mapped_begin();
318 auto it_incremented = ++it;
319 EXPECT_EQ(it, it_incremented);
320 EXPECT_NE(map.mapped_begin(), it_incremented);
321 }
322
TEST(FlatMap,MappedIteratorPostfixIncrementCorrectReturnAndSideEffect)323 TEST(FlatMap, MappedIteratorPostfixIncrementCorrectReturnAndSideEffect) {
324 Single map({{{-4, 'a'}}});
325
326 auto it = map.mapped_begin();
327 auto it_original = it++;
328 EXPECT_EQ(map.mapped_begin(), it_original);
329 EXPECT_NE(it, it_original);
330 }
331
TEST(FlatMap,MappedIteratorPrefixDecrementCorrectReturnAndSideEffect)332 TEST(FlatMap, MappedIteratorPrefixDecrementCorrectReturnAndSideEffect) {
333 Single map({{{-4, 'a'}}});
334
335 auto it = map.mapped_end();
336 auto it_decremented = --it;
337 EXPECT_EQ(it, it_decremented);
338 EXPECT_NE(map.mapped_end(), it_decremented);
339 }
340
TEST(FlatMap,MappedIteratorPostfixDecrementCorrectReturnAndSideEffect)341 TEST(FlatMap, MappedIteratorPostfixDecrementCorrectReturnAndSideEffect) {
342 Single map({{{-4, 'a'}}});
343
344 auto it = map.mapped_end();
345 auto it_original = it--;
346 EXPECT_EQ(map.mapped_end(), it_original);
347 EXPECT_NE(it, it_original);
348 }
349
TEST(FlatMap,PairsConstructionWithOneElement)350 TEST(FlatMap, PairsConstructionWithOneElement) {
351 constexpr FlatMap kMap(Pair<int, char>{1, 'a'});
352
353 ASSERT_EQ(kMap.size(), 1u);
354 ASSERT_NE(kMap.find(1), kMap.cend());
355 EXPECT_EQ(kMap.at(1), 'a');
356 }
357
TEST(FlatMap,PairsConstructionWithMoreThanOneElements)358 TEST(FlatMap, PairsConstructionWithMoreThanOneElements) {
359 using FlatMapItem = Pair<int, char>;
360 constexpr FlatMap kMap = {
361 FlatMapItem{-4, 'a'},
362 FlatMapItem{-1, 'b'},
363 FlatMapItem{0, 'c'},
364 FlatMapItem{49, 'd'},
365 FlatMapItem{99, 'e'},
366 };
367
368 ASSERT_EQ(kMap.size(), 5u);
369 for (const auto& [key, value] : kMap) {
370 EXPECT_EQ(kMap.at(key), value);
371 }
372 }
373
374 } // namespace pw::containers
375