| 497 | |
| 498 | template <unsigned ElementSize = 128> |
| 499 | class SparseBitVector |
| 500 | { |
| 501 | |
| 502 | using ElementList = std::list<SparseBitVectorElement<ElementSize>>; |
| 503 | using ElementListIter = typename ElementList::iterator; |
| 504 | using ElementListConstIter = typename ElementList::const_iterator; |
| 505 | enum |
| 506 | { |
| 507 | BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE |
| 508 | }; |
| 509 | |
| 510 | ElementList Elements; |
| 511 | // Pointer to our current Element. This has no visible effect on the external |
| 512 | // state of a SparseBitVector, it's just used to improve performance in the |
| 513 | // common case of testing/modifying bits with similar indices. |
| 514 | mutable ElementListIter CurrElementIter; |
| 515 | |
| 516 | // This is like std::lower_bound, except we do linear searching from the |
| 517 | // current position. |
| 518 | ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const |
| 519 | { |
| 520 | |
| 521 | // We cache a non-const iterator so we're forced to resort to const_cast to |
| 522 | // get the begin/end in the case where 'this' is const. To avoid duplication |
| 523 | // of code with the only difference being whether the const cast is present |
| 524 | // 'this' is always const in this particular function and we sort out the |
| 525 | // difference in FindLowerBound and FindLowerBoundConst. |
| 526 | ElementListIter Begin = |
| 527 | const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin(); |
| 528 | ElementListIter End = |
| 529 | const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end(); |
| 530 | |
| 531 | if (Elements.empty()) |
| 532 | { |
| 533 | CurrElementIter = Begin; |
| 534 | return CurrElementIter; |
| 535 | } |
| 536 | |
| 537 | // Make sure our current iterator is valid. |
| 538 | if (CurrElementIter == End) |
| 539 | --CurrElementIter; |
| 540 | |
| 541 | // Search from our current iterator, either backwards or forwards, |
| 542 | // depending on what element we are looking for. |
| 543 | ElementListIter ElementIter = CurrElementIter; |
| 544 | if (CurrElementIter->index() == ElementIndex) |
| 545 | { |
| 546 | return ElementIter; |
| 547 | } |
| 548 | else if (CurrElementIter->index() > ElementIndex) |
| 549 | { |
| 550 | while (ElementIter != Begin |
| 551 | && ElementIter->index() > ElementIndex) |
| 552 | --ElementIter; |
| 553 | } |
| 554 | else |
| 555 | { |
| 556 | while (ElementIter != End && |