include/llvm/ADT/EquivalenceClasses.h

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