LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

EquivalenceClasses.h

Go to the documentation of this file.
00001 //===-- llvm/ADT/EquivalenceClasses.h - Generic Equiv. Classes --*- C++ -*-===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 // 
00010 // Generic implementation of equivalence classes and implementation of
00011 // union-find algorithms A not-so-fancy implementation: 2 level tree i.e root
00012 // and one more level Overhead of a union = size of the equivalence class being
00013 // attached Overhead of a find = 1.
00014 // 
00015 //===----------------------------------------------------------------------===//
00016 
00017 #ifndef LLVM_ADT_EQUIVALENCECLASSES_H
00018 #define LLVM_ADT_EQUIVALENCECLASSES_H
00019 
00020 #include <map>
00021 #include <set>
00022 #include <vector>
00023 
00024 namespace llvm {
00025 
00026 template <class ElemTy>
00027 class EquivalenceClasses {
00028   // Maps each element to the element that is the leader of its 
00029   // equivalence class.
00030   std::map<ElemTy, ElemTy> Elem2LeaderMap;
00031   
00032   // Maintains the set of leaders
00033   std::set<ElemTy> LeaderSet;
00034 
00035   // Caches the equivalence class for each leader
00036   std::map<ElemTy, std::set<ElemTy> > LeaderToEqClassMap;
00037 
00038   // Make Element2 the leader of the union of classes Element1 and Element2
00039   // Element1 and Element2 are presumed to be leaders of their respective
00040   // equivalence classes.
00041   void attach(ElemTy Element1, ElemTy Element2) {
00042     for (typename std::map<ElemTy, ElemTy>::iterator ElemI = 
00043      Elem2LeaderMap.begin(), ElemE = Elem2LeaderMap.end(); 
00044    ElemI != ElemE; ++ElemI) {
00045       if (ElemI->second == Element1)
00046   Elem2LeaderMap[ElemI->first] = Element2;
00047     }
00048   }
00049 
00050 public:
00051   // If an element has not yet in any class, make it a separate new class.
00052   // Return the leader of the class containing the element.
00053   ElemTy addElement (ElemTy NewElement) {
00054     typename std::map<ElemTy, ElemTy>::iterator ElemI = 
00055       Elem2LeaderMap.find(NewElement);
00056     if (ElemI == Elem2LeaderMap.end()) {
00057       Elem2LeaderMap[NewElement] = NewElement;
00058       LeaderSet.insert(NewElement);
00059       return NewElement;
00060     }
00061     else
00062       return ElemI->second;
00063   }
00064   
00065   ElemTy findClass(ElemTy Element) const {
00066     typename std::map<ElemTy, ElemTy>::const_iterator I =
00067       Elem2LeaderMap.find(Element);
00068     return (I == Elem2LeaderMap.end())? (ElemTy) 0 : I->second;
00069   }
00070 
00071   /// Attach the set with Element1 to the set with Element2 adding Element1 and
00072   /// Element2 to the set of equivalence classes if they are not there already.
00073   /// Implication: Make Element1 the element in the smaller set.
00074   /// Take Leader[Element1] out of the set of leaders.
00075   void unionSetsWith(ElemTy Element1, ElemTy Element2) {
00076     // If either Element1 or Element2 does not already exist, include it
00077     const ElemTy& leader1 = addElement(Element1);
00078     const ElemTy& leader2 = addElement(Element2);
00079     assert(leader1 != (ElemTy) 0 && leader2 != (ElemTy) 0);
00080     if (leader1 != leader2) {
00081       attach(leader1, leader2);
00082       LeaderSet.erase(leader1);
00083     }
00084   }
00085   
00086   // Returns a vector containing all the elements in the equivalence class
00087   // including Element1
00088   const std::set<ElemTy> & getEqClass(ElemTy Element1) {
00089     assert(Elem2LeaderMap.find(Element1) != Elem2LeaderMap.end());
00090     const ElemTy classLeader = Elem2LeaderMap[Element1];
00091     
00092     std::set<ElemTy> & EqClass = LeaderToEqClassMap[classLeader];
00093     
00094     // If the EqClass vector is empty, it has not been computed yet: do it now
00095     if (EqClass.empty()) {
00096       for (typename std::map<ElemTy, ElemTy>::iterator
00097              ElemI = Elem2LeaderMap.begin(), ElemE = Elem2LeaderMap.end(); 
00098            ElemI != ElemE; ++ElemI)
00099         if (ElemI->second == classLeader)
00100           EqClass.insert(ElemI->first);
00101       assert(! EqClass.empty());        // must at least include the leader
00102     }
00103     
00104     return EqClass;
00105   }
00106 
00107         std::set<ElemTy>& getLeaderSet()       { return LeaderSet; }
00108   const std::set<ElemTy>& getLeaderSet() const { return LeaderSet; }
00109 
00110         std::map<ElemTy, ElemTy>& getLeaderMap()       { return Elem2LeaderMap;}
00111   const std::map<ElemTy, ElemTy>& getLeaderMap() const { return Elem2LeaderMap;}
00112 };
00113 
00114 } // End llvm namespace
00115 
00116 #endif