2 * Copyright 2015 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_DOUBLE_EQ(100.0, m.at(32));
153 EXPECT_FALSE(m.find(32) == m.end());
155 EXPECT_TRUE(m.find(32) == m.end());
157 EXPECT_THROW(m.at(32), std::out_of_range);
159 sorted_vector_map<int,float> m2 = m;
160 EXPECT_TRUE(m2 == m);
161 EXPECT_FALSE(m2 != m);
162 auto it = m2.lower_bound(1 << 20);
163 EXPECT_TRUE(it == m2.end());
164 m2.insert(it, std::make_pair(1 << 20, 10.0f));
166 EXPECT_TRUE(m2.count(1 << 20) == 1);
168 EXPECT_TRUE(m <= m2);
170 const sorted_vector_map<int,float>& cm = m;
171 auto range = cm.equal_range(42);
172 auto lbound = cm.lower_bound(42);
173 auto ubound = cm.upper_bound(42);
174 EXPECT_TRUE(range.first == lbound);
175 EXPECT_TRUE(range.second == ubound);
176 EXPECT_FALSE(range.first == cm.end());
177 EXPECT_FALSE(range.second == cm.end());
178 m.erase(m.lower_bound(42));
181 sorted_vector_map<int,float> m3;
182 m3.insert(m2.begin(), m2.end());
184 EXPECT_TRUE(m3 == m2);
185 EXPECT_FALSE(m3 == m);
187 EXPECT_TRUE(m != m2);
188 EXPECT_TRUE(m2 == m3);
189 EXPECT_TRUE(m3 != m);
194 EXPECT_TRUE(m3 != m2);
195 EXPECT_TRUE(m3 != m);
196 EXPECT_TRUE(m == m2);
199 m.insert(m.begin() + 3, std::make_pair(1 << 15, 1.0f));
203 TEST(SortedVectorTypes, Sizes) {
204 EXPECT_EQ(sizeof(sorted_vector_set<int>),
205 sizeof(std::vector<int>));
206 EXPECT_EQ(sizeof(sorted_vector_map<int,int>),
207 sizeof(std::vector<std::pair<int,int> >));
209 typedef sorted_vector_set<int,std::less<int>,
210 std::allocator<int>,OneAtATimePolicy> SetT;
211 typedef sorted_vector_map<int,int,std::less<int>,
212 std::allocator<std::pair<int,int>>,OneAtATimePolicy> MapT;
214 EXPECT_EQ(sizeof(SetT), sizeof(std::vector<int>));
215 EXPECT_EQ(sizeof(MapT), sizeof(std::vector<std::pair<int,int> >));
218 TEST(SortedVectorTypes, InitializerLists) {
219 sorted_vector_set<int> empty_initialized_set{};
220 EXPECT_TRUE(empty_initialized_set.empty());
222 sorted_vector_set<int> singleton_initialized_set{1};
223 EXPECT_EQ(1, singleton_initialized_set.size());
224 EXPECT_EQ(1, *singleton_initialized_set.begin());
226 sorted_vector_set<int> forward_initialized_set{1, 2};
227 sorted_vector_set<int> backward_initialized_set{2, 1};
228 EXPECT_EQ(2, forward_initialized_set.size());
229 EXPECT_EQ(1, *forward_initialized_set.begin());
230 EXPECT_EQ(2, *forward_initialized_set.rbegin());
231 EXPECT_TRUE(forward_initialized_set == backward_initialized_set);
233 sorted_vector_map<int,int> empty_initialized_map{};
234 EXPECT_TRUE(empty_initialized_map.empty());
236 sorted_vector_map<int,int> singleton_initialized_map{{1,10}};
237 EXPECT_EQ(1, singleton_initialized_map.size());
238 EXPECT_EQ(10, singleton_initialized_map[1]);
240 sorted_vector_map<int,int> forward_initialized_map{{1,10}, {2,20}};
241 sorted_vector_map<int,int> backward_initialized_map{{2,20}, {1,10}};
242 EXPECT_EQ(2, forward_initialized_map.size());
243 EXPECT_EQ(10, forward_initialized_map[1]);
244 EXPECT_EQ(20, forward_initialized_map[2]);
245 EXPECT_TRUE(forward_initialized_map == backward_initialized_map);
248 TEST(SortedVectorTypes, CustomCompare) {
249 sorted_vector_set<int,less_invert<int> > s;
250 for (int i = 0; i < 200; ++i)
254 sorted_vector_map<int,float,less_invert<int> > m;
255 for (int i = 0; i < 200; ++i)
260 TEST(SortedVectorTypes, GrowthPolicy) {
261 typedef sorted_vector_set<CountCopyCtor,
262 std::less<CountCopyCtor>,
263 std::allocator<CountCopyCtor>,
268 for (int i = 0; i < 20; ++i) {
269 a.insert(CountCopyCtor(i));
272 SetT::iterator it = a.begin();
273 EXPECT_FALSE(it == a.end());
275 EXPECT_EQ(it->val_, 0);
276 // 1 copy for the initial insertion, 19 more for reallocs on the
277 // additional insertions.
278 EXPECT_EQ(it->count_, 20);
281 std::list<CountCopyCtor> v;
282 for (int i = 0; i < 20; ++i) {
283 v.emplace_back(20 + i);
285 a.insert(v.begin(), v.end());
289 EXPECT_FALSE(it == a.end());
291 EXPECT_EQ(it->val_, 0);
292 // Should be only 1 more copy for inserting this above range.
293 EXPECT_EQ(it->count_, 21);
297 TEST(SortedVectorTest, EmptyTest) {
298 sorted_vector_set<int> emptySet;
299 EXPECT_TRUE(emptySet.lower_bound(10) == emptySet.end());
300 EXPECT_TRUE(emptySet.find(10) == emptySet.end());
302 sorted_vector_map<int,int> emptyMap;
303 EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
304 EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
305 EXPECT_THROW(emptyMap.at(10), std::out_of_range);
308 TEST(SortedVectorTest, MoveTest) {
309 sorted_vector_set<std::unique_ptr<int>> s;
310 s.insert(std::unique_ptr<int>(new int(5)));
311 s.insert(s.end(), std::unique_ptr<int>(new int(10)));
312 EXPECT_EQ(s.size(), 2);
314 for (const auto& p : s) {
315 EXPECT_TRUE(*p == 5 || *p == 10);
318 sorted_vector_map<int, std::unique_ptr<int>> m;
319 m.insert(std::make_pair(5, std::unique_ptr<int>(new int(5))));
320 m.insert(m.end(), std::make_pair(10, std::unique_ptr<int>(new int(10))));
323 EXPECT_EQ(*m[10], 10);
326 TEST(SortedVectorTest, ShrinkTest) {
327 sorted_vector_set<int> s;
329 // Hopefully your resize policy doubles when capacity is full, or this will
331 while (s.capacity() == s.size()) {
335 // The standard does not actually enforce that this be true, but assume that
336 // vector::shrink_to_fit respects the caller.
337 EXPECT_EQ(s.capacity(), s.size());