SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
|
A class supporting rank queries in constant time. The implementation is a space saving version of the data structure proposed by Vigna (WEA 2008). More...
#include <rank_support_v5.hpp>
Inherits sdsl::rank_support.
Public Types | |
typedef bit_vector | bit_vector_type |
Public Member Functions | |
rank_support_v5 (const bit_vector *v=NULL) | |
rank_support_v5 (const rank_support_v5 &rs) | |
void | init (const bit_vector *v=NULL) |
Initializes the data structure. | |
const size_type | rank (size_type idx) const |
Answers rank queries for the supported bit_vector if init() was called before. | |
const size_type | operator() (size_type idx) const |
Alias for rank(i) | |
const size_type | size () const |
size_type | serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const |
Serializes rank_support. | |
void | load (std::istream &in, const bit_vector *v=NULL) |
Loads the rank_support. | |
void | set_vector (const bit_vector *v=NULL) |
Sets the supported bit_vector to the given pointer. | |
rank_support_v5 & | operator= (const rank_support_v5 &rs) |
Assign Operator. | |
void | swap (rank_support_v5 &rs) |
swap Operator | |
bool | operator== (const rank_support_v5 &rs) const |
Equality Operator. | |
bool | operator!= (const rank_support_v5 &rs) const |
Unequality Operator. |
A class supporting rank queries in constant time. The implementation is a space saving version of the data structure proposed by Vigna (WEA 2008).
The superblock size is 2048. Each superblock is subdivided into 2048/(6*64) = 5 blocks (with some bit remaining). So absolute counts for the superblock add 64/2048 bits on top of each supported bit. Since the first of the 6 relative count values is 0, we can fit the remaining 5 in (each of width log(2048)=11) in a 64 bit word. The relative counts add another 64/2048 bits bits on top of each supported bit. In total this results is 128/2048= 6.25% overhead.
void sdsl::rank_support_v5< b, pattern_len >::init | ( | const bit_vector * | v = NULL | ) | [inline, virtual] |
Initializes the data structure.
v | The supported bit_vector. If v equals NULL the previous set bit_vector is supported. Otherwise v will be supported. |
Implements sdsl::rank_support.
void sdsl::rank_support_v5< b, pattern_len >::load | ( | std::istream & | in, |
const bit_vector * | v = NULL |
||
) | [inline, virtual] |
Loads the rank_support.
in | In-Stream to load the rank_support data from. |
v | The supported bit_vector. |
Implements sdsl::rank_support.
bool sdsl::rank_support_v5< b, pattern_len >::operator!= | ( | const rank_support_v5< b, pattern_len > & | rs | ) | const [inline] |
Unequality Operator.
Two rank_support_v5s are not equal if any member variable are not equal.
Required for the Equality Comparable Concept of the STL.
rank_support_v5< b, pattern_len > & sdsl::rank_support_v5< b, pattern_len >::operator= | ( | const rank_support_v5< b, pattern_len > & | rs | ) | [inline] |
Assign Operator.
Required for the Assignable Concept of the STL.
bool sdsl::rank_support_v5< b, pattern_len >::operator== | ( | const rank_support_v5< b, pattern_len > & | rs | ) | const [inline] |
Equality Operator.
Two rank_support_v5s are equal if all member variables are equal.
Required for the Equality Comparable Concept of the STL.
const rank_support_v5< b, pattern_len >::size_type sdsl::rank_support_v5< b, pattern_len >::rank | ( | size_type | i | ) | const [inline, virtual] |
Answers rank queries for the supported bit_vector if init() was called before.
i | Argument for the length of the prefix v[0..i-1]. |
Implements sdsl::rank_support.
rank_support_v5< b, pattern_len >::size_type sdsl::rank_support_v5< b, pattern_len >::serialize | ( | std::ostream & | out, |
structure_tree_node * | v = NULL , |
||
std::string | name = "" |
||
) | const [inline, virtual] |
Serializes rank_support.
out | Out-Stream to serialize the data to. |
Implements sdsl::rank_support.
void sdsl::rank_support_v5< b, pattern_len >::set_vector | ( | const bit_vector * | v = NULL | ) | [inline, virtual] |
Sets the supported bit_vector to the given pointer.
v | The new bit_vector to support. |
Implements sdsl::rank_support.
void sdsl::rank_support_v5< b, pattern_len >::swap | ( | rank_support_v5< b, pattern_len > & | rs | ) | [inline] |
swap Operator
Swap two rank_support_v5 in constant time. Required for the Container Concept of the STL.