1 //=== llvm/unittest/ADT/EquivalenceClassesTest.cpp - the structure tests --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/ADT/EquivalenceClasses.h"
11 #include "gtest/gtest.h"
17 TEST(EquivalenceClassesTest, NoMerges) {
18 EquivalenceClasses<int> EqClasses;
19 // Until we merged any sets, check that every element is only equivalent to
21 for (int i = 0; i < 3; i++)
22 for (int j = 0; j < 3; j++)
24 EXPECT_TRUE(EqClasses.isEquivalent(i, j));
26 EXPECT_FALSE(EqClasses.isEquivalent(i, j));
29 TEST(EquivalenceClassesTest, SimpleMerge1) {
30 EquivalenceClasses<int> EqClasses;
31 // Check that once we merge (A, B), (B, C), (C, D), then all elements belong
33 EqClasses.unionSets(0, 1);
34 EqClasses.unionSets(1, 2);
35 EqClasses.unionSets(2, 3);
36 for (int i = 0; i < 4; ++i)
37 for (int j = 0; j < 4; ++j)
38 EXPECT_TRUE(EqClasses.isEquivalent(i, j));
41 TEST(EquivalenceClassesTest, SimpleMerge2) {
42 EquivalenceClasses<int> EqClasses;
43 // Check that once we merge (A, B), (C, D), (A, C), then all elements belong
45 EqClasses.unionSets(0, 1);
46 EqClasses.unionSets(2, 3);
47 EqClasses.unionSets(0, 2);
48 for (int i = 0; i < 4; ++i)
49 for (int j = 0; j < 4; ++j)
50 EXPECT_TRUE(EqClasses.isEquivalent(i, j));
53 TEST(EquivalenceClassesTest, TwoSets) {
54 EquivalenceClasses<int> EqClasses;
55 // Form sets of odd and even numbers, check that we split them into these
56 // two sets correcrly.
57 for (int i = 0; i < 30; i += 2)
58 EqClasses.unionSets(0, i);
59 for (int i = 1; i < 30; i += 2)
60 EqClasses.unionSets(1, i);
62 for (int i = 0; i < 30; i++)
63 for (int j = 0; j < 30; j++)
65 EXPECT_TRUE(EqClasses.isEquivalent(i, j));
67 EXPECT_FALSE(EqClasses.isEquivalent(i, j));
70 TEST(EquivalenceClassesTest, MultipleSets) {
71 EquivalenceClasses<int> EqClasses;
72 // Split numbers from [0, 100) into sets so that values in the same set have
73 // equal remainders (mod 17).
74 for (int i = 0; i < 100; i++)
75 EqClasses.unionSets(i % 17, i);
77 for (int i = 0; i < 100; i++)
78 for (int j = 0; j < 100; j++)
80 EXPECT_TRUE(EqClasses.isEquivalent(i, j));
82 EXPECT_FALSE(EqClasses.isEquivalent(i, j));