A . More...

#include <rrr_vector.hpp>

Public Types
enum	{ block_size = t_bs }

typedef bit_vector::size_type	size_type

typedef bit_vector::value_type	value_type

typedef bit_vector::difference_type	difference_type

typedef t_rac	rac_type

typedef random_access_const_iterator< rrr_vector >	iterator

typedef iterator	const_iterator

typedef bv_tag	index_category

typedef rank_support_rrr< 1, t_bs, t_rac, t_k >	rank_1_type

typedef rank_support_rrr< 0, t_bs, t_rac, t_k >	rank_0_type

typedef select_support_rrr< 1, t_bs, t_rac, t_k >	select_1_type

typedef select_support_rrr< 0, t_bs, t_rac, t_k >	select_0_type

typedef rrr_helper< t_bs >	rrr_helper_type

typedef rrr_helper_type::number_type	number_type

Public Member Functions
Default constructor	rrr_vector ()

	rrr_vector (rrr_vector const &v)

	rrr_vector (rrr_vector &&v)

rrr_vector &	operator= (rrr_vector const &v)

rrr_vector &	operator= (rrr_vector &&v)

Constructor	rrr_vector (bit_vector const &bv)

Accessing the i th element of the original bit_vector value_type	operator[] (size_type i) const

Get the integer value of the binary string of length len starting at position idx uint64_t	get_int (size_type idx, uint8_t len=64) const

Returns the size of the original bit vector size_type	size () const

Answers select queries Serializes the data structure into the given ostream size_type	serialize (std::ostream &out, structure_tree_node *v=nullptr, std::string name="") const

Loads the data structure from the given istream void	load (std::istream &in)

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)

iterator	begin () const

iterator	end () const

bool	operator== (rrr_vector const &v) const

bool	operator!= (rrr_vector const &v) const

Public Attributes
rac_type const &	bt = m_bt

bit_vector const &	btnr = m_btnr

Friends
class	rank_support_rrr< 0, t_bs, t_rac, t_k >

class	rank_support_rrr< 1, t_bs, t_rac, t_k >

class	select_support_rrr< 0, t_bs, t_rac, t_k >

class	select_support_rrr< 1, t_bs, t_rac, t_k >

Detailed Description

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>
class sdsl::rrr_vector< t_bs, t_rac, t_k >

A .

Template Parameters

t_bs	Size of a basic block.
t_rac	Random access integer vector. Use to store the block types. It is possible to use WTs for t_rac.
t_k	A rank sample value is stored before every t_k-th basic block.

References:

Rasmus Pagh Low redundancy in dictionaries with O(1) worst case lookup time Technical Report 1998. ftp://ftp.cs.au.dk/BRICS/Reports/RS/98/28/BRICS-RS-98-28.pdf, Section 2.
Rajeev Raman, V. Raman and S. Srinivasa Rao Succinct Indexable Dictionaries with Applications to representations of k-ary trees and multi-sets. SODA 2002.
Francisco Claude, Gonzalo Navarro: Practical Rank/Select Queries over Arbitrary Sequences. SPIRE 2008: 176-187
On the fly-decoding and encoding was discovered in; Gonzalo Navarro, Eliana Providel: Fast, Small, Simple Rank/Select on Bitmaps. SEA 2012

In this version the block size can be adjust by the template parameter t_bs!

See also: sdsl::rrr_vector for a specialized version for block_size=15

Definition at line 68 of file rrr_vector.hpp.

Member Typedef Documentation

◆ const_iterator

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef iterator sdsl::rrr_vector< t_bs, t_rac, t_k >::const_iterator

Definition at line 79 of file rrr_vector.hpp.

◆ difference_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef bit_vector::difference_type sdsl::rrr_vector< t_bs, t_rac, t_k >::difference_type

Definition at line 76 of file rrr_vector.hpp.

◆ index_category

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef bv_tag sdsl::rrr_vector< t_bs, t_rac, t_k >::index_category

Definition at line 80 of file rrr_vector.hpp.

◆ iterator

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef random_access_const_iterator<rrr_vector> sdsl::rrr_vector< t_bs, t_rac, t_k >::iterator

Definition at line 78 of file rrr_vector.hpp.

◆ number_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef rrr_helper_type::number_type sdsl::rrr_vector< t_bs, t_rac, t_k >::number_type

Definition at line 93 of file rrr_vector.hpp.

◆ rac_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef t_rac sdsl::rrr_vector< t_bs, t_rac, t_k >::rac_type

Definition at line 77 of file rrr_vector.hpp.

◆ rank_0_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef rank_support_rrr<0, t_bs, t_rac, t_k> sdsl::rrr_vector< t_bs, t_rac, t_k >::rank_0_type

Definition at line 83 of file rrr_vector.hpp.

◆ rank_1_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef rank_support_rrr<1, t_bs, t_rac, t_k> sdsl::rrr_vector< t_bs, t_rac, t_k >::rank_1_type

Definition at line 82 of file rrr_vector.hpp.

◆ rrr_helper_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef rrr_helper<t_bs> sdsl::rrr_vector< t_bs, t_rac, t_k >::rrr_helper_type

Definition at line 92 of file rrr_vector.hpp.

◆ select_0_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef select_support_rrr<0, t_bs, t_rac, t_k> sdsl::rrr_vector< t_bs, t_rac, t_k >::select_0_type

Definition at line 85 of file rrr_vector.hpp.

◆ select_1_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef select_support_rrr<1, t_bs, t_rac, t_k> sdsl::rrr_vector< t_bs, t_rac, t_k >::select_1_type

Definition at line 84 of file rrr_vector.hpp.

◆ size_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef bit_vector::size_type sdsl::rrr_vector< t_bs, t_rac, t_k >::size_type

Definition at line 74 of file rrr_vector.hpp.

◆ value_type

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

typedef bit_vector::value_type sdsl::rrr_vector< t_bs, t_rac, t_k >::value_type

Definition at line 75 of file rrr_vector.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

anonymous enum

Enumerator
block_size

Definition at line 95 of file rrr_vector.hpp.

Constructor & Destructor Documentation

◆ rrr_vector() [1/4]

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

Default constructor sdsl::rrr_vector< t_bs, t_rac, t_k >::rrr_vector ( )

inline

Definition at line 116 of file rrr_vector.hpp.

◆ rrr_vector() [2/4]

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

sdsl::rrr_vector< t_bs, t_rac, t_k >::rrr_vector ( rrr_vector< t_bs, t_rac, t_k > const & v )

inline

Definition at line 117 of file rrr_vector.hpp.

◆ rrr_vector() [3/4]

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

sdsl::rrr_vector< t_bs, t_rac, t_k >::rrr_vector ( rrr_vector< t_bs, t_rac, t_k > && v )

inline

Definition at line 126 of file rrr_vector.hpp.

◆ rrr_vector() [4/4]

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

Constructor sdsl::rrr_vector< t_bs, t_rac, t_k >::rrr_vector ( bit_vector const & bv )

inline

Parameters

bv	Uncompressed bitvector.
k	Store rank samples and pointers each k-th blocks.

Definition at line 158 of file rrr_vector.hpp.

Member Function Documentation

◆ begin()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

iterator sdsl::rrr_vector< t_bs, t_rac, t_k >::begin ( ) const

inline

Definition at line 413 of file rrr_vector.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

template<typename archive_t>

void sdsl::rrr_vector< t_bs, t_rac, t_k >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar )

inline

Definition at line 403 of file rrr_vector.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

template<typename archive_t>

void sdsl::rrr_vector< t_bs, t_rac, t_k >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar ) const

inline

Definition at line 392 of file rrr_vector.hpp.

◆ end()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

iterator sdsl::rrr_vector< t_bs, t_rac, t_k >::end ( ) const

inline

Definition at line 418 of file rrr_vector.hpp.

◆ get_int()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

Get the integer value of the binary string of length len starting at position idx uint64_t sdsl::rrr_vector< t_bs, t_rac, t_k >::get_int	(	size_type	idx,
		uint8_t	len = 64 ) const

inline

Parameters

idx	Starting index of the binary representation of the integer.
len	Length of the binary representation of the integer. Default value is 64.

Returns: The integer value of the binary string of length len starting at position idx.

Precondition: idx+len-1 in [0..size()-1]; len in [1..64]

Definition at line 308 of file rrr_vector.hpp.

◆ load()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

Loads the data structure from the given istream void sdsl::rrr_vector< t_bs, t_rac, t_k >::load ( std::istream & in )

inline

Definition at line 381 of file rrr_vector.hpp.

◆ operator!=()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

bool sdsl::rrr_vector< t_bs, t_rac, t_k >::operator!= ( rrr_vector< t_bs, t_rac, t_k > const & v ) const

inline

Definition at line 429 of file rrr_vector.hpp.

◆ operator=() [1/2]

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

rrr_vector & sdsl::rrr_vector< t_bs, t_rac, t_k >::operator= ( rrr_vector< t_bs, t_rac, t_k > && v )

inline

Definition at line 139 of file rrr_vector.hpp.

◆ operator=() [2/2]

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

rrr_vector & sdsl::rrr_vector< t_bs, t_rac, t_k >::operator= ( rrr_vector< t_bs, t_rac, t_k > const & v )

inline

Definition at line 130 of file rrr_vector.hpp.

◆ operator==()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

bool sdsl::rrr_vector< t_bs, t_rac, t_k >::operator== ( rrr_vector< t_bs, t_rac, t_k > const & v ) const

inline

Definition at line 423 of file rrr_vector.hpp.

◆ operator[]()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

Accessing the i th element of the original bit_vector value_type sdsl::rrr_vector< t_bs, t_rac, t_k >::operator[] ( size_type i ) const

inline

Parameters

i	An index i with $0 \leq i < size()$ .

Returns: The i-th bit of the original bit_vector

Definition at line 276 of file rrr_vector.hpp.

◆ serialize()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

Answers select queries Serializes the data structure into the given ostream size_type sdsl::rrr_vector< t_bs, t_rac, t_k >::serialize	(	std::ostream &	out,
		structure_tree_node *	v = nullptr,
		std::string	name = "" ) const

inline

Definition at line 366 of file rrr_vector.hpp.

◆ size()

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

Returns the size of the original bit vector size_type sdsl::rrr_vector< t_bs, t_rac, t_k >::size ( ) const

inline

Definition at line 359 of file rrr_vector.hpp.

Friends And Related Symbol Documentation

◆ rank_support_rrr< 0, t_bs, t_rac, t_k >

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

friend class rank_support_rrr< 0, t_bs, t_rac, t_k >

friend

Definition at line 85 of file rrr_vector.hpp.

◆ rank_support_rrr< 1, t_bs, t_rac, t_k >

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

friend class rank_support_rrr< 1, t_bs, t_rac, t_k >

friend

Definition at line 85 of file rrr_vector.hpp.

◆ select_support_rrr< 0, t_bs, t_rac, t_k >

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

friend class select_support_rrr< 0, t_bs, t_rac, t_k >

friend

Definition at line 85 of file rrr_vector.hpp.

◆ select_support_rrr< 1, t_bs, t_rac, t_k >

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

friend class select_support_rrr< 1, t_bs, t_rac, t_k >

friend

Definition at line 85 of file rrr_vector.hpp.

Member Data Documentation

◆ bt

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

rac_type const& sdsl::rrr_vector< t_bs, t_rac, t_k >::bt = m_bt

Definition at line 112 of file rrr_vector.hpp.

◆ btnr

template<uint16_t t_bs = 63, class t_rac = int_vector<>, uint16_t t_k = 32>

bit_vector const& sdsl::rrr_vector< t_bs, t_rac, t_k >::btnr = m_btnr

Definition at line 113 of file rrr_vector.hpp.

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

/builddir/build/BUILD/sdsl-lite-3.0.3-build/sdsl-lite-3.0.3/include/sdsl/rrr_vector.hpp

Public Types

Public Member Functions

Public Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ difference_type

◆ index_category

◆ iterator

◆ number_type

◆ rac_type

◆ rank_0_type

◆ rank_1_type

◆ rrr_helper_type

◆ select_0_type

◆ select_1_type

◆ size_type

◆ value_type

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ rrr_vector() [1/4]

◆ rrr_vector() [2/4]

◆ rrr_vector() [3/4]

◆ rrr_vector() [4/4]

Member Function Documentation

◆ begin()

◆ CEREAL_LOAD_FUNCTION_NAME()

◆ CEREAL_SAVE_FUNCTION_NAME()

◆ end()

◆ get_int()

◆ load()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]()

◆ serialize()

◆ size()

Friends And Related Symbol Documentation

◆ rank_support_rrr< 0, t_bs, t_rac, t_k >

◆ rank_support_rrr< 1, t_bs, t_rac, t_k >

◆ select_support_rrr< 0, t_bs, t_rac, t_k >

◆ select_support_rrr< 1, t_bs, t_rac, t_k >

Member Data Documentation

◆ bt

◆ btnr