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 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