69 words.shrink_to_fit();
77 return mask & containingWord;
83 if (
test(bit))
return false;
94 containingWord |= mask;
102 containingWord &= mask;
122 laterOffset -= earlierOffset;
124 const Word *eWords = &earlierOffsetCBV.
words[0];
125 const size_t eSize = earlierOffsetCBV.
words.size();
126 const Word *lWords = &laterOffsetCBV.
words[0];
127 const size_t lSize = laterOffsetCBV.
words.size();
130 for ( ; e != laterOffset && e != eSize; ++e) { }
133 for ( ; e != eSize && l != lSize; ++e, ++l)
135 if (eWords[e] & lWords[l])
return true;
143 if (
this == &rhs)
return true;
151 while (lhsSetIndex <
words.size() && rhsSetIndex < rhs.
words.size())
156 ||
words[lhsSetIndex] != rhs.
words[rhsSetIndex])
166 return lhsSetIndex >=
words.size() && rhsSetIndex >= rhs.
words.size();
171 return !(*
this == rhs);
176 if (
words.size() == 0)
179 return words.size() != 0;
182 if (rhs.
words.size() == 0)
return false;
184 if (
this == &rhs)
return false;
196 const Word *rhsWords = &rhs.
words[rhsIndex];
203 for (
size_t i = 0 ; i <
length; ++i)
205 const Word oldWord = thisWords[i];
207 thisWords[i] = thisWords[i] | rhsWords[i];
208 changed |= oldWord ^ thisWords[i];
224 bool changed =
false;
225 for (
size_t i = 0; i <
words.size(); ++i)
227 if (!changed) changed =
words[i] != 0;
234 bool changed =
false;
239 for (
size_t i = 0; i < thisIndex; ++i)
241 if (!changed) changed =
words[i] != 0;
246 for ( ; thisIndex <
words.size() && rhsIndex < rhs.
words.size(); ++thisIndex, ++rhsIndex)
248 if (!changed) oldWord =
words[thisIndex];
250 if (!changed) changed = oldWord !=
words[thisIndex];
254 for ( ; thisIndex <
words.size(); ++thisIndex)
256 if (!changed &&
words[thisIndex] != 0) changed =
true;
257 words[thisIndex] = 0;
270 if (!
canHold(greaterOffset) || !rhs.
canHold(greaterOffset))
return false;
272 bool changed =
false;
276 for ( ; thisIndex <
words.size() && rhsIndex < rhs.
words.size(); ++thisIndex, ++rhsIndex)
278 if (!changed) oldWord =
words[thisIndex];
280 if (!changed) changed = oldWord !=
words[thisIndex];
301 size_t h =
words.size();
304 h ^= w + 0x9e3779b9 + (h << 6) + (h >> 2);
327 if (newOffset >=
offset)
return;
378 size_t index = start;
399 assert(!atEnd() &&
"CoreBitVectorIterator::++(pre): incrementing past end!");
403 if (bit ==
WordSize || (*wordIt >> bit) == 0)
407 while (wordIt != cbv->words.end() && *wordIt == 0) ++wordIt;
411 if (wordIt != cbv->words.end())
413 while (bit !=
WordSize && (*wordIt & ((
Word)0b1 << bit)) == 0) ++bit;
421 assert(!atEnd() &&
"CoreBitVectorIterator::++(pre): incrementing past end!");
429 assert(!atEnd() &&
"CoreBitVectorIterator::*: dereferencing end!");
430 size_t wordsIndex = wordIt - cbv->words.begin();
435 return cbv->offset + wordsIndex *
WordSize + bit;
440 assert(cbv == rhs.
cbv &&
"CoreBitVectorIterator::==: comparing iterators from different CBVs");
442 if (wordIt == cbv->words.end())
return rhs.
wordIt == cbv->words.end();
443 return wordIt == rhs.
wordIt && bit == rhs.
bit;
448 assert(cbv == rhs.
cbv &&
"CoreBitVectorIterator::!=: comparing iterators from different CBVs");
449 return !(*
this == rhs);
454 return wordIt == cbv->words.end();
const CoreBitVectorIterator & operator++(void)
Pre-increment: ++it.
const CoreBitVector * cbv
CoreBitVector we are iterating over.
std::vector< Word >::const_iterator wordIt
Word in words we are looking at.
bool operator==(const CoreBitVectorIterator &rhs) const
Equality: *this == rhs.
CoreBitVectorIterator(void)=delete
bool operator!=(const CoreBitVectorIterator &rhs) const
Inequality: *this != rhs.
u32_t operator*(void) const
Dereference: *it.
size_t nextSetIndex(const size_t start) const
bool operator==(const CoreBitVector &rhs) const
Returns true if this CBV and rhs have the same bits set.
bool intersects(const CoreBitVector &rhs) const
Returns true if this CBV and rhs share any set bits.
void clear(void)
Empty the CBV.
bool test_and_set(u32_t bit)
CoreBitVector & operator=(const CoreBitVector &rhs)
Copy assignment.
bool canHold(u32_t bit) const
Returns true if bit can fit in this CBV without resizing.
void reset(u32_t bit)
Resets bit in the CBV.
void set(u32_t bit)
Sets bit in the CBV.
bool operator-=(const CoreBitVector &rhs)
void extendForward(u32_t bit)
Add enough words (append) to be able to include bit.
static const size_t WordSize
bool operator&=(const CoreBitVector &rhs)
void extendTo(u32_t bit)
Add enough words (append xor prepend) to be able to include bit.
u32_t offset
The first bit of the first word.
bool test(u32_t bit) const
Returns true if bit is set in this CBV.
std::vector< Word > words
Our actual bit vector.
const_iterator begin(void) const
u32_t finalBit(void) const
Returns the last bit that this CBV can hold.
bool intersectWithComplement(const CoreBitVector &rhs)
const_iterator end(void) const
bool empty(void) const
Returns true if no bits are set.
void extendBackward(u32_t bit)
Add enough words (prepend) to be able to include bit.
u32_t count(void) const
Returns number of bits set.
size_t indexForBit(u32_t bit) const
Returns the index into words which would hold bit.
CoreBitVector(void)
Construct empty CBV.
bool contains(const CoreBitVector &rhs) const
Returns true if this CBV is a superset of rhs.
bool operator!=(const CoreBitVector &rhs) const
Returns true if either this CBV or rhs has a bit set unique to the other.
bool operator|=(const CoreBitVector &rhs)
size_t hash(void) const
Hash for this CBV.
constexpr std::remove_reference< T >::type && move(T &&t) noexcept
unsigned countPopulation(T Value)