185 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/EquivalenceClasses.h"10#include "gmock/gmock.h"11#include "gtest/gtest.h"12 13using namespace llvm;14 15namespace llvm {16 17TEST(EquivalenceClassesTest, CopyAssignemnt) {18 EquivalenceClasses<int> EC, Copy;19 EC.insert(1);20 EC.insert(4);21 EquivalenceClasses<int> &Ref = Copy = EC;22 EXPECT_EQ(Copy.getNumClasses(), 2u);23 EXPECT_EQ(&Ref, &Copy);24}25 26TEST(EquivalenceClassesTest, NoMerges) {27 EquivalenceClasses<int> EqClasses;28 // Until we merged any sets, check that every element is only equivalent to29 // itself.30 for (int i = 0; i < 3; i++)31 for (int j = 0; j < 3; j++)32 if (i == j)33 EXPECT_TRUE(EqClasses.isEquivalent(i, j));34 else35 EXPECT_FALSE(EqClasses.isEquivalent(i, j));36}37 38TEST(EquivalenceClassesTest, SimpleMerge1) {39 EquivalenceClasses<int> EqClasses;40 // Check that once we merge (A, B), (B, C), (C, D), then all elements belong41 // to one set.42 EqClasses.unionSets(0, 1);43 EqClasses.unionSets(1, 2);44 EqClasses.unionSets(2, 3);45 for (int i = 0; i < 4; ++i)46 for (int j = 0; j < 4; ++j)47 EXPECT_TRUE(EqClasses.isEquivalent(i, j));48}49 50TEST(EquivalenceClassesTest, SimpleMerge2) {51 EquivalenceClasses<int> EqClasses;52 // Check that once we merge (A, B), (C, D), (A, C), then all elements belong53 // to one set.54 EqClasses.unionSets(0, 1);55 EqClasses.unionSets(2, 3);56 EqClasses.unionSets(0, 2);57 for (int i = 0; i < 4; ++i)58 for (int j = 0; j < 4; ++j)59 EXPECT_TRUE(EqClasses.isEquivalent(i, j));60}61 62TEST(EquivalenceClassesTest, SimpleErase1) {63 EquivalenceClasses<int> EqClasses;64 // Check that erase head success.65 // After erase A from (A, B ,C, D), <B, C, D> belong to one set.66 EqClasses.unionSets(0, 1);67 EqClasses.unionSets(2, 3);68 EqClasses.unionSets(0, 2);69 EXPECT_TRUE(EqClasses.erase(0));70 for (int i = 1; i < 4; ++i)71 for (int j = 1; j < 4; ++j)72 EXPECT_TRUE(EqClasses.isEquivalent(i, j));73}74 75TEST(EquivalenceClassesTest, SimpleErase2) {76 EquivalenceClasses<int> EqClasses;77 // Check that erase tail success.78 // After erase D from (A, B ,C, D), <A, B, C> belong to one set.79 EqClasses.unionSets(0, 1);80 EqClasses.unionSets(2, 3);81 EqClasses.unionSets(0, 2);82 EXPECT_TRUE(EqClasses.erase(3));83 for (int i = 0; i < 3; ++i)84 for (int j = 0; j < 3; ++j)85 EXPECT_TRUE(EqClasses.isEquivalent(i, j));86}87 88TEST(EquivalenceClassesTest, SimpleErase3) {89 EquivalenceClasses<int> EqClasses;90 // Check that erase a value in the middle success.91 // After erase B from (A, B ,C, D), <A, C, D> belong to one set.92 EqClasses.unionSets(0, 1);93 EqClasses.unionSets(2, 3);94 EqClasses.unionSets(0, 2);95 EXPECT_TRUE(EqClasses.erase(1));96 for (int i = 0; i < 3; ++i)97 for (int j = 0; j < 3; ++j)98 EXPECT_TRUE(EqClasses.isEquivalent(i, j) ^ ((i == 1) ^ (j == 1)));99}100 101TEST(EquivalenceClassesTest, SimpleErase4) {102 EquivalenceClasses<int> EqClasses;103 // Check that erase a single class success.104 EqClasses.insert(0);105 EXPECT_TRUE(EqClasses.getNumClasses() == 1);106 EXPECT_TRUE(EqClasses.erase(0));107 EXPECT_TRUE(EqClasses.getNumClasses() == 0);108 EXPECT_FALSE(EqClasses.erase(1));109}110 111TEST(EquivalenceClassesTest, EraseKeepsLeaderBit) {112 EquivalenceClasses<int> EC;113 114 // Create a set {1, 2} where 1 is the leader.115 EC.unionSets(1, 2);116 117 // Verify initial state.118 EXPECT_EQ(EC.getLeaderValue(2), 1);119 120 // Erase 2, the non-leader member.121 EXPECT_TRUE(EC.erase(2));122 123 // Verify that we have exactly one equivalence class.124 ASSERT_NE(EC.begin(), EC.end());125 ASSERT_EQ(std::next(EC.begin()), EC.end());126 127 // Verify that 1 is still a leader after erasing 2.128 const auto *Elem = *EC.begin();129 ASSERT_NE(Elem, nullptr);130 EXPECT_EQ(Elem->getData(), 1);131 EXPECT_TRUE(Elem->isLeader()) << "The leader bit was lost!";132}133 134TEST(EquivalenceClassesTest, TwoSets) {135 EquivalenceClasses<int> EqClasses;136 // Form sets of odd and even numbers, check that we split them into these137 // two sets correcrly.138 for (int i = 0; i < 30; i += 2)139 EqClasses.unionSets(0, i);140 for (int i = 1; i < 30; i += 2)141 EqClasses.unionSets(1, i);142 143 for (int i = 0; i < 30; i++)144 for (int j = 0; j < 30; j++)145 if (i % 2 == j % 2)146 EXPECT_TRUE(EqClasses.isEquivalent(i, j));147 else148 EXPECT_FALSE(EqClasses.isEquivalent(i, j));149}150 151TEST(EquivalenceClassesTest, MembersIterator) {152 EquivalenceClasses<int> EC;153 EC.unionSets(1, 2);154 EC.insert(4);155 EC.insert(5);156 EC.unionSets(5, 1);157 EXPECT_EQ(EC.getNumClasses(), 2u);158 159 EXPECT_THAT(EC.members(4), testing::ElementsAre(4));160 EXPECT_THAT(EC.members(1), testing::ElementsAre(5, 1, 2));161}162 163// Type-parameterized tests: Run the same test cases with different element164// types.165template <typename T> class ParameterizedTest : public testing::Test {};166 167TYPED_TEST_SUITE_P(ParameterizedTest);168 169TYPED_TEST_P(ParameterizedTest, MultipleSets) {170 TypeParam EqClasses;171 // Split numbers from [0, 100) into sets so that values in the same set have172 // equal remainders (mod 17).173 for (int i = 0; i < 100; i++)174 EqClasses.unionSets(i % 17, i);175 176 for (int i = 0; i < 100; i++)177 for (int j = 0; j < 100; j++)178 if (i % 17 == j % 17)179 EXPECT_TRUE(EqClasses.isEquivalent(i, j));180 else181 EXPECT_FALSE(EqClasses.isEquivalent(i, j));182}183 184} // llvm185