diff options
Diffstat (limited to 'unittests/ADT/SparseMultiSetTest.cpp')
| -rw-r--r-- | unittests/ADT/SparseMultiSetTest.cpp | 235 |
1 files changed, 235 insertions, 0 deletions
diff --git a/unittests/ADT/SparseMultiSetTest.cpp b/unittests/ADT/SparseMultiSetTest.cpp new file mode 100644 index 0000000..032990e --- /dev/null +++ b/unittests/ADT/SparseMultiSetTest.cpp @@ -0,0 +1,235 @@ +//===------ ADT/SparseSetTest.cpp - SparseSet unit tests - -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/SparseMultiSet.h" +#include "gtest/gtest.h" + +using namespace llvm; + +namespace { + +typedef SparseMultiSet<unsigned> USet; + +// Empty set tests. +TEST(SparseMultiSetTest, EmptySet) { + USet Set; + EXPECT_TRUE(Set.empty()); + EXPECT_EQ(0u, Set.size()); + + Set.setUniverse(10); + + // Lookups on empty set. + EXPECT_TRUE(Set.find(0) == Set.end()); + EXPECT_TRUE(Set.find(9) == Set.end()); + + // Same thing on a const reference. + const USet &CSet = Set; + EXPECT_TRUE(CSet.empty()); + EXPECT_EQ(0u, CSet.size()); + EXPECT_TRUE(CSet.find(0) == CSet.end()); + USet::const_iterator I = CSet.find(5); + EXPECT_TRUE(I == CSet.end()); +} + +// Single entry set tests. +TEST(SparseMultiSetTest, SingleEntrySet) { + USet Set; + Set.setUniverse(10); + USet::iterator I = Set.insert(5); + EXPECT_TRUE(I != Set.end()); + EXPECT_TRUE(*I == 5); + + EXPECT_FALSE(Set.empty()); + EXPECT_EQ(1u, Set.size()); + + EXPECT_TRUE(Set.find(0) == Set.end()); + EXPECT_TRUE(Set.find(9) == Set.end()); + + EXPECT_FALSE(Set.contains(0)); + EXPECT_TRUE(Set.contains(5)); + + // Extra insert. + I = Set.insert(5); + EXPECT_TRUE(I != Set.end()); + EXPECT_TRUE(I == ++Set.find(5)); + I--; + EXPECT_TRUE(I == Set.find(5)); + + // Erase non-existent element. + I = Set.find(1); + EXPECT_TRUE(I == Set.end()); + EXPECT_EQ(2u, Set.size()); + EXPECT_EQ(5u, *Set.find(5)); + + // Erase iterator. + I = Set.find(5); + EXPECT_TRUE(I != Set.end()); + I = Set.erase(I); + EXPECT_TRUE(I != Set.end()); + I = Set.erase(I); + EXPECT_TRUE(I == Set.end()); + EXPECT_TRUE(Set.empty()); +} + +// Multiple entry set tests. +TEST(SparseMultiSetTest, MultipleEntrySet) { + USet Set; + Set.setUniverse(10); + + Set.insert(5); + Set.insert(5); + Set.insert(5); + Set.insert(3); + Set.insert(2); + Set.insert(1); + Set.insert(4); + EXPECT_EQ(7u, Set.size()); + + // Erase last element by key. + EXPECT_TRUE(Set.erase(Set.find(4)) == Set.end()); + EXPECT_EQ(6u, Set.size()); + EXPECT_FALSE(Set.contains(4)); + EXPECT_TRUE(Set.find(4) == Set.end()); + + // Erase first element by key. + EXPECT_EQ(3u, Set.count(5)); + EXPECT_TRUE(Set.find(5) != Set.end()); + EXPECT_TRUE(Set.erase(Set.find(5)) != Set.end()); + EXPECT_EQ(5u, Set.size()); + EXPECT_EQ(2u, Set.count(5)); + + Set.insert(6); + Set.insert(7); + EXPECT_EQ(7u, Set.size()); + + // Erase tail by iterator. + EXPECT_TRUE(Set.getTail(6) == Set.getHead(6)); + USet::iterator I = Set.erase(Set.find(6)); + EXPECT_TRUE(I == Set.end()); + EXPECT_EQ(6u, Set.size()); + + // Erase tails by iterator. + EXPECT_EQ(2u, Set.count(5)); + I = Set.getTail(5); + I = Set.erase(I); + EXPECT_TRUE(I == Set.end()); + --I; + EXPECT_EQ(1u, Set.count(5)); + EXPECT_EQ(5u, *I); + I = Set.erase(I); + EXPECT_TRUE(I == Set.end()); + EXPECT_EQ(0u, Set.count(5)); + + Set.insert(8); + Set.insert(8); + Set.insert(8); + Set.insert(8); + Set.insert(8); + + // Erase all the 8s + EXPECT_EQ(5, std::distance(Set.getHead(8), Set.end())); + Set.eraseAll(8); + EXPECT_EQ(0, std::distance(Set.getHead(8), Set.end())); + + // Clear and resize the universe. + Set.clear(); + EXPECT_EQ(0u, Set.size()); + EXPECT_FALSE(Set.contains(3)); + Set.setUniverse(1000); + + // Add more than 256 elements. + for (unsigned i = 100; i != 800; ++i) + Set.insert(i); + + for (unsigned i = 0; i != 10; ++i) + Set.eraseAll(i); + + for (unsigned i = 100; i != 800; ++i) + EXPECT_EQ(1u, Set.count(i)); + + EXPECT_FALSE(Set.contains(99)); + EXPECT_FALSE(Set.contains(800)); + EXPECT_EQ(700u, Set.size()); +} + +// Test out iterators +TEST(SparseMultiSetTest, Iterators) { + USet Set; + Set.setUniverse(100); + + Set.insert(0); + Set.insert(1); + Set.insert(2); + Set.insert(0); + Set.insert(1); + Set.insert(0); + + USet::RangePair RangePair = Set.equal_range(0); + USet::iterator B = RangePair.first; + USet::iterator E = RangePair.second; + + // Move the iterators around, going to end and coming back. + EXPECT_EQ(3, std::distance(B, E)); + EXPECT_EQ(B, --(--(--E))); + EXPECT_EQ(++(++(++E)), Set.end()); + EXPECT_EQ(B, --(--(--E))); + EXPECT_EQ(++(++(++E)), Set.end()); + + // Insert into the tail, and move around again + Set.insert(0); + EXPECT_EQ(B, --(--(--(--E)))); + EXPECT_EQ(++(++(++(++E))), Set.end()); + EXPECT_EQ(B, --(--(--(--E)))); + EXPECT_EQ(++(++(++(++E))), Set.end()); + + // Erase a tail, and move around again + USet::iterator Erased = Set.erase(Set.getTail(0)); + EXPECT_EQ(Erased, E); + EXPECT_EQ(B, --(--(--E))); + + USet Set2; + Set2.setUniverse(11); + Set2.insert(3); + EXPECT_TRUE(!Set2.contains(0)); + EXPECT_TRUE(!Set.contains(3)); + + EXPECT_EQ(Set2.getHead(3), Set2.getTail(3)); + EXPECT_EQ(Set2.getHead(0), Set2.getTail(0)); + B = Set2.find(3); + EXPECT_EQ(Set2.find(3), --(++B)); +} + +struct Alt { + unsigned Value; + explicit Alt(unsigned x) : Value(x) {} + unsigned getSparseSetIndex() const { return Value - 1000; } +}; + +TEST(SparseMultiSetTest, AltStructSet) { + typedef SparseMultiSet<Alt> ASet; + ASet Set; + Set.setUniverse(10); + Set.insert(Alt(1005)); + + ASet::iterator I = Set.find(5); + ASSERT_TRUE(I != Set.end()); + EXPECT_EQ(1005u, I->Value); + + Set.insert(Alt(1006)); + Set.insert(Alt(1006)); + I = Set.erase(Set.find(6)); + ASSERT_TRUE(I != Set.end()); + EXPECT_EQ(1006u, I->Value); + I = Set.erase(Set.find(6)); + ASSERT_TRUE(I == Set.end()); + + EXPECT_TRUE(Set.contains(5)); + EXPECT_FALSE(Set.contains(6)); +} +} // namespace |