1 //=== llvm/unittest/ADT/EquivalenceClassesTest.cpp - the structure tests --===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "llvm/ADT/EquivalenceClasses.h" 11 #include "gtest/gtest.h" 12 13 using namespace llvm; 14 15 namespace llvm { 16 17 TEST(EquivalenceClassesTest, NoMerges) { 18 EquivalenceClasses<int> EqClasses; 19 // Until we merged any sets, check that every element is only equivalent to 20 // itself. 21 for (int i = 0; i < 3; i++) 22 for (int j = 0; j < 3; j++) 23 if (i == j) 24 EXPECT_TRUE(EqClasses.isEquivalent(i, j)); 25 else 26 EXPECT_FALSE(EqClasses.isEquivalent(i, j)); 27 } 28 29 TEST(EquivalenceClassesTest, SimpleMerge1) { 30 EquivalenceClasses<int> EqClasses; 31 // Check that once we merge (A, B), (B, C), (C, D), then all elements belong 32 // to one set. 33 EqClasses.unionSets(0, 1); 34 EqClasses.unionSets(1, 2); 35 EqClasses.unionSets(2, 3); 36 for (int i = 0; i < 4; ++i) 37 for (int j = 0; j < 4; ++j) 38 EXPECT_TRUE(EqClasses.isEquivalent(i, j)); 39 } 40 41 TEST(EquivalenceClassesTest, SimpleMerge2) { 42 EquivalenceClasses<int> EqClasses; 43 // Check that once we merge (A, B), (C, D), (A, C), then all elements belong 44 // to one set. 45 EqClasses.unionSets(0, 1); 46 EqClasses.unionSets(2, 3); 47 EqClasses.unionSets(0, 2); 48 for (int i = 0; i < 4; ++i) 49 for (int j = 0; j < 4; ++j) 50 EXPECT_TRUE(EqClasses.isEquivalent(i, j)); 51 } 52 53 TEST(EquivalenceClassesTest, TwoSets) { 54 EquivalenceClasses<int> EqClasses; 55 // Form sets of odd and even numbers, check that we split them into these 56 // two sets correcrly. 57 for (int i = 0; i < 30; i += 2) 58 EqClasses.unionSets(0, i); 59 for (int i = 1; i < 30; i += 2) 60 EqClasses.unionSets(1, i); 61 62 for (int i = 0; i < 30; i++) 63 for (int j = 0; j < 30; j++) 64 if (i % 2 == j % 2) 65 EXPECT_TRUE(EqClasses.isEquivalent(i, j)); 66 else 67 EXPECT_FALSE(EqClasses.isEquivalent(i, j)); 68 } 69 70 TEST(EquivalenceClassesTest, MultipleSets) { 71 EquivalenceClasses<int> EqClasses; 72 // Split numbers from [0, 100) into sets so that values in the same set have 73 // equal remainders (mod 17). 74 for (int i = 0; i < 100; i++) 75 EqClasses.unionSets(i % 17, i); 76 77 for (int i = 0; i < 100; i++) 78 for (int j = 0; j < 100; j++) 79 if (i % 17 == j % 17) 80 EXPECT_TRUE(EqClasses.isEquivalent(i, j)); 81 else 82 EXPECT_FALSE(EqClasses.isEquivalent(i, j)); 83 } 84 85 } // llvm 86
