EquivalenceClasses.h revision 551ccae044b0ff658fe629dd67edd5ffe75d10e8 
1//===-- llvm/ADT/EquivalenceClasses.h - Generic Equiv. Classes --*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
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.
7//
8//===----------------------------------------------------------------------===//
9//
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.
14//
15//===----------------------------------------------------------------------===//
16
17#ifndef LLVM_ADT_EQUIVALENCECLASSES_H
18#define LLVM_ADT_EQUIVALENCECLASSES_H
19
20#include <map>
21#include <set>
22#include <vector>
23
24namespace llvm {
25
26template <class ElemTy>
27class EquivalenceClasses {
28  // Maps each element to the element that is the leader of its
29  // equivalence class.
30  std::map<ElemTy, ElemTy> Elem2LeaderMap;
31
32  // Maintains the set of leaders
33  std::set<ElemTy> LeaderSet;
34
35  // Caches the equivalence class for each leader
36  std::map<ElemTy, std::set<ElemTy> > LeaderToEqClassMap;
37
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;
47    }
48  }
49
50public:
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);
59      return NewElement;
60    }
61    else
62      return ElemI->second;
63  }
64
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;
69  }
70
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);
83    }
84  }
85
86  // Returns a vector containing all the elements in the equivalence class
87  // including Element1
88  const std::set<ElemTy> & getEqClass(ElemTy Element1) {
89    assert(Elem2LeaderMap.find(Element1) != Elem2LeaderMap.end());
90    const ElemTy classLeader = Elem2LeaderMap[Element1];
91
92    std::set<ElemTy> & EqClass = LeaderToEqClassMap[classLeader];
93
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
102    }
103
104    return EqClass;
105  }
106
107        std::set<ElemTy>& getLeaderSet()       { return LeaderSet; }
108  const std::set<ElemTy>& getLeaderSet() const { return LeaderSet; }
109
110        std::map<ElemTy, ElemTy>& getLeaderMap()       { return Elem2LeaderMap;}
111  const std::map<ElemTy, ElemTy>& getLeaderMap() const { return Elem2LeaderMap;}
112};
113
114} // End llvm namespace
115
116#endif
117