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 // Type-parameterized tests: Run the same test cases with different element 70 // types. 71 template <typename T> class ParameterizedTest : public testing::Test {}; 72 73 TYPED_TEST_SUITE_P(ParameterizedTest); 74 75 TYPED_TEST_P(ParameterizedTest, MultipleSets) { 76 TypeParam EqClasses; 77 // Split numbers from [0, 100) into sets so that values in the same set have 78 // equal remainders (mod 17). 79 for (int i = 0; i < 100; i++) 80 EqClasses.unionSets(i % 17, i); 81 82 for (int i = 0; i < 100; i++) 83 for (int j = 0; j < 100; j++) 84 if (i % 17 == j % 17) 85 EXPECT_TRUE(EqClasses.isEquivalent(i, j)); 86 else 87 EXPECT_FALSE(EqClasses.isEquivalent(i, j)); 88 } 89 90 namespace { 91 // A dummy struct for testing EquivalenceClasses with a comparator. 92 struct TestStruct { 93 TestStruct(int value) : value(value) {} 94 95 bool operator==(const TestStruct &other) const { 96 return value == other.value; 97 } 98 99 int value; 100 }; 101 // Comparator to be used in test case. 102 struct TestStructComparator { 103 bool operator()(const TestStruct &lhs, const TestStruct &rhs) const { 104 return lhs.value < rhs.value; 105 } 106 }; 107 } // namespace 108 109 REGISTER_TYPED_TEST_SUITE_P(ParameterizedTest, MultipleSets); 110 using ParamTypes = 111 testing::Types<EquivalenceClasses<int>, 112 EquivalenceClasses<TestStruct, TestStructComparator>>; 113 INSTANTIATE_TYPED_TEST_SUITE_P(EquivalenceClassesTest, ParameterizedTest, 114 ParamTypes); 115 116 } // llvm 117