9#ifndef INCLUDED_SDSL_SD_VECTOR
10#define INCLUDED_SDSL_SD_VECTOR
35template <uint8_t t_b = 1,
37 class t_select_1 =
typename t_hi_bit_vector::select_1_type,
38 class t_select_0 =
typename t_hi_bit_vector::select_0_type>
41template <uint8_t t_b = 1,
43 class t_select_1 =
typename t_hi_bit_vector::select_1_type,
44 class t_select_0 =
typename t_hi_bit_vector::select_0_type>
45class select_support_sd;
52 template <
typename,
typename,
typename>
99 assert(i >= m_tail && i < m_size);
100 assert(m_items < m_capacity);
103 m_highpos += (cur_high - m_last_high);
104 m_last_high = cur_high;
105 m_low[m_items++] = i;
106 m_high[m_highpos++] = 1;
132 class t_select_1 =
typename t_hi_bit_vector::select_1_type,
133 class t_select_0 =
typename t_hi_bit_vector::select_0_type>
166 uint8_t
const &
wl = m_wl;
180 m_high_1_select(sd.m_high_1_select),
181 m_high_0_select(sd.m_high_0_select)
183 m_high_1_select.set_vector(&m_high);
184 m_high_0_select.set_vector(&m_high);
192 *
this = std::move(tmp);
203 m_low = std::move(v.m_low);
204 m_high = std::move(v.m_high);
205 m_high_1_select = std::move(v.m_high_1_select);
206 m_high_1_select.set_vector(&m_high);
207 m_high_0_select = std::move(v.m_high_0_select);
208 m_high_0_select.set_vector(&m_high);
215 *
this = std::move(sd);
223 uint8_t logn =
bits::hi(m_size) + 1;
231 uint64_t
const * bvp = bv.
data();
232 for (
size_type i = 0, mm = 0, last_high = 0, highpos = 0; i < (bv.
size() + 63) / 64; ++i, ++bvp)
241 if (position >= bv.
size())
245 highpos += (cur_high - last_high);
246 last_high = cur_high;
248 m_low[mm++] = position;
254 m_high = std::move(
high);
255 util::init_support(m_high_1_select, &m_high);
256 util::init_support(m_high_0_select, &m_high);
259 template <
class t_itr>
268 throw std::runtime_error(
"sd_vector: source list is not sorted.");
271 m_size = *(
end - 1) + 1;
273 uint8_t logn =
bits::hi(m_size) + 1;
282 size_type mm = 0, last_high = 0, highpos = 0;
285 auto position = *itr;
288 highpos += (cur_high - last_high);
289 last_high = cur_high;
291 m_low[mm++] = position;
296 m_high = std::move(
high);
297 util::init_support(m_high_1_select, &m_high);
298 util::init_support(m_high_0_select, &m_high);
305 throw std::runtime_error(
"sd_vector: builder is not at full capacity.");
308 m_size = builder.m_size;
310 m_low = std::move(builder.m_low);
311 m_high = std::move(builder.m_high);
312 util::init_support(m_high_1_select, &(this->m_high));
313 util::init_support(m_high_0_select, &(this->m_high));
331 size_type sel_high = m_high_0_select(high_val + 1);
332 size_type rank_low = sel_high - high_val;
338 while (m_high[sel_high] and m_low[rank_low] > val_low)
348 return m_high[sel_high] and m_low[rank_low] == val_low;
361 uint64_t i = idx + len - 1;
362 uint64_t high_val = (i >> (m_wl));
363 uint64_t sel_high = m_high_0_select(high_val + 1);
364 uint64_t rank_low = sel_high - high_val;
370 while (m_high[sel_high] and m_low[rank_low] > val_low)
383 while (!m_high[sel_high])
385 if (sel_high > 0 and (high_val << m_wl) >= idx)
395 while (m_high[sel_high])
397 uint64_t val = (high_val << m_wl) + m_low[rank_low];
400 res |= 1ULL << (val - idx);
430 written_bytes +=
write_member(m_size, out, child,
"size");
432 written_bytes += m_low.
serialize(out, child,
"low");
433 written_bytes += m_high.serialize(out, child,
"high");
434 written_bytes += m_high_1_select.serialize(out, child,
"high_1_select");
435 written_bytes += m_high_0_select.serialize(out, child,
"high_0_select");
437 return written_bytes;
447 m_high_1_select.load(in, &m_high);
448 m_high_0_select.load(in, &m_high);
451 template <
typename archive_t>
462 template <
typename archive_t>
470 m_high_1_select.set_vector(&m_high);
472 m_high_0_select.set_vector(&m_high);
487 return m_size == v.m_size && m_wl == v.m_wl && m_low == v.m_low && m_high == v.m_high;
492 return !(*
this == v);
500template <u
int8_t t_b>
527template <u
int8_t t_b,
class t_hi_bit_vector,
class t_select_1,
class t_select_0>
530 static_assert(t_b == 1u or t_b == 0u,
"rank_support_sd: bit pattern must be `0` or `1`");
555 assert(m_v !=
nullptr);
556 assert(i <= m_v->
size());
560 size_type sel_high = m_v->high_0_select(high_val + 1);
561 size_type rank_low = sel_high - high_val;
573 while (m_v->high[sel_high] and m_v->low[rank_low] >= val_low);
602 template <
typename archive_t>
606 template <
typename archive_t>
612 return *m_v == *other.m_v;
617 return !(*
this == other);
621template <u
int8_t t_b,
class t_sd_vec>
627 return v->low[i - 1] +
628 ((v->high_1_select(i) + 1 - i) << (v->wl));
633template <
class t_sd_vec>
639 auto ones = v->low.size();
640 assert(0 < i and i <= v->
size() - ones);
648 auto mid = lb + (rb - lb) / 2;
650 auto rank0 = x + 1 - mid;
673template <u
int8_t t_b,
class t_hi_bit_vector,
class t_select_1,
class t_select_0>
728 template <
typename archive_t>
732 template <
typename archive_t>
738 return *m_v == *other.m_v;
743 return !(*
this == other);
751template <
typename t_sd_vector = sd_vector<>>
757 using rank_1 =
typename t_sd_vector::rank_1_type;
788 for (
size_type i = 0, sel0 = 1; i < m_v->high.size(); i += 64)
791 w = m_v->high.get_int(i, 64);
793 rank_0 = (i + 64) - rank1;
794 if (rank1 > 0 and (w >> 63) & 1)
796 uint64_t pos = rank_0 * bs + m_v->low[rank1 - 1];
801 z = rank_0 * bs - rank1;
803 while (sel0 <= z and sel0 <= zeros)
805 m_pointer[(sel0 - 1) / (64 * bs)] = i / 64;
806 m_rank1[(sel0 - 1) / (64 * bs)] = old_rank1;
817 size_type j = m_pointer[(i - 1) / (64 * bs)] * 64;
818 size_type rank1 = m_rank1[(i - 1) / (64 * bs)];
822 if (rank1 > 0 and (m_v->high[j - 1]) & 1)
824 pos = (j - rank1) * bs + m_v->low[rank1 - 1];
829 pos = (j - rank1) * bs;
832 uint64_t w = m_v->high.
get_int(j, 64);
837 if (_rank1 > 0 and (w >> 63) & 1)
839 pos = (j + 64 - _rank1) * bs + m_v->low[_rank1 - 1];
840 _rank0 = pos + 1 - _rank1;
844 pos = (j + 64 - _rank1) * bs;
845 _rank0 = pos - _rank1;
850 w = m_v->high.get_int(j, 64);
864 if (_rank1 > 0 and (w >> 7) & 1)
866 pos = (j + 8 - _rank1) * bs + m_v->low[_rank1 - 1];
867 _rank0 = pos + 1 - _rank1;
871 pos = (j + 8 - _rank1) * bs;
872 _rank0 = pos - _rank1;
894 pos = (j - rank1) * bs;
898 pos = pos - (zeros - i) - 1;
904 pos = (j - 1 - rank1) * bs;
905 size_type one_pos = pos + m_v->low[rank1];
910 pos = one_pos - (zeros - i) - 1;
916 w = m_v->high.get_int(j, 64);
949 written_bytes += m_pointer.
serialize(out, child,
"pointer");
950 written_bytes += m_rank1.
serialize(out, child,
"rank1");
952 return written_bytes;
955 template <
typename archive_t>
962 template <
typename archive_t>
971 return (m_pointer == other.m_pointer) && (m_rank1 == other.m_rank1);
976 return !(*
this == other);
999 if (m_capacity > m_size)
1001 throw std::runtime_error(
"sd_vector_builder: requested capacity is larger than vector size.");
1011 m_high =
bit_vector(m_capacity + (1ULL << logm), 0);
1019 throw std::runtime_error(
"sd_vector: the builder is not full.");
1022 m_size = builder.m_size;
1023 m_wl = builder.m_wl;
1024 m_low = std::move(builder.m_low);
1025 m_high = std::move(builder.m_high);
1026 util::init_support(m_high_1_select, &m_high);
1027 util::init_support(m_high_0_select, &m_high);
1029 builder = sd_vector_builder();
bits.hpp contains the sdsl::bits class.
cereal.hpp offers cereal support
A generic vector class for integers of width .
int_vector_size_type size_type
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.
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.
uint64_t const * data() const noexcept
Pointer to the raw data of 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.
sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > bit_vector_type
void load(std::istream &, bit_vector_type const *v=nullptr)
void set_vector(bit_vector_type const *v=nullptr)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
size_type operator()(size_type i) const
bool operator==(rank_support_sd const &other) const noexcept
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
bit_vector::size_type size_type
rank_support_sd(bit_vector_type const *v=nullptr)
size_type rank(size_type i) const
bool operator!=(rank_support_sd const &other) const noexcept
Class for in-place construction of sd_vector from a strictly increasing sequence.
void set(size_type i)
Set a bit to 1.
size_type capacity() const
bit_vector::size_type size_type
A bit vector which compresses very sparse populated bit vectors by.
hi_bit_vector_type const & high
sd_vector(bit_vector const &bv)
t_select_0 select_0_support_type
select_1_support_type const & high_1_select
rank_support_sd< 1, t_hi_bit_vector, select_1_support_type, select_0_support_type > rank_1_type
bool operator!=(sd_vector const &v) const
sd_vector(sd_vector &&sd)
void load(std::istream &in)
Loads the data structure from the given istream.
bit_vector::size_type size_type
value_type operator[](size_type i) const
Accessing the i-th element of the original bit_vector.
sd_vector & operator=(sd_vector const &v)
sd_vector(const t_itr begin, const t_itr end)
sd_vector & operator=(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.
t_select_1 select_1_support_type
select_0_support_type const & high_0_select
sd_vector(sd_vector_builder &builder)
t_hi_bit_vector hi_bit_vector_type
sd_vector(sd_vector const &sd)
rank_support_sd< 0, t_hi_bit_vector, select_1_support_type, select_0_support_type > rank_0_type
select_support_sd< 0, t_hi_bit_vector, select_1_support_type, select_0_support_type > select_0_type
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.
bool operator==(sd_vector const &v) const
select_support_sd< 1, t_hi_bit_vector, select_1_support_type, select_0_support_type > select_1_type
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
size_type size() const
Returns the size of the original bit vector.
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
bit_vector::difference_type difference_type
random_access_const_iterator< sd_vector > iterator
Select_0 data structure for sd_vector.
void CEREAL_SAVE_FUNCTION_NAME(archive_t &ar) const
void CEREAL_LOAD_FUNCTION_NAME(archive_t &ar)
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
bool operator!=(select_0_support_sd const &other) const noexcept
bit_vector::size_type size_type
typename t_sd_vector::rank_1_type rank_1
select_0_support_sd(bit_vector_type const *v=nullptr)
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.
t_sd_vector bit_vector_type
bool operator==(select_0_support_sd const &other) const noexcept
typename t_sd_vector::select_0_type sel0_type
void set_vector(bit_vector_type const *v=nullptr)
void load(std::istream &in, bit_vector_type const *v=nullptr)
Select data structure for sd_vector.
void set_vector(bit_vector_type const *v=nullptr)
void CEREAL_SAVE_FUNCTION_NAME(archive_t &) const
sd_vector< t_hi_bit_vector, t_select_1, t_select_0 > bit_vector_type
select_support_sd(bit_vector_type const *v=nullptr)
void CEREAL_LOAD_FUNCTION_NAME(archive_t &)
bool operator==(select_support_sd const &other) const noexcept
size_type serialize(std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
bool operator!=(select_support_sd const &other) const noexcept
void load(std::istream &, bit_vector_type const *v=nullptr)
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.
bit_vector::size_type size_type
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.
Number of set bits in v t_int_vec::size_type cnt_one_bits(t_int_vec const &v)
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)
int_vector< 1 > bit_vector
bit_vector is a specialization of the int_vector.
int_vector ::size_type size(range_type const &r)
Size of a range.
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.
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
static constexpr uint32_t lo(uint64_t x)
Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
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.
static constexpr uint8_t lt_cnt[256]
Lookup table for byte popcounts.
bit_vector::size_type size_type
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, t_sd_vec const *v)
static size_type select(size_type i, t_sd_vec const *v)
bit_vector::size_type size_type
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.