9#ifndef INCLUDED_SDSL_RANK_SUPPORT_INT
10#define INCLUDED_SDSL_RANK_SUPPORT_INT
28class structure_tree_node;
32#define likely(x) __builtin_expect((x), 1)
33#define unlikely(x) __builtin_expect((x), 0)
49template <u
int8_t alphabet_size>
57 static_assert(alphabet_size > 2,
"Rank support is only implemented on int_vectors with an alphabet size of > 2.");
63 template <
typename u
intX_t>
64 static constexpr uintX_t
bm_rec(
const uintX_t w,
const uint8_t length,
const uint8_t max_length)
66 return (length >= max_length) ? w :
bm_rec(w | (w << length), length << 1, max_length);
71 std::array<uint64_t, alphabet_size>
masks{};
76 for (uint8_t i =
sigma_bits * 2; i < 64; i <<= 1)
80 uint64_t tmp_carry =
masks[1];
88 static constexpr uint8_t
sigma{alphabet_size};
93 static const std::array<uint64_t, alphabet_size>
masks;
103 assert((v !=
nullptr) ?
sigma_bits == v->width() :
true);
192 template <
typename... value_t>
193 static constexpr std::array<uint64_t,
sizeof...(value_t)>
198 uint64_t
const w_even =
even_mask & word;
230 return *(data + word_position);
234template <u
int8_t alphabet_size>
bits.hpp contains the sdsl::bits class.
A generic vector class for integers of width .
The base class of classes supporting rank_queries for a sdsl::int_vector in constant time.
virtual void load(std::istream &in, int_vector<> const *v=nullptr)=0
Loads the rank_support_int.
virtual void set_vector(int_vector<> const *v=nullptr)=0
Sets the supported int_vector to the given pointer.
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.
int_vector const * m_v
Pointer to the rank supported bit_vector.
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.
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.
rank_support_int & operator=(rank_support_int &&)=default
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(int_vector<> const *v=nullptr)
Constructor.
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
static constexpr uint8_t bits_per_word
int_vector ::value_type value_type
rank_support_int(rank_support_int const &)=default
Copy constructor.
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
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.
rank_support_int & operator=(rank_support_int const &)=default
static constexpr uint64_t extract_word(uint64_t const *data, const size_type word_position) noexcept
Returns the word a the given word position.
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)
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.