aboutsummaryrefslogtreecommitdiffstats
path: root/unittests/ADT/IntEqClassesTest.cpp
blob: fc908c1e8bff3c1bf7af053d6cb4e9dba4db8074 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//===---- ADT/IntEqClassesTest.cpp - IntEqClasses unit tests ----*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/IntEqClasses.h"
#include "gtest/gtest.h"

using namespace llvm;

namespace {

TEST(IntEqClasses, Simple) {
  IntEqClasses ec(10);

  ec.join(0, 1);
  ec.join(3, 2);
  ec.join(4, 5);
  ec.join(7, 6);

  EXPECT_EQ(0u, ec.findLeader(0));
  EXPECT_EQ(0u, ec.findLeader(1));
  EXPECT_EQ(2u, ec.findLeader(2));
  EXPECT_EQ(2u, ec.findLeader(3));
  EXPECT_EQ(4u, ec.findLeader(4));
  EXPECT_EQ(4u, ec.findLeader(5));
  EXPECT_EQ(6u, ec.findLeader(6));
  EXPECT_EQ(6u, ec.findLeader(7));
  EXPECT_EQ(8u, ec.findLeader(8));
  EXPECT_EQ(9u, ec.findLeader(9));

  // join two non-leaders.
  ec.join(1, 3);

  EXPECT_EQ(0u, ec.findLeader(0));
  EXPECT_EQ(0u, ec.findLeader(1));
  EXPECT_EQ(0u, ec.findLeader(2));
  EXPECT_EQ(0u, ec.findLeader(3));
  EXPECT_EQ(4u, ec.findLeader(4));
  EXPECT_EQ(4u, ec.findLeader(5));
  EXPECT_EQ(6u, ec.findLeader(6));
  EXPECT_EQ(6u, ec.findLeader(7));
  EXPECT_EQ(8u, ec.findLeader(8));
  EXPECT_EQ(9u, ec.findLeader(9));

  // join two leaders.
  ec.join(4, 8);

  EXPECT_EQ(0u, ec.findLeader(0));
  EXPECT_EQ(0u, ec.findLeader(1));
  EXPECT_EQ(0u, ec.findLeader(2));
  EXPECT_EQ(0u, ec.findLeader(3));
  EXPECT_EQ(4u, ec.findLeader(4));
  EXPECT_EQ(4u, ec.findLeader(5));
  EXPECT_EQ(6u, ec.findLeader(6));
  EXPECT_EQ(6u, ec.findLeader(7));
  EXPECT_EQ(4u, ec.findLeader(8));
  EXPECT_EQ(9u, ec.findLeader(9));

  // join mixed.
  ec.join(9, 1);

  EXPECT_EQ(0u, ec.findLeader(0));
  EXPECT_EQ(0u, ec.findLeader(1));
  EXPECT_EQ(0u, ec.findLeader(2));
  EXPECT_EQ(0u, ec.findLeader(3));
  EXPECT_EQ(4u, ec.findLeader(4));
  EXPECT_EQ(4u, ec.findLeader(5));
  EXPECT_EQ(6u, ec.findLeader(6));
  EXPECT_EQ(6u, ec.findLeader(7));
  EXPECT_EQ(4u, ec.findLeader(8));
  EXPECT_EQ(0u, ec.findLeader(9));

  // compressed map.
  ec.compress();
  EXPECT_EQ(3u, ec.getNumClasses());

  EXPECT_EQ(0u, ec[0]);
  EXPECT_EQ(0u, ec[1]);
  EXPECT_EQ(0u, ec[2]);
  EXPECT_EQ(0u, ec[3]);
  EXPECT_EQ(1u, ec[4]);
  EXPECT_EQ(1u, ec[5]);
  EXPECT_EQ(2u, ec[6]);
  EXPECT_EQ(2u, ec[7]);
  EXPECT_EQ(1u, ec[8]);
  EXPECT_EQ(0u, ec[9]);

  // uncompressed map.
  ec.uncompress();
  EXPECT_EQ(0u, ec.findLeader(0));
  EXPECT_EQ(0u, ec.findLeader(1));
  EXPECT_EQ(0u, ec.findLeader(2));
  EXPECT_EQ(0u, ec.findLeader(3));
  EXPECT_EQ(4u, ec.findLeader(4));
  EXPECT_EQ(4u, ec.findLeader(5));
  EXPECT_EQ(6u, ec.findLeader(6));
  EXPECT_EQ(6u, ec.findLeader(7));
  EXPECT_EQ(4u, ec.findLeader(8));
  EXPECT_EQ(0u, ec.findLeader(9));
}

} // end anonymous namespace