llvm/unittests/ADT/EquivalenceClassesTest.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-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(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 // 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