2 * Copyright 2014 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>
21 using folly::sorted_vector_set;
22 using folly::sorted_vector_map;
27 struct less_invert : std::binary_function<T,T,bool> {
28 bool operator()(const T& a, const T& b) const {
33 template<class Container>
34 void check_invariant(Container& c) {
41 for (; it != end; ++it, ++prev) {
42 EXPECT_TRUE(c.value_comp()(*prev, *it));
46 struct OneAtATimePolicy {
47 template<class Container>
48 void increase_capacity(Container& c) {
49 if (c.size() == c.capacity()) {
50 c.reserve(c.size() + 1);
55 struct CountCopyCtor {
56 explicit CountCopyCtor() : val_(0) {}
58 explicit CountCopyCtor(int val) : val_(val), count_(0) {}
60 CountCopyCtor(const CountCopyCtor& c)
62 , count_(c.count_ + 1)
65 bool operator<(const CountCopyCtor& o) const {
75 TEST(SortedVectorTypes, SimpleSetTest) {
76 sorted_vector_set<int> s;
77 EXPECT_TRUE(s.empty());
78 for (int i = 0; i < 1000; ++i) {
79 s.insert(rand() % 100000);
81 EXPECT_FALSE(s.empty());
84 sorted_vector_set<int> s2;
85 s2.insert(s.begin(), s.end());
89 auto it = s2.lower_bound(32);
92 it = s2.lower_bound(32);
95 auto oldSz = s2.size();
97 EXPECT_TRUE(s2.size() == oldSz + 1);
100 const sorted_vector_set<int>& cs2 = s2;
101 auto range = cs2.equal_range(32);
102 auto lbound = cs2.lower_bound(32);
103 auto ubound = cs2.upper_bound(32);
104 EXPECT_TRUE(range.first == lbound);
105 EXPECT_TRUE(range.second == ubound);
106 EXPECT_TRUE(range.first != cs2.end());
107 EXPECT_TRUE(range.second != cs2.end());
108 EXPECT_TRUE(cs2.count(32) == 1);
109 EXPECT_FALSE(cs2.find(32) == cs2.end());
112 s2.insert(s2.begin() + 3, 33);
113 EXPECT_TRUE(s2.find(33) != s2.begin());
114 EXPECT_TRUE(s2.find(33) != s2.end());
120 EXPECT_FALSE(it == s2.end());
122 EXPECT_TRUE(s2.size() == oldSz);
125 sorted_vector_set<int> cpy(s);
126 check_invariant(cpy);
127 EXPECT_TRUE(cpy == s);
128 sorted_vector_set<int> cpy2(s);
130 EXPECT_TRUE(cpy2 != cpy);
131 EXPECT_TRUE(cpy2 != s);
132 check_invariant(cpy2);
133 EXPECT_TRUE(cpy2.count(100001) == 1);
135 check_invariant(cpy2);
137 EXPECT_TRUE(s != cpy);
138 EXPECT_TRUE(s != cpy2);
139 EXPECT_TRUE(cpy2 == cpy);
142 TEST(SortedVectorTypes, SimpleMapTest) {
143 sorted_vector_map<int,float> m;
144 for (int i = 0; i < 1000; ++i) {
151 EXPECT_TRUE(m.count(32) == 1);
152 EXPECT_FALSE(m.find(32) == m.end());
154 EXPECT_TRUE(m.find(32) == m.end());
157 sorted_vector_map<int,float> m2 = m;
158 EXPECT_TRUE(m2 == m);
159 EXPECT_FALSE(m2 != m);
160 auto it = m2.lower_bound(1 << 20);
161 EXPECT_TRUE(it == m2.end());
162 m2.insert(it, std::make_pair(1 << 20, 10.0f));
164 EXPECT_TRUE(m2.count(1 << 20) == 1);
166 EXPECT_TRUE(m <= m2);
168 const sorted_vector_map<int,float>& cm = m;
169 auto range = cm.equal_range(42);
170 auto lbound = cm.lower_bound(42);
171 auto ubound = cm.upper_bound(42);
172 EXPECT_TRUE(range.first == lbound);
173 EXPECT_TRUE(range.second == ubound);
174 EXPECT_FALSE(range.first == cm.end());
175 EXPECT_FALSE(range.second == cm.end());
176 m.erase(m.lower_bound(42));
179 sorted_vector_map<int,float> m3;
180 m3.insert(m2.begin(), m2.end());
182 EXPECT_TRUE(m3 == m2);
183 EXPECT_FALSE(m3 == m);
185 EXPECT_TRUE(m != m2);
186 EXPECT_TRUE(m2 == m3);
187 EXPECT_TRUE(m3 != m);
192 EXPECT_TRUE(m3 != m2);
193 EXPECT_TRUE(m3 != m);
194 EXPECT_TRUE(m == m2);
197 m.insert(m.begin() + 3, std::make_pair(1 << 15, 1.0f));
201 TEST(SortedVectorTypes, Sizes) {
202 EXPECT_EQ(sizeof(sorted_vector_set<int>),
203 sizeof(std::vector<int>));
204 EXPECT_EQ(sizeof(sorted_vector_map<int,int>),
205 sizeof(std::vector<std::pair<int,int> >));
207 typedef sorted_vector_set<int,std::less<int>,
208 std::allocator<int>,OneAtATimePolicy> SetT;
209 typedef sorted_vector_map<int,int,std::less<int>,
210 std::allocator<int>,OneAtATimePolicy> MapT;
212 EXPECT_EQ(sizeof(SetT), sizeof(std::vector<int>));
213 EXPECT_EQ(sizeof(MapT), sizeof(std::vector<std::pair<int,int> >));
216 TEST(SortedVectorTypes, InitializerLists) {
217 sorted_vector_set<int> empty_initialized_set{};
218 EXPECT_TRUE(empty_initialized_set.empty());
220 sorted_vector_set<int> singleton_initialized_set{1};
221 EXPECT_EQ(1, singleton_initialized_set.size());
222 EXPECT_EQ(1, *singleton_initialized_set.begin());
224 sorted_vector_set<int> forward_initialized_set{1, 2};
225 sorted_vector_set<int> backward_initialized_set{2, 1};
226 EXPECT_EQ(2, forward_initialized_set.size());
227 EXPECT_EQ(1, *forward_initialized_set.begin());
228 EXPECT_EQ(2, *forward_initialized_set.rbegin());
229 EXPECT_TRUE(forward_initialized_set == backward_initialized_set);
231 sorted_vector_map<int,int> empty_initialized_map{};
232 EXPECT_TRUE(empty_initialized_map.empty());
234 sorted_vector_map<int,int> singleton_initialized_map{{1,10}};
235 EXPECT_EQ(1, singleton_initialized_map.size());
236 EXPECT_EQ(10, singleton_initialized_map[1]);
238 sorted_vector_map<int,int> forward_initialized_map{{1,10}, {2,20}};
239 sorted_vector_map<int,int> backward_initialized_map{{2,20}, {1,10}};
240 EXPECT_EQ(2, forward_initialized_map.size());
241 EXPECT_EQ(10, forward_initialized_map[1]);
242 EXPECT_EQ(20, forward_initialized_map[2]);
243 EXPECT_TRUE(forward_initialized_map == backward_initialized_map);
246 TEST(SortedVectorTypes, CustomCompare) {
247 sorted_vector_set<int,less_invert<int> > s;
248 for (int i = 0; i < 200; ++i)
252 sorted_vector_map<int,float,less_invert<int> > m;
253 for (int i = 0; i < 200; ++i)
258 TEST(SortedVectorTypes, GrowthPolicy) {
259 typedef sorted_vector_set<CountCopyCtor,
260 std::less<CountCopyCtor>,
261 std::allocator<CountCopyCtor>,
266 for (int i = 0; i < 20; ++i) {
267 a.insert(CountCopyCtor(i));
270 SetT::iterator it = a.begin();
271 EXPECT_FALSE(it == a.end());
273 EXPECT_EQ(it->val_, 0);
274 // 1 copy for the initial insertion, 19 more for reallocs on the
275 // additional insertions.
276 EXPECT_EQ(it->count_, 20);
279 std::list<CountCopyCtor> v;
280 for (int i = 0; i < 20; ++i) {
281 v.push_back(CountCopyCtor(20 + i));
283 a.insert(v.begin(), v.end());
287 EXPECT_FALSE(it == a.end());
289 EXPECT_EQ(it->val_, 0);
290 // Should be only 1 more copy for inserting this above range.
291 EXPECT_EQ(it->count_, 21);
295 TEST(SortedVectorTest, EmptyTest) {
296 sorted_vector_set<int> emptySet;
297 EXPECT_TRUE(emptySet.lower_bound(10) == emptySet.end());
298 EXPECT_TRUE(emptySet.find(10) == emptySet.end());
300 sorted_vector_map<int,int> emptyMap;
301 EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
302 EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
305 TEST(SortedVectorTest, MoveTest) {
306 sorted_vector_set<std::unique_ptr<int>> s;
307 s.insert(std::unique_ptr<int>(new int(5)));
308 s.insert(s.end(), std::unique_ptr<int>(new int(10)));
309 EXPECT_EQ(s.size(), 2);
311 for (const auto& p : s) {
312 EXPECT_TRUE(*p == 5 || *p == 10);
315 sorted_vector_map<int, std::unique_ptr<int>> m;
316 m.insert(std::make_pair(5, std::unique_ptr<int>(new int(5))));
317 m.insert(m.end(), std::make_pair(10, std::unique_ptr<int>(new int(10))));
320 EXPECT_EQ(*m[10], 10);
323 TEST(SortedVectorTest, ShrinkTest) {
324 sorted_vector_set<int> s;
326 // Hopefully your resize policy doubles when capacity is full, or this will
328 while (s.capacity() == s.size()) {
332 // The standard does not actually enforce that this be true, but assume that
333 // vector::shrink_to_fit respects the caller.
334 EXPECT_EQ(s.capacity(), s.size());