9#ifndef INCLUDED_SDSL_RANK_SUPPORT_INT
10#define INCLUDED_SDSL_RANK_SUPPORT_INT
20#define likely(x) __builtin_expect((x), 1)
21#define unlikely(x) __builtin_expect((x), 0)
37template <u
int8_t alphabet_size>
45 static_assert(alphabet_size > 2,
"Rank support is only implemented on int_vectors with an alphabet size of > 2.");
51 template <
typename u
intX_t>
52 static constexpr uintX_t
bm_rec(
const uintX_t w,
const uint8_t length,
const uint8_t max_length)
54 return (length >= max_length) ? w :
bm_rec(w | (w << length), length << 1, max_length);
59 std::array<uint64_t, alphabet_size>
masks{};
67 uint64_t tmp_carry =
masks[1];
74 static constexpr uint8_t
sigma{ alphabet_size };
79 static const std::array<uint64_t, alphabet_size>
masks;
89 assert((v !=
nullptr) ?
sigma_bits == v->width() :
true);
177 template <
typename... value_t>
178 static constexpr std::array<uint64_t,
sizeof...(value_t)>
word_prefix_rank(
const uint64_t word,
180 const value_t... values)
noexcept
184 uint64_t
const w_even =
even_mask & word;
216 return *(data + word_position);
220template <u
int8_t alphabet_size>
A generic vector class for integers of width .
The base class of classes supporting rank_queries for a sdsl::int_vector in constant time.
static constexpr uint64_t carry_select_mask
static constexpr uint64_t set_positions(const uint64_t w, const value_type v) noexcept
Count how often value v occurs in the word w.
static constexpr uint64_t set_positions_prefix(const uint64_t w, const value_type v) noexcept
Count how often value v or smaller occurs in the word w.
static constexpr uintX_t bm_rec(const uintX_t w, const uint8_t length, const uint8_t max_length)
Constructs a bit mask with the pattern w of a given length.
rank_support_int(const int_vector<> *v=nullptr)
Constructor.
static std::array< uint64_t, alphabet_size > generate_mask_array()
virtual size_type prefix_rank(const size_type i, const value_type v) const =0
Answers rank queries for the supported int_vector.
virtual void load(std::istream &in, const int_vector<> *v=nullptr)=0
Loads the rank_support_int.
rank_support_int & operator=(rank_support_int &&)=default
static constexpr uint64_t extract_word(const uint64_t *data, const size_type word_position) noexcept
Returns the word a the given word position.
rank_support_int(rank_support_int &&)=default
virtual size_type rank(const size_type i, const value_type v) const =0
Answers rank queries for the supported int_vector.
static constexpr uint8_t sigma_bits
rank_support_int(const rank_support_int &)=default
Copy constructor.
rank_support_int & operator=(const rank_support_int &)=default
static constexpr std::array< uint64_t, sizeof...(value_t)> word_prefix_rank(const uint64_t word, const size_type bit_pos, const value_t... values) noexcept
Counts the occurrences of elements smaller or equal to v in the word starting at data up to position ...
static constexpr uint8_t sigma
const int_vector * m_v
Pointer to the rank supported bit_vector.
static constexpr uint8_t bits_per_word
int_vector ::value_type value_type
static constexpr uint64_t mask_prefix(value_type const v, uint64_t const w_even, uint64_t const w_odd) noexcept
Mask the set prefix positions.
static constexpr uint32_t full_word_prefix_rank(const uint64_t word, const value_type v) noexcept
Counts the occurrences of v in the word starting at data up to position idx.
static constexpr uint64_t even_mask
static constexpr uint32_t word_rank(const uint64_t word, const size_type bit_pos, const value_type v) noexcept
Counts the occurrences of elements smaller or equal to v in the word starting at data up to position ...
static const std::array< uint64_t, alphabet_size > masks
int_vector ::size_type size_type
virtual void set_vector(const int_vector<> *v=nullptr)=0
Sets the supported int_vector to the given pointer.
static constexpr uint32_t full_word_rank(const uint64_t word, const value_type v) noexcept
Counts the occurrences of v in the word starting at data up to position idx.
virtual size_type operator()(const size_type idx, const value_type v) const =0
Alias for rank(idx, v)
virtual size_type serialize(std::ostream &out, structure_tree_node *v, const std::string name) const =0
Serializes rank_support_int.
virtual ~rank_support_int()
Destructor.
int_vector.hpp contains the sdsl::int_vector class.
Namespace for the succinct data structure library.
constexpr size_t ceil_log2(size_t const n)
constexpr size_t floor_log2(size_t const n)
rank_support_int_scan.hpp contains rank_support_int_scan that support a sdsl::int_vector with linear ...
rank_support_int_v.hpp contains rank_support_int_v.
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.
uint128_t.hpp contains contains the definition of a 128-bit unsigned integer type.