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 >:

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_v5 &	operator= (const rank_support_v5 &)=default

rank_support_v5 &	operator= (rank_support_v5 &&)=default

size_type	rank (size_type idx) const
	Answers rank queries for the supported bit_vector.

size_type	operator() (size_type idx) const
	Alias for rank(i)

size_type	size () const

size_type	serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const
	Serializes rank_support.

void	load (std::istream &in, const bit_vector *v=nullptr)
	Loads the rank_support.

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.

Public Member Functions inherited from sdsl::rank_support
	rank_support (const bit_vector *v=nullptr)
	Constructor.

	rank_support (const rank_support &)=default
	Copy constructor.

	rank_support (rank_support &&)=default

rank_support &	operator= (const rank_support &)=default

rank_support &	operator= (rank_support &&)=default

virtual	~rank_support ()
	Destructor.

virtual size_type	rank (size_type i) const =0
	Answers rank queries for the supported bit_vector.

virtual size_type	operator() (size_type idx) const =0
	Alias for rank(i)

virtual size_type	serialize (std::ostream &out, structure_tree_node *v, std::string name) const =0
	Serializes rank_support.

virtual void	load (std::istream &in, const bit_vector *v=nullptr)=0
	Loads the rank_support.

virtual void	set_vector (const bit_vector *v=nullptr)=0
	Sets the supported bit_vector to the given pointer.

Additional Inherited Members
Protected Attributes inherited from sdsl::rank_support
const bit_vector *	m_v
	Pointer to the rank supported bit_vector.

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: 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_b	Bit pattern `0`,`1`,`10`,`01` which should be ranked.
t_pat_len	Length 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

in	In-Stream to load the rank_support data from.
v	The 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

i	Argument 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

out	Out-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

v	The 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:

/builddir/build/BUILD/sdsl-lite-3.0.1/include/sdsl/rank_support_v5.hpp

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ bit_vector_type

◆ trait_type

Member Enumeration Documentation

◆ anonymous enum

◆ anonymous enum

Constructor & Destructor Documentation

◆ rank_support_v5() [1/3]

◆ rank_support_v5() [2/3]

◆ rank_support_v5() [3/3]

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

◆ CEREAL_SAVE_FUNCTION_NAME()

◆ load()

◆ operator!=()

◆ operator()()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ rank()

◆ serialize()

◆ set_vector()

◆ size()