21 : dataPtr(dataPtr), endIndex(endIndex) {
24 currentIndex = getNextIndexWithValue<true>(dataPtr, startIndex, endIndex);
26 currentIndex = startIndex;
37 dataPtr = other.dataPtr;
38 currentIndex = other.currentIndex;
39 endIndex = other.endIndex;
45 currentIndex = getNextIndexWithValue<true>(dataPtr, ++currentIndex, endIndex);
56 for (
size_t i = 0;
i < n; ++
i) {
57 currentIndex = getNextIndexWithValue<true>(dataPtr, ++currentIndex, endIndex);
67 return currentIndex != other.currentIndex;
71 return currentIndex == other.currentIndex;
77 : dataPtr(dataPtr), lowerBound(lowerBound) {
80 currentIndex = getNextIndexWithValue<true, true>(dataPtr, lowerBound, upperBound);
82 currentIndex = upperBound;
87 : dataPtr(other.dataPtr), currentIndex(other.currentIndex), lowerBound(other.lowerBound) {
94 dataPtr = other.dataPtr;
95 currentIndex = other.currentIndex;
96 lowerBound = other.lowerBound;
102 currentIndex = getNextIndexWithValue<true, true>(dataPtr, lowerBound, --currentIndex);
112 for (
size_t i = 0;
i < n; ++
i) {
113 currentIndex = getNextIndexWithValue<true, true>(dataPtr, lowerBound, --currentIndex);
119 return currentIndex - 1;
123 return currentIndex != other.currentIndex;
127 return currentIndex == other.currentIndex;
136 uint64_t bucketCount = length >> 6;
137 if ((length & mod64mask) != 0) {
143 buckets =
new uint64_t[bucketCount];
144 std::fill_n(buckets, bucketCount, -1ull);
145 truncateLastBucket();
147 buckets =
new uint64_t[bucketCount]();
155template<
typename InputIterator>
164BitVector::BitVector(uint64_t bucketCount, uint64_t bitCount) : bitCount(bitCount), buckets(nullptr) {
165 STORM_LOG_ASSERT((bucketCount << 6) == bitCount,
"Bit count does not match number of buckets.");
166 buckets =
new uint64_t[bucketCount]();
170 buckets =
new uint64_t[other.bucketCount()];
171 std::copy_n(other.buckets, other.bucketCount(), buckets);
176 if (
this != &other) {
177 if (buckets && bucketCount() != other.bucketCount()) {
181 bitCount = other.bitCount;
183 buckets =
new uint64_t[other.bucketCount()];
185 std::copy_n(other.buckets, other.bucketCount(), buckets);
193 }
else if (this->
size() > other.
size()) {
197 uint64_t* first1 = this->buckets;
198 uint64_t* last1 = this->buckets + this->bucketCount();
199 uint64_t* first2 = other.buckets;
201 for (; first1 != last1; ++first1, ++first2) {
202 if (*first1 < *first2) {
204 }
else if (*first1 > *first2) {
213 other.buckets =
nullptr;
218 if (
this != &other) {
219 bitCount = other.bitCount;
221 delete[] this->buckets;
222 this->buckets = other.buckets;
223 other.buckets =
nullptr;
231 if (this->bitCount != other.bitCount)
235 return std::equal(this->buckets, this->buckets + this->bucketCount(), other.buckets);
239 return !(*
this == other);
243 STORM_LOG_ASSERT(index < bitCount,
"Invalid call to BitVector::set: written index " << index <<
" out of bounds.");
244 uint64_t bucket = index >> 6;
246 uint64_t mask = 1ull << (63 - (index & mod64mask));
248 buckets[bucket] |= mask;
250 buckets[bucket] &= ~mask;
254template<
typename InputIterator>
256 for (InputIterator it =
begin; it !=
end; ++it) {
257 this->
set(*it, value);
262 uint64_t bucket = index >> 6;
263 uint64_t mask = 1ull << (63 - (index & mod64mask));
264 return (this->buckets[bucket] & mask) == mask;
268 STORM_LOG_ASSERT(index < bitCount,
"Invalid call to BitVector::get: read index " << index <<
" out of bounds.");
269 return (*
this)[index];
273 if (newLength > bitCount) {
274 uint64_t newBucketCount = newLength >> 6;
275 if ((newLength & mod64mask) != 0) {
279 if (newBucketCount > this->bucketCount()) {
280 uint64_t* newBuckets =
new uint64_t[newBucketCount];
281 std::copy_n(buckets, this->bucketCount(), newBuckets);
283 if (this->bucketCount() > 0) {
284 newBuckets[this->bucketCount() - 1] |= ((1ull << (64 - (bitCount & mod64mask))) - 1ull);
286 std::fill_n(newBuckets + this->bucketCount(), newBucketCount - this->bucketCount(), -1ull);
288 std::fill_n(newBuckets + this->bucketCount(), newBucketCount - this->bucketCount(), 0);
291 buckets = newBuckets;
292 bitCount = newLength;
296 buckets[this->bucketCount() - 1] |= ((1ull << (64 - (bitCount & mod64mask))) - 1ull);
298 bitCount = newLength;
300 truncateLastBucket();
302 uint64_t newBucketCount = newLength >> 6;
303 if ((newLength & mod64mask) != 0) {
309 if (newBucketCount < this->bucketCount()) {
310 uint64_t* newBuckets =
new uint64_t[newBucketCount];
311 std::copy_n(buckets, newBucketCount, newBuckets);
313 buckets = newBuckets;
314 bitCount = newLength;
316 bitCount = newLength;
317 truncateLastBucket();
322 STORM_LOG_ASSERT(
size() % 64 == 0,
"We expect the length of the left bitvector to be a multiple of 64.");
332 bitCount = bucketCount() * 64;
339 if (minimumLength > bitCount) {
341 uint64_t newLength = std::max(
static_cast<uint64_t
>(64), bitCount);
343 while (newLength < minimumLength) {
344 newLength = newLength << 1;
351 STORM_LOG_ASSERT(bitCount == other.bitCount,
"Length of the bit vectors does not match.");
353 std::transform(this->buckets, this->buckets + this->bucketCount(), other.buckets, result.buckets,
354 [](uint64_t
const& a, uint64_t
const& b) { return a & b; });
359 STORM_LOG_ASSERT(bitCount == other.bitCount,
"Length of the bit vectors does not match.");
360 std::transform(this->buckets, this->buckets + this->bucketCount(), other.buckets, this->buckets,
361 [](uint64_t
const& a, uint64_t
const& b) { return a & b; });
366 STORM_LOG_ASSERT(bitCount == other.bitCount,
"Length of the bit vectors does not match.");
368 std::transform(this->buckets, this->buckets + this->bucketCount(), other.buckets, result.buckets,
369 [](uint64_t
const& a, uint64_t
const& b) { return a | b; });
374 STORM_LOG_ASSERT(bitCount == other.bitCount,
"Length of the bit vectors does not match.");
375 std::transform(this->buckets, this->buckets + this->bucketCount(), other.buckets, this->buckets,
376 [](uint64_t
const& a, uint64_t
const& b) { return a | b; });
381 STORM_LOG_ASSERT(bitCount == other.bitCount,
"Length of the bit vectors does not match.");
383 std::transform(this->buckets, this->buckets + this->bucketCount(), other.buckets, result.buckets,
384 [](uint64_t
const& a, uint64_t
const& b) { return a ^ b; });
385 result.truncateLastBucket();
390 STORM_LOG_ASSERT(bitCount == filter.bitCount,
"Length of the bit vectors does not match.");
397 uint64_t position = 0;
398 for (
auto bit : filter) {
400 result.
set(position);
407 for (
auto bit : (*this)) {
419 std::transform(this->buckets, this->buckets + this->bucketCount(), result.buckets, [](uint64_t
const& a) { return ~a; });
420 result.truncateLastBucket();
425 std::transform(this->buckets, this->buckets + this->bucketCount(), this->buckets, [](uint64_t
const& a) {
return ~a; });
426 truncateLastBucket();
433 if (firstUnsetIndex == this->bitCount) {
437 uint64_t bucketIndex = firstUnsetIndex >> 6;
438 std::fill_n(buckets, bucketIndex, 0);
441 uint64_t& bucket = this->buckets[bucketIndex];
442 uint64_t indexInBucket = firstUnsetIndex & mod64mask;
443 if (indexInBucket > 0) {
445 uint64_t mask = ~(-1ull << (64 - indexInBucket));
450 uint64_t mask = 1ull << (63 - indexInBucket);
456 STORM_LOG_ASSERT(bitCount == other.bitCount,
"Length of the bit vectors does not match.");
459 std::transform(this->buckets, this->buckets + this->bucketCount(), other.buckets, result.buckets,
460 [](uint64_t
const& a, uint64_t
const& b) { return (~a | b); });
461 result.truncateLastBucket();
466 STORM_LOG_ASSERT(bitCount == other.bitCount,
"Length of the bit vectors does not match.");
468 uint64_t
const* it1 = buckets;
469 uint64_t
const* ite1 = buckets + bucketCount();
470 uint64_t
const* it2 = other.buckets;
472 for (; it1 != ite1; ++it1, ++it2) {
473 if ((*it1 & *it2) != *it1) {
481 STORM_LOG_ASSERT(bitCount == other.bitCount,
"Length of the bit vectors does not match.");
483 uint64_t
const* it1 = buckets;
484 uint64_t
const* ite1 = buckets + bucketCount();
485 uint64_t
const* it2 = other.buckets;
487 for (; it1 != ite1; ++it1, ++it2) {
488 if ((*it1 & *it2) != 0) {
496 STORM_LOG_ASSERT((bitIndex & mod64mask) == 0,
"Bit index must be a multiple of 64.");
500 uint64_t index = bitIndex >> 6;
502 uint64_t
const* first1 = buckets + index;
503 uint64_t
const* first2 = other.buckets;
504 uint64_t
const* last2 = other.buckets + other.bucketCount();
506 for (; first2 != last2; ++first1, ++first2) {
507 if (*first1 != *first2) {
516 for (uint64_t
i = 0;
i < this->
size(); ++
i) {
517 if (this->
get(inversePermutation[
i])) {
525 STORM_LOG_ASSERT(inversePermutation.size() == rowGroupIndices.size() - 1,
"Inverse permutation and row group indices do not match.");
527 uint64_t targetIndex = 0u;
528 for (
auto const sourceGroupIndex : inversePermutation) {
529 for (uint64_t sourceIndex = rowGroupIndices[sourceGroupIndex]; sourceIndex < rowGroupIndices[sourceGroupIndex + 1]; ++sourceIndex, ++targetIndex) {
530 if (this->
get(sourceIndex)) {
531 result.
set(targetIndex,
true);
535 STORM_LOG_ASSERT(targetIndex == result.
size(),
"Target index does not match the size of the result.");
540 STORM_LOG_ASSERT((bitIndex & mod64mask) == 0,
"Bit index must be a multiple of 64.");
544 uint64_t index = bitIndex >> 6;
546 uint64_t* first1 = buckets + index;
547 uint64_t
const* first2 = other.buckets;
548 uint64_t
const* last2 = other.buckets + other.bucketCount();
550 for (; first2 != last2; ++first1, ++first2) {
557 uint64_t endPos = std::min(bitIndex + nrOfBits, bitCount);
558 for (uint64_t tmpIndex = bitIndex; tmpIndex < endPos; ++tmpIndex) {
559 set(tmpIndex, newValue);
564 uint64_t numberOfBuckets = numberOfBits >> 6;
565 uint64_t index = bitIndex >> 6;
566 STORM_LOG_ASSERT(index + numberOfBuckets <= this->bucketCount(),
"Argument is out-of-range.");
569 std::copy(this->buckets + index, this->buckets + index + numberOfBuckets, result.buckets);
570 result.truncateLastBucket();
575 if (numberOfBits == 0) {
579 uint64_t
const firstBucket = bitIndex >> 6;
580 uint8_t
const bitIndexInFirstBucket = bitIndex & mod64mask;
581 uint8_t
const availableBitsInFirstBucket =
static_cast<uint8_t
>(64 - bitIndexInFirstBucket);
584 uint64_t result = buckets[firstBucket] << bitIndexInFirstBucket;
586 if (availableBitsInFirstBucket < numberOfBits) {
587 result |= buckets[firstBucket + 1] >> availableBitsInFirstBucket;
590 return result >> (64 - numberOfBits);
596 uint64_t bucket = bitIndex >> 6;
597 uint64_t bitIndexInBucket = bitIndex & mod64mask;
600 if (bitIndexInBucket == 0) {
603 mask = (1ull << (64 - bitIndexInBucket)) - 1ull;
606 if (bitIndexInBucket < 62) {
608 mask &= ~((1ull << (62 - (bitIndexInBucket))) - 1ull);
609 return (buckets[bucket] & mask) >> (62 - bitIndexInBucket);
612 return buckets[bucket] & mask;
619 "Integer value (" << value <<
") too large to fit in the given number of bits (" << numberOfBits <<
").");
621 uint64_t bucket = bitIndex >> 6;
622 uint64_t bitIndexInBucket = bitIndex & mod64mask;
625 if (bitIndexInBucket == 0) {
628 mask = (1ull << (64 - bitIndexInBucket)) - 1ull;
631 if (bitIndexInBucket + numberOfBits < 64) {
633 mask &= ~((1ull << (64 - (bitIndexInBucket + numberOfBits))) - 1ull);
634 buckets[bucket] = (buckets[bucket] & ~mask) | (value << (64 - (bitIndexInBucket + numberOfBits)));
635 }
else if (bitIndexInBucket + numberOfBits > 64) {
637 buckets[bucket] = (buckets[bucket] & ~mask) | (value >> (numberOfBits + (bitIndexInBucket - 64)));
641 numberOfBits -= (64 - bitIndexInBucket);
644 value <<= (64 - numberOfBits);
647 mask = ((1ull << (64 - numberOfBits)) - 1ull);
648 buckets[bucket] = (buckets[bucket] & mask) | value;
650 buckets[bucket] = (buckets[bucket] & ~mask) | value;
655 uint64_t* last = buckets + bucketCount();
656 uint64_t* it = std::find_if(buckets, last, [](uint64_t
const& a) {
return a != 0; });
665 uint64_t* last = buckets + bucketCount() - 1;
666 for (uint64_t
const* it = buckets; it < last; ++it) {
673 uint64_t mask = ~((1ull << (64 - (bitCount & mod64mask))) - 1ull);
674 if ((*last & mask) != mask) {
681 std::fill_n(buckets, this->bucketCount(), 0);
685 std::fill_n(buckets, this->bucketCount(), -1ull);
686 truncateLastBucket();
694 STORM_LOG_ASSERT(index <= bitCount,
"Invalid call to BitVector::getNumberOfSetBitsBeforeIndex: read index " << index <<
" out of bounds.");
695 uint64_t
const lastBucketIndex = index >> 6;
699 for (uint64_t
i = 0;
i < lastBucketIndex; ++
i) {
700 result += std::popcount(buckets[
i]);
704 uint8_t
const endIndexInLastBucket = index & mod64mask;
705 if (endIndexInLastBucket != 0) {
706 result += std::popcount(buckets[lastBucketIndex] >> (64 - endIndexInLastBucket));
713 std::vector<uint64_t> bitsSetBeforeIndices;
714 bitsSetBeforeIndices.reserve(this->
size());
715 uint64_t lastIndex = 0;
716 uint64_t currentNumberOfSetBits = 0;
717 for (
auto index : *
this) {
718 while (lastIndex <= index) {
719 bitsSetBeforeIndices.push_back(currentNumberOfSetBits);
722 ++currentNumberOfSetBits;
724 return bitsSetBeforeIndices;
732 return static_cast<size_t>(bitCount);
736 return sizeof(*this) +
sizeof(uint64_t) * bucketCount();
763 return getNextIndexWithValue<true>(buckets, startingIndex, bitCount);
767#ifdef ASSERT_BITVECTOR
769 "The result is inconsistent with the next set index of the complement of this bitvector");
771 return getNextIndexWithValue<false>(buckets, startingIndex, bitCount);
775 return getNextIndexWithValue<true, true>(buckets, 0, endIndex);
779#ifdef ASSERT_BITVECTOR
781 "The result is inconsistent with the next set index of the complement of this bitvector");
783 return getNextIndexWithValue<false, true>(buckets, 0, endIndex);
786template<
bool Value,
bool Backward>
787uint64_t BitVector::getNextIndexWithValue(uint64_t
const* dataPtr, uint64_t startingIndex, uint64_t endIndex) {
788 if (startingIndex >= endIndex) {
789 return Backward ? startingIndex : endIndex;
792 uint64_t currentBucketIndexOffset = Backward ? endIndex - 1 : startingIndex;
793 uint_fast8_t currentBitInBucket = currentBucketIndexOffset & mod64mask;
794 uint64_t
const* bucketIt = dataPtr + (currentBucketIndexOffset >> 6);
795 currentBucketIndexOffset = (currentBucketIndexOffset >> 6 << 6);
798 uint64_t relevantBitsInBucket;
799 if constexpr (Backward) {
800 relevantBitsInBucket = -1ull << (63 - currentBitInBucket);
802 relevantBitsInBucket = -1ull >> currentBitInBucket;
804 uint64_t currentBucket = Value ? (*bucketIt & relevantBitsInBucket) : (*bucketIt | ~relevantBitsInBucket);
807 if (currentBucket == (Value ? 0ull : -1ull)) {
811 if constexpr (Backward) {
812 if (currentBucketIndexOffset <= startingIndex) {
814 return startingIndex;
817 currentBucketIndexOffset -= 64;
820 currentBucketIndexOffset += 64;
821 if (currentBucketIndexOffset >= endIndex) {
827 }
while ((*bucketIt) == (Value ? 0ull : -1ull));
829 currentBucket = *bucketIt;
830 currentBitInBucket = Backward ? 63u : 0u;
833 if constexpr (!Value) {
834 currentBucket = ~currentBucket;
837 STORM_LOG_ASSERT(currentBucket != 0ull,
"Bitvector's getNextIndexWithValue method in invalid state.");
839#if (defined(__GNUG__) || defined(__clang__))
841 if constexpr (Backward) {
843 return std::max<uint64_t>(startingIndex,
844 currentBucketIndexOffset + 64ull - __builtin_ctzll(currentBucket));
847 return std::min<uint64_t>(endIndex, currentBucketIndexOffset + __builtin_clzll(currentBucket));
851 uint64_t compareMask = 1ull << (63 - currentBitInBucket);
852 while (!
static_cast<bool>(currentBucket & compareMask)) {
853 if constexpr (Backward) {
854 compareMask <<= 1ull;
855 --currentBitInBucket;
857 compareMask >>= 1ull;
858 ++currentBitInBucket;
861 if constexpr (Backward) {
862 return std::max(startingIndex, currentBucketIndexOffset + currentBitInBucket + 1ull);
864 return std::min(endIndex, currentBucketIndexOffset + currentBitInBucket);
871#ifdef ASSERT_BITVECTOR
876 uint64_t offset = start % 64;
877 uint64_t* getBucket = buckets + (start / 64);
878 uint64_t* insertBucket = result.buckets;
884 for (; noBits + 64 <= length; ++getBucket, ++insertBucket, noBits += 64) {
885 *insertBucket = *getBucket;
889 getValue = *getBucket;
891 noBits += (64 - offset);
895 for (; noBits + 64 <= length; ++getBucket, ++insertBucket, noBits += 64) {
896 getValue = *getBucket;
906 uint64_t remainingBits = length - noBits;
907 STORM_LOG_ASSERT(getBucket != buckets + bucketCount(),
"Bucket index incorrect.");
909 getValue = (*getBucket >> (64 - remainingBits)) << (64 - remainingBits);
912 STORM_LOG_ASSERT(insertBucket != result.buckets + result.bucketCount(),
"Bucket index incorrect.");
914 *insertBucket = getValue;
918 if (remainingBits > offset) {
922 STORM_LOG_ASSERT(insertBucket != result.buckets + result.bucketCount(),
"Bucket index incorrect.");
927#ifdef ASSERT_BITVECTOR
929 for (uint64_t
i = 0;
i < length; ++
i) {
930 if (result.get(
i) !=
get(start +
i)) {
932 STORM_LOG_ERROR(
"Getting from " << start <<
" with length " << length);
933 std::stringstream stream;
936 result.printBits(stream);
941 for (uint64_t
i = 0;
i < bitCount; ++
i) {
942 if (i < start || i >= start + length) {
943 if (original.get(
i) !=
get(
i)) {
945 STORM_LOG_ERROR(
"Getting from " << start <<
" with length " << length);
946 std::stringstream stream;
949 original.printBits(stream);
960void BitVector::setFromBitVector(uint64_t start, BitVector
const& other) {
961#ifdef ASSERT_BITVECTOR
966 uint64_t offset = start % 64;
967 uint64_t* insertBucket = buckets + (start / 64);
968 uint64_t* getBucket = other.buckets;
974 for (; noBits + 64 <= other.bitCount; ++insertBucket, ++getBucket, noBits += 64) {
975 *insertBucket = *getBucket;
979 getValue = *getBucket;
980 writeValue = (*insertBucket >> (64 - offset)) << (64 - offset);
983 noBits += (64 - offset);
987 for (; noBits + 64 <= other.bitCount; ++insertBucket, noBits += 64) {
992 getValue = *getBucket;
999 uint64_t remainingBits = other.bitCount - noBits;
1001 STORM_LOG_ASSERT(insertBucket != buckets + bucketCount(),
"Bucket index incorrect.");
1002 STORM_LOG_ASSERT(getBucket != other.buckets + other.bucketCount(),
"Bucket index incorrect.");
1004 getValue = *getBucket;
1006 getValue = getValue << (64 - offset);
1009 writeValue = (*insertBucket << remainingBits) >> remainingBits;
1010 if (remainingBits > offset && offset > 0) {
1013 STORM_LOG_ASSERT(getBucket != other.buckets + other.bucketCount(),
"Bucket index incorrect.");
1014 getValue |= *getBucket >> offset;
1020#ifdef ASSERT_BITVECTOR
1022 for (uint64_t
i = 0;
i < other.bitCount; ++
i) {
1023 if (other.get(
i) !=
get(start +
i)) {
1025 STORM_LOG_ERROR(
"Setting from " << start <<
" with length " << other.bitCount);
1026 std::stringstream stream;
1029 other.printBits(stream);
1034 for (uint64_t
i = 0;
i < bitCount; ++
i) {
1035 if (i < start || i >= start + other.bitCount) {
1036 if (original.get(
i) !=
get(
i)) {
1038 STORM_LOG_ERROR(
"Setting from " << start <<
" with length " << other.bitCount);
1039 std::stringstream stream;
1042 original.printBits(stream);
1054 uint64_t elem1 =
getAsInt(start1, length);
1055 uint64_t elem2 =
getAsInt(start2, length);
1056 if (elem1 < elem2) {
1065 BitVector elem1 = getAsBitVector(start1, length);
1066 BitVector elem2 = getAsBitVector(start2, length);
1068 if (!(elem1 < elem2)) {
1070#ifdef ASSERT_BITVECTOR
1072 for (uint64_t
i = 0;
i < length; ++
i) {
1073 if (
get(start1 +
i) >
get(start2 +
i)) {
1076 STORM_LOG_ASSERT(
get(start1 +
i) >=
get(start2 +
i),
"Bit vector not sorted for indices " << start1 +
i <<
" and " << start2 +
i);
1082#ifdef ASSERT_BITVECTOR
1087 setFromBitVector(start1, elem2);
1088 setFromBitVector(start2, elem1);
1090#ifdef ASSERT_BITVECTOR
1093 for (uint64_t
i = 0;
i < length; ++
i) {
1094 tmp = check.get(
i + start1);
1095 check.set(
i + start1, check.get(
i + start2));
1096 check.set(
i + start2, tmp);
1101 for (uint64_t
i = 0;
i < length; ++
i) {
1102 if (
get(start1 +
i) >
get(start2 +
i)) {
1105 STORM_LOG_ASSERT(
get(start1 +
i) >=
get(start2 +
i),
"Bit vector not sorted for indices " << start1 +
i <<
" and " << start2 +
i);
1113void BitVector::truncateLastBucket() {
1114 if ((bitCount & mod64mask) != 0) {
1115 buckets[bucketCount() - 1] &= ~((1ll << (64 - (bitCount & mod64mask))) - 1ll);
1119size_t BitVector::bucketCount()
const {
1120 size_t result = (bitCount >> 6);
1121 if ((bitCount & mod64mask) != 0) {
1127std::ostream& operator<<(std::ostream& out,
BitVector const& bitvector) {
1128 out <<
"bit vector(" << bitvector.
getNumberOfSetBits() <<
"/" << bitvector.bitCount <<
") [";
1129 for (
auto index : bitvector) {
1130 out << index <<
" ";
1137void BitVector::printBits(std::ostream& out)
const {
1140 for (; index * 64 + 64 <= bitCount; ++index) {
1141 std::bitset<64> tmp(buckets[index]);
1146 if (index * 64 < bitCount) {
1148 std::bitset<64> tmp(buckets[index]);
1149 for (
size_t i = 0;
i + index * 64 < bitCount; ++
i) {
1158 std::size_t seed = 14695981039346656037ull;
1160 uint8_t* it =
reinterpret_cast<uint8_t*
>(bv.buckets);
1161 uint8_t
const* ite = it + 8 * bv.bucketCount();
1167 seed += (seed << 1) + (seed << 4) + (seed << 5) + (seed << 7) + (seed << 8) + (seed << 40);
1183inline __attribute__((always_inline)) uint64_t fmix64(uint64_t k) {
1185 k *= 0xff51afd7ed558ccdull;
1187 k *= 0xc4ceb9fe1a85ec53ull;
1193inline uint32_t
rotl32(uint32_t x, int8_t r) {
1194 return (x << r) | (x >> (32 - r));
1197inline uint64_t
rotl64(uint64_t x, int8_t r) {
1198 return (x << r) | (x >> (64 - r));
1205inline __attribute__((always_inline)) uint32_t getblock64(uint64_t
const* p,
int i) {
1211 uint8_t
const* data =
reinterpret_cast<uint8_t const*
>(bv.buckets);
1212 uint32_t len = bv.bucketCount() * 8;
1213 const int nblocks = bv.bucketCount() * 2;
1218 const uint32_t c1 = 0xcc9e2d51;
1219 const uint32_t c2 = 0x1b873593;
1224 const uint32_t* blocks =
reinterpret_cast<uint32_t const*
>(data + nblocks * 4);
1226 for (
int i = -nblocks;
i;
i++) {
1227 uint32_t k1 = getblock32(blocks,
i);
1235 h1 = h1 * 5 + 0xe6546b64;
1250 uint8_t
const* data =
reinterpret_cast<uint8_t const*
>(bv.buckets);
1251 uint64_t len = bv.bucketCount() * 8;
1252 const int nblocks = bv.bucketCount() / 2;
1257 const uint64_t c1 = 0x87c37b91114253d5ull;
1258 const uint64_t c2 = 0x4cf5ad432745937full;
1263 const uint64_t* blocks = (
const uint64_t*)(data);
1265 for (
int i = 0;
i < nblocks;
i++) {
1266 uint64_t k1 = getblock64(blocks,
i * 2 + 0);
1267 uint64_t k2 = getblock64(blocks,
i * 2 + 1);
1276 h1 = h1 * 5 + 0x52dce729;
1285 h2 = h2 * 5 + 0x38495ab5;
1291 uint8_t
const* tail =
reinterpret_cast<uint8_t const*
>(data + nblocks * 16);
1299 k2 ^= ((uint64_t)tail[14]) << 48;
1302 k2 ^= ((uint64_t)tail[13]) << 40;
1305 k2 ^= ((uint64_t)tail[12]) << 32;
1308 k2 ^= ((uint64_t)tail[11]) << 24;
1311 k2 ^= ((uint64_t)tail[10]) << 16;
1314 k2 ^= ((uint64_t)tail[9]) << 8;
1317 k2 ^= ((uint64_t)tail[8]) << 0;
1325 k1 ^= ((uint64_t)tail[7]) << 56;
1328 k1 ^= ((uint64_t)tail[6]) << 48;
1331 k1 ^= ((uint64_t)tail[5]) << 40;
1334 k1 ^= ((uint64_t)tail[4]) << 32;
1337 k1 ^= ((uint64_t)tail[3]) << 24;
1340 k1 ^= ((uint64_t)tail[2]) << 16;
1343 k1 ^= ((uint64_t)tail[1]) << 8;
1346 k1 ^= ((uint64_t)tail[0]) << 0;
1374 for (uint64_t
i = 0;
i < bucketCount(); ++
i) {
1375 os <<
" " << buckets[
i];
1380 std::vector<std::string> splitted;
1381 std::stringstream ss(description);
1382 ss >> std::noskipws;
1387 splitted.push_back(field);
1391 splitted.push_back(std::string());
1396 for (uint64_t
i = 0;
i < splitted.size() - 1; ++
i) {
1397 bv.buckets[
i] = std::stoul(splitted[
i + 1]);
1403template BitVector::BitVector(uint64_t length, std::vector<uint64_t>::iterator begin, std::vector<uint64_t>::iterator end);
1404template BitVector::BitVector(uint64_t length, std::vector<uint64_t>::const_iterator begin, std::vector<uint64_t>::const_iterator end);
1407template void BitVector::set(std::vector<uint64_t>::iterator begin, std::vector<uint64_t>::iterator end,
bool value);
1408template void BitVector::set(std::vector<uint64_t>::const_iterator begin, std::vector<uint64_t>::const_iterator end,
bool value);
1419 return boost::hash_range(bitvector.buckets, bitvector.buckets + bitvector.bucketCount());
A class that enables iterating over the indices of the bit vector whose corresponding bits are set to...
uint64_t operator*() const
Returns the index of the current bit to which this iterator points.
const_iterator & operator++()
Increases the position of the iterator to the position of the next bit that is set to true in the und...
bool operator==(const_iterator const &other) const
Compares the iterator with another iterator for equality.
const_iterator & operator+=(size_t n)
Increases the position of the iterator to the position of the n'th next bit that is set to true in th...
const_iterator & operator=(const_iterator const &other)
Assigns the contents of the given iterator to the current one via copying the former's contents.
bool operator!=(const_iterator const &other) const
Compares the iterator with another iterator for inequality.
A class that enables iterating over the indices of the bit vector whose corresponding bits are set to...
bool operator==(const_reverse_iterator const &other) const
Compares the iterator with another iterator for equality.
uint64_t operator*() const
Returns the index of the current bit to which this iterator points.
const_reverse_iterator()
Constructs a reverse iterator over the indices of the set bits in the given bit vector,...
const_reverse_iterator & operator+=(size_t n)
Lets the iterator point to the n'th previous bit with value 1.
const_reverse_iterator & operator++()
Lets the iterator point to the previous bit with value 1.
const_reverse_iterator & operator=(const_reverse_iterator const &other)
bool operator!=(const_reverse_iterator const &other) const
Compares the iterator with another iterator for inequality.
A bit vector that is internally represented as a vector of 64-bit values.
~BitVector()
Deconstructs a bit vector by deleting the underlying storage.
void complement()
Negates all bits in the bit vector.
BitVector & operator|=(BitVector const &other)
Performs a logical "or" with the given bit vector and assigns the result to the current bit vector.
BitVector operator^(BitVector const &other) const
Performs a logical "xor" with the given bit vector.
void setMultiple(uint64_t bitIndex, uint64_t nrOfBits, bool newValue=true)
Sets multiple bits to the given value.
bool operator<(BitVector const &other) const
Retrieves whether the current bit vector is (in some order) smaller than the given one.
const_reverse_iterator rbegin() const
Returns a reverse iterator to the indices of the set bits in the bit vector.
void fill()
Sets all bits from the bit vector.
uint64_t getNextSetIndex(uint64_t startingIndex) const
Retrieves the index of the bit that is the next bit set to true in the bit vector.
uint64_t getTwoBitsAligned(uint64_t bitIndex) const
bool isDisjointFrom(BitVector const &other) const
Checks whether none of the bits that are set in the current bit vector are also set in the given bit ...
bool full() const
Retrieves whether all bits are set in this bit vector.
std::vector< uint64_t > getNumberOfSetBitsBeforeIndices() const
Retrieves a vector that holds at position i the number of bits set before index i.
const_reverse_iterator rend() const
Returns a reverse iterator pointing at the element past the front of the bit vector.
bool hasUniqueSetBit() const
BitVector()
Constructs an empty bit vector of length 0.
const_iterator end() const
Returns an iterator pointing at the element past the back of the bit vector.
void grow(uint64_t minimumLength, bool init=false)
Enlarges the bit vector such that it holds at least the given number of bits (but possibly more).
void store(std::ostream &) const
BitVector operator%(BitVector const &filter) const
Computes a bit vector that contains only the values of the bits given by the filter.
BitVector operator|(BitVector const &other) const
Performs a logical "or" with the given bit vector.
bool empty() const
Retrieves whether no bits are set to true in this bit vector.
std::size_t getSizeInBytes() const
Returns (an approximation of) the size of the bit vector measured in bytes.
void clear()
Removes all set bits from the bit vector.
bool isSubsetOf(BitVector const &other) const
Checks whether all bits that are set in the current bit vector are also set in the given bit vector.
BitVector implies(BitVector const &other) const
Performs a logical "implies" with the given bit vector.
BitVector & operator=(BitVector const &other)
Assigns the contents of the given bit vector to the current bit vector via a deep copy.
uint64_t getNumberOfSetBits() const
Returns the number of bits that are set to true in this bit vector.
uint64_t getNextUnsetIndex(uint64_t startingIndex) const
Retrieves the index of the bit that is the next bit set to false in the bit vector.
bool compareAndSwap(uint64_t start1, uint64_t start2, uint64_t length)
Compare two intervals [start1, start1+length] and [start2, start2+length] and swap them if the second...
BitVector operator&(BitVector const &other) const
Performs a logical "and" with the given bit vector.
void setFromInt(uint64_t bitIndex, uint64_t numberOfBits, uint64_t value)
Sets the selected number of lowermost bits of the provided value at the given bit index.
BitVector permute(std::vector< uint64_t > const &inversePermutation) const
Apply a permutation of entries.
void set(uint64_t index, bool value=true)
Sets the given truth value at the given index.
void increment()
Increments the (unsigned) number represented by this BitVector by one.
bool matches(uint64_t bitIndex, BitVector const &other) const
Checks whether the given bit vector matches the bits starting from the given index in the current bit...
const_iterator begin() const
Returns an iterator to the indices of the set bits in the bit vector.
uint64_t getStartOfZeroSequenceBefore(uint64_t endIndex) const
Retrieves the smallest index i such that all bits in the range [i,endIndex) are 0.
uint64_t getAsInt(uint64_t bitIndex, uint64_t numberOfBits) const
Retrieves the content of the current bit vector at the given index for the given number of bits as an...
BitVector operator~() const
Performs a logical "not" on the bit vector.
bool operator!=(BitVector const &other) const
Compares the given bit vector with the current one.
size_t size() const
Retrieves the number of bits this bit vector can store.
void resize(uint64_t newLength, bool init=false)
Resizes the bit vector to hold the given new number of bits.
BitVector & operator&=(BitVector const &other)
Performs a logical "and" with the given bit vector and assigns the result to the current bit vector.
static BitVector load(std::string const &description)
void expandSize(bool init=false)
bool get(uint64_t index) const
Retrieves the truth value of the bit at the given index and performs a bound check.
bool operator==(BitVector const &other) const
Compares the given bit vector with the current one.
uint64_t getNumberOfSetBitsBeforeIndex(uint64_t index) const
Retrieves the number of bits set in this bit vector with an index strictly smaller than the given one...
BitVector permuteGroupedVector(std::vector< uint64_t > const &inversePermutation, std::vector< uint64_t > const &rowGroupIndices) const
Apply a permutation of entries assuming a grouped vector.
uint64_t getStartOfOneSequenceBefore(uint64_t endIndex) const
Retrieves the smallest index i such that all bits in the range [i,endIndex) are 1.
bool operator[](uint64_t index) const
Retrieves the truth value of the bit at the given index.
void concat(BitVector const &extension)
Concatenate this bitvector with another bitvector.
#define STORM_LOG_ERROR(message)
#define STORM_LOG_ASSERT(cond, message)
void writeValue(std::ostream &os, ValueType value, std::unordered_map< ValueType, std::string > const &placeholders)
Write value to stream while using the placeholders.
uint32_t rotl32(uint32_t x, int8_t r)
uint64_t rotl64(uint64_t x, int8_t r)
boost::container::flat_set< Key, std::less< Key >, boost::container::new_allocator< Key > > FlatSet
Redefinition of flat_set was needed, because from Boost 1.70 on the default allocator is set to void.
__attribute__((always_inline)) uint32_t fmix32(uint32_t h)
std::size_t operator()(storm::storage::BitVector const &bv) const
StateType operator()(storm::storage::BitVector const &bv) const