|
| rank_support_int_v (const int_vector<> *text_ptr=nullptr) |
| Constructs and initialises the rank support structure for the given text.
|
|
| rank_support_int_v (const rank_support_int_v &)=default |
| Defaulted copy constructor.
|
|
| rank_support_int_v (rank_support_int_v &&)=default |
| Defaulted move constructor.
|
|
rank_support_int_v & | operator= (const rank_support_int_v &)=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, const int_vector<> *) |
| 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 (const int_vector<> *) |
| Does nothing for the rank_support_int structure.
|
|
| rank_support_int (const int_vector<> *v=nullptr) |
| Constructor.
|
|
| rank_support_int (const rank_support_int &)=default |
| Copy constructor.
|
|
| rank_support_int (rank_support_int &&)=default |
|
rank_support_int & | operator= (const rank_support_int &)=default |
|
rank_support_int & | operator= (rank_support_int &&)=default |
|
virtual | ~rank_support_int () |
| Destructor.
|
|
virtual size_type | rank (const size_type i, const value_type v) const =0 |
| Answers rank queries for the supported int_vector.
|
|
virtual size_type | operator() (const size_type idx, const value_type v) const =0 |
| Alias for rank(idx, v)
|
|
virtual size_type | prefix_rank (const size_type i, const value_type v) const =0 |
| Answers rank queries for the supported int_vector.
|
|
virtual size_type | serialize (std::ostream &out, structure_tree_node *v, const std::string name) const =0 |
| Serializes rank_support_int.
|
|
virtual void | load (std::istream &in, const int_vector<> *v=nullptr)=0 |
| Loads the rank_support_int.
|
|
virtual void | set_vector (const int_vector<> *v=nullptr)=0 |
| Sets the supported int_vector to the given pointer.
|
|
|
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 (const uint64_t *data, const size_type word_position) noexcept |
| Returns the word a the given word position.
|
|
const int_vector * | 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() |
|
template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
class sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >
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.
- Template Parameters
-
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. |
- Reference
- Christopher Pockrandt: EPR-Dictionaries: A practical and fast data structure for constant time searches in unidirectional and bidirectional FM-indices. WEA 2008: 154-168
Definition at line 156 of file rank_support_int_v.hpp.
template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
Constructs and initialises the rank support structure for the given text.
- Parameters
-
[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 200 of file rank_support_int_v.hpp.