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