include/Support/EquivalenceClasses.h

   1 //===-- Support/EquivalenceClasses.h -------------------------*- C++ -*--=//
   2 //
   3 // Generic implementation of equivalence classes and implementation of
   4 // union-find algorithms
   5 // A not-so-fancy implementation: 2 level tree i.e root and one more level
   6 // Overhead of a union = size of the equivalence class being attached
   7 // Overhead of a find = 1.
   8 //
   9 //===------------------------------------------------------------------===//
  10
  11 #ifndef LLVM_SUPPORT_EQUIVALENCE_CLASSES_H
  12 #define LLVM_SUPPORT_EQUIVALENCE_CLASSES_H
  13
  14 #include <map>
  15 #include <set>
  16 #include <vector>
  17 using std::map;
  18 using std::set;
  19 using std::vector;
  20
  21 template <class ElemTy>
  22 class EquivalenceClasses {
  23   // Maps each element to the element that is the leader of its
  24   // equivalence class.
  25   map<ElemTy, ElemTy> Elem2ECLeaderMap;
  26
  27   // Make Element2 the leader of the union of classes Element1 and Element2
  28   // Element1 and Element2 are presumed to be leaders of their respective
  29   // equivalence classes.
  30   void attach(ElemTy Element1, ElemTy Element2) {
  31     for (typename map<ElemTy, ElemTy>::iterator ElemI =
  32            Elem2ECLeaderMap.begin(), ElemE = Elem2ECLeaderMap.end();
  33          ElemI != ElemE; ++ElemI) {
  34       if (ElemI->second == Element1)
  35         Elem2ECLeaderMap[ElemI->first] = Element2;
  36     }
  37   }
  38
  39 public:
  40
  41   void addElement (ElemTy NewElement) {
  42     if (Elem2ECLeaderMap.find(NewElement) == Elem2ECLeaderMap.end())
  43       Elem2ECLeaderMap[NewElement] = NewElement;
  44   }
  45
  46   ElemTy findClass(ElemTy Element) {
  47     if (Elem2ECLeaderMap.find(Element) == Elem2ECLeaderMap.end())
  48       return 0;
  49     else
  50       return Elem2ECLeaderMap[Element];
  51   }
  52
  53   /// Attach the set with Element1 to the set with Element2 adding Element1 and
  54   /// Element2 to the set of equivalence classes if they are not there already.
  55   /// Implication: Make Element1 the element in the smaller set.
  56   void unionElements(ElemTy Element1, ElemTy Element2) {
  57     // If either Element1 or Element2 does not already exist, include it
  58     if (Elem2ECLeaderMap.find(Element1) == Elem2ECLeaderMap.end())
  59       Elem2ECLeaderMap[Element1] = Element1;
  60     if (Elem2ECLeaderMap.find(Element2) == Elem2ECLeaderMap.end())
  61       Elem2ECLeaderMap[Element2] = Element2;
  62
  63     attach(Elem2ECLeaderMap[Element1], Elem2ECLeaderMap[Element2]);
  64   }
  65
  66   // Returns a vector containing all the elements in the equivalent class
  67   // including Element1
  68   vector<ElemTy> getEqClass(ElemTy Element1) {
  69     vector<ElemTy> EqClass;
  70
  71     if (Elem2ECLeaderMap.find(EqClass) == Elem2ECLeaderMap.end())
  72       return EqClass;
  73
  74     ElemTy classLeader = Elem2ECLeaderMap[Element1];
  75
  76     for (typename map<ElemTy, ElemTy>::iterator ElemI =
  77            Elem2ECLeaderMap.begin(), ElemE = Elem2ECLeaderMap.end();
  78          ElemI != ElemE; ++ElemI) {
  79       if (ElemI->second == classLeader)
  80         EqClass.push_back(ElemI->first);
  81     }
  82
  83     return EqClass;
  84
  85   }
  86
  87   map<ElemTy, ElemTy> getLeaderMap() {
  88     return Elem2ECLeaderMap ;
  89   }
  90
  91 };
  92
  93 #endif