9 #ifndef INCLUDED_SDSL_SD_VECTOR
10 #define INCLUDED_SDSL_SD_VECTOR
22 template <uint8_t t_b = 1,
24 class t_select_1 =
typename t_hi_bit_vector::select_1_type,
25 class t_select_0 =
typename t_hi_bit_vector::select_0_type>
26 class rank_support_sd;
29 template <uint8_t t_b = 1,
31 class t_select_1 =
typename t_hi_bit_vector::select_1_type,
32 class t_select_0 =
typename t_hi_bit_vector::select_0_type>
33 class select_support_sd;
36 template <
typename,
typename,
typename>
44 template <
typename,
typename,
typename>
79 assert(i >= m_tail && i < m_size);
80 assert(m_items < m_capacity);
83 m_highpos += (cur_high - m_last_high);
84 m_last_high = cur_high;
86 m_high[m_highpos++] = 1;
112 class t_select_1 =
typename t_hi_bit_vector::select_1_type,
113 class t_select_0 =
typename t_hi_bit_vector::select_0_type>
146 const uint8_t &
wl = m_wl;
159 , m_high_1_select(sd.m_high_1_select)
160 , m_high_0_select(sd.m_high_0_select)
162 m_high_1_select.set_vector(&m_high);
163 m_high_0_select.set_vector(&m_high);
171 *
this = std::move(tmp);
182 m_low = std::move(v.m_low);
183 m_high = std::move(v.m_high);
184 m_high_1_select = std::move(v.m_high_1_select);
185 m_high_1_select.set_vector(&m_high);
186 m_high_0_select = std::move(v.m_high_0_select);
187 m_high_0_select.set_vector(&m_high);
199 uint8_t logn =
bits::hi(m_size) + 1;
207 const uint64_t * bvp = bv.
data();
208 for (
size_type i = 0, mm = 0, last_high = 0, highpos = 0; i < (bv.
size() + 63) / 64; ++i, ++bvp)
217 if (position >= bv.
size())
221 highpos += (cur_high - last_high);
222 last_high = cur_high;
224 m_low[mm++] = position;
230 m_high = std::move(
high);
231 util::init_support(m_high_1_select, &m_high);
232 util::init_support(m_high_0_select, &m_high);
235 template <
class t_itr>
239 if (!is_sorted(
begin,
end)) {
throw std::runtime_error(
"sd_vector: source list is not sorted."); }
241 m_size = *(
end - 1) + 1;
243 uint8_t logn =
bits::hi(m_size) + 1;
252 size_type mm = 0, last_high = 0, highpos = 0;
255 auto position = *itr;
258 highpos += (cur_high - last_high);
259 last_high = cur_high;
261 m_low[mm++] = position;
266 m_high = std::move(
high);
267 util::init_support(m_high_1_select, &m_high);
268 util::init_support(m_high_0_select, &m_high);
275 throw std::runtime_error(
"sd_vector: builder is not at full capacity.");
278 m_size = builder.m_size;
280 m_low = std::move(builder.m_low);
281 m_high = std::move(builder.m_high);
282 util::init_support(m_high_1_select, &(this->m_high));
283 util::init_support(m_high_0_select, &(this->m_high));
301 size_type sel_high = m_high_0_select(high_val + 1);
302 size_type rank_low = sel_high - high_val;
303 if (0 == rank_low)
return 0;
307 while (m_high[sel_high] and m_low[rank_low] > val_low)
317 return m_high[sel_high] and m_low[rank_low] == val_low;
330 uint64_t i = idx + len - 1;
331 uint64_t high_val = (i >> (m_wl));
332 uint64_t sel_high = m_high_0_select(high_val + 1);
333 uint64_t rank_low = sel_high - high_val;
334 if (0 == rank_low)
return 0;
338 while (m_high[sel_high] and m_low[rank_low] > val_low)
351 while (!m_high[sel_high])
353 if (sel_high > 0 and (high_val << m_wl) >= idx)
363 while (m_high[sel_high])
365 uint64_t val = (high_val << m_wl) + m_low[rank_low];
366 if (val >= idx) { res |= 1ULL << (val - idx); }
392 written_bytes +=
write_member(m_size, out, child,
"size");
394 written_bytes += m_low.
serialize(out, child,
"low");
395 written_bytes += m_high.serialize(out, child,
"high");
396 written_bytes += m_high_1_select.serialize(out, child,
"high_1_select");
397 written_bytes += m_high_0_select.serialize(out, child,
"high_0_select");
399 return written_bytes;
409 m_high_1_select.load(in, &m_high);
410 m_high_0_select.load(in, &m_high);
413 template <
typename archive_t>
424 template <
typename archive_t>
432 m_high_1_select.set_vector(&m_high);
434 m_high_0_select.set_vector(&m_high);
443 return m_size == v.m_size && m_wl == v.m_wl && m_low == v.m_low && m_high == v.m_high;
453 template <u
int8_t t_b>
474 template <u
int8_t t_b,
class t_hi_bit_vector,
class t_select_1,
class t_select_0>
477 static_assert(t_b == 1u or t_b == 0u,
"rank_support_sd: bit pattern must be `0` or `1`");
499 assert(m_v !=
nullptr);
500 assert(i <= m_v->
size());
504 size_type sel_high = m_v->high_0_select(high_val + 1);
505 size_type rank_low = sel_high - high_val;
513 }
while (m_v->high[sel_high] and m_v->low[rank_low] >= val_low);
530 template <
typename archive_t>
534 template <
typename archive_t>
543 template <u
int8_t t_b,
class t_sd_vec>
549 return v->low[i - 1] +
550 ((v->high_1_select(i) + 1 - i) << (v->wl));
555 template <
class t_sd_vec>
561 auto ones = v->low.size();
562 assert(0 < i and i <= v->
size() - ones);
570 auto mid = lb + (rb - lb) / 2;
572 auto rank0 = x + 1 - mid;
573 if (rank0 >= i) { rb = mid; }
592 template <u
int8_t t_b,
class t_hi_bit_vector,
class t_select_1,
class t_select_0>
629 template <
typename archive_t>
633 template <
typename archive_t>
646 template <
typename t_sd_vector = sd_vector<>>
652 using rank_1 =
typename t_sd_vector::rank_1_type;
683 for (
size_type i = 0, sel0 = 1; i < m_v->high.size(); i += 64)
686 w = m_v->high.get_int(i, 64);
688 rank_0 = (i + 64) - rank1;
689 if (rank1 > 0 and (w >> 63) & 1)
691 uint64_t pos = rank_0 * bs + m_v->low[rank1 - 1];
696 z = rank_0 * bs - rank1;
698 while (sel0 <= z and sel0 <= zeros)
700 m_pointer[(sel0 - 1) / (64 * bs)] = i / 64;
701 m_rank1[(sel0 - 1) / (64 * bs)] = old_rank1;
712 size_type j = m_pointer[(i - 1) / (64 * bs)] * 64;
713 size_type rank1 = m_rank1[(i - 1) / (64 * bs)];
717 if (rank1 > 0 and (m_v->high[j - 1]) & 1)
719 pos = (j - rank1) * bs + m_v->low[rank1 - 1];
724 pos = (j - rank1) * bs;
727 uint64_t w = m_v->high.
get_int(j, 64);
731 if (_rank1 > 0 and (w >> 63) & 1)
733 pos = (j + 64 - _rank1) * bs + m_v->low[_rank1 - 1];
734 _rank0 = pos + 1 - _rank1;
738 pos = (j + 64 - _rank1) * bs;
739 _rank0 = pos - _rank1;
744 w = m_v->high.get_int(j, 64);
756 if (_rank1 > 0 and (w >> 7) & 1)
758 pos = (j + 8 - _rank1) * bs + m_v->low[_rank1 - 1];
759 _rank0 = pos + 1 - _rank1;
763 pos = (j + 8 - _rank1) * bs;
764 _rank0 = pos - _rank1;
784 pos = (j - rank1) * bs;
788 pos = pos - (zeros - i) - 1;
794 pos = (j - 1 - rank1) * bs;
795 size_type one_pos = pos + m_v->low[rank1];
800 pos = one_pos - (zeros - i) - 1;
804 if (j % 64 == 0) { w = m_v->high.get_int(j, 64); }
826 written_bytes += m_pointer.
serialize(out, child,
"pointer");
827 written_bytes += m_rank1.
serialize(out, child,
"rank1");
829 return written_bytes;
832 template <
typename archive_t>
839 template <
typename archive_t>
848 return (m_pointer == other.m_pointer) && (m_rank1 == other.m_rank1);
873 if (m_capacity > m_size)
875 throw std::runtime_error(
"sd_vector_builder: requested capacity is larger than vector size.");
885 m_high =
bit_vector(m_capacity + (1ULL << logm), 0);
891 if (builder.
items() != builder.
capacity()) {
throw std::runtime_error(
"sd_vector: the builder is not full."); }
893 m_size = builder.m_size;
895 m_low = std::move(builder.m_low);
896 m_high = std::move(builder.m_high);
897 util::init_support(m_high_1_select, &m_high);
898 util::init_support(m_high_0_select, &m_high);
900 builder = sd_vector_builder();
value_type get_int(size_type idx, const uint8_t len=64) const
Get the integer value of the binary string of length len starting at position idx in the int_vector.
int_vector_size_type size_type
ptrdiff_t difference_type
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
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.
Generic iterator for a random access container.
Rank data structure for sd_vector.
bit_vector::size_type size_type
sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > bit_vector_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
size_type operator()(size_type i) const
rank_support_sd(const bit_vector_type *v=nullptr)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
bool operator==(const rank_support_sd &other) const noexcept
void load(std::istream &, const bit_vector_type *v=nullptr)
size_type rank(size_type i) const
void set_vector(const bit_vector_type *v=nullptr)
bool operator!=(const rank_support_sd &other) const noexcept
Class for in-place construction of sd_vector from a strictly increasing sequence.
bit_vector::size_type size_type
void set(size_type i)
Set a bit to 1.
size_type capacity() const
A bit vector which compresses very sparse populated bit vectors by.
const select_1_support_type & high_1_select
t_select_1 select_1_support_type
select_support_sd< 1, t_hi_bit_vector, select_1_support_type, select_0_support_type > select_1_type
rank_support_sd< 0, t_hi_bit_vector, select_1_support_type, select_0_support_type > rank_0_type
bit_vector::size_type size_type
sd_vector(const bit_vector &bv)
sd_vector(sd_vector &&sd)
const hi_bit_vector_type & high
void load(std::istream &in)
Loads the data structure from the given istream.
value_type operator[](size_type i) const
Accessing the i-th element of the original bit_vector.
t_select_0 select_0_support_type
t_hi_bit_vector hi_bit_vector_type
sd_vector(const t_itr begin, const t_itr end)
sd_vector & operator=(const sd_vector &v)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
Serializes the data structure into the given ostream.
rank_support_sd< 1, t_hi_bit_vector, select_1_support_type, select_0_support_type > rank_1_type
bit_vector::difference_type difference_type
sd_vector & operator=(sd_vector &&v)
sd_vector(sd_vector_builder &builder)
random_access_const_iterator< sd_vector > iterator
bool operator==(const sd_vector &v) const
uint64_t get_int(size_type idx, const uint8_t len=64) const
Get the integer value of the binary string of length len starting at position idx.
select_support_sd< 0, t_hi_bit_vector, select_1_support_type, select_0_support_type > select_0_type
bool operator!=(const sd_vector &v) const
const select_0_support_type & high_0_select
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
sd_vector(const sd_vector &sd)
size_type size() const
Returns the size of the original bit vector.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
Select_0 data structure for sd_vector.
bool operator!=(const select_0_support_sd &other) const noexcept
void set_vector(const bit_vector_type *v=nullptr)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
t_sd_vector bit_vector_type
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
select_0_support_sd(const bit_vector_type *v=nullptr)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
void load(std::istream &in, const bit_vector_type *v=nullptr)
bit_vector::size_type size_type
typename t_sd_vector::rank_1_type rank_1
bool operator==(const select_0_support_sd &other) const noexcept
size_type operator()(size_type i) const
size_type select(size_type i) const
Returns the position of the i-th occurrence in the bit vector.
typename t_sd_vector::select_0_type sel0_type
Select data structure for sd_vector.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
bool operator!=(const select_support_sd &other) const noexcept
bool operator==(const select_support_sd &other) const noexcept
sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > bit_vector_type
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
void set_vector(const bit_vector_type *v=nullptr)
void load(std::istream &, const bit_vector_type *v=nullptr)
size_type operator()(size_type i) const
select_support_sd(const bit_vector_type *v=nullptr)
size_type select(size_type i) const
Returns the position of the i-th occurrence in the bit vector.
bit_vector::size_type size_type
static void add_size(structure_tree_node *v, uint64_t value)
static structure_tree_node * add_child(structure_tree_node *v, const std::string &name, const std::string &type)
int_vector.hpp contains the sdsl::int_vector class.
iterators.hpp contains an generic iterator for random access containers.
Number of set bits in v t_int_vec::size_type cnt_one_bits(const t_int_vec &v)
Namespace for the succinct data structure library.
size_t write_member(const T &t, std::ostream &out, sdsl::structure_tree_node *v=nullptr, std::string name="")
void read_member(T &t, std::istream &in)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
int_vector ::size_type size(const range_type &r)
Size of a range.
size_t serialize_empty_object(std::ostream &, structure_tree_node *v=nullptr, std::string name="", const T *t=nullptr)
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
static SDSL_CONSTEXPR uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
constexpr static 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.
constexpr static uint8_t lt_cnt[256]
Lookup table for byte popcounts.
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
static SDSL_CONSTEXPR uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
static size_type adjust_rank(size_type r, size_type n)
bit_vector::size_type size_type
static size_type adjust_rank(size_type r, size_type)
bit_vector::size_type size_type
static size_type select(size_type i, const t_sd_vec *v)
bit_vector::size_type size_type
static size_type select(size_type i, const t_sd_vec *v)
bit_vector::size_type size_type
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.