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