23#include "pasta/bit_vector/support/find_l2_flat_with.hpp"
24#include "pasta/bit_vector/support/find_l2_wide_with.hpp"
25#include "pasta/bit_vector/support/optimized_for.hpp"
26#include "pasta/utils/container/aligned_vector.hpp"
34#include <tlx/container/simple_vector.hpp>
51 uint64_t*
const data_;
77 BitAccess(uint64_t*
const data,
size_t const position) noexcept
79 position_(position) {}
87 operator bool() const noexcept {
88 uint8_t
const offset = uint64_t(position_) & uint64_t(0b111111);
89 return (data_[position_ >> 6] >> offset) & 1ULL;
100 uint64_t
const mask = 1ULL << (uint64_t(position_) & uint64_t(0b111111));
101 data_[position_ >> 6] = (data_[position_ >> 6] & ~mask) | (-value & mask);
115 return position_ - other.position_;
130 return a.position_ == b.position_ && a.data_ == b.data_;
145 return a.position_ != b.position_ || a.data_ != b.data_;
182 template <OptimizedFor o,
typename v>
185 template <OptimizedFor o,
typename v>
188 template <OptimizedFor o,
typename v>
191 template <OptimizedFor o,
typename v>
194 template <OptimizedFor o, FindL2FlatWith f,
typename v>
197 template <OptimizedFor o, FindL2W
ideWith f,
typename v>
212 size_t bit_size_ = 0;
216 tlx::SimpleVector<RawDataType, tlx::SimpleVectorMode::NoInitNoDestroy> data_;
243 : bit_access_(
data, position) {}
263 ++bit_access_.position_;
276 return a.bit_access_ == b.bit_access_;
281 return a.bit_access_ != b.bit_access_;
287 return a.bit_access_.distance(b.bit_access_);
310 size_((bit_size_ >> 6) + 1),
312 raw_data_(data_.data()) {}
323 uint64_t
const fill_value = init_value ? ~(0ULL) : 0ULL;
324 std::fill_n(raw_data_, size_, fill_value);
351 size_ = (bit_size_ >> 6) + 1;
353 raw_data_ = data_.data();
362 void resize(
size_t const size,
bool const init_value)
noexcept {
363 size_t const old_bit_size = bit_size_;
365 size_ = (bit_size_ >> 6) + 1;
367 raw_data_ = data_.data();
369 if (old_bit_size < bit_size_) {
370 size_t max_bitwise = std::min(bit_size_, ((old_bit_size + 63) / 64) * 64);
371 for (
size_t i = old_bit_size; i < max_bitwise; ++i) {
374 size_t const old_size = (old_bit_size + 63) / 64;
375 uint64_t
const fill_value = init_value ? ~(0ULL) : 0ULL;
376 std::fill_n(raw_data_ + old_size, size_ - old_size, fill_value);
396 return Iterator(raw_data_, bit_size_);
406 std::span<uint64_t>
data() noexcept {
407 return std::span{raw_data_, size_};
417 std::span<uint64_t>
data() const noexcept {
418 return std::span{raw_data_, size_};
430 uint64_t
data(
size_t const index)
const noexcept {
431 return raw_data_[index];
438 [[nodiscard(
"space usage computed but not used")]]
size_t
440 return (data_.size() *
sizeof(
RawDataType)) +
sizeof(*this);
453 for (
size_t i = 0; i < bv.bit_size_; ++i) {
454 os << (bv[i] ?
"1" :
"0");
Utility class used for the access operator of the BitVector.
Definition: bit_vector.hpp:46
BitAccess(BitAccess &&)=delete
Avoiding implicit generation of the move constructor.
int64_t distance(BitAccess const &other) const noexcept
Computes the distance to another BitAccess instance.
Definition: bit_vector.hpp:114
BitAccess & operator=(BitAccess const &)=delete
Avoiding implicit copy assignment.
BitAccess & operator=(bool const value) noexcept
Assignment operator to set a bit within the bit vector.
Definition: bit_vector.hpp:97
BitAccess()=delete
Deleted constructor.
BitAccess & operator=(BitAccess &&)=delete
Avoiding implicit move assignment.
friend bool operator==(BitAccess const &a, BitAccess const &b) noexcept
Comparison of two BitAccess instances for equality.
Definition: bit_vector.hpp:129
BitAccess(uint64_t *const data, size_t const position) noexcept
Constructor setting 64-bit word and position of the bit in the word.
Definition: bit_vector.hpp:77
friend bool operator!=(BitAccess const &a, BitAccess const &b) noexcept
Comparison of two BitAccess instances for inequality.
Definition: bit_vector.hpp:144
Uncompressed, highly tuned, fixed size bit vector.
Definition: bit_vector.hpp:179
Iterator begin() noexcept
Get iterator representing the first element of the BitVector.
Definition: bit_vector.hpp:384
BitAccess operator[](size_t const index) const noexcept
Access operator to read to a bit of the bit vector.
Definition: bit_vector.hpp:341
BitVector & operator=(BitVector const &)=delete
Deleted copy assignment.
uint64_t RawDataType
Type that is used to store the raw data of the bit vector.
Definition: bit_vector.hpp:202
BitVector()=default
Default empty constructor.
RawDataType const * RawDataConstAccess
Definition: bit_vector.hpp:208
friend std::ostream & operator<<(std::ostream &os, BitVector const &bv)
formatted output of the BitVector
Definition: bit_vector.hpp:452
std::span< uint64_t > data() const noexcept
Direct access to the raw data of the bit vector.
Definition: bit_vector.hpp:417
RawDataType * RawDataPointer
Definition: bit_vector.hpp:205
size_t size() const noexcept
Get the size of the bit vector in bits.
Definition: bit_vector.hpp:447
BitVector(size_t const size, bool const init_value) noexcept
Constructor. Creates a bit vector that holds a specific, fixed number of bits set to a default value.
Definition: bit_vector.hpp:321
uint64_t data(size_t const index) const noexcept
Direct access to one 64-bit element of the raw data of the bit vector.
Definition: bit_vector.hpp:430
Iterator end() noexcept
Get iterator representing the end of the BitVector.
Definition: bit_vector.hpp:395
BitVector(BitVector const &)=delete
Deleted copy constructor.
void resize(size_t const size) noexcept
Resize the bit vector to contain size bits.
Definition: bit_vector.hpp:349
std::span< uint64_t > data() noexcept
Direct access to the raw data of the bit vector.
Definition: bit_vector.hpp:406
void resize(size_t const size, bool const init_value) noexcept
Resize the bit vector to contain size bits and fill new bits with default value.
Definition: bit_vector.hpp:362
size_t space_usage() const
Estimate for the space usage.
Definition: bit_vector.hpp:439
BitVector(size_t const size) noexcept
Constructor. Creates a bit vector that holds a specific, fixed number of bits.
Definition: bit_vector.hpp:308
BitAccess operator[](size_t const index) noexcept
Access operator to read/write to a bit of the bit vector.
Definition: bit_vector.hpp:332
Select support for BitVector that can be used as an alternative to RankSelect for bit vectors up to l...
Definition: flat_rank_select.hpp:73
Rank support for BitVector that can be used as an alternative to Rank for bit vectors up to length 2^...
Definition: flat_rank.hpp:82
Select support for BitVector.
Definition: rank_select.hpp:77
Rank support for BitVector.
Definition: rank.hpp:102
Select support for BitVector.
Definition: wide_rank_select.hpp:62
Rank support for BitVector that can be used as an alternative to Rank for bit vectors up to length 2^...
Definition: wide_rank.hpp:76
Custom iterator for BitVector.
Definition: bit_vector.hpp:224
friend bool operator==(Iterator const &a, Iterator const &b) noexcept
Iterator comparison equality.
Definition: bit_vector.hpp:275
Iterator operator++(int32_t) noexcept
Postfix increment.
Definition: bit_vector.hpp:268
Iterator & operator++() noexcept
Prefix increment.
Definition: bit_vector.hpp:262
std::forward_iterator_tag iterator_category
Iterator category.
Definition: bit_vector.hpp:226
Iterator(uint64_t *const data, size_t const position) noexcept
Constructor. Creates Iterator pointing at a bit and holds pointer to data.
Definition: bit_vector.hpp:242
friend bool operator!=(Iterator const &a, Iterator const &b) noexcept
Iterator comparison inequality.
Definition: bit_vector.hpp:280
pointer operator->() noexcept
Iterator is dereferenceable. Obtain value it is pointing at.
Definition: bit_vector.hpp:257
friend differece_type operator-(Iterator const &a, Iterator const &b) noexcept
Iterator distance computation.
Definition: bit_vector.hpp:285
std::ptrdiff_t differece_type
Difference type.
Definition: bit_vector.hpp:228
reference operator*() noexcept
Iterator is dereferenceable. Obtain value it is pointing at.
Definition: bit_vector.hpp:249