| //===------ 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 |