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