}
};
-template<class Container>
+template <class Container>
void check_invariant(Container& c) {
auto it = c.begin();
auto end = c.end();
- if (it == end)
+ if (it == end) {
return;
+ }
auto prev = it;
++it;
for (; it != end; ++it, ++prev) {
}
struct OneAtATimePolicy {
- template<class Container>
+ template <class Container>
void increase_capacity(Container& c) {
if (c.size() == c.capacity()) {
c.reserve(c.size() + 1);
int count_;
};
-}
+struct Opaque {
+ int value;
+ friend bool operator==(Opaque a, Opaque b) {
+ return a.value == b.value;
+ }
+ friend bool operator<(Opaque a, Opaque b) {
+ return a.value < b.value;
+ }
+ struct Compare : std::less<int>, std::less<Opaque> {
+ using is_transparent = void;
+ using std::less<int>::operator();
+ using std::less<Opaque>::operator();
+ bool operator()(int a, Opaque b) const {
+ return std::less<int>::operator()(a, b.value);
+ }
+ bool operator()(Opaque a, int b) const {
+ return std::less<int>::operator()(a.value, b);
+ }
+ };
+};
+
+} // namespace
TEST(SortedVectorTypes, SimpleSetTest) {
sorted_vector_set<int> s;
EXPECT_TRUE(cpy2 == cpy);
}
+TEST(SortedVectorTypes, TransparentSetTest) {
+ sorted_vector_set<Opaque, Opaque::Compare> s;
+ EXPECT_TRUE(s.empty());
+ for (int i = 0; i < 1000; ++i) {
+ s.insert(Opaque{rand() % 100000});
+ }
+ EXPECT_FALSE(s.empty());
+ check_invariant(s);
+
+ sorted_vector_set<Opaque, Opaque::Compare> s2;
+ s2.insert(s.begin(), s.end());
+ check_invariant(s2);
+ EXPECT_TRUE(s == s2);
+
+ auto it = s2.lower_bound(32);
+ if (it->value == 32) {
+ s2.erase(it);
+ it = s2.lower_bound(32);
+ }
+ check_invariant(s2);
+ auto oldSz = s2.size();
+ s2.insert(it, Opaque{32});
+ EXPECT_TRUE(s2.size() == oldSz + 1);
+ check_invariant(s2);
+
+ const sorted_vector_set<Opaque, Opaque::Compare>& cs2 = s2;
+ auto range = cs2.equal_range(32);
+ auto lbound = cs2.lower_bound(32);
+ auto ubound = cs2.upper_bound(32);
+ EXPECT_TRUE(range.first == lbound);
+ EXPECT_TRUE(range.second == ubound);
+ EXPECT_TRUE(range.first != cs2.end());
+ EXPECT_TRUE(range.second != cs2.end());
+ EXPECT_TRUE(cs2.count(32) == 1);
+ EXPECT_FALSE(cs2.find(32) == cs2.end());
+
+ // Bad insert hint.
+ s2.insert(s2.begin() + 3, Opaque{33});
+ EXPECT_TRUE(s2.find(33) != s2.begin());
+ EXPECT_TRUE(s2.find(33) != s2.end());
+ check_invariant(s2);
+ s2.erase(Opaque{33});
+ check_invariant(s2);
+
+ it = s2.find(32);
+ EXPECT_FALSE(it == s2.end());
+ s2.erase(it);
+ EXPECT_TRUE(s2.size() == oldSz);
+ check_invariant(s2);
+
+ sorted_vector_set<Opaque, Opaque::Compare> cpy(s);
+ check_invariant(cpy);
+ EXPECT_TRUE(cpy == s);
+ sorted_vector_set<Opaque, Opaque::Compare> cpy2(s);
+ cpy2.insert(Opaque{100001});
+ EXPECT_TRUE(cpy2 != cpy);
+ EXPECT_TRUE(cpy2 != s);
+ check_invariant(cpy2);
+ EXPECT_TRUE(cpy2.count(100001) == 1);
+ s.swap(cpy2);
+ check_invariant(cpy2);
+ check_invariant(s);
+ EXPECT_TRUE(s != cpy);
+ EXPECT_TRUE(s != cpy2);
+ EXPECT_TRUE(cpy2 == cpy);
+}
+
+TEST(SortedVectorTypes, BadHints) {
+ for (int toInsert = -1; toInsert <= 7; ++toInsert) {
+ for (int hintPos = 0; hintPos <= 4; ++hintPos) {
+ sorted_vector_set<int> s;
+ for (int i = 0; i <= 3; ++i) {
+ s.insert(i * 2);
+ }
+ s.insert(s.begin() + hintPos, toInsert);
+ size_t expectedSize = (toInsert % 2) == 0 ? 4 : 5;
+ EXPECT_EQ(s.size(), expectedSize);
+ check_invariant(s);
+ }
+ }
+}
+
TEST(SortedVectorTypes, SimpleMapTest) {
sorted_vector_map<int,float> m;
for (int i = 0; i < 1000; ++i) {
check_invariant(m);
}
+TEST(SortedVectorTypes, TransparentMapTest) {
+ sorted_vector_map<Opaque, float, Opaque::Compare> m;
+ for (int i = 0; i < 1000; ++i) {
+ m[Opaque{i}] = i / 1000.0;
+ }
+ check_invariant(m);
+
+ m[Opaque{32}] = 100.0;
+ check_invariant(m);
+ EXPECT_TRUE(m.count(32) == 1);
+ EXPECT_DOUBLE_EQ(100.0, m.at(Opaque{32}));
+ EXPECT_FALSE(m.find(32) == m.end());
+ m.erase(Opaque{32});
+ EXPECT_TRUE(m.find(32) == m.end());
+ check_invariant(m);
+ EXPECT_THROW(m.at(Opaque{32}), std::out_of_range);
+
+ sorted_vector_map<Opaque, float, Opaque::Compare> m2 = m;
+ EXPECT_TRUE(m2 == m);
+ EXPECT_FALSE(m2 != m);
+ auto it = m2.lower_bound(1 << 20);
+ EXPECT_TRUE(it == m2.end());
+ m2.insert(it, std::make_pair(Opaque{1 << 20}, 10.0f));
+ check_invariant(m2);
+ EXPECT_TRUE(m2.count(1 << 20) == 1);
+ EXPECT_TRUE(m < m2);
+ EXPECT_TRUE(m <= m2);
+
+ const sorted_vector_map<Opaque, float, Opaque::Compare>& cm = m;
+ auto range = cm.equal_range(42);
+ auto lbound = cm.lower_bound(42);
+ auto ubound = cm.upper_bound(42);
+ EXPECT_TRUE(range.first == lbound);
+ EXPECT_TRUE(range.second == ubound);
+ EXPECT_FALSE(range.first == cm.end());
+ EXPECT_FALSE(range.second == cm.end());
+ m.erase(m.lower_bound(42));
+ check_invariant(m);
+
+ sorted_vector_map<Opaque, float, Opaque::Compare> m3;
+ m3.insert(m2.begin(), m2.end());
+ check_invariant(m3);
+ EXPECT_TRUE(m3 == m2);
+ EXPECT_FALSE(m3 == m);
+
+ EXPECT_TRUE(m != m2);
+ EXPECT_TRUE(m2 == m3);
+ EXPECT_TRUE(m3 != m);
+ m.swap(m3);
+ check_invariant(m);
+ check_invariant(m2);
+ check_invariant(m3);
+ EXPECT_TRUE(m3 != m2);
+ EXPECT_TRUE(m3 != m);
+ EXPECT_TRUE(m == m2);
+
+ // Bad insert hint.
+ m.insert(m.begin() + 3, std::make_pair(Opaque{1 << 15}, 1.0f));
+ check_invariant(m);
+}
+
TEST(SortedVectorTypes, Sizes) {
EXPECT_EQ(sizeof(sorted_vector_set<int>),
sizeof(std::vector<int>));
TEST(SortedVectorTypes, CustomCompare) {
sorted_vector_set<int,less_invert<int> > s;
- for (int i = 0; i < 200; ++i)
+ for (int i = 0; i < 200; ++i) {
s.insert(i);
+ }
check_invariant(s);
sorted_vector_map<int,float,less_invert<int> > m;
- for (int i = 0; i < 200; ++i)
+ for (int i = 0; i < 200; ++i) {
m[i] = 12.0;
+ }
check_invariant(m);
}
TEST(SortedVectorTest, MoveTest) {
sorted_vector_set<std::unique_ptr<int>> s;
- s.insert(std::unique_ptr<int>(new int(5)));
- s.insert(s.end(), std::unique_ptr<int>(new int(10)));
+ s.insert(std::make_unique<int>(5));
+ s.insert(s.end(), std::make_unique<int>(10));
EXPECT_EQ(s.size(), 2);
for (const auto& p : s) {
}
sorted_vector_map<int, std::unique_ptr<int>> m;
- m.insert(std::make_pair(5, std::unique_ptr<int>(new int(5))));
- m.insert(m.end(), std::make_pair(10, std::unique_ptr<int>(new int(10))));
+ m.insert(std::make_pair(5, std::make_unique<int>(5)));
+ m.insert(m.end(), std::make_pair(10, std::make_unique<int>(10)));
EXPECT_EQ(*m[5], 5);
EXPECT_EQ(*m[10], 10);
testing::ElementsAreArray({1, 2, 4, 5, 6, 7, 8, 10}));
}
+TEST(SortedVectorTypes, TestSetBulkInsertionMiddleValuesEqualDuplication) {
+ auto s = makeVectorOfWrappers<CountCopyCtor, int>({4, 6, 8});
+
+ sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+ check_invariant(vset);
+
+ s = makeVectorOfWrappers<CountCopyCtor, int>({8, 10, 12});
+
+ vset.insert(s.begin(), s.end());
+ check_invariant(vset);
+ EXPECT_EQ(vset.rbegin()->count_, 1);
+
+ EXPECT_THAT(
+ extractValues(vset),
+ testing::ElementsAreArray({4, 6, 8, 10, 12}));
+}
+
+TEST(SortedVectorTypes, TestSetBulkInsertionSortMergeDups) {
+ auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
+
+ sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+ check_invariant(vset);
+
+ // Add an unsorted range that will have to be merged in.
+ s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
+
+ vset.insert(s.begin(), s.end());
+ check_invariant(vset);
+ EXPECT_EQ(vset.rbegin()->count_, 1);
+ EXPECT_THAT(
+ extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
+}
+
+TEST(SortedVectorTypes, TestSetInsertionDupsOneByOne) {
+ auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
+
+ sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
+ check_invariant(vset);
+
+ // Add an unsorted range that will have to be merged in.
+ s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
+
+ for (const auto& elem : s) {
+ vset.insert(elem);
+ }
+ check_invariant(vset);
+ EXPECT_EQ(vset.rbegin()->count_, 3);
+ EXPECT_THAT(
+ extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
+}
+
TEST(SortedVectorTypes, TestSetBulkInsertionSortNoMerge) {
auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
vmap.insert(
std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
}
+
+TEST(SortedVectorTypes, TestSetCreationFromVector) {
+ std::vector<int> vec = {3, 1, -1, 5, 0};
+ sorted_vector_set<int> vset(std::move(vec));
+ check_invariant(vset);
+ EXPECT_THAT(vset, testing::ElementsAreArray({-1, 0, 1, 3, 5}));
+}
+
+TEST(SortedVectorTypes, TestMapCreationFromVector) {
+ std::vector<std::pair<int, int>> vec = {
+ {3, 1}, {1, 5}, {-1, 2}, {5, 3}, {0, 3}};
+ sorted_vector_map<int, int> vmap(std::move(vec));
+ check_invariant(vmap);
+ auto contents = std::vector<std::pair<int, int>>(vmap.begin(), vmap.end());
+ auto expected_contents = std::vector<std::pair<int, int>>({
+ {-1, 2}, {0, 3}, {1, 5}, {3, 1}, {5, 3},
+ });
+ EXPECT_EQ(contents, expected_contents);
+}
projects / folly.git / blobdiff