1218885Sdim//===-- llvm/ADT/IntEqClasses.h - Equiv. Classes of Integers ----*- C++ -*-===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// Equivalence classes for small integers. This is a mapping of the integers 11218885Sdim// 0 .. N-1 into M equivalence classes numbered 0 .. M-1. 12218885Sdim// 13218885Sdim// Initially each integer has its own equivalence class. Classes are joined by 14218885Sdim// passing a representative member of each class to join(). 15218885Sdim// 16218885Sdim// Once the classes are built, compress() will number them 0 .. M-1 and prevent 17218885Sdim// further changes. 18218885Sdim// 19218885Sdim//===----------------------------------------------------------------------===// 20218885Sdim 21218885Sdim#ifndef LLVM_ADT_INTEQCLASSES_H 22218885Sdim#define LLVM_ADT_INTEQCLASSES_H 23218885Sdim 24218885Sdim#include "llvm/ADT/SmallVector.h" 25218885Sdim 26218885Sdimnamespace llvm { 27218885Sdim 28218885Sdimclass IntEqClasses { 29218885Sdim /// EC - When uncompressed, map each integer to a smaller member of its 30218885Sdim /// equivalence class. The class leader is the smallest member and maps to 31218885Sdim /// itself. 32218885Sdim /// 33218885Sdim /// When compressed, EC[i] is the equivalence class of i. 34218885Sdim SmallVector<unsigned, 8> EC; 35218885Sdim 36218885Sdim /// NumClasses - The number of equivalence classes when compressed, or 0 when 37218885Sdim /// uncompressed. 38218885Sdim unsigned NumClasses; 39218885Sdim 40218885Sdimpublic: 41218885Sdim /// IntEqClasses - Create an equivalence class mapping for 0 .. N-1. 42218885Sdim IntEqClasses(unsigned N = 0) : NumClasses(0) { grow(N); } 43218885Sdim 44218885Sdim /// grow - Increase capacity to hold 0 .. N-1, putting new integers in unique 45218885Sdim /// equivalence classes. 46218885Sdim /// This requires an uncompressed map. 47218885Sdim void grow(unsigned N); 48218885Sdim 49218885Sdim /// clear - Clear all classes so that grow() will assign a unique class to 50218885Sdim /// every integer. 51218885Sdim void clear() { 52218885Sdim EC.clear(); 53218885Sdim NumClasses = 0; 54218885Sdim } 55218885Sdim 56218885Sdim /// join - Join the equivalence classes of a and b. After joining classes, 57218885Sdim /// findLeader(a) == findLeader(b). 58218885Sdim /// This requires an uncompressed map. 59218885Sdim void join(unsigned a, unsigned b); 60218885Sdim 61218885Sdim /// findLeader - Compute the leader of a's equivalence class. This is the 62218885Sdim /// smallest member of the class. 63218885Sdim /// This requires an uncompressed map. 64218885Sdim unsigned findLeader(unsigned a) const; 65218885Sdim 66218885Sdim /// compress - Compress equivalence classes by numbering them 0 .. M. 67218885Sdim /// This makes the equivalence class map immutable. 68218885Sdim void compress(); 69218885Sdim 70218885Sdim /// getNumClasses - Return the number of equivalence classes after compress() 71218885Sdim /// was called. 72218885Sdim unsigned getNumClasses() const { return NumClasses; } 73218885Sdim 74218885Sdim /// operator[] - Return a's equivalence class number, 0 .. getNumClasses()-1. 75218885Sdim /// This requires a compressed map. 76218885Sdim unsigned operator[](unsigned a) const { 77218885Sdim assert(NumClasses && "operator[] called before compress()"); 78218885Sdim return EC[a]; 79218885Sdim } 80218885Sdim 81218885Sdim /// uncompress - Change back to the uncompressed representation that allows 82218885Sdim /// editing. 83218885Sdim void uncompress(); 84218885Sdim}; 85218885Sdim 86218885Sdim} // End llvm namespace 87218885Sdim 88218885Sdim#endif 89