8#ifndef INCLUDED_SDSL_SELECT_SUPPORT
9#define INCLUDED_SDSL_SELECT_SUPPORT
27class structure_tree_node;
80template <u
int8_t bit_pattern, u
int8_t pattern_len>
232 if (i > 0 and v[i - 1] and !v[i])
238 return word_pos ? (*(data - 1) >> 63) : 0;
273 if (i > 0 and !v[i - 1] and v[i])
279 return word_pos ? (*(data - 1) >> 63) : 1;
294 uint64_t
const * data = v.
data();
299 for (
auto end = v.
data() + (v.
size() >> 6); data < end; ++data)
332 return bits::sel(~(((w << 1) | carry) | w), i);
336 return i > 0 and !v[i - 1] and !v[i];
340 return word_pos ? (*(data - 1) >> 63) : 1;
355 uint64_t
const * data = v.
data();
360 for (
auto end = v.
data() + (v.
size() >> 6); data < end; ++data)
378 res =
bits::cnt((w >> (offset - 1)) & (w >> offset));
393 return bits::sel(((w << 1) | carry) & w, i);
397 if (i > 0 and v[i - 1] and v[i])
403 return word_pos ? (*(data - 1) >> 63) : 0;
bits.hpp contains the sdsl::bits class.
A generic vector class for integers of width .
int_vector_size_type size_type
bool empty() const noexcept
Equivalent to size() == 0.
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 bit_size() const noexcept
The number of bits in the int_vector.
The base class of classes supporting select queries for a sdsl::bit_vector in constant time.
int_vector< 1 > const * m_v
Pointer to the select supported sdsl::bit_vector.
virtual void load(std::istream &in, int_vector< 1 > const *v=nullptr)=0
Load the select_support from an in file stream.
virtual void set_vector(int_vector< 1 > const *v=nullptr)=0
This method sets the supported bit_vector.
virtual size_type operator()(size_type i) const =0
Alias for select.
virtual size_type select(size_type i) const =0
Select returns the index of the i-th 1-bit in the supported bit_vector.
int_vector< 1 >::size_type size_type
virtual size_type serialize(std::ostream &out, structure_tree_node *v, std::string name) const =0
Serialize the select_support to an out file stream.
select_support(int_vector< 1 > const *f_v=nullptr)
Constructor of select_support.
select_support(select_support const &f_v)
Copy constructor.
virtual ~select_support()
Destructor of select_support.
int_vector.hpp contains the sdsl::int_vector class.
Number of set bits in v t_int_vec::size_type cnt_one_bits(t_int_vec const &v)
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_zeroone_bits(t_int_vec const &v)
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_onezero_bits(t_int_vec const &v)
Namespace for the succinct data structure library.
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
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 uint64_t lo_unset[65]
lo_unset[i] is a 64-bit word with the i least significant bits not set and the high bits set.
static constexpr uint32_t cnt01(uint64_t x, uint64_t &c)
Count 01 bit pairs in the word x.
static constexpr uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
static constexpr uint64_t map01(uint64_t x, uint64_t c=1)
Map all 01 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
static constexpr uint32_t cnt10(uint64_t x, uint64_t &c)
Count 10 bit pairs in the word 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 uint64_t map10(uint64_t x, uint64_t c=0)
Map all 10 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
static uint64_t init_carry()
static size_type args_in_the_word(uint64_t, uint64_t &)
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
static uint64_t init_carry(uint64_t const *data, size_type word_pos)
select_support::size_type size_type
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
static size_type arg_cnt(bit_vector const &v)
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
static uint64_t get_carry(uint64_t w)
static bool found_arg(size_type i, bit_vector const &v)
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
static bool found_arg(size_type i, bit_vector const &v)
static size_type arg_cnt(bit_vector const &v)
select_support::size_type size_type
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static uint64_t get_carry(uint64_t w)
static uint64_t init_carry(uint64_t const *data, size_type word_pos)
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t)
select_support::size_type size_type
static uint64_t init_carry(uint64_t const *, size_type)
static uint64_t get_carry(uint64_t)
static size_type arg_cnt(bit_vector const &v)
static bool found_arg(size_type i, bit_vector const &v)
static size_type args_in_the_word(uint64_t w, uint64_t &)
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
select_support::size_type size_type
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
static uint64_t init_carry(uint64_t const *data, size_type word_pos)
static bool found_arg(size_type i, bit_vector const &v)
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static uint64_t get_carry(uint64_t w)
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
static size_type arg_cnt(bit_vector const &v)
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
static uint64_t init_carry(uint64_t const *data, size_type word_pos)
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static uint64_t get_carry(uint64_t w)
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
static size_type arg_cnt(bit_vector const &v)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
select_support::size_type size_type
static bool found_arg(size_type i, bit_vector const &v)
static uint64_t init_carry(uint64_t const *, size_type)
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t)
static size_type args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t)
select_support::size_type size_type
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t)
static bool found_arg(size_type i, bit_vector const &v)
static size_type arg_cnt(bit_vector const &v)
static uint64_t get_carry(uint64_t)
static size_type args_in_the_word(uint64_t w, uint64_t &)
static uint64_t get_carry(uint64_t)
static size_type ith_arg_pos_in_the_word(uint64_t, size_type, uint64_t)
static uint64_t init_carry(uint64_t const *, size_type)
static size_type args_in_the_word(uint64_t, uint64_t &)
select_support::size_type size_type
static bool found_arg(size_type, bit_vector const &)
static size_type ith_arg_pos_in_the_first_word(uint64_t, size_type, uint8_t, uint64_t)
static size_type args_in_the_first_word(uint64_t, uint8_t, uint64_t)
static size_type arg_cnt(bit_vector const &)
util.hpp contains some helper methods for int_vector and other stuff like demangle class names.