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(V1: 0, V2: 1); |
33 | EqClasses.unionSets(V1: 1, V2: 2); |
34 | EqClasses.unionSets(V1: 2, V2: 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(V1: 0, V2: 1); |
45 | EqClasses.unionSets(V1: 2, V2: 3); |
46 | EqClasses.unionSets(V1: 0, V2: 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(V1: 0, V2: i); |
58 | for (int i = 1; i < 30; i += 2) |
59 | EqClasses.unionSets(V1: 1, V2: 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 | |