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
108
109
110
111
112
113
114
115
116
|
//===-- llvm/ADT/EquivalenceClasses.h - Generic Equiv. Classes --*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Generic implementation of equivalence classes and implementation of
// union-find algorithms A not-so-fancy implementation: 2 level tree i.e root
// and one more level Overhead of a union = size of the equivalence class being
// attached Overhead of a find = 1.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_EQUIVALENCECLASSES_H
#define LLVM_ADT_EQUIVALENCECLASSES_H
#include <map>
#include <set>
#include <vector>
namespace llvm {
template <class ElemTy>
class EquivalenceClasses {
// Maps each element to the element that is the leader of its
// equivalence class.
std::map<ElemTy, ElemTy> Elem2LeaderMap;
// Maintains the set of leaders
std::set<ElemTy> LeaderSet;
// Caches the equivalence class for each leader
std::map<ElemTy, std::set<ElemTy> > LeaderToEqClassMap;
// Make Element2 the leader of the union of classes Element1 and Element2
// Element1 and Element2 are presumed to be leaders of their respective
// equivalence classes.
void attach(ElemTy Element1, ElemTy Element2) {
for (typename std::map<ElemTy, ElemTy>::iterator ElemI =
Elem2LeaderMap.begin(), ElemE = Elem2LeaderMap.end();
ElemI != ElemE; ++ElemI) {
if (ElemI->second == Element1)
Elem2LeaderMap[ElemI->first] = Element2;
}
}
public:
// If an element has not yet in any class, make it a separate new class.
// Return the leader of the class containing the element.
ElemTy addElement (ElemTy NewElement) {
typename std::map<ElemTy, ElemTy>::iterator ElemI =
Elem2LeaderMap.find(NewElement);
if (ElemI == Elem2LeaderMap.end()) {
Elem2LeaderMap[NewElement] = NewElement;
LeaderSet.insert(NewElement);
return NewElement;
}
else
return ElemI->second;
}
ElemTy findClass(ElemTy Element) const {
typename std::map<ElemTy, ElemTy>::const_iterator I =
Elem2LeaderMap.find(Element);
return (I == Elem2LeaderMap.end())? (ElemTy) 0 : I->second;
}
/// Attach the set with Element1 to the set with Element2 adding Element1 and
/// Element2 to the set of equivalence classes if they are not there already.
/// Implication: Make Element1 the element in the smaller set.
/// Take Leader[Element1] out of the set of leaders.
void unionSetsWith(ElemTy Element1, ElemTy Element2) {
// If either Element1 or Element2 does not already exist, include it
const ElemTy& leader1 = addElement(Element1);
const ElemTy& leader2 = addElement(Element2);
assert(leader1 != (ElemTy) 0 && leader2 != (ElemTy) 0);
if (leader1 != leader2) {
attach(leader1, leader2);
LeaderSet.erase(leader1);
}
}
// Returns a vector containing all the elements in the equivalence class
// including Element1
const std::set<ElemTy> & getEqClass(ElemTy Element1) {
assert(Elem2LeaderMap.find(Element1) != Elem2LeaderMap.end());
const ElemTy classLeader = Elem2LeaderMap[Element1];
std::set<ElemTy> & EqClass = LeaderToEqClassMap[classLeader];
// If the EqClass vector is empty, it has not been computed yet: do it now
if (EqClass.empty()) {
for (typename std::map<ElemTy, ElemTy>::iterator
ElemI = Elem2LeaderMap.begin(), ElemE = Elem2LeaderMap.end();
ElemI != ElemE; ++ElemI)
if (ElemI->second == classLeader)
EqClass.insert(ElemI->first);
assert(! EqClass.empty()); // must at least include the leader
}
return EqClass;
}
std::set<ElemTy>& getLeaderSet() { return LeaderSet; }
const std::set<ElemTy>& getLeaderSet() const { return LeaderSet; }
std::map<ElemTy, ElemTy>& getLeaderMap() { return Elem2LeaderMap;}
const std::map<ElemTy, ElemTy>& getLeaderMap() const { return Elem2LeaderMap;}
};
} // End llvm namespace
#endif
|
