|
| rank_support_int_scan (const int_vector<> *v=nullptr) |
|
| rank_support_int_scan (const rank_support_int_scan &rs)=default |
|
| rank_support_int_scan (rank_support_int_scan &&rs)=default |
|
rank_support_int_scan & | operator= (const rank_support_int_scan &rs)=default |
|
rank_support_int_scan & | operator= (rank_support_int_scan &&rs)=default |
|
size_type | rank (size_type idx, const value_type v) const |
| Counts the occurrences of v in the prefix [0..idx-1]. More...
|
|
size_type | operator() (size_type idx, const value_type v) const |
| Alias for rank(idx, v) More...
|
|
size_type | prefix_rank (size_type idx, const value_type v) const |
| Counts the occurrences of elements smaller or equal to v in the prefix [0..idx-1]. More...
|
|
size_type | size () const |
|
size_type | serialize (std::ostream &out, structure_tree_node *v=nullptr, const std::string name="") const |
| Serializes rank_support_int. More...
|
|
void | load (std::istream &, const int_vector<> *v=nullptr) |
| Loads the rank_support_int. More...
|
|
void | set_vector (const int_vector<> *v=nullptr) |
| Sets the supported int_vector to the given pointer. More...
|
|
| rank_support_int (const int_vector<> *v=nullptr) |
| Constructor. More...
|
|
| rank_support_int (const rank_support_int &)=default |
| Copy constructor. More...
|
|
| 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. More...
|
|
virtual size_type | rank (const size_type i, const value_type v) const =0 |
| Answers rank queries for the supported int_vector. More...
|
|
virtual size_type | operator() (const size_type idx, const value_type v) const =0 |
| Alias for rank(idx, v) More...
|
|
virtual size_type | prefix_rank (const size_type i, const value_type v) const =0 |
| Answers rank queries for the supported int_vector. More...
|
|
virtual size_type | serialize (std::ostream &out, structure_tree_node *v, const std::string name) const =0 |
| Serializes rank_support_int. More...
|
|
virtual void | load (std::istream &in, const int_vector<> *v=nullptr)=0 |
| Loads the rank_support_int. More...
|
|
virtual void | set_vector (const int_vector<> *v=nullptr)=0 |
| Sets the supported int_vector to the given pointer. More...
|
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
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. More...
|
|
static constexpr uint64_t | extract_word (const uint64_t *data, const size_type word_position) noexcept |
| Returns the word a the given word position. More...
|
|
const int_vector * | m_v |
| Pointer to the rank supported bit_vector. More...
|
|
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>
class sdsl::rank_support_int_scan< alphabet_size >
A class supporting rank queries in linear time.
- Template Parameters
-
- Space complexity
- Constant.
- Time complexity
- Linear in the size of the supported vector.
Definition at line 28 of file rank_support_int_scan.hpp.