| 253 | |
| 254 | template <unsigned ElementSize = 128> |
| 255 | class SparseBitVector { |
| 256 | using ElementList = std::list<SparseBitVectorElement<ElementSize>>; |
| 257 | using ElementListIter = typename ElementList::iterator; |
| 258 | using ElementListConstIter = typename ElementList::const_iterator; |
| 259 | enum { |
| 260 | BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE |
| 261 | }; |
| 262 | |
| 263 | ElementList Elements; |
| 264 | // Pointer to our current Element. This has no visible effect on the external |
| 265 | // state of a SparseBitVector, it's just used to improve performance in the |
| 266 | // common case of testing/modifying bits with similar indices. |
| 267 | mutable ElementListIter CurrElementIter; |
| 268 | |
| 269 | // This is like std::lower_bound, except we do linear searching from the |
| 270 | // current position. |
| 271 | ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const { |
| 272 | |
| 273 | // We cache a non-const iterator so we're forced to resort to const_cast to |
| 274 | // get the begin/end in the case where 'this' is const. To avoid duplication |
| 275 | // of code with the only difference being whether the const cast is present |
| 276 | // 'this' is always const in this particular function and we sort out the |
| 277 | // difference in FindLowerBound and FindLowerBoundConst. |
| 278 | ElementListIter Begin = |
| 279 | const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin(); |
| 280 | ElementListIter End = |
| 281 | const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end(); |
| 282 | |
| 283 | if (Elements.empty()) { |
| 284 | CurrElementIter = Begin; |
| 285 | return CurrElementIter; |
| 286 | } |
| 287 | |
| 288 | // Make sure our current iterator is valid. |
| 289 | if (CurrElementIter == End) |
| 290 | --CurrElementIter; |
| 291 | |
| 292 | // Search from our current iterator, either backwards or forwards, |
| 293 | // depending on what element we are looking for. |
| 294 | ElementListIter ElementIter = CurrElementIter; |
| 295 | if (CurrElementIter->index() == ElementIndex) { |
| 296 | return ElementIter; |
| 297 | } else if (CurrElementIter->index() > ElementIndex) { |
| 298 | while (ElementIter != Begin |
| 299 | && ElementIter->index() > ElementIndex) |
| 300 | --ElementIter; |
| 301 | } else { |
| 302 | while (ElementIter != End && |
| 303 | ElementIter->index() < ElementIndex) |
| 304 | ++ElementIter; |
| 305 | } |
| 306 | CurrElementIter = ElementIter; |
| 307 | return ElementIter; |
| 308 | } |
| 309 | ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const { |
| 310 | return FindLowerBoundImpl(ElementIndex); |
| 311 | } |
| 312 | ElementListIter FindLowerBound(unsigned ElementIndex) { |