|
134
|
1 //=== llvm/unittest/ADT/EquivalenceClassesTest.cpp - the structure tests --===//
|
|
|
2 //
|
|
147
|
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
|
|
134
|
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
|
