include/Support/EquivalenceClasses.h

   1 //===-- Support/EquivalenceClasses.h ----------------------------*- 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 SUPPORT_EQUIVALENCECLASSES_H
  18 #define SUPPORT_EQUIVALENCECLASSES_H
  19
  20 #include <map>
  21 #include <set>
  22 #include <vector>
  23
  24 namespace llvm {
  25
  26 template <class ElemTy>
  27 class 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
  50 public:
  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