include/Support/BitSetVector.h

   1 //===-- BitVectorSet.h - A bit-vector representation of sets -----*- C++ -*--=//
   2 //
   3 // class BitVectorSet --
   4 //
   5 // An implementation of the bit-vector representation of sets.
   6 // Unlike vector<bool>, this allows much more efficient parallel set
   7 // operations on bits, by using the bitset template .  The bitset template
   8 // unfortunately can only represent sets with a size chosen at compile-time.
   9 // We therefore use a vector of bitsets.  The maxmimum size of our sets
  10 // (i.e., the size of the universal set) can be chosen at creation time.
  11 //
  12 // External functions:
  13 //
  14 // bool Disjoint(const BitSetVector& set1, const BitSetVector& set2):
  15 //    Tests if two sets have an empty intersection.
  16 //    This is more efficient than !(set1 & set2).any().
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #ifndef SUPPORT_BITSETVECTOR_H
  21 #define SUPPORT_BITSETVECTOR_H
  22
  23 #include <bitset>
  24 #include <vector>
  25 #include <functional>
  26 #include <iostream>
  27
  28 class BitSetVector {
  29   enum { BITSET_WORDSIZE = sizeof(long)*8 };
  30
  31   // Types used internal to the representation
  32   typedef std::bitset<BITSET_WORDSIZE> bitword;
  33   typedef bitword::reference reference;
  34   class iterator;
  35
  36   // Data used in the representation
  37   std::vector<bitword> bitsetVec;
  38   unsigned maxSize;
  39
  40 private:
  41   // Utility functions for the representation
  42   static unsigned NumWords(unsigned Size) {
  43     return (Size+BITSET_WORDSIZE-1)/BITSET_WORDSIZE;
  44   }
  45   static unsigned LastWordSize(unsigned Size) { return Size % BITSET_WORDSIZE; }
  46
  47   // Clear the unused bits in the last word.
  48   // The unused bits are the high (BITSET_WORDSIZE - LastWordSize()) bits
  49   void ClearUnusedBits() {
  50     unsigned long usedBits = (1U << LastWordSize(size())) - 1;
  51     bitsetVec.back() &= bitword(usedBits);
  52   }
  53
  54   const bitword& getWord(unsigned i) const { return bitsetVec[i]; }
  55         bitword& getWord(unsigned i)       { return bitsetVec[i]; }
  56
  57   friend bool Disjoint(const BitSetVector& set1,
  58                        const BitSetVector& set2);
  59
  60   BitSetVector();                       // do not implement!
  61
  62 public:
  63   ///
  64   /// Constructor: create a set of the maximum size maxSetSize.
  65   /// The set is initialized to empty.
  66   ///
  67   BitSetVector(unsigned maxSetSize)
  68     : bitsetVec(NumWords(maxSetSize)), maxSize(maxSetSize) { }
  69
  70   /// size - Return the number of bits tracked by this bit vector...
  71   unsigned size() const { return maxSize; }
  72
  73   ///
  74   ///  Modifier methods: reset, set for entire set, operator[] for one element.
  75   ///
  76   void reset() {
  77     for (unsigned i=0, N = bitsetVec.size(); i < N; ++i)
  78       bitsetVec[i].reset();
  79   }
  80   void set() {
  81     for (unsigned i=0, N = bitsetVec.size(); i < N; ++i) // skip last word
  82       bitsetVec[i].set();
  83     ClearUnusedBits();
  84   }
  85   reference operator[](unsigned n) {
  86     assert(n  < size() && "BitSetVector: Bit number out of range");
  87     unsigned ndiv = n / BITSET_WORDSIZE, nmod = n % BITSET_WORDSIZE;
  88     return bitsetVec[ndiv][nmod];
  89   }
  90   iterator begin() { return iterator::begin(*this); }
  91   iterator end()   { return iterator::end(*this);   }
  92
  93   ///
  94   ///  Comparison operations: equal, not equal
  95   ///
  96   bool operator == (const BitSetVector& set2) const {
  97     assert(maxSize == set2.maxSize && "Illegal == comparison");
  98     for (unsigned i = 0; i < bitsetVec.size(); ++i)
  99       if (getWord(i) != set2.getWord(i))
 100         return false;
 101     return true;
 102   }
 103   bool operator != (const BitSetVector& set2) const {
 104     return ! (*this == set2);
 105   }
 106
 107   ///
 108   ///  Set membership operations: single element, any, none, count
 109   ///
 110   bool test(unsigned n) const {
 111     assert(n  < size() && "BitSetVector: Bit number out of range");
 112     unsigned ndiv = n / BITSET_WORDSIZE, nmod = n % BITSET_WORDSIZE;
 113     return bitsetVec[ndiv].test(nmod);
 114   }
 115   bool any() const {
 116     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 117       if (bitsetVec[i].any())
 118         return true;
 119     return false;
 120   }
 121   bool none() const {
 122     return ! any();
 123   }
 124   unsigned count() const {
 125     unsigned n = 0;
 126     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 127       n += bitsetVec[i].count();
 128     return n;
 129   }
 130   bool all() const {
 131     return (count() == size());
 132   }
 133
 134   ///
 135   ///  Set operations: intersection, union, disjoint union, complement.
 136   ///
 137   BitSetVector operator& (const BitSetVector& set2) const {
 138     assert(maxSize == set2.maxSize && "Illegal intersection");
 139     BitSetVector result(maxSize);
 140     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 141       result.getWord(i) = getWord(i) & set2.getWord(i);
 142     return result;
 143   }
 144   BitSetVector operator| (const BitSetVector& set2) const {
 145     assert(maxSize == set2.maxSize && "Illegal intersection");
 146     BitSetVector result(maxSize);
 147     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 148       result.getWord(i) = getWord(i) | set2.getWord(i);
 149     return result;
 150   }
 151   BitSetVector operator^ (const BitSetVector& set2) const {
 152     assert(maxSize == set2.maxSize && "Illegal intersection");
 153     BitSetVector result(maxSize);
 154     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 155       result.getWord(i) = getWord(i) ^ set2.getWord(i);
 156     return result;
 157   }
 158   BitSetVector operator~ () const {
 159     BitSetVector result(maxSize);
 160     for (unsigned i = 0; i < bitsetVec.size(); ++i)
 161       (result.getWord(i) = getWord(i)).flip();
 162     result.ClearUnusedBits();
 163     return result;
 164   }
 165
 166   ///
 167   ///  Printing and debugging support
 168   ///
 169   void print(std::ostream &O) const;
 170   void dump() const { print(std::cerr); }
 171
 172 public:
 173   //
 174   // An iterator to enumerate the bits in a BitSetVector.
 175   // Eventually, this needs to inherit from bidirectional_iterator.
 176   // But this iterator may not be as useful as I once thought and
 177   // may just go away.
 178   //
 179   class iterator {
 180     unsigned   currentBit;
 181     unsigned   currentWord;
 182     BitSetVector* bitvec;
 183     iterator(unsigned B, unsigned W, BitSetVector& _bitvec)
 184       : currentBit(B), currentWord(W), bitvec(&_bitvec) { }
 185   public:
 186     iterator(BitSetVector& _bitvec)
 187       : currentBit(0), currentWord(0), bitvec(&_bitvec) { }
 188     iterator(const iterator& I)
 189       : currentBit(I.currentBit),currentWord(I.currentWord),bitvec(I.bitvec) { }
 190     iterator& operator=(const iterator& I) {
 191       currentWord = I.currentWord;
 192       currentBit = I.currentBit;
 193       bitvec = I.bitvec;
 194       return *this;
 195     }
 196
 197     // Increment and decrement operators (pre and post)
 198     iterator& operator++() {
 199       if (++currentBit == BITSET_WORDSIZE)
 200         { currentBit = 0; if (currentWord < bitvec->size()) ++currentWord; }
 201       return *this;
 202     }
 203     iterator& operator--() {
 204       if (currentBit == 0) {
 205         currentBit = BITSET_WORDSIZE-1;
 206         currentWord = (currentWord == 0)? bitvec->size() : --currentWord;
 207       }
 208       else
 209         --currentBit;
 210       return *this;
 211     }
 212     iterator operator++(int) { iterator copy(*this); ++*this; return copy; }
 213     iterator operator--(int) { iterator copy(*this); --*this; return copy; }
 214
 215     // Dereferencing operators
 216     reference operator*() {
 217       assert(currentWord < bitvec->size() &&
 218              "Dereferencing iterator past the end of a BitSetVector");
 219       return bitvec->getWord(currentWord)[currentBit];
 220     }
 221
 222     // Comparison operator
 223     bool operator==(const iterator& I) {
 224       return (I.bitvec == bitvec &&
 225               I.currentWord == currentWord && I.currentBit == currentBit);
 226     }
 227
 228   protected:
 229     static iterator begin(BitSetVector& _bitvec) { return iterator(_bitvec); }
 230     static iterator end(BitSetVector& _bitvec)   { return iterator(0,
 231                                                     _bitvec.size(), _bitvec); }
 232     friend class BitSetVector;
 233   };
 234 };
 235
 236
 237 inline void BitSetVector::print(std::ostream& O) const
 238 {
 239   for (std::vector<bitword>::const_iterator
 240          I=bitsetVec.begin(), E=bitsetVec.end(); I != E; ++I)
 241     O << "<" << (*I) << ">" << (I+1 == E? "\n" : ", ");
 242 }
 243
 244 inline std::ostream& operator<< (std::ostream& O, const BitSetVector& bset)
 245 {
 246   bset.print(O);
 247   return O;
 248 };
 249
 250
 251 ///
 252 /// Optimized versions of fundamental comparison operations
 253 ///
 254 inline bool Disjoint(const BitSetVector& set1,
 255                      const BitSetVector& set2)
 256 {
 257   assert(set1.size() == set2.size() && "Illegal intersection");
 258   for (unsigned i = 0; i < set1.bitsetVec.size(); ++i)
 259     if ((set1.getWord(i) & set2.getWord(i)).any())
 260       return false;
 261   return true;
 262 }
 263
 264 #endif