8#ifndef INCLUDED_SDSL_SELECT_SUPPORT
9#define INCLUDED_SDSL_SELECT_SUPPORT
72template <u
int8_t bit_pattern, u
int8_t pattern_len>
158 if (i > 0 and v[i - 1] and !v[i])
return true;
161 static uint64_t
init_carry(
const uint64_t * data,
size_type word_pos) {
return word_pos ? (*(data - 1) >> 63) : 0; }
162 static uint64_t
get_carry(uint64_t w) {
return w >> 63; }
186 if (i > 0 and !v[i - 1] and v[i])
return true;
189 static uint64_t
init_carry(
const uint64_t * data,
size_type word_pos) {
return word_pos ? (*(data - 1) >> 63) : 1; }
190 static uint64_t
get_carry(uint64_t w) {
return w >> 63; }
200 const uint64_t * data = v.
data();
201 if (v.
empty())
return 0;
204 for (
auto end = v.
data() + (v.
size() >> 6); data < end; ++data)
237 return bits::sel(~(((w << 1) | carry) | w), i);
240 static uint64_t
init_carry(
const uint64_t * data,
size_type word_pos) {
return word_pos ? (*(data - 1) >> 63) : 1; }
241 static uint64_t
get_carry(uint64_t w) {
return w >> 63; }
251 const uint64_t * data = v.
data();
252 if (v.
empty())
return 0;
255 for (
auto end = v.
data() + (v.
size() >> 6); data < end; ++data)
273 res =
bits::cnt((w >> (offset - 1)) & (w >> offset));
288 return bits::sel(((w << 1) | carry) & w, i);
292 if (i > 0 and v[i - 1] and v[i])
return true;
295 static uint64_t
init_carry(
const uint64_t * data,
size_type word_pos) {
return word_pos ? (*(data - 1) >> 63) : 0; }
296 static uint64_t
get_carry(uint64_t w) {
return w >> 63; }
A generic vector class for integers of width .
bool empty() const noexcept
Equivalent to size() == 0.
int_vector_size_type size_type
size_type bit_size() const noexcept
The number of bits in the int_vector.
size_type size() const noexcept
The number of elements in the int_vector.
const uint64_t * data() const noexcept
Pointer to the raw data of the int_vector.
The base class of classes supporting select queries for a sdsl::bit_vector in constant time.
select_support(const select_support &f_v)
Copy constructor.
const int_vector< 1 > * m_v
Pointer to the select supported sdsl::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.
virtual void load(std::istream &in, const int_vector< 1 > *v=nullptr)=0
Load the select_support from an in file stream.
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.
virtual ~select_support()
Destructor of select_support.
select_support(const int_vector< 1 > *f_v=nullptr)
Constructor of select_support.
virtual void set_vector(const int_vector< 1 > *v=nullptr)=0
This method sets the supported bit_vector.
int_vector.hpp contains the sdsl::int_vector class.
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_onezero_bits(const t_int_vec &v)
Number of occurrences of bit pattern in v t_int_vec::size_type cnt_zeroone_bits(const t_int_vec &v)
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.
rank_support.hpp contains classes that support a sdsl::bit_vector with constant time rank information...
select_support_mcl.hpp contains classes that support a sdsl::bit_vector with constant time select inf...
select_support_scan.hpp contains classes that support a sdsl::bit_vector with linear time select.
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 bool found_arg(size_type i, const bit_vector &v)
static size_type ith_arg_pos_in_the_word(uint64_t w, size_type i, uint64_t carry)
select_support::size_type size_type
static size_type arg_cnt(const bit_vector &v)
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 ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
static uint64_t init_carry(const uint64_t *data, size_type word_pos)
static uint64_t get_carry(uint64_t w)
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, const bit_vector &v)
select_support::size_type size_type
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static uint64_t init_carry(const uint64_t *data, size_type word_pos)
static size_type arg_cnt(const bit_vector &v)
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 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)
static bool found_arg(size_type i, const bit_vector &v)
select_support::size_type size_type
static size_type arg_cnt(const bit_vector &v)
static uint64_t get_carry(uint64_t)
static uint64_t init_carry(const uint64_t *, size_type)
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)
static size_type arg_cnt(const bit_vector &v)
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 bool found_arg(size_type i, const bit_vector &v)
static size_type args_in_the_word(uint64_t w, uint64_t &carry)
static uint64_t init_carry(const uint64_t *data, size_type word_pos)
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 ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t carry)
static uint64_t init_carry(const uint64_t *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 args_in_the_first_word(uint64_t w, uint8_t offset, uint64_t carry)
select_support::size_type size_type
static size_type arg_cnt(const bit_vector &v)
static bool found_arg(size_type i, const bit_vector &v)
static size_type arg_cnt(const bit_vector &v)
static size_type ith_arg_pos_in_the_first_word(uint64_t w, size_type i, uint8_t offset, uint64_t)
static bool found_arg(size_type i, const bit_vector &v)
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 uint64_t init_carry(const uint64_t *, size_type)
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 size_type args_in_the_word(uint64_t, uint64_t &)
static uint64_t init_carry(const uint64_t *, size_type)
static bool found_arg(size_type, const bit_vector &)
select_support::size_type size_type
static size_type arg_cnt(const bit_vector &)
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)