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
TEST(EquivalenceClassesTest,NoMerges)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
TEST(EquivalenceClassesTest,SimpleMerge1)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
TEST(EquivalenceClassesTest,SimpleMerge2)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
TEST(EquivalenceClassesTest,TwoSets)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
TYPED_TEST_P(ParameterizedTest,MultipleSets)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 {
TestStructllvm::__anon494d7ee70111::TestStruct93 TestStruct(int value) : value(value) {}
94
operator ==llvm::__anon494d7ee70111::TestStruct95 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 {
operator ()llvm::__anon494d7ee70111::TestStructComparator103 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