SDSL 3.0.1
Succinct Data Structure Library
sdsl::rank_support_v5< t_b, t_pat_len > Class Template Reference

A class supporting rank queries in constant time. More...

#include <rank_support_v5.hpp>

Inheritance diagram for sdsl::rank_support_v5< t_b, t_pat_len >:
sdsl::rank_support

Public Types

enum  { bit_pat = t_b }
 
enum  { bit_pat_len = t_pat_len }
 
typedef bit_vector bit_vector_type
 
typedef rank_support_trait< t_b, t_pat_len > trait_type
 
- Public Types inherited from sdsl::rank_support
typedef bit_vector::size_type size_type
 

Public Member Functions

 rank_support_v5 (const bit_vector *v=nullptr)
 
 rank_support_v5 (const rank_support_v5 &)=default
 
 rank_support_v5 (rank_support_v5 &&)=default
 
rank_support_v5operator= (const rank_support_v5 &)=default
 
rank_support_v5operator= (rank_support_v5 &&)=default
 
size_type rank (size_type idx) const
 Answers rank queries for the supported bit_vector. More...
 
size_type operator() (size_type idx) const
 Alias for rank(i) More...
 
size_type size () const
 
size_type serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
 Serializes rank_support. More...
 
void load (std::istream &in, const bit_vector *v=nullptr)
 Loads the rank_support. More...
 
template<typename archive_t >
void CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
 
template<typename archive_t >
void CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
 
bool operator== (const rank_support_v5 &other) const noexcept
 
bool operator!= (const rank_support_v5 &other) const noexcept
 
void set_vector (const bit_vector *v=nullptr)
 Sets the supported bit_vector to the given pointer. More...
 
- Public Member Functions inherited from sdsl::rank_support
 rank_support (const bit_vector *v=nullptr)
 Constructor. More...
 
 rank_support (const rank_support &)=default
 Copy constructor. More...
 
 rank_support (rank_support &&)=default
 
rank_supportoperator= (const rank_support &)=default
 
rank_supportoperator= (rank_support &&)=default
 
virtual ~rank_support ()
 Destructor. More...
 
virtual size_type rank (size_type i) const =0
 Answers rank queries for the supported bit_vector. More...
 
virtual size_type operator() (size_type idx) const =0
 Alias for rank(i) More...
 
virtual size_type serialize (std::ostream &out, structure_tree_node *v, std::string name) const =0
 Serializes rank_support. More...
 
virtual void load (std::istream &in, const bit_vector *v=nullptr)=0
 Loads the rank_support. More...
 
virtual void set_vector (const bit_vector *v=nullptr)=0
 Sets the supported bit_vector to the given pointer. More...
 

Additional Inherited Members

- Protected Attributes inherited from sdsl::rank_support
const bit_vectorm_v
 Pointer to the rank supported bit_vector. More...
 

Detailed Description

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
class sdsl::rank_support_v5< t_b, t_pat_len >

A class supporting rank queries in constant time.

Space complexity
$ 0.0625n$ bits for a bit vector of length n bits.

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 (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 in 128/2048= 6.25% overhead.

Template Parameters
t_bBit pattern 0,1,10,01 which should be ranked.
t_pat_lenLength of the bit pattern.

Definition at line 38 of file rank_support_v5.hpp.

Member Typedef Documentation

◆ bit_vector_type

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
typedef bit_vector sdsl::rank_support_v5< t_b, t_pat_len >::bit_vector_type

Definition at line 46 of file rank_support_v5.hpp.

◆ trait_type

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
typedef rank_support_trait<t_b, t_pat_len> sdsl::rank_support_v5< t_b, t_pat_len >::trait_type

Definition at line 47 of file rank_support_v5.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
anonymous enum
Enumerator
bit_pat 

Definition at line 48 of file rank_support_v5.hpp.

◆ anonymous enum

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
anonymous enum
Enumerator
bit_pat_len 

Definition at line 52 of file rank_support_v5.hpp.

Constructor & Destructor Documentation

◆ rank_support_v5() [1/3]

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
sdsl::rank_support_v5< t_b, t_pat_len >::rank_support_v5 ( const bit_vector v = nullptr)
inlineexplicit

Definition at line 62 of file rank_support_v5.hpp.

◆ rank_support_v5() [2/3]

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
sdsl::rank_support_v5< t_b, t_pat_len >::rank_support_v5 ( const rank_support_v5< t_b, t_pat_len > &  )
default

◆ rank_support_v5() [3/3]

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
sdsl::rank_support_v5< t_b, t_pat_len >::rank_support_v5 ( rank_support_v5< t_b, t_pat_len > &&  )
default

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
template<typename archive_t >
void sdsl::rank_support_v5< t_b, t_pat_len >::CEREAL_LOAD_FUNCTION_NAME ( archive_t &  ar)
inline

Definition at line 163 of file rank_support_v5.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
template<typename archive_t >
void sdsl::rank_support_v5< t_b, t_pat_len >::CEREAL_SAVE_FUNCTION_NAME ( archive_t &  ar) const
inline

Definition at line 157 of file rank_support_v5.hpp.

◆ load()

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
void sdsl::rank_support_v5< t_b, t_pat_len >::load ( std::istream &  in,
const bit_vector v = nullptr 
)
inlinevirtual

Loads the rank_support.

Parameters
inIn-Stream to load the rank_support data from.
vThe supported bit_vector.

Implements sdsl::rank_support.

Definition at line 150 of file rank_support_v5.hpp.

◆ operator!=()

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
bool sdsl::rank_support_v5< t_b, t_pat_len >::operator!= ( const rank_support_v5< t_b, t_pat_len > &  other) const
inlinenoexcept

Definition at line 170 of file rank_support_v5.hpp.

◆ operator()()

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
size_type sdsl::rank_support_v5< t_b, t_pat_len >::operator() ( size_type  idx) const
inlinevirtual

Alias for rank(i)

Implements sdsl::rank_support.

Definition at line 138 of file rank_support_v5.hpp.

◆ operator=() [1/2]

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
rank_support_v5 & sdsl::rank_support_v5< t_b, t_pat_len >::operator= ( const rank_support_v5< t_b, t_pat_len > &  )
default

◆ operator=() [2/2]

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
rank_support_v5 & sdsl::rank_support_v5< t_b, t_pat_len >::operator= ( rank_support_v5< t_b, t_pat_len > &&  )
default

◆ operator==()

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
bool sdsl::rank_support_v5< t_b, t_pat_len >::operator== ( const rank_support_v5< t_b, t_pat_len > &  other) const
inlinenoexcept

Definition at line 168 of file rank_support_v5.hpp.

◆ rank()

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
size_type sdsl::rank_support_v5< t_b, t_pat_len >::rank ( size_type  i) const
inlinevirtual

Answers rank queries for the supported bit_vector.

Parameters
iArgument for the length of the prefix v[0..i-1].
Returns
Number of 1-bits in the prefix [0..i-1] of the supported bit_vector.
Note
Method init has to be called before the first call of rank.
See also
init

Implements sdsl::rank_support.

Definition at line 118 of file rank_support_v5.hpp.

◆ serialize()

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
size_type sdsl::rank_support_v5< t_b, t_pat_len >::serialize ( std::ostream &  out,
structure_tree_node v = nullptr,
std::string  name = "" 
) const
inlinevirtual

Serializes rank_support.

Parameters
outOut-Stream to serialize the data to.

Implements sdsl::rank_support.

Definition at line 141 of file rank_support_v5.hpp.

◆ set_vector()

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
void sdsl::rank_support_v5< t_b, t_pat_len >::set_vector ( const bit_vector v = nullptr)
inlinevirtual

Sets the supported bit_vector to the given pointer.

Parameters
vThe new bit_vector to support.
Note
Method init has to be called before the next call of rank.
See also
init, rank

Implements sdsl::rank_support.

Definition at line 172 of file rank_support_v5.hpp.

◆ size()

template<uint8_t t_b = 1, uint8_t t_pat_len = 1>
size_type sdsl::rank_support_v5< t_b, t_pat_len >::size ( ) const
inline

Definition at line 139 of file rank_support_v5.hpp.


The documentation for this class was generated from the following file: