SDSL 3.0.2
Succinct Data Structure Library
|
A rank structure proposed by Christopher Pockrandt. More...
#include <rank_support_int_v.hpp>
Classes | |
struct | superblock_entry |
Stores a superblock entry in a cache friendly pattern. More... | |
Public Types | |
typedef int_vector ::size_type | size_type |
typedef int_vector ::value_type | value_type |
![]() | |
typedef int_vector ::size_type | size_type |
typedef int_vector ::value_type | value_type |
Public Member Functions | |
rank_support_int_v (int_vector<> const *text_ptr=nullptr) | |
Constructs and initialises the rank support structure for the given text. | |
rank_support_int_v (rank_support_int_v const &)=default | |
Defaulted copy constructor. | |
rank_support_int_v (rank_support_int_v &&)=default | |
Defaulted move constructor. | |
rank_support_int_v & | operator= (rank_support_int_v const &)=default |
Defaulted copy assignment. | |
rank_support_int_v & | operator= (rank_support_int_v &&)=default |
Defaulted move assignment. | |
~rank_support_int_v ()=default | |
Defaulted destructor. | |
size_type | rank (const size_type position, const value_type v) const |
Counts the occurrences of v in the prefix [0..idx-1]. | |
size_type | operator() (const size_type position, const value_type v) const |
Alias for rank(position, v) | |
size_type | prefix_rank (const size_type position, const value_type v) const |
Counts the occurrences of elements smaller or equal to v in the prefix [0..idx-1]. | |
size_type | size () const |
Returns the size of the original text. | |
value_type | value_at (const size_type position) const |
Returns the text value at the given position. | |
size_type | serialize (std::ostream &out, structure_tree_node *v=nullptr, const std::string name="") const |
Saves to the stream. | |
void | load (std::istream &in, int_vector<> const *) |
Loads from the stream. | |
template<typename archive_t > | |
void | CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const |
Saves to the archive. | |
template<typename archive_t > | |
void | CEREAL_LOAD_FUNCTION_NAME (archive_t &ar) |
Loads from the archive. | |
void | set_vector (int_vector<> const *) |
Does nothing for the rank_support_int structure. | |
![]() | |
rank_support_int (int_vector<> const *v=nullptr) | |
Constructor. | |
rank_support_int (rank_support_int const &)=default | |
Copy constructor. | |
rank_support_int (rank_support_int &&)=default | |
rank_support_int & | operator= (rank_support_int const &)=default |
rank_support_int & | operator= (rank_support_int &&)=default |
virtual | ~rank_support_int () |
Destructor. | |
Friends | |
bool | operator== (rank_support_int_v const &lhs, rank_support_int_v const &rhs) noexcept |
Equality operator. | |
bool | operator!= (rank_support_int_v const &lhs, rank_support_int_v const &rhs) noexcept |
Inequality operator. | |
Additional Inherited Members | |
![]() | |
template<typename uintX_t > | |
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 () |
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 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 uint64_t | set_positions (const uint64_t w, const value_type v) noexcept |
Count how often value v occurs in the word w. | |
template<typename... value_t> | |
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 idx. | |
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 idx. | |
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 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. | |
static constexpr uint64_t | extract_word (uint64_t const *data, const size_type word_position) noexcept |
Returns the word a the given word position. | |
![]() | |
int_vector const * | m_v |
Pointer to the rank supported bit_vector. | |
![]() | |
static constexpr uint8_t | sigma {alphabet_size} |
static constexpr uint8_t | sigma_bits {ceil_log2(alphabet_size)} |
static constexpr uint8_t | bits_per_word {(64 / sigma_bits) * sigma_bits} |
static constexpr uint64_t | even_mask {bm_rec<uint64_t>(bits::lo_set[sigma_bits], sigma_bits * 2, 64)} |
static constexpr uint64_t | carry_select_mask {bm_rec<uint64_t>(1ULL << sigma_bits, sigma_bits * 2, 64)} |
static const std::array< uint64_t, alphabet_size > | masks = generate_mask_array() |
A rank structure proposed by Christopher Pockrandt.
This data structure is similar to rank data structures on bit vectors. It supports constant time rank and prefix_rank queries on int vectors.
alphabet_size | Size of the alphabet represented in the int_vector, i.e., largest value + 1. |
words_per_block | Words per block (equivalent to the number of popcount operations in the worst-case per rank query). |
blocks_per_superblock | Blocks per superblock. |
Definition at line 176 of file rank_support_int_v.hpp.
typedef int_vector ::size_type sdsl::rank_support_int< alphabet_size >::size_type |
Definition at line 54 of file rank_support_int.hpp.
typedef int_vector ::value_type sdsl::rank_support_int< alphabet_size >::value_type |
Definition at line 55 of file rank_support_int.hpp.
|
inlineexplicit |
Constructs and initialises the rank support structure for the given text.
[in] | text_ptr | The pointer to the text to build the rank support for. |
The text will be copied into the superblock structure to utilise better cache locality when computing the prefix rank for a given symbol and prefix length. Accordingly, the pointer to the text of the base class will always be a nullptr.
Definition at line 220 of file rank_support_int_v.hpp.
|
default |
Defaulted copy constructor.
|
default |
Defaulted move constructor.
|
default |
Defaulted destructor.
|
inline |
Loads from the archive.
Definition at line 418 of file rank_support_int_v.hpp.
|
inline |
Saves to the archive.
Definition at line 410 of file rank_support_int_v.hpp.
|
inlinevirtual |
Loads from the stream.
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 389 of file rank_support_int_v.hpp.
|
inlinevirtual |
Alias for rank(position, v)
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 327 of file rank_support_int_v.hpp.
|
default |
Defaulted move assignment.
|
default |
Defaulted copy assignment.
|
inlinevirtual |
Counts the occurrences of elements smaller or equal to v in the prefix [0..idx-1].
position | The position of the symbol to get the prefix rank for (corresponds to length of the prefix: [0..position - 1] ). |
v | The alphabet symbol to get the rank for. |
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 338 of file rank_support_int_v.hpp.
|
inlinevirtual |
Counts the occurrences of v in the prefix [0..idx-1].
position | The position of the symbol to get the prefix rank for (corresponds to length of the prefix: [0..position - 1] ). |
v | The alphabet symbol to get the rank for. |
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 313 of file rank_support_int_v.hpp.
|
inlinevirtual |
Saves to the stream.
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 379 of file rank_support_int_v.hpp.
|
inlinevirtual |
Does nothing for the rank_support_int structure.
Implements sdsl::rank_support_int< alphabet_size >.
Definition at line 425 of file rank_support_int_v.hpp.
|
inline |
Returns the size of the original text.
Definition at line 364 of file rank_support_int_v.hpp.
|
inline |
Returns the text value at the given position.
[in] | position | The text position to get the value from. |
Definition at line 372 of file rank_support_int_v.hpp.
|
friend |
Inequality operator.
Definition at line 403 of file rank_support_int_v.hpp.
|
friend |
Equality operator.
Definition at line 397 of file rank_support_int_v.hpp.