include/llvm/ADT/SparseBitVector.h

   1 //===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector -*- C++ -*- ===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Daniel Berlin and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the SparseBitVector class.  See the doxygen comment for
  11 // SparseBitVector for more details on the algorithm used.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_ADT_SPARSEBITVECTOR_H
  16 #define LLVM_ADT_SPARSEBITVECTOR_H
  17
  18 #include <cassert>
  19 #include <cstring>
  20 #include <list>
  21 #include <algorithm>
  22 #include "llvm/Support/DataTypes.h"
  23 #include "llvm/ADT/STLExtras.h"
  24 #include "llvm/Support/MathExtras.h"
  25
  26 namespace llvm {
  27
  28 /// SparseBitVector is an implementation of a bitvector that is sparse by only
  29 /// storing the elements that have non-zero bits set.  In order to make this
  30 /// fast for the most common cases, SparseBitVector is implemented as a linked
  31 /// list of SparseBitVectorElements.  We maintain a pointer to the last
  32 /// SparseBitVectorElement accessed (in the form of a list iterator), in order
  33 /// to make multiple in-order test/set constant time after the first one is
  34 /// executed.  Note that using vectors to store SparseBitVectorElement's does
  35 /// not work out very well because it causes insertion in the middle to take
  36 /// enormous amounts of time with a large amount of bits.  Other structures that
  37 /// have better worst cases for insertion in the middle (various balanced trees,
  38 /// etc) do not perform as well in practice as a linked list with this iterator
  39 /// kept up to date.  They are also significantly more memory intensive.
  40
  41
  42 template <unsigned ElementSize = 128>
  43 struct SparseBitVectorElement {
  44 public:
  45   typedef unsigned long BitWord;
  46   enum {
  47     BITWORD_SIZE = sizeof(BitWord) * 8,
  48     BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
  49     BITS_PER_ELEMENT = ElementSize
  50   };
  51 private:
  52   // Index of Element in terms of where first bit starts.
  53   unsigned ElementIndex;
  54   BitWord Bits[BITWORDS_PER_ELEMENT];
  55   SparseBitVectorElement();
  56 public:
  57   explicit SparseBitVectorElement(unsigned Idx) {
  58     ElementIndex = Idx;
  59     memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
  60   }
  61
  62   ~SparseBitVectorElement() {
  63   }
  64
  65   // Copy ctor.
  66   SparseBitVectorElement(const SparseBitVectorElement &RHS) {
  67     ElementIndex = RHS.ElementIndex;
  68     std::copy(&RHS.Bits[0], &RHS.Bits[BITWORDS_PER_ELEMENT], Bits);
  69   }
  70
  71   // Comparison.
  72   bool operator==(const SparseBitVectorElement &RHS) const {
  73     if (ElementIndex != RHS.ElementIndex)
  74       return false;
  75     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
  76       if (Bits[i] != RHS.Bits[i])
  77         return false;
  78     return true;
  79   }
  80
  81   bool operator!=(const SparseBitVectorElement &RHS) const {
  82     return !(*this == RHS);
  83   }
  84
  85   // Return the bits that make up word Idx in our element.
  86   BitWord word(unsigned Idx) const {
  87     assert (Idx < BITWORDS_PER_ELEMENT);
  88     return Bits[Idx];
  89   }
  90
  91   unsigned index() const {
  92     return ElementIndex;
  93   }
  94
  95   bool empty() const {
  96     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
  97       if (Bits[i])
  98         return false;
  99     return true;
 100   }
 101
 102   void set(unsigned Idx) {
 103     Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
 104   }
 105
 106   bool test_and_set (unsigned Idx) {
 107     bool old = test(Idx);
 108     if (!old)
 109       set(Idx);
 110     return !old;
 111   }
 112
 113   void reset(unsigned Idx) {
 114     Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
 115   }
 116
 117   bool test(unsigned Idx) const {
 118     return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
 119   }
 120
 121   unsigned count() const {
 122     unsigned NumBits = 0;
 123     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 124       if (sizeof(BitWord) == 4)
 125         NumBits += CountPopulation_32(Bits[i]);
 126       else if (sizeof(BitWord) == 8)
 127         NumBits += CountPopulation_64(Bits[i]);
 128       else
 129         assert(0 && "Unsupported!");
 130     return NumBits;
 131   }
 132
 133   /// find_first - Returns the index of the first set bit.
 134   int find_first() const {
 135     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
 136       if (Bits[i] != 0) {
 137         if (sizeof(BitWord) == 4)
 138           return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
 139         else if (sizeof(BitWord) == 8)
 140           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
 141         else
 142           assert(0 && "Unsupported!");
 143       }
 144     assert(0 && "Illegal empty element");
 145   }
 146
 147   /// find_next - Returns the index of the next set bit following the
 148   /// "Prev" bit. Returns -1 if the next set bit is not found.
 149   int find_next(unsigned Prev) const {
 150     ++Prev;
 151     if (Prev >= BITS_PER_ELEMENT)
 152       return -1;
 153
 154     unsigned WordPos = Prev / BITWORD_SIZE;
 155     unsigned BitPos = Prev % BITWORD_SIZE;
 156     BitWord Copy = Bits[WordPos];
 157     assert (WordPos <= BITWORDS_PER_ELEMENT
 158             && "Word Position outside of element");
 159
 160     // Mask off previous bits.
 161     Copy &= ~0L << BitPos;
 162
 163     if (Copy != 0) {
 164       if (sizeof(BitWord) == 4)
 165         return WordPos * BITWORD_SIZE + CountTrailingZeros_32(Copy);
 166       else if (sizeof(BitWord) == 8)
 167         return WordPos * BITWORD_SIZE + CountTrailingZeros_64(Copy);
 168       else
 169         assert(0 && "Unsupported!");
 170     }
 171
 172     // Check subsequent words.
 173     for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
 174       if (Bits[i] != 0) {
 175         if (sizeof(BitWord) == 4)
 176           return i * BITWORD_SIZE + CountTrailingZeros_32(Bits[i]);
 177         else if (sizeof(BitWord) == 8)
 178           return i * BITWORD_SIZE + CountTrailingZeros_64(Bits[i]);
 179         else
 180           assert(0 && "Unsupported!");
 181       }
 182     return -1;
 183   }
 184
 185   // Union this element with RHS and return true if this one changed.
 186   bool unionWith(const SparseBitVectorElement &RHS) {
 187     bool changed = false;
 188     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 189       BitWord old = changed ? 0 : Bits[i];
 190
 191       Bits[i] |= RHS.Bits[i];
 192       if (old != Bits[i])
 193         changed = true;
 194     }
 195     return changed;
 196   }
 197
 198   // Return true if we have any bits in common with RHS
 199   bool intersects(const SparseBitVectorElement &RHS) const {
 200     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 201       if (RHS.Bits[i] & Bits[i])
 202         return true;
 203     }
 204     return false;
 205   }
 206
 207   // Intersect this Element with RHS and return true if this one changed.
 208   // BecameZero is set to true if this element became all-zero bits.
 209   bool intersectWith(const SparseBitVectorElement &RHS,
 210                      bool &BecameZero) {
 211     bool changed = false;
 212     bool allzero = true;
 213
 214     BecameZero = false;
 215     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 216       BitWord old = changed ? 0 : Bits[i];
 217
 218       Bits[i] &= RHS.Bits[i];
 219       if (Bits[i] != 0)
 220         allzero = false;
 221
 222       if (old != Bits[i])
 223         changed = true;
 224     }
 225     BecameZero = !allzero;
 226     return changed;
 227   }
 228   // Intersect this Element with the complement of RHS and return true if this
 229   // one changed.  BecameZero is set to true if this element became all-zero
 230   // bits.
 231   bool intersectWithComplement(const SparseBitVectorElement &RHS,
 232                      bool &BecameZero) {
 233     bool changed = false;
 234     bool allzero = true;
 235
 236     BecameZero = false;
 237     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 238       BitWord old = changed ? 0 : Bits[i];
 239
 240       Bits[i] &= ~RHS.Bits[i];
 241       if (Bits[i] != 0)
 242         allzero = false;
 243
 244       if (old != Bits[i])
 245         changed = true;
 246     }
 247     BecameZero = !allzero;
 248     return changed;
 249   }
 250   // Three argument version of intersectWithComplement that intersects
 251   // RHS1 & ~RHS2 into this element
 252   void intersectWithComplement(const SparseBitVectorElement &RHS1,
 253                                const SparseBitVectorElement &RHS2,
 254                                bool &BecameZero) {
 255     bool allzero = true;
 256
 257     BecameZero = false;
 258     for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
 259       Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
 260       if (Bits[i] != 0)
 261         allzero = false;
 262     }
 263     BecameZero = !allzero;
 264   }
 265
 266 };
 267
 268 template <unsigned ElementSize = 128>
 269 class SparseBitVector {
 270   typedef std::list<SparseBitVectorElement<ElementSize> *> ElementList;
 271   typedef typename ElementList::iterator ElementListIter;
 272   typedef typename ElementList::const_iterator ElementListConstIter;
 273   enum {
 274     BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
 275   };
 276
 277   // Pointer to our current Element.
 278   ElementListIter CurrElementIter;
 279   ElementList Elements;
 280
 281   // This is like std::lower_bound, except we do linear searching from the
 282   // current position.
 283   ElementListIter FindLowerBound(unsigned ElementIndex) {
 284
 285     if (Elements.empty()) {
 286       CurrElementIter = Elements.begin();
 287       return Elements.begin();
 288     }
 289
 290     // Make sure our current iterator is valid.
 291     if (CurrElementIter == Elements.end())
 292       --CurrElementIter;
 293
 294     // Search from our current iterator, either backwards or forwards,
 295     // depending on what element we are looking for.
 296     ElementListIter ElementIter = CurrElementIter;
 297     if ((*CurrElementIter)->index() == ElementIndex) {
 298       return ElementIter;
 299     } else if ((*CurrElementIter)->index() > ElementIndex) {
 300       while (ElementIter != Elements.begin()
 301              && (*ElementIter)->index() > ElementIndex)
 302         --ElementIter;
 303     } else {
 304       while (ElementIter != Elements.end() &&
 305              (*ElementIter)->index() <= ElementIndex)
 306         ++ElementIter;
 307       --ElementIter;
 308     }
 309     CurrElementIter = ElementIter;
 310     return ElementIter;
 311   }
 312
 313   // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
 314   // than it would be, in order to be efficient.
 315   class SparseBitVectorIterator {
 316   private:
 317     bool AtEnd;
 318
 319     const SparseBitVector<ElementSize> *BitVector;
 320
 321     // Current element inside of bitmap.
 322     ElementListConstIter Iter;
 323
 324     // Current bit number inside of our bitmap.
 325     unsigned BitNumber;
 326
 327     // Current word number inside of our element.
 328     unsigned WordNumber;
 329
 330     // Current bits from the element.
 331     typename SparseBitVectorElement<ElementSize>::BitWord Bits;
 332
 333     // Move our iterator to the first non-zero bit in the bitmap.
 334     void AdvanceToFirstNonZero() {
 335       if (AtEnd)
 336         return;
 337       if (BitVector->Elements.empty()) {
 338         AtEnd = true;
 339         return;
 340       }
 341       Iter = BitVector->Elements.begin();
 342       BitNumber = (*Iter)->index() * ElementSize;
 343       unsigned BitPos = (*Iter)->find_first();
 344       BitNumber += BitPos;
 345       WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
 346       Bits = (*Iter)->word(WordNumber);
 347       Bits >>= BitPos % BITWORD_SIZE;
 348     }
 349
 350     // Move our iterator to the next non-zero bit.
 351     void AdvanceToNextNonZero() {
 352       if (AtEnd)
 353         return;
 354
 355       while (Bits && !(Bits & 1)) {
 356         Bits >>= 1;
 357         BitNumber += 1;
 358       }
 359
 360       // See if we ran out of Bits in this word.
 361       if (!Bits) {
 362         int NextSetBitNumber = (*Iter)->find_next(BitNumber % ElementSize) ;
 363         // If we ran out of set bits in this element, move to next element.
 364         if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
 365           ++Iter;
 366           WordNumber = 0;
 367
 368           // We may run out of elements in the bitmap.
 369           if (Iter == BitVector->Elements.end()) {
 370             AtEnd = true;
 371             return;
 372           }
 373           // Set up for next non zero word in bitmap.
 374           BitNumber = (*Iter)->index() * ElementSize;
 375           NextSetBitNumber = (*Iter)->find_first();
 376           BitNumber += NextSetBitNumber;
 377           WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
 378           Bits = (*Iter)->word(WordNumber);
 379           Bits >>= NextSetBitNumber % BITWORD_SIZE;
 380         } else {
 381           WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
 382           Bits = (*Iter)->word(WordNumber);
 383           Bits >>= NextSetBitNumber % BITWORD_SIZE;
 384         }
 385       }
 386     }
 387   public:
 388     // Preincrement.
 389     inline SparseBitVectorIterator& operator++() {
 390       ++BitNumber;
 391       Bits >>= 1;
 392       AdvanceToNextNonZero();
 393       return *this;
 394     }
 395
 396     // Postincrement.
 397     inline SparseBitVectorIterator operator++(int) {
 398       SparseBitVectorIterator tmp = *this;
 399       ++*this;
 400       return tmp;
 401     }
 402
 403     // Return the current set bit number.
 404     unsigned operator*() const {
 405       return BitNumber;
 406     }
 407
 408     bool operator==(const SparseBitVectorIterator &RHS) const {
 409       // If they are both at the end, ignore the rest of the fields.
 410       if (AtEnd == RHS.AtEnd)
 411         return true;
 412       // Otherwise they are the same if they have the same bit number and
 413       // bitmap.
 414       return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
 415     }
 416     bool operator!=(const SparseBitVectorIterator &RHS) const {
 417       return !(*this == RHS);
 418     }
 419     SparseBitVectorIterator(): BitVector(NULL) {
 420     }
 421
 422
 423     SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
 424                             bool end = false):BitVector(RHS) {
 425       Iter = BitVector->Elements.begin();
 426       BitNumber = 0;
 427       Bits = 0;
 428       WordNumber = ~0;
 429       AtEnd = end;
 430       AdvanceToFirstNonZero();
 431     }
 432   };
 433 public:
 434   typedef SparseBitVectorIterator iterator;
 435
 436   SparseBitVector () {
 437     CurrElementIter = Elements.begin ();
 438   }
 439
 440   ~SparseBitVector() {
 441     for_each(Elements.begin(), Elements.end(),
 442              deleter<SparseBitVectorElement<ElementSize> >);
 443   }
 444
 445   // SparseBitVector copy ctor.
 446   SparseBitVector(const SparseBitVector &RHS) {
 447     ElementListConstIter ElementIter = RHS.Elements.begin();
 448     while (ElementIter != RHS.Elements.end()) {
 449       SparseBitVectorElement<ElementSize> *ElementCopy;
 450       ElementCopy = new SparseBitVectorElement<ElementSize>(*(*ElementIter));
 451       Elements.push_back(ElementCopy);
 452     }
 453
 454     CurrElementIter = Elements.begin ();
 455   }
 456
 457   // Test, Reset, and Set a bit in the bitmap.
 458   bool test(unsigned Idx) {
 459     if (Elements.empty())
 460       return false;
 461
 462     unsigned ElementIndex = Idx / ElementSize;
 463     ElementListIter ElementIter = FindLowerBound(ElementIndex);
 464
 465     // If we can't find an element that is supposed to contain this bit, there
 466     // is nothing more to do.
 467     if (ElementIter == Elements.end() ||
 468         (*ElementIter)->index() != ElementIndex)
 469       return false;
 470     return (*ElementIter)->test(Idx % ElementSize);
 471   }
 472
 473   void reset(unsigned Idx) {
 474     if (Elements.empty())
 475       return;
 476
 477     unsigned ElementIndex = Idx / ElementSize;
 478     ElementListIter ElementIter = FindLowerBound(ElementIndex);
 479
 480     // If we can't find an element that is supposed to contain this bit, there
 481     // is nothing more to do.
 482     if (ElementIter == Elements.end() ||
 483         (*ElementIter)->index() != ElementIndex)
 484       return;
 485     (*ElementIter)->reset(Idx % ElementSize);
 486
 487     // When the element is zeroed out, delete it.
 488     if ((*ElementIter)->empty()) {
 489       delete (*ElementIter);
 490       ++CurrElementIter;
 491       Elements.erase(ElementIter);
 492     }
 493   }
 494
 495   void set(unsigned Idx) {
 496     SparseBitVectorElement<ElementSize> *Element;
 497     unsigned ElementIndex = Idx / ElementSize;
 498
 499     if (Elements.empty()) {
 500       Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 501       Elements.push_back(Element);
 502     } else {
 503       ElementListIter ElementIter = FindLowerBound(ElementIndex);
 504
 505       if (ElementIter != Elements.end() &&
 506           (*ElementIter)->index() == ElementIndex)
 507         Element = *ElementIter;
 508       else {
 509         Element = new SparseBitVectorElement<ElementSize>(ElementIndex);
 510         // Insert does insert before, and lower bound gives the one before.
 511         Elements.insert(++ElementIter, Element);
 512       }
 513     }
 514     Element->set(Idx % ElementSize);
 515   }
 516
 517   bool test_and_set (unsigned Idx) {
 518     bool old = test(Idx);
 519     if (!old)
 520       set(Idx);
 521     return !old;
 522   }
 523
 524   // Union our bitmap with the RHS and return true if we changed.
 525   bool operator|=(const SparseBitVector &RHS) {
 526     bool changed = false;
 527     ElementListIter Iter1 = Elements.begin();
 528     ElementListConstIter Iter2 = RHS.Elements.begin();
 529
 530     // IE They may both be end
 531     if (Iter1 == Iter2)
 532       return false;
 533
 534     // See if the first bitmap element is the same in both.  This is only
 535     // possible if they are the same bitmap.
 536     if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
 537       if (*Iter1 == *Iter2)
 538         return false;
 539
 540     while (Iter2 != RHS.Elements.end()) {
 541       if (Iter1 == Elements.end() || (*Iter1)->index() > (*Iter2)->index()) {
 542         SparseBitVectorElement<ElementSize> *NewElem;
 543
 544         NewElem = new SparseBitVectorElement<ElementSize>(*(*Iter2));
 545         Elements.insert(Iter1, NewElem);
 546         ++Iter2;
 547         changed = true;
 548       } else if ((*Iter1)->index() == (*Iter2)->index()) {
 549         changed |= (*Iter1)->unionWith(*(*Iter2));
 550         ++Iter1;
 551         ++Iter2;
 552       } else {
 553         ++Iter1;
 554       }
 555     }
 556     CurrElementIter = Elements.begin();
 557     return changed;
 558   }
 559
 560   // Intersect our bitmap with the RHS and return true if ours changed.
 561   bool operator&=(const SparseBitVector &RHS) {
 562     bool changed = false;
 563     ElementListIter Iter1 = Elements.begin();
 564     ElementListConstIter Iter2 = RHS.Elements.begin();
 565
 566     // IE They may both be end.
 567     if (Iter1 == Iter2)
 568       return false;
 569
 570     // See if the first bitmap element is the same in both.  This is only
 571     // possible if they are the same bitmap.
 572     if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
 573       if (*Iter1 == *Iter2)
 574         return false;
 575
 576     // Loop through, intersecting as we go, erasing elements when necessary.
 577     while (Iter2 != RHS.Elements.end()) {
 578       if (Iter1 == Elements.end())
 579         return changed;
 580
 581       if ((*Iter1)->index() > (*Iter2)->index()) {
 582         ++Iter2;
 583       } else if ((*Iter1)->index() == (*Iter2)->index()) {
 584         bool BecameZero;
 585         changed |= (*Iter1)->intersectWith(*(*Iter2), BecameZero);
 586         if (BecameZero) {
 587           ElementListIter IterTmp = Iter1;
 588           delete *IterTmp;
 589           Elements.erase(IterTmp);
 590         }
 591         ++Iter1;
 592         ++Iter2;
 593       } else {
 594         ElementListIter IterTmp = Iter1;
 595         ++Iter1;
 596         delete *IterTmp;
 597         Elements.erase(IterTmp);
 598       }
 599     }
 600     for_each(Iter1, Elements.end(),
 601              deleter<SparseBitVectorElement<ElementSize> >);
 602     Elements.erase(Iter1, Elements.end());
 603     CurrElementIter = Elements.begin();
 604     return changed;
 605   }
 606
 607   // Intersect our bitmap with the complement of the RHS and return true if ours
 608   // changed.
 609   bool intersectWithComplement(const SparseBitVector &RHS) {
 610     bool changed = false;
 611     ElementListIter Iter1 = Elements.begin();
 612     ElementListConstIter Iter2 = RHS.Elements.begin();
 613
 614     // IE They may both be end.
 615     if (Iter1 == Iter2)
 616       return false;
 617
 618     // See if the first bitmap element is the same in both.  This is only
 619     // possible if they are the same bitmap.
 620     if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
 621       if (*Iter1 == *Iter2) {
 622         for_each(Elements.begin(), Elements.end(),
 623                  deleter<SparseBitVectorElement<ElementSize> >);
 624         Elements.clear();
 625         return true;
 626       }
 627
 628     // Loop through, intersecting as we go, erasing elements when necessary.
 629     while (Iter2 != RHS.Elements.end()) {
 630       if (Iter1 == Elements.end())
 631         return changed;
 632
 633       if ((*Iter1)->index() > (*Iter2)->index()) {
 634         ++Iter2;
 635       } else if ((*Iter1)->index() == (*Iter2)->index()) {
 636         bool BecameZero;
 637         changed |= (*Iter1)->intersectWithComplement(*(*Iter2), BecameZero);
 638         if (BecameZero) {
 639           ElementListIter IterTmp = Iter1;
 640           delete *IterTmp;
 641           Elements.erase(IterTmp);
 642         }
 643         ++Iter1;
 644         ++Iter2;
 645       } else {
 646         ElementListIter IterTmp = Iter1;
 647         ++Iter1;
 648         delete *IterTmp;
 649         Elements.erase(IterTmp);
 650       }
 651     }
 652     CurrElementIter = Elements.begin();
 653     return changed;
 654   }
 655
 656   bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
 657     return intersectWithComplement(*RHS);
 658   }
 659
 660
 661   //  Three argument version of intersectWithComplement.  Result of RHS1 & ~RHS2
 662   //  is stored into this bitmap.
 663   void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
 664                                const SparseBitVector<ElementSize> &RHS2)
 665   {
 666     for_each(Elements.begin(), Elements.end(),
 667              deleter<SparseBitVectorElement<ElementSize> >);
 668     Elements.clear();
 669
 670     ElementListConstIter Iter1 = RHS1.Elements.begin();
 671     ElementListConstIter Iter2 = RHS2.Elements.begin();
 672
 673     // IE They may both be end.
 674     if (Iter1 == Iter2)
 675       return;
 676
 677     // See if the first bitmap element is the same in both.  This is only
 678     // possible if they are the same bitmap.
 679     if (Iter1 != RHS1.Elements.end() && Iter2 != RHS2.Elements.end())
 680       if (*Iter1 == *Iter2) {
 681         return;
 682       }
 683
 684     // Loop through, intersecting as we go, erasing elements when necessary.
 685     while (Iter2 != RHS2.Elements.end()) {
 686       if (Iter1 == RHS1.Elements.end())
 687         return;
 688
 689       if ((*Iter1)->index() > (*Iter2)->index()) {
 690         ++Iter2;
 691       } else if ((*Iter1)->index() == (*Iter2)->index()) {
 692         bool BecameZero = false;
 693         SparseBitVectorElement<ElementSize> *NewElement =
 694           new SparseBitVectorElement<ElementSize>((*Iter1)->index());
 695
 696         NewElement->intersectWithComplement(*(*Iter1), *(*Iter2), BecameZero);
 697         if (BecameZero) {
 698           delete NewElement;
 699         } else {
 700           Elements.push_back(NewElement);
 701         }
 702
 703         ++Iter1;
 704         ++Iter2;
 705       } else {
 706         ++Iter1;
 707       }
 708     }
 709     // copy the remaining elements
 710
 711     while (Iter1 != RHS1.Elements.end()) {
 712         SparseBitVectorElement<ElementSize> *NewElement =
 713           new SparseBitVectorElement<ElementSize>(*(*Iter1));
 714         Elements.push_back(NewElement);
 715       }
 716
 717     CurrElementIter = Elements.begin();
 718     return;
 719   }
 720
 721   void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
 722                                const SparseBitVector<ElementSize> *RHS2) {
 723     intersectWithComplement(*RHS1, *RHS2);
 724   }
 725
 726   bool intersects(const SparseBitVector<ElementSize> *RHS) const {
 727     return intersects(*RHS);
 728   }
 729
 730   // Return true if we share any bits in common with RHS
 731   bool intersects(const SparseBitVector<ElementSize> &RHS) const {
 732     ElementListConstIter Iter1 = Elements.begin();
 733     ElementListConstIter Iter2 = RHS.Elements.begin();
 734
 735     // IE They may both be end.
 736     if (Iter1 == Iter2)
 737       return false;
 738
 739     // See if the first bitmap element is the same in both.  This is only
 740     // possible if they are the same bitmap.
 741     if (Iter1 != Elements.end() && Iter2 != RHS.Elements.end())
 742       if (*Iter1 == *Iter2) {
 743         return true;
 744       }
 745
 746     // Loop through, intersecting stopping when we hit bits in common.
 747     while (Iter2 != RHS.Elements.end()) {
 748       if (Iter1 == Elements.end())
 749         return false;
 750
 751       if ((*Iter1)->index() > (*Iter2)->index()) {
 752         ++Iter2;
 753       } else if ((*Iter1)->index() == (*Iter2)->index()) {
 754         if ((*Iter1)->intersects(*(*Iter2)))
 755           return true;
 756         ++Iter1;
 757         ++Iter2;
 758       } else {
 759         ++Iter1;
 760       }
 761     }
 762     return false;
 763   }
 764
 765   // Return the first set bit in the bitmap.  Return -1 if no bits are set.
 766   int find_first() const {
 767     if (Elements.empty())
 768       return -1;
 769     const SparseBitVectorElement<ElementSize> *First = *(Elements.begin());
 770     return (First->index() * ElementSize) + First->find_first();
 771   }
 772
 773   // Return true if the SparseBitVector is empty
 774   bool empty() const {
 775     return Elements.empty();
 776   }
 777
 778   unsigned count() const {
 779     unsigned BitCount = 0;
 780     for (ElementListConstIter Iter = Elements.begin();
 781          Iter != Elements.end();
 782          ++Iter)
 783       BitCount += (*Iter)->count();
 784
 785     return BitCount;
 786   }
 787   iterator begin() const {
 788     return iterator(this);
 789   }
 790
 791   iterator end() const {
 792     return iterator(this, ~0);
 793   }
 794 };
 795
 796 // Convenience functions to allow Or and And without dereferencing in the user
 797 // code.
 798
 799 template <unsigned ElementSize>
 800 inline bool operator |=(SparseBitVector<ElementSize> &LHS,
 801                         const SparseBitVector<ElementSize> *RHS) {
 802   return LHS |= *RHS;
 803 }
 804
 805 template <unsigned ElementSize>
 806 inline bool operator |=(SparseBitVector<ElementSize> *LHS,
 807                         const SparseBitVector<ElementSize> &RHS) {
 808   return LHS->operator|=(RHS);
 809 }
 810
 811 template <unsigned ElementSize>
 812 inline bool operator &=(SparseBitVector<ElementSize> *LHS,
 813                         const SparseBitVector<ElementSize> &RHS) {
 814   return LHS->operator&=(RHS);
 815 }
 816
 817 template <unsigned ElementSize>
 818 inline bool operator &=(SparseBitVector<ElementSize> &LHS,
 819                         const SparseBitVector<ElementSize> *RHS) {
 820   return LHS &= (*RHS);
 821 }
 822
 823 }
 824
 825 #endif