2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <folly/sorted_vector_types.h>
22 #include <folly/portability/GTest.h>
24 using folly::sorted_vector_set;
25 using folly::sorted_vector_map;
31 bool operator()(const T& a, const T& b) const {
36 template<class Container>
37 void check_invariant(Container& c) {
44 for (; it != end; ++it, ++prev) {
45 EXPECT_TRUE(c.value_comp()(*prev, *it));
49 struct OneAtATimePolicy {
50 template<class Container>
51 void increase_capacity(Container& c) {
52 if (c.size() == c.capacity()) {
53 c.reserve(c.size() + 1);
58 struct CountCopyCtor {
59 explicit CountCopyCtor() : val_(0) {}
61 explicit CountCopyCtor(int val) : val_(val), count_(0) {}
63 CountCopyCtor(const CountCopyCtor& c)
65 , count_(c.count_ + 1)
68 bool operator<(const CountCopyCtor& o) const {
78 TEST(SortedVectorTypes, SimpleSetTest) {
79 sorted_vector_set<int> s;
80 EXPECT_TRUE(s.empty());
81 for (int i = 0; i < 1000; ++i) {
82 s.insert(rand() % 100000);
84 EXPECT_FALSE(s.empty());
87 sorted_vector_set<int> s2;
88 s2.insert(s.begin(), s.end());
92 auto it = s2.lower_bound(32);
95 it = s2.lower_bound(32);
98 auto oldSz = s2.size();
100 EXPECT_TRUE(s2.size() == oldSz + 1);
103 const sorted_vector_set<int>& cs2 = s2;
104 auto range = cs2.equal_range(32);
105 auto lbound = cs2.lower_bound(32);
106 auto ubound = cs2.upper_bound(32);
107 EXPECT_TRUE(range.first == lbound);
108 EXPECT_TRUE(range.second == ubound);
109 EXPECT_TRUE(range.first != cs2.end());
110 EXPECT_TRUE(range.second != cs2.end());
111 EXPECT_TRUE(cs2.count(32) == 1);
112 EXPECT_FALSE(cs2.find(32) == cs2.end());
115 s2.insert(s2.begin() + 3, 33);
116 EXPECT_TRUE(s2.find(33) != s2.begin());
117 EXPECT_TRUE(s2.find(33) != s2.end());
123 EXPECT_FALSE(it == s2.end());
125 EXPECT_TRUE(s2.size() == oldSz);
128 sorted_vector_set<int> cpy(s);
129 check_invariant(cpy);
130 EXPECT_TRUE(cpy == s);
131 sorted_vector_set<int> cpy2(s);
133 EXPECT_TRUE(cpy2 != cpy);
134 EXPECT_TRUE(cpy2 != s);
135 check_invariant(cpy2);
136 EXPECT_TRUE(cpy2.count(100001) == 1);
138 check_invariant(cpy2);
140 EXPECT_TRUE(s != cpy);
141 EXPECT_TRUE(s != cpy2);
142 EXPECT_TRUE(cpy2 == cpy);
145 TEST(SortedVectorTypes, SimpleMapTest) {
146 sorted_vector_map<int,float> m;
147 for (int i = 0; i < 1000; ++i) {
154 EXPECT_TRUE(m.count(32) == 1);
155 EXPECT_DOUBLE_EQ(100.0, m.at(32));
156 EXPECT_FALSE(m.find(32) == m.end());
158 EXPECT_TRUE(m.find(32) == m.end());
160 EXPECT_THROW(m.at(32), std::out_of_range);
162 sorted_vector_map<int,float> m2 = m;
163 EXPECT_TRUE(m2 == m);
164 EXPECT_FALSE(m2 != m);
165 auto it = m2.lower_bound(1 << 20);
166 EXPECT_TRUE(it == m2.end());
167 m2.insert(it, std::make_pair(1 << 20, 10.0f));
169 EXPECT_TRUE(m2.count(1 << 20) == 1);
171 EXPECT_TRUE(m <= m2);
173 const sorted_vector_map<int,float>& cm = m;
174 auto range = cm.equal_range(42);
175 auto lbound = cm.lower_bound(42);
176 auto ubound = cm.upper_bound(42);
177 EXPECT_TRUE(range.first == lbound);
178 EXPECT_TRUE(range.second == ubound);
179 EXPECT_FALSE(range.first == cm.end());
180 EXPECT_FALSE(range.second == cm.end());
181 m.erase(m.lower_bound(42));
184 sorted_vector_map<int,float> m3;
185 m3.insert(m2.begin(), m2.end());
187 EXPECT_TRUE(m3 == m2);
188 EXPECT_FALSE(m3 == m);
190 EXPECT_TRUE(m != m2);
191 EXPECT_TRUE(m2 == m3);
192 EXPECT_TRUE(m3 != m);
197 EXPECT_TRUE(m3 != m2);
198 EXPECT_TRUE(m3 != m);
199 EXPECT_TRUE(m == m2);
202 m.insert(m.begin() + 3, std::make_pair(1 << 15, 1.0f));
206 TEST(SortedVectorTypes, Sizes) {
207 EXPECT_EQ(sizeof(sorted_vector_set<int>),
208 sizeof(std::vector<int>));
209 EXPECT_EQ(sizeof(sorted_vector_map<int,int>),
210 sizeof(std::vector<std::pair<int,int> >));
212 typedef sorted_vector_set<int,std::less<int>,
213 std::allocator<int>,OneAtATimePolicy> SetT;
214 typedef sorted_vector_map<int,int,std::less<int>,
215 std::allocator<std::pair<int,int>>,OneAtATimePolicy> MapT;
217 EXPECT_EQ(sizeof(SetT), sizeof(std::vector<int>));
218 EXPECT_EQ(sizeof(MapT), sizeof(std::vector<std::pair<int,int> >));
221 TEST(SortedVectorTypes, InitializerLists) {
222 sorted_vector_set<int> empty_initialized_set{};
223 EXPECT_TRUE(empty_initialized_set.empty());
225 sorted_vector_set<int> singleton_initialized_set{1};
226 EXPECT_EQ(1, singleton_initialized_set.size());
227 EXPECT_EQ(1, *singleton_initialized_set.begin());
229 sorted_vector_set<int> forward_initialized_set{1, 2};
230 sorted_vector_set<int> backward_initialized_set{2, 1};
231 EXPECT_EQ(2, forward_initialized_set.size());
232 EXPECT_EQ(1, *forward_initialized_set.begin());
233 EXPECT_EQ(2, *forward_initialized_set.rbegin());
234 EXPECT_TRUE(forward_initialized_set == backward_initialized_set);
236 sorted_vector_map<int,int> empty_initialized_map{};
237 EXPECT_TRUE(empty_initialized_map.empty());
239 sorted_vector_map<int,int> singleton_initialized_map{{1,10}};
240 EXPECT_EQ(1, singleton_initialized_map.size());
241 EXPECT_EQ(10, singleton_initialized_map[1]);
243 sorted_vector_map<int,int> forward_initialized_map{{1,10}, {2,20}};
244 sorted_vector_map<int,int> backward_initialized_map{{2,20}, {1,10}};
245 EXPECT_EQ(2, forward_initialized_map.size());
246 EXPECT_EQ(10, forward_initialized_map[1]);
247 EXPECT_EQ(20, forward_initialized_map[2]);
248 EXPECT_TRUE(forward_initialized_map == backward_initialized_map);
251 TEST(SortedVectorTypes, CustomCompare) {
252 sorted_vector_set<int,less_invert<int> > s;
253 for (int i = 0; i < 200; ++i)
257 sorted_vector_map<int,float,less_invert<int> > m;
258 for (int i = 0; i < 200; ++i)
263 TEST(SortedVectorTypes, GrowthPolicy) {
264 typedef sorted_vector_set<CountCopyCtor,
265 std::less<CountCopyCtor>,
266 std::allocator<CountCopyCtor>,
271 for (int i = 0; i < 20; ++i) {
272 a.insert(CountCopyCtor(i));
275 SetT::iterator it = a.begin();
276 EXPECT_FALSE(it == a.end());
278 EXPECT_EQ(it->val_, 0);
279 // 1 copy for the initial insertion, 19 more for reallocs on the
280 // additional insertions.
281 EXPECT_EQ(it->count_, 20);
284 std::list<CountCopyCtor> v;
285 for (int i = 0; i < 20; ++i) {
286 v.emplace_back(20 + i);
288 a.insert(v.begin(), v.end());
292 EXPECT_FALSE(it == a.end());
294 EXPECT_EQ(it->val_, 0);
295 // Should be only 1 more copy for inserting this above range.
296 EXPECT_EQ(it->count_, 21);
300 TEST(SortedVectorTest, EmptyTest) {
301 sorted_vector_set<int> emptySet;
302 EXPECT_TRUE(emptySet.lower_bound(10) == emptySet.end());
303 EXPECT_TRUE(emptySet.find(10) == emptySet.end());
305 sorted_vector_map<int,int> emptyMap;
306 EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
307 EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
308 EXPECT_THROW(emptyMap.at(10), std::out_of_range);
311 TEST(SortedVectorTest, MoveTest) {
312 sorted_vector_set<std::unique_ptr<int>> s;
313 s.insert(std::unique_ptr<int>(new int(5)));
314 s.insert(s.end(), std::unique_ptr<int>(new int(10)));
315 EXPECT_EQ(s.size(), 2);
317 for (const auto& p : s) {
318 EXPECT_TRUE(*p == 5 || *p == 10);
321 sorted_vector_map<int, std::unique_ptr<int>> m;
322 m.insert(std::make_pair(5, std::unique_ptr<int>(new int(5))));
323 m.insert(m.end(), std::make_pair(10, std::unique_ptr<int>(new int(10))));
326 EXPECT_EQ(*m[10], 10);
329 TEST(SortedVectorTest, ShrinkTest) {
330 sorted_vector_set<int> s;
332 // Hopefully your resize policy doubles when capacity is full, or this will
334 while (s.capacity() == s.size()) {
338 // The standard does not actually enforce that this be true, but assume that
339 // vector::shrink_to_fit respects the caller.
340 EXPECT_EQ(s.capacity(), s.size());
343 TEST(SortedVectorTypes, EraseTest) {
344 sorted_vector_set<int> s1;
346 sorted_vector_set<int> s2(s1);
347 EXPECT_EQ(0, s1.erase(0));