1afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman//===------ ADT/SparseSetTest.cpp - SparseSet unit tests - -----*- C++ -*-===// 2afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman// 3afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman// The LLVM Compiler Infrastructure 4afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman// 5afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman// This file is distributed under the University of Illinois Open Source 6afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman// License. See LICENSE.TXT for details. 7afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman// 8afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman//===----------------------------------------------------------------------===// 9afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 10afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman#include "llvm/ADT/SparseMultiSet.h" 11afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman#include "gtest/gtest.h" 12afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 13afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilsemanusing namespace llvm; 14afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 15afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilsemannamespace { 16afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 17afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilsemantypedef SparseMultiSet<unsigned> USet; 18afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 19afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman// Empty set tests. 20afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael IlsemanTEST(SparseMultiSetTest, EmptySet) { 21afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman USet Set; 22afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.empty()); 23afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(0u, Set.size()); 24afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 25afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.setUniverse(10); 26afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 27afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Lookups on empty set. 28afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.find(0) == Set.end()); 29afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.find(9) == Set.end()); 30afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 31afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Same thing on a const reference. 32afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman const USet &CSet = Set; 33afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(CSet.empty()); 34afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(0u, CSet.size()); 35afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(CSet.find(0) == CSet.end()); 36afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman USet::const_iterator I = CSet.find(5); 37afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(I == CSet.end()); 38afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman} 39afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 40afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman// Single entry set tests. 41afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael IlsemanTEST(SparseMultiSetTest, SingleEntrySet) { 42afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman USet Set; 43afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.setUniverse(10); 44afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman USet::iterator I = Set.insert(5); 45afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(I != Set.end()); 46afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(*I == 5); 47afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 48afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_FALSE(Set.empty()); 49afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(1u, Set.size()); 50afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 51afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.find(0) == Set.end()); 52afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.find(9) == Set.end()); 53afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 54afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_FALSE(Set.contains(0)); 55afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.contains(5)); 56afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 57afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Extra insert. 58afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman I = Set.insert(5); 59afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(I != Set.end()); 60afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(I == ++Set.find(5)); 61afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman I--; 62afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(I == Set.find(5)); 63afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 64afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Erase non-existent element. 65afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman I = Set.find(1); 66afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(I == Set.end()); 67afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(2u, Set.size()); 68afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(5u, *Set.find(5)); 69afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 70afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Erase iterator. 71afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman I = Set.find(5); 72afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(I != Set.end()); 73afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman I = Set.erase(I); 74afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(I != Set.end()); 75afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman I = Set.erase(I); 76afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(I == Set.end()); 77afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.empty()); 78afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman} 79afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 80afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman// Multiple entry set tests. 81afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael IlsemanTEST(SparseMultiSetTest, MultipleEntrySet) { 82afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman USet Set; 83afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.setUniverse(10); 84afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 85afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(5); 86afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(5); 87afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(5); 88afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(3); 89afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(2); 90afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(1); 91afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(4); 92afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(7u, Set.size()); 93afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 94afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Erase last element by key. 95afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.erase(Set.find(4)) == Set.end()); 96afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(6u, Set.size()); 97afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_FALSE(Set.contains(4)); 98afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.find(4) == Set.end()); 99afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 100afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Erase first element by key. 101afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(3u, Set.count(5)); 102afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.find(5) != Set.end()); 103afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.erase(Set.find(5)) != Set.end()); 104afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(5u, Set.size()); 105afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(2u, Set.count(5)); 106afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 107afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(6); 108afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(7); 109afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(7u, Set.size()); 110afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 111afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Erase tail by iterator. 112afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.getTail(6) == Set.getHead(6)); 113afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman USet::iterator I = Set.erase(Set.find(6)); 114afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(I == Set.end()); 115afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(6u, Set.size()); 116afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 117afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Erase tails by iterator. 118afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(2u, Set.count(5)); 119afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman I = Set.getTail(5); 120afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman I = Set.erase(I); 121afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(I == Set.end()); 122afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman --I; 123afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(1u, Set.count(5)); 124afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(5u, *I); 125afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman I = Set.erase(I); 126afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(I == Set.end()); 127afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(0u, Set.count(5)); 128afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 129afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(8); 130afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(8); 131afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(8); 132afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(8); 133afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(8); 134afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 135afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Erase all the 8s 13619f24454b516042b618298522e79bf9e6fa5ccbdNAKAMURA Takumi EXPECT_EQ(5, std::distance(Set.getHead(8), Set.end())); 137afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.eraseAll(8); 13819f24454b516042b618298522e79bf9e6fa5ccbdNAKAMURA Takumi EXPECT_EQ(0, std::distance(Set.getHead(8), Set.end())); 139afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 140afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Clear and resize the universe. 141afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.clear(); 142afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(0u, Set.size()); 143afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_FALSE(Set.contains(3)); 144afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.setUniverse(1000); 145afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 146afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Add more than 256 elements. 147afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman for (unsigned i = 100; i != 800; ++i) 148afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(i); 149afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 150afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman for (unsigned i = 0; i != 10; ++i) 151afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.eraseAll(i); 152afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 153afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman for (unsigned i = 100; i != 800; ++i) 154afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(1u, Set.count(i)); 155afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 156afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_FALSE(Set.contains(99)); 157afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_FALSE(Set.contains(800)); 158afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(700u, Set.size()); 159afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman} 160afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 161afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman// Test out iterators 162afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael IlsemanTEST(SparseMultiSetTest, Iterators) { 163afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman USet Set; 164afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.setUniverse(100); 165afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 166afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(0); 167afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(1); 168afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(2); 169afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(0); 170afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(1); 171afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(0); 172afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 173afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman USet::RangePair RangePair = Set.equal_range(0); 174afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman USet::iterator B = RangePair.first; 175afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman USet::iterator E = RangePair.second; 176afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 177afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Move the iterators around, going to end and coming back. 178421db34270ca7d5a08b571713a5d9c83ed07b872NAKAMURA Takumi EXPECT_EQ(3, std::distance(B, E)); 179afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(B, --(--(--E))); 180afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(++(++(++E)), Set.end()); 181afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(B, --(--(--E))); 182afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(++(++(++E)), Set.end()); 183afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 184afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Insert into the tail, and move around again 185afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(0); 186afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(B, --(--(--(--E)))); 187afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(++(++(++(++E))), Set.end()); 188afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(B, --(--(--(--E)))); 189afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(++(++(++(++E))), Set.end()); 190afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 191afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman // Erase a tail, and move around again 192afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman USet::iterator Erased = Set.erase(Set.getTail(0)); 193afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(Erased, E); 194afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(B, --(--(--E))); 195afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 196afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman USet Set2; 197afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set2.setUniverse(11); 198afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set2.insert(3); 199afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(!Set2.contains(0)); 200afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(!Set.contains(3)); 201afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 202afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(Set2.getHead(3), Set2.getTail(3)); 203afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(Set2.getHead(0), Set2.getTail(0)); 204afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman B = Set2.find(3); 205afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(Set2.find(3), --(++B)); 206afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman} 207afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 208afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilsemanstruct Alt { 209afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman unsigned Value; 210afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman explicit Alt(unsigned x) : Value(x) {} 211afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman unsigned getSparseSetIndex() const { return Value - 1000; } 212afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman}; 213afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 214afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael IlsemanTEST(SparseMultiSetTest, AltStructSet) { 215afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman typedef SparseMultiSet<Alt> ASet; 216afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman ASet Set; 217afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.setUniverse(10); 218afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(Alt(1005)); 219afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 220afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman ASet::iterator I = Set.find(5); 221afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman ASSERT_TRUE(I != Set.end()); 222afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(1005u, I->Value); 223afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 224afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(Alt(1006)); 225afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman Set.insert(Alt(1006)); 226afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman I = Set.erase(Set.find(6)); 227afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman ASSERT_TRUE(I != Set.end()); 228afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_EQ(1006u, I->Value); 229afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman I = Set.erase(Set.find(6)); 230afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman ASSERT_TRUE(I == Set.end()); 231afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman 232afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_TRUE(Set.contains(5)); 233afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman EXPECT_FALSE(Set.contains(6)); 234afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman} 235afe77f33b2a361ed0d001596dcdde0e16d57abeeMichael Ilseman} // namespace 236