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 SUPPORT_EQUIVALENCECLASSES_H
  12 #define SUPPORT_EQUIVALENCECLASSES_H
  13
  14 #include <map>
  15 #include <vector>
  16
  17 template <class ElemTy>
  18 class EquivalenceClasses {
  19   // Maps each element to the element that is the leader of its
  20   // equivalence class.
  21   std::map<ElemTy, ElemTy> Elem2ECLeaderMap;
  22
  23   // Make Element2 the leader of the union of classes Element1 and Element2
  24   // Element1 and Element2 are presumed to be leaders of their respective
  25   // equivalence classes.
  26   void attach(ElemTy Element1, ElemTy Element2) {
  27     for (typename std::map<ElemTy, ElemTy>::iterator ElemI =
  28            Elem2ECLeaderMap.begin(), ElemE = Elem2ECLeaderMap.end();
  29          ElemI != ElemE; ++ElemI) {
  30       if (ElemI->second == Element1)
  31         Elem2ECLeaderMap[ElemI->first] = Element2;
  32     }
  33   }
  34
  35 public:
  36
  37   void addElement (ElemTy NewElement) {
  38     if (Elem2ECLeaderMap.find(NewElement) == Elem2ECLeaderMap.end())
  39       Elem2ECLeaderMap[NewElement] = NewElement;
  40   }
  41
  42   ElemTy findClass(ElemTy Element) {
  43     if (Elem2ECLeaderMap.find(Element) == Elem2ECLeaderMap.end())
  44       return 0;
  45     else
  46       return Elem2ECLeaderMap[Element];
  47   }
  48
  49   /// Attach the set with Element1 to the set with Element2 adding Element1 and
  50   /// Element2 to the set of equivalence classes if they are not there already.
  51   /// Implication: Make Element1 the element in the smaller set.
  52   void unionSetsWith(ElemTy Element1, ElemTy Element2) {
  53     // If either Element1 or Element2 does not already exist, include it
  54     if (Elem2ECLeaderMap.find(Element1) == Elem2ECLeaderMap.end())
  55       Elem2ECLeaderMap[Element1] = Element1;
  56     if (Elem2ECLeaderMap.find(Element2) == Elem2ECLeaderMap.end())
  57       Elem2ECLeaderMap[Element2] = Element2;
  58
  59     attach(Elem2ECLeaderMap[Element1], Elem2ECLeaderMap[Element2]);
  60   }
  61
  62   // Returns a vector containing all the elements in the equivalent class
  63   // including Element1
  64   std::vector<ElemTy> getEqClass(ElemTy Element1) {
  65     std::vector<ElemTy> EqClass;
  66
  67     if (Elem2ECLeaderMap.find(EqClass) == Elem2ECLeaderMap.end())
  68       return EqClass;
  69
  70     ElemTy classLeader = Elem2ECLeaderMap[Element1];
  71
  72     for (typename std::map<ElemTy, ElemTy>::iterator ElemI =
  73            Elem2ECLeaderMap.begin(), ElemE = Elem2ECLeaderMap.end();
  74          ElemI != ElemE; ++ElemI) {
  75       if (ElemI->second == classLeader)
  76         EqClass.push_back(ElemI->first);
  77     }
  78
  79     return EqClass;
  80
  81   }
  82
  83   std::map<ElemTy, ElemTy>& getLeaderMap() {
  84     return Elem2ECLeaderMap ;
  85   }
  86
  87 };
  88
  89 #endif