unittests/ADT/EquivalenceClassesTest.cpp

   1 //=== llvm/unittest/ADT/EquivalenceClassesTest.cpp - the structure tests --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/ADT/EquivalenceClasses.h"
  11 #include "gtest/gtest.h"
  12
  13 using namespace llvm;
  14
  15 namespace llvm {
  16
  17 TEST(EquivalenceClassesTest, NoMerges) {
  18   EquivalenceClasses<int> EqClasses;
  19   // Until we merged any sets, check that every element is only equivalent to
  20   // itself.
  21   for (int i = 0; i < 3; i++)
  22     for (int j = 0; j < 3; j++)
  23       if (i == j)
  24         EXPECT_TRUE(EqClasses.isEquivalent(i, j));
  25       else
  26         EXPECT_FALSE(EqClasses.isEquivalent(i, j));
  27 }
  28
  29 TEST(EquivalenceClassesTest, SimpleMerge1) {
  30   EquivalenceClasses<int> EqClasses;
  31   // Check that once we merge (A, B), (B, C), (C, D), then all elements belong
  32   // to one set.
  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));
  39 }
  40
  41 TEST(EquivalenceClassesTest, SimpleMerge2) {
  42   EquivalenceClasses<int> EqClasses;
  43   // Check that once we merge (A, B), (C, D), (A, C), then all elements belong
  44   // to one set.
  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));
  51 }
  52
  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);
  61
  62   for (int i = 0; i < 30; i++)
  63     for (int j = 0; j < 30; j++)
  64       if (i % 2 == j % 2)
  65         EXPECT_TRUE(EqClasses.isEquivalent(i, j));
  66       else
  67         EXPECT_FALSE(EqClasses.isEquivalent(i, j));
  68 }
  69
  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);
  76
  77   for (int i = 0; i < 100; i++)
  78     for (int j = 0; j < 100; j++)
  79       if (i % 17 == j % 17)
  80         EXPECT_TRUE(EqClasses.isEquivalent(i, j));
  81       else
  82         EXPECT_FALSE(EqClasses.isEquivalent(i, j));
  83 }
  84
  85 } // llvm