2 * Copyright 2016 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>
18 #include <gtest/gtest.h>
22 using folly::sorted_vector_set;
23 using folly::sorted_vector_map;
29 bool operator()(const T& a, const T& b) const {
34 template<class Container>
35 void check_invariant(Container& c) {
42 for (; it != end; ++it, ++prev) {
43 EXPECT_TRUE(c.value_comp()(*prev, *it));
47 struct OneAtATimePolicy {
48 template<class Container>
49 void increase_capacity(Container& c) {
50 if (c.size() == c.capacity()) {
51 c.reserve(c.size() + 1);
56 struct CountCopyCtor {
57 explicit CountCopyCtor() : val_(0) {}
59 explicit CountCopyCtor(int val) : val_(val), count_(0) {}
61 CountCopyCtor(const CountCopyCtor& c)
63 , count_(c.count_ + 1)
66 bool operator<(const CountCopyCtor& o) const {
76 TEST(SortedVectorTypes, SimpleSetTest) {
77 sorted_vector_set<int> s;
78 EXPECT_TRUE(s.empty());
79 for (int i = 0; i < 1000; ++i) {
80 s.insert(rand() % 100000);
82 EXPECT_FALSE(s.empty());
85 sorted_vector_set<int> s2;
86 s2.insert(s.begin(), s.end());
90 auto it = s2.lower_bound(32);
93 it = s2.lower_bound(32);
96 auto oldSz = s2.size();
98 EXPECT_TRUE(s2.size() == oldSz + 1);
101 const sorted_vector_set<int>& cs2 = s2;
102 auto range = cs2.equal_range(32);
103 auto lbound = cs2.lower_bound(32);
104 auto ubound = cs2.upper_bound(32);
105 EXPECT_TRUE(range.first == lbound);
106 EXPECT_TRUE(range.second == ubound);
107 EXPECT_TRUE(range.first != cs2.end());
108 EXPECT_TRUE(range.second != cs2.end());
109 EXPECT_TRUE(cs2.count(32) == 1);
110 EXPECT_FALSE(cs2.find(32) == cs2.end());
113 s2.insert(s2.begin() + 3, 33);
114 EXPECT_TRUE(s2.find(33) != s2.begin());
115 EXPECT_TRUE(s2.find(33) != s2.end());
121 EXPECT_FALSE(it == s2.end());
123 EXPECT_TRUE(s2.size() == oldSz);
126 sorted_vector_set<int> cpy(s);
127 check_invariant(cpy);
128 EXPECT_TRUE(cpy == s);
129 sorted_vector_set<int> cpy2(s);
131 EXPECT_TRUE(cpy2 != cpy);
132 EXPECT_TRUE(cpy2 != s);
133 check_invariant(cpy2);
134 EXPECT_TRUE(cpy2.count(100001) == 1);
136 check_invariant(cpy2);
138 EXPECT_TRUE(s != cpy);
139 EXPECT_TRUE(s != cpy2);
140 EXPECT_TRUE(cpy2 == cpy);
143 TEST(SortedVectorTypes, SimpleMapTest) {
144 sorted_vector_map<int,float> m;
145 for (int i = 0; i < 1000; ++i) {
152 EXPECT_TRUE(m.count(32) == 1);
153 EXPECT_DOUBLE_EQ(100.0, m.at(32));
154 EXPECT_FALSE(m.find(32) == m.end());
156 EXPECT_TRUE(m.find(32) == m.end());
158 EXPECT_THROW(m.at(32), std::out_of_range);
160 sorted_vector_map<int,float> m2 = m;
161 EXPECT_TRUE(m2 == m);
162 EXPECT_FALSE(m2 != m);
163 auto it = m2.lower_bound(1 << 20);
164 EXPECT_TRUE(it == m2.end());
165 m2.insert(it, std::make_pair(1 << 20, 10.0f));
167 EXPECT_TRUE(m2.count(1 << 20) == 1);
169 EXPECT_TRUE(m <= m2);
171 const sorted_vector_map<int,float>& cm = m;
172 auto range = cm.equal_range(42);
173 auto lbound = cm.lower_bound(42);
174 auto ubound = cm.upper_bound(42);
175 EXPECT_TRUE(range.first == lbound);
176 EXPECT_TRUE(range.second == ubound);
177 EXPECT_FALSE(range.first == cm.end());
178 EXPECT_FALSE(range.second == cm.end());
179 m.erase(m.lower_bound(42));
182 sorted_vector_map<int,float> m3;
183 m3.insert(m2.begin(), m2.end());
185 EXPECT_TRUE(m3 == m2);
186 EXPECT_FALSE(m3 == m);
188 EXPECT_TRUE(m != m2);
189 EXPECT_TRUE(m2 == m3);
190 EXPECT_TRUE(m3 != m);
195 EXPECT_TRUE(m3 != m2);
196 EXPECT_TRUE(m3 != m);
197 EXPECT_TRUE(m == m2);
200 m.insert(m.begin() + 3, std::make_pair(1 << 15, 1.0f));
204 TEST(SortedVectorTypes, Sizes) {
205 EXPECT_EQ(sizeof(sorted_vector_set<int>),
206 sizeof(std::vector<int>));
207 EXPECT_EQ(sizeof(sorted_vector_map<int,int>),
208 sizeof(std::vector<std::pair<int,int> >));
210 typedef sorted_vector_set<int,std::less<int>,
211 std::allocator<int>,OneAtATimePolicy> SetT;
212 typedef sorted_vector_map<int,int,std::less<int>,
213 std::allocator<std::pair<int,int>>,OneAtATimePolicy> MapT;
215 EXPECT_EQ(sizeof(SetT), sizeof(std::vector<int>));
216 EXPECT_EQ(sizeof(MapT), sizeof(std::vector<std::pair<int,int> >));
219 TEST(SortedVectorTypes, InitializerLists) {
220 sorted_vector_set<int> empty_initialized_set{};
221 EXPECT_TRUE(empty_initialized_set.empty());
223 sorted_vector_set<int> singleton_initialized_set{1};
224 EXPECT_EQ(1, singleton_initialized_set.size());
225 EXPECT_EQ(1, *singleton_initialized_set.begin());
227 sorted_vector_set<int> forward_initialized_set{1, 2};
228 sorted_vector_set<int> backward_initialized_set{2, 1};
229 EXPECT_EQ(2, forward_initialized_set.size());
230 EXPECT_EQ(1, *forward_initialized_set.begin());
231 EXPECT_EQ(2, *forward_initialized_set.rbegin());
232 EXPECT_TRUE(forward_initialized_set == backward_initialized_set);
234 sorted_vector_map<int,int> empty_initialized_map{};
235 EXPECT_TRUE(empty_initialized_map.empty());
237 sorted_vector_map<int,int> singleton_initialized_map{{1,10}};
238 EXPECT_EQ(1, singleton_initialized_map.size());
239 EXPECT_EQ(10, singleton_initialized_map[1]);
241 sorted_vector_map<int,int> forward_initialized_map{{1,10}, {2,20}};
242 sorted_vector_map<int,int> backward_initialized_map{{2,20}, {1,10}};
243 EXPECT_EQ(2, forward_initialized_map.size());
244 EXPECT_EQ(10, forward_initialized_map[1]);
245 EXPECT_EQ(20, forward_initialized_map[2]);
246 EXPECT_TRUE(forward_initialized_map == backward_initialized_map);
249 TEST(SortedVectorTypes, CustomCompare) {
250 sorted_vector_set<int,less_invert<int> > s;
251 for (int i = 0; i < 200; ++i)
255 sorted_vector_map<int,float,less_invert<int> > m;
256 for (int i = 0; i < 200; ++i)
261 TEST(SortedVectorTypes, GrowthPolicy) {
262 typedef sorted_vector_set<CountCopyCtor,
263 std::less<CountCopyCtor>,
264 std::allocator<CountCopyCtor>,
269 for (int i = 0; i < 20; ++i) {
270 a.insert(CountCopyCtor(i));
273 SetT::iterator it = a.begin();
274 EXPECT_FALSE(it == a.end());
276 EXPECT_EQ(it->val_, 0);
277 // 1 copy for the initial insertion, 19 more for reallocs on the
278 // additional insertions.
279 EXPECT_EQ(it->count_, 20);
282 std::list<CountCopyCtor> v;
283 for (int i = 0; i < 20; ++i) {
284 v.emplace_back(20 + i);
286 a.insert(v.begin(), v.end());
290 EXPECT_FALSE(it == a.end());
292 EXPECT_EQ(it->val_, 0);
293 // Should be only 1 more copy for inserting this above range.
294 EXPECT_EQ(it->count_, 21);
298 TEST(SortedVectorTest, EmptyTest) {
299 sorted_vector_set<int> emptySet;
300 EXPECT_TRUE(emptySet.lower_bound(10) == emptySet.end());
301 EXPECT_TRUE(emptySet.find(10) == emptySet.end());
303 sorted_vector_map<int,int> emptyMap;
304 EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
305 EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
306 EXPECT_THROW(emptyMap.at(10), std::out_of_range);
309 TEST(SortedVectorTest, MoveTest) {
310 sorted_vector_set<std::unique_ptr<int>> s;
311 s.insert(std::unique_ptr<int>(new int(5)));
312 s.insert(s.end(), std::unique_ptr<int>(new int(10)));
313 EXPECT_EQ(s.size(), 2);
315 for (const auto& p : s) {
316 EXPECT_TRUE(*p == 5 || *p == 10);
319 sorted_vector_map<int, std::unique_ptr<int>> m;
320 m.insert(std::make_pair(5, std::unique_ptr<int>(new int(5))));
321 m.insert(m.end(), std::make_pair(10, std::unique_ptr<int>(new int(10))));
324 EXPECT_EQ(*m[10], 10);
327 TEST(SortedVectorTest, ShrinkTest) {
328 sorted_vector_set<int> s;
330 // Hopefully your resize policy doubles when capacity is full, or this will
332 while (s.capacity() == s.size()) {
336 // The standard does not actually enforce that this be true, but assume that
337 // vector::shrink_to_fit respects the caller.
338 EXPECT_EQ(s.capacity(), s.size());