9#ifndef SDSL_BIT_VECTOR_IL
10#define SDSL_BIT_VECTOR_IL
33template <u
int8_t t_b = 1, u
int32_t t_bs = 512>
35template <u
int8_t t_b = 1, u
int32_t t_bs = 512>
41 return std::is_integral<T>::value and x > 1 and !(x & (x - 1));
53template <u
int32_t t_bs = 512>
56 static_assert(t_bs >= 64,
"bit_vector_il: blocksize must be be at least 64 bits.");
57 static_assert(
power_of_two(t_bs),
"bit_vector_il: blocksize must be a power of two.");
86 void init_rank_samples()
88 uint32_t blockSize_U64 =
bits::hi(t_bs >> 6);
90 std::queue<size_type> lbs, rbs;
92 rbs.push(m_superblocks);
99 if ( idx < m_rank_samples.
size())
102 size_type pos = (mid << blockSize_U64) + mid;
103 m_rank_samples[idx++] = m_data[pos];
125 m_superblocks = (m_size + t_bs) / t_bs;
129 size_type mem = blocks + m_superblocks + 1;
136 uint64_t
const * bvp = bv.
data();
141 for (
size_type i = 0, sample_cnt = sample_rate; i < blocks; ++i, ++sample_cnt)
143 if (sample_cnt == sample_rate)
155 if (m_block_num > 1024 * 64)
160 m_rank_samples.
resize(std::min(1024ULL, 1ULL <<
bits::hi(m_superblocks)));
176 return ((m_data[block] >> (i & 63)) & 1ULL);
189 assert(idx + len - 1 < m_size);
192 bs = (idx + len - 1) >> m_block_shift;
193 size_type e_block = bs + ((idx + len - 1) >> 6) + 1;
194 if (b_block == e_block)
196 return (m_data[b_block] >> (idx & 63)) &
bits::lo_set[len];
200 uint8_t b_len = 64 - (idx & 63);
201 return (m_data[b_block] >> (idx & 63)) | (m_data[e_block] &
bits::lo_set[len - b_len]) << b_len;
216 written_bytes +=
write_member(m_size, out, child,
"size");
217 written_bytes +=
write_member(m_block_num, out, child,
"block_num");
218 written_bytes +=
write_member(m_superblocks, out, child,
"superblocks");
219 written_bytes +=
write_member(m_block_shift, out, child,
"block_shift");
220 written_bytes += m_data.
serialize(out, child,
"data");
221 written_bytes += m_rank_samples.
serialize(out, child,
"rank_samples");
223 return written_bytes;
234 m_rank_samples.
load(in);
237 template <
typename archive_t>
248 template <
typename archive_t>
271 return m_size == v.m_size && m_data == v.m_data;
276 return !(*
this == v);
280template <u
int8_t t_b, u
int32_t t_bs>
283 static_assert(t_b == 1 or t_b == 0,
"rank_support_il only supports bitpatterns 0 or 1.");
305 size_type SBlockNum = i >> m_block_shift;
306 size_type SBlockPos = (SBlockNum << m_block_size_U64) + SBlockNum;
307 uint64_t resp = m_v->m_data[SBlockPos];
308 uint64_t
const * B = (m_v->m_data.data() + (SBlockPos + 1));
309 uint64_t rem = i & 63;
310 uint64_t
bits = (i & m_block_mask) - rem;
322 size_type SBlockNum = i >> m_block_shift;
323 size_type SBlockPos = (SBlockNum << m_block_size_U64) + SBlockNum;
324 uint64_t resp = (SBlockNum << m_block_shift) - m_v->m_data[SBlockPos];
325 uint64_t
const * B = (m_v->m_data.data() + (SBlockPos + 1));
326 uint64_t rem = i & 63;
327 uint64_t
bits = (i & m_block_mask) - rem;
343 m_block_mask = t_bs - 1;
344 m_block_size_U64 =
bits::hi(t_bs >> 6);
389 template <
typename archive_t>
393 template <
typename archive_t>
399 return (*m_v == *other.m_v);
404 return !(*
this == other);
408template <u
int8_t t_b, u
int32_t t_bs>
411 static_assert(t_b == 1 or t_b == 0,
"select_support_il only supports bitpatterns 0 or 1.");
434 size_type lb = 0, rb = m_v->m_superblocks;
444 if (idx < m_v->m_rank_samples.size())
446 if (m_v->m_rank_samples[idx] >= i)
448 idx = (idx << 1) + 1;
453 idx = (idx << 1) + 2;
460 size_type pos = (mid << m_block_size_U64) + mid;
463 if (m_v->m_data[pos] >= i)
475 res = (rb - 1) << m_block_shift;
477 uint64_t
const * w = m_v->m_data.data() + ((rb - 1) << m_block_size_U64) + (rb - 1);
496 size_type lb = 0, rb = m_v->m_superblocks;
506 if (idx < m_v->m_rank_samples.size())
508 if (((mid << m_block_shift) - m_v->m_rank_samples[idx]) >= i)
510 idx = (idx << 1) + 1;
515 idx = (idx << 1) + 2;
522 size_type pos = (mid << m_block_size_U64) + mid;
525 if (((mid << m_block_shift) - m_v->m_data[pos]) >= i)
537 res = (rb - 1) << m_block_shift;
540 uint64_t
const * w = m_v->m_data.data() + ((rb - 1) << m_block_size_U64) + (rb - 1);
561 m_block_size_U64 =
bits::hi(t_bs >> 6);
606 template <
typename archive_t>
610 template <
typename archive_t>
616 return (*m_v == *other.m_v);
621 return !(*
this == other);
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
A bit vector which interleaves the original bit_vector with rank information.
bit_vector_il(bit_vector_il &&)=default
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
void load(std::istream &in)
Loads the data structure from the given istream.
bit_vector::difference_type difference_type
bit_vector_il(bit_vector const &bv)
value_type operator[](size_type i) const
Accessing the i-th element of the original bit_vector.
uint64_t get_int(size_type idx, uint8_t len=64) const
Get the integer value of the binary string of length len starting at position idx.
bit_vector_il & operator=(bit_vector_il &&)=default
bool operator==(bit_vector_il const &v) const
select_support_il< 1, t_bs > select_1_type
bit_vector_il & operator=(bit_vector_il const &)=default
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
size_type size() const
Returns the size of the original bit vector.
select_support_il< 0, t_bs > select_0_type
bit_vector_il(bit_vector_il const &)=default
rank_support_il< 1, t_bs > rank_1_type
bool operator!=(bit_vector_il const &v) const
random_access_const_iterator< bit_vector_il > iterator
bit_vector::size_type size_type
rank_support_il< 0, t_bs > rank_0_type
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
A generic vector class for integers of width .
uint64_t const * data() const noexcept
Pointer to the raw data of the int_vector.
int_vector_size_type size_type
ptrdiff_t difference_type
void load(std::istream &in)
Load the int_vector for a stream.
size_type size() const noexcept
The number of elements in the int_vector.
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the int_vector to a stream.
void resize(const size_type size)
Resize the int_vector in terms of elements.
Generic iterator for a random access container.
rank_support_il & operator=(rank_support_il const &rs)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
rank_support_il(bit_vector_type const *v=nullptr)
size_type rank(size_type i) const
Returns the position of the i-th occurrence in the bit vector.
bool operator!=(rank_support_il const &other) const noexcept
size_type operator()(size_type i) const
bool operator==(rank_support_il const &other) const noexcept
void load(std::istream &, bit_vector_type const *v=nullptr)
bit_vector_il< t_bs > bit_vector_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
bit_vector::size_type size_type
void set_vector(bit_vector_type const *v=nullptr)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
void load(std::istream &, bit_vector_type const *v=nullptr)
size_type select(size_type i) const
Returns the position of the i-th occurrence in the bit vector.
select_support_il(bit_vector_type const *v=nullptr)
bool operator!=(select_support_il const &other) const noexcept
size_type operator()(size_type i) const
select_support_il & operator=(select_support_il const &rs)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
bool operator==(select_support_il const &other) const noexcept
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
bit_vector_il< t_bs > bit_vector_type
bit_vector::size_type size_type
void set_vector(bit_vector_type const *v=nullptr)
static structure_tree_node * add_child(structure_tree_node *v, std::string const &name, std::string const &type)
static void add_size(structure_tree_node *v, uint64_t value)
int_vector.hpp contains the sdsl::int_vector class.
io.hpp contains some methods for reading/writing sdsl structures.
iterators.hpp contains an generic iterator for random access containers.
Namespace for the succinct data structure library.
size_t write_member(T const &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
constexpr bool power_of_two(T x)
size_t serialize_empty_object(std::ostream &, structure_tree_node *v=nullptr, std::string name="", T const *t=nullptr)
Contains declarations and definitions of data structure concepts.
A helper class for bitwise tricks on 64 bit words.
static constexpr uint32_t sel(uint64_t x, uint32_t i)
Calculate the position of the i-th rightmost 1 bit in the 64bit integer x.
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
static constexpr uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
static constexpr uint64_t lo_set[65]
lo_set[i] is a 64-bit word with the i least significant bits set and the high bits not set.
structure_tree.hpp contains a helper class which can represent the memory structure of a class.
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.