1 //===-- Support/EquivalenceClasses.h ----------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Generic implementation of equivalence classes and implementation of
11 // union-find algorithms A not-so-fancy implementation: 2 level tree i.e root
12 // and one more level Overhead of a union = size of the equivalence class being
13 // attached Overhead of a find = 1.
15 //===----------------------------------------------------------------------===//
17 #ifndef SUPPORT_EQUIVALENCECLASSES_H
18 #define SUPPORT_EQUIVALENCECLASSES_H
26 template <class ElemTy>
27 class EquivalenceClasses {
28 // Maps each element to the element that is the leader of its
30 std::map<ElemTy, ElemTy> Elem2LeaderMap;
32 // Maintains the set of leaders
33 std::set<ElemTy> LeaderSet;
35 // Caches the equivalence class for each leader
36 std::map<ElemTy, std::set<ElemTy> > LeaderToEqClassMap;
38 // Make Element2 the leader of the union of classes Element1 and Element2
39 // Element1 and Element2 are presumed to be leaders of their respective
40 // equivalence classes.
41 void attach(ElemTy Element1, ElemTy Element2) {
42 for (typename std::map<ElemTy, ElemTy>::iterator ElemI =
43 Elem2LeaderMap.begin(), ElemE = Elem2LeaderMap.end();
44 ElemI != ElemE; ++ElemI) {
45 if (ElemI->second == Element1)
46 Elem2LeaderMap[ElemI->first] = Element2;
51 // If an element has not yet in any class, make it a separate new class.
52 // Return the leader of the class containing the element.
53 ElemTy addElement (ElemTy NewElement) {
54 typename std::map<ElemTy, ElemTy>::iterator ElemI =
55 Elem2LeaderMap.find(NewElement);
56 if (ElemI == Elem2LeaderMap.end()) {
57 Elem2LeaderMap[NewElement] = NewElement;
58 LeaderSet.insert(NewElement);
65 ElemTy findClass(ElemTy Element) const {
66 typename std::map<ElemTy, ElemTy>::const_iterator I =
67 Elem2LeaderMap.find(Element);
68 return (I == Elem2LeaderMap.end())? (ElemTy) 0 : I->second;
71 /// Attach the set with Element1 to the set with Element2 adding Element1 and
72 /// Element2 to the set of equivalence classes if they are not there already.
73 /// Implication: Make Element1 the element in the smaller set.
74 /// Take Leader[Element1] out of the set of leaders.
75 void unionSetsWith(ElemTy Element1, ElemTy Element2) {
76 // If either Element1 or Element2 does not already exist, include it
77 const ElemTy& leader1 = addElement(Element1);
78 const ElemTy& leader2 = addElement(Element2);
79 assert(leader1 != (ElemTy) 0 && leader2 != (ElemTy) 0);
80 if (leader1 != leader2) {
81 attach(leader1, leader2);
82 LeaderSet.erase(leader1);
86 // Returns a vector containing all the elements in the equivalence class
88 const std::set<ElemTy> & getEqClass(ElemTy Element1) {
89 assert(Elem2LeaderMap.find(Element1) != Elem2LeaderMap.end());
90 const ElemTy classLeader = Elem2LeaderMap[Element1];
92 std::set<ElemTy> & EqClass = LeaderToEqClassMap[classLeader];
94 // If the EqClass vector is empty, it has not been computed yet: do it now
95 if (EqClass.empty()) {
96 for (typename std::map<ElemTy, ElemTy>::iterator
97 ElemI = Elem2LeaderMap.begin(), ElemE = Elem2LeaderMap.end();
98 ElemI != ElemE; ++ElemI)
99 if (ElemI->second == classLeader)
100 EqClass.insert(ElemI->first);
101 assert(! EqClass.empty()); // must at least include the leader
107 std::set<ElemTy>& getLeaderSet() { return LeaderSet; }
108 const std::set<ElemTy>& getLeaderSet() const { return LeaderSet; }
110 std::map<ElemTy, ElemTy>& getLeaderMap() { return Elem2LeaderMap;}
111 const std::map<ElemTy, ElemTy>& getLeaderMap() const { return Elem2LeaderMap;}
114 } // End llvm namespace