sdsl::rank_support_v< b, pattern_len > Class Template Reference

A class supporting rank queries in constant time. The implementation is a version of the data structure proposed by Vigna (WEA 2008). More...

#include <rank_support_v.hpp>

Inherits sdsl::rank_support.

List of all members.

Public Types
typedef bit_vector	bit_vector_type
Public Member Functions
	rank_support_v (const bit_vector *v=NULL)
	rank_support_v (const rank_support_v &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 int_vector< 1 > *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_v &	operator= (const rank_support_v &rs)
	Assign Operator.
void	swap (rank_support_v &rs)
	swap Operator
bool	operator== (const rank_support_v &rs) const
	Equality Operator.
bool	operator!= (const rank_support_v &rs) const
	Inequality Operator.

---

Detailed Description

template<uint8_t b = 1, uint8_t pattern_len = 1>
class sdsl::rank_support_v< b, pattern_len >

A class supporting rank queries in constant time. The implementation is a version of the data structure proposed by Vigna (WEA 2008).

Space complexity

for a bit vector of length n bits.

The superblock size is 512. Each superblock is subdivided into 512/64 = 8 blocks. So absolute counts for the superblock add 64/512 bits on top of each supported bit. Since the first of the 8 relative count values is 0, we can fit the remaining 7 (each of width log(512)=9) in a 64bit word. The relative counts add another 64/512 bits on top of each supported bit. In total this results in 128/512=25% overhead.

---

Member Function Documentation

template<uint8_t b, uint8_t pattern_len>

void sdsl::rank_support_v< b, pattern_len >::init

(

const bit_vector *

v = NULL

)

[inline, virtual]

Initializes the data structure.

Parameters:

v	The supported bit_vector. If v equals NULL the previous set bit_vector is supported. Otherwise v will be supported.

Note:

Call this function before the first call of rank.

See also:

rank

Implements sdsl::rank_support.

template<uint8_t b, uint8_t pattern_len>

void sdsl::rank_support_v< b, pattern_len >::load	(	std::istream &	in,
		const int_vector< 1 > *	v = NULL
	)		[inline, virtual]

Loads the rank_support.

Parameters:

in	In-Stream to load the rank_support data from.
v	The supported bit_vector.

Implements sdsl::rank_support.

template<uint8_t b, uint8_t pattern_len>

bool sdsl::rank_support_v< b, pattern_len >::operator!=

(

const rank_support_v< b, pattern_len > &

rs

)

const [inline]

Inequality Operator.

Two rank_support_vs are not equal if any member variable are not equal.

Required for the Equality Comparable Concept of the STL.

See also:

operator==

template<uint8_t b, uint8_t pattern_len>

rank_support_v< b, pattern_len > & sdsl::rank_support_v< b, pattern_len >::operator=

(

const rank_support_v< b, pattern_len > &

rs

)

[inline]

Assign Operator.

Required for the Assignable Concept of the STL.

template<uint8_t b, uint8_t pattern_len>

bool sdsl::rank_support_v< b, pattern_len >::operator==

(

const rank_support_v< b, pattern_len > &

rs

)

const [inline]

Equality Operator.

Two rank_support_vs are equal if all member variables are equal.

Required for the Equality Comparable Concept of the STL.

See also:

operator!=

template<uint8_t b, uint8_t pattern_len>

const rank_support_v< b, pattern_len >::size_type sdsl::rank_support_v< b, pattern_len >::rank

(

size_type

i

)

const [inline, virtual]

Answers rank queries for the supported bit_vector if init() was called before.

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.

template<uint8_t b, uint8_t pattern_len>

rank_support_v< b, pattern_len >::size_type sdsl::rank_support_v< b, pattern_len >::serialize	(	std::ostream &	out,
		structure_tree_node *	v = NULL,
		std::string	name = ""
	)		const [inline, virtual]

Serializes rank_support.

Parameters:

out	Out-Stream to serialize the data to.

Implements sdsl::rank_support.

template<uint8_t b, uint8_t pattern_len>

void sdsl::rank_support_v< b, pattern_len >::set_vector

(

const bit_vector *

v = NULL

)

[inline, virtual]

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.

template<uint8_t b, uint8_t pattern_len>

void sdsl::rank_support_v< b, pattern_len >::swap

(

rank_support_v< b, pattern_len > &

rs

)

[inline]

swap Operator

Swap two rank_support_v in constant time. All members (excluded the pointer to the supported bit_vector) are swapped. Required for the Container Concept of the STL.

---

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

• sdsl/include/sdsl/rank_support_v.hpp