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
12using namespace llvm;
13
14namespace llvm {
15
16TEST(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
28TEST(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
40TEST(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
52TEST(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.
71template <typename T> class ParameterizedTest : public testing::Test {};
72
73TYPED_TEST_SUITE_P(ParameterizedTest);
74
75TYPED_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
90namespace {
91// A dummy struct for testing EquivalenceClasses with a comparator.
92struct 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.
102struct TestStructComparator {
103 bool operator()(const TestStruct &lhs, const TestStruct &rhs) const {
104 return lhs.value < rhs.value;
105 }
106};
107} // namespace
108
109REGISTER_TYPED_TEST_SUITE_P(ParameterizedTest, MultipleSets);
110using ParamTypes =
111 testing::Types<EquivalenceClasses<int>,
112 EquivalenceClasses<TestStruct, TestStructComparator>>;
113INSTANTIATE_TYPED_TEST_SUITE_P(EquivalenceClassesTest, ParameterizedTest,
114 ParamTypes, );
115
116} // llvm
117

source code of llvm/unittests/ADT/EquivalenceClassesTest.cpp