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 "gtest/gtest.h"
20
21 namespace pw::containers {
22 namespace {
23 constexpr FlatMap<int, char, 5> kOddMap({{
24 {-3, 'a'},
25 {0, 'b'},
26 {1, 'c'},
27 {50, 'd'},
28 {100, 'e'},
29 }});
30 } // namespace
31
TEST(FlatMap,Size)32 TEST(FlatMap, Size) { EXPECT_EQ(kOddMap.size(), static_cast<uint32_t>(5)); }
33
TEST(FlatMap,EmptyFlatMapSize)34 TEST(FlatMap, EmptyFlatMapSize) {
35 constexpr FlatMap<int, char, 0> kEmpty({{}});
36 EXPECT_EQ(kEmpty.size(), static_cast<uint32_t>(0));
37 }
38
TEST(FlatMap,Empty)39 TEST(FlatMap, Empty) {
40 constexpr FlatMap<int, char, 0> kEmpty({{}});
41 EXPECT_TRUE(kEmpty.empty());
42 }
43
TEST(FlatMap,NotEmpty)44 TEST(FlatMap, NotEmpty) {
45 constexpr FlatMap<int, char, 1> kNotEmpty({{}});
46 EXPECT_FALSE(kNotEmpty.empty());
47 }
48
TEST(FlatMap,EmptyFlatMapFind)49 TEST(FlatMap, EmptyFlatMapFind) {
50 constexpr FlatMap<int, char, 0> kEmpty({{}});
51 EXPECT_EQ(kEmpty.find(0), kEmpty.end());
52 }
53
TEST(FlatMap,EmptyFlatMapLowerBound)54 TEST(FlatMap, EmptyFlatMapLowerBound) {
55 constexpr FlatMap<int, char, 0> kEmpty({{}});
56 EXPECT_EQ(kEmpty.lower_bound(0), kEmpty.end());
57 }
58
TEST(FlatMap,EmptyFlatMapUpperBound)59 TEST(FlatMap, EmptyFlatMapUpperBound) {
60 constexpr FlatMap<int, char, 0> kEmpty({{}});
61 EXPECT_EQ(kEmpty.upper_bound(0), kEmpty.end());
62 }
63
TEST(FlatMap,EmptyEqualRange)64 TEST(FlatMap, EmptyEqualRange) {
65 constexpr FlatMap<int, char, 0> kEmpty({{}});
66 EXPECT_EQ(kEmpty.equal_range(0).first, kEmpty.end());
67 EXPECT_EQ(kEmpty.equal_range(0).second, kEmpty.end());
68 }
69
TEST(FlatMap,Contains)70 TEST(FlatMap, Contains) {
71 EXPECT_TRUE(kOddMap.contains(0));
72 EXPECT_FALSE(kOddMap.contains(10));
73 }
74
TEST(FlatMap,Iterate)75 TEST(FlatMap, Iterate) {
76 char value = 'a';
77 for (const auto& item : kOddMap) {
78 EXPECT_EQ(value, item.second);
79 EXPECT_EQ(&item, kOddMap.find(item.first));
80 value += 1;
81 }
82 }
83
TEST(FlatMap,EqualRange)84 TEST(FlatMap, EqualRange) {
85 auto pair = kOddMap.equal_range(1);
86 EXPECT_EQ(1, pair.first->first);
87 EXPECT_EQ(50, pair.second->first);
88
89 pair = kOddMap.equal_range(75);
90 EXPECT_EQ(100, pair.first->first);
91 EXPECT_EQ(100, pair.second->first);
92 }
93
TEST(FlatMap,Find)94 TEST(FlatMap, Find) {
95 auto it = kOddMap.find(50);
96 EXPECT_EQ(50, it->first);
97 EXPECT_EQ('d', it->second);
98
99 auto not_found = kOddMap.find(-1);
100 EXPECT_EQ(kOddMap.cend(), not_found);
101 }
102
TEST(FlatMap,UpperBoundLessThanSmallestKey)103 TEST(FlatMap, UpperBoundLessThanSmallestKey) {
104 EXPECT_EQ(-3, kOddMap.upper_bound(std::numeric_limits<int>::min())->first);
105 EXPECT_EQ(-3, kOddMap.upper_bound(-123)->first);
106 EXPECT_EQ(-3, kOddMap.upper_bound(-4)->first);
107 }
108
TEST(FlatMap,UpperBoundBetweenTheTwoSmallestKeys)109 TEST(FlatMap, UpperBoundBetweenTheTwoSmallestKeys) {
110 EXPECT_EQ(0, kOddMap.upper_bound(-3)->first);
111 EXPECT_EQ(0, kOddMap.upper_bound(-2)->first);
112 EXPECT_EQ(0, kOddMap.upper_bound(-1)->first);
113 }
114
TEST(FlatMap,UpperBoundIntermediateKeys)115 TEST(FlatMap, UpperBoundIntermediateKeys) {
116 EXPECT_EQ(1, kOddMap.upper_bound(0)->first);
117 EXPECT_EQ('c', kOddMap.upper_bound(0)->second);
118 EXPECT_EQ(50, kOddMap.upper_bound(1)->first);
119 EXPECT_EQ('d', kOddMap.upper_bound(1)->second);
120 EXPECT_EQ(50, kOddMap.upper_bound(2)->first);
121 EXPECT_EQ(50, kOddMap.upper_bound(49)->first);
122 EXPECT_EQ(100, kOddMap.upper_bound(51)->first);
123 }
124
TEST(FlatMap,UpperBoundGreaterThanLargestKey)125 TEST(FlatMap, UpperBoundGreaterThanLargestKey) {
126 EXPECT_EQ(kOddMap.end(), kOddMap.upper_bound(100));
127 EXPECT_EQ(kOddMap.end(), kOddMap.upper_bound(2384924));
128 EXPECT_EQ(kOddMap.end(),
129 kOddMap.upper_bound(std::numeric_limits<int>::max()));
130 }
131
TEST(FlatMap,LowerBoundLessThanSmallestKey)132 TEST(FlatMap, LowerBoundLessThanSmallestKey) {
133 EXPECT_EQ(-3, kOddMap.lower_bound(std::numeric_limits<int>::min())->first);
134 EXPECT_EQ(-3, kOddMap.lower_bound(-123)->first);
135 EXPECT_EQ(-3, kOddMap.lower_bound(-4)->first);
136 }
137
TEST(FlatMap,LowerBoundBetweenTwoSmallestKeys)138 TEST(FlatMap, LowerBoundBetweenTwoSmallestKeys) {
139 EXPECT_EQ(-3, kOddMap.lower_bound(-3)->first);
140 EXPECT_EQ(0, kOddMap.lower_bound(-2)->first);
141 EXPECT_EQ(0, kOddMap.lower_bound(-1)->first);
142 }
143
TEST(FlatMap,LowerBoundIntermediateKeys)144 TEST(FlatMap, LowerBoundIntermediateKeys) {
145 EXPECT_EQ(0, kOddMap.lower_bound(0)->first);
146 EXPECT_EQ('b', kOddMap.lower_bound(0)->second);
147 EXPECT_EQ(1, kOddMap.lower_bound(1)->first);
148 EXPECT_EQ('c', kOddMap.lower_bound(1)->second);
149 EXPECT_EQ(50, kOddMap.lower_bound(2)->first);
150 EXPECT_EQ(50, kOddMap.lower_bound(49)->first);
151 EXPECT_EQ(100, kOddMap.lower_bound(51)->first);
152 }
153
TEST(FlatMap,LowerBoundGreaterThanLargestKey)154 TEST(FlatMap, LowerBoundGreaterThanLargestKey) {
155 EXPECT_EQ(100, kOddMap.lower_bound(100)->first);
156 EXPECT_EQ(kOddMap.end(), kOddMap.lower_bound(2384924));
157 EXPECT_EQ(kOddMap.end(),
158 kOddMap.lower_bound(std::numeric_limits<int>::max()));
159 }
160
TEST(FlatMap,ForEachIteration)161 TEST(FlatMap, ForEachIteration) {
162 for (const auto& item : kOddMap) {
163 EXPECT_NE(item.first, 2);
164 }
165 }
166
TEST(FlatMap,MapsWithUnsortedKeys)167 TEST(FlatMap, MapsWithUnsortedKeys) {
168 constexpr FlatMap<int, const char*, 2> bad_array({{
169 {2, "hello"},
170 {1, "goodbye"},
171 }});
172
173 EXPECT_EQ(bad_array.begin()->first, 1);
174
175 constexpr FlatMap<int, const char*, 2> too_short({{
176 {1, "goodbye"},
177 }});
178 EXPECT_EQ(too_short.begin()->first, 0);
179 }
180
181 } // namespace pw::containers
182