sdsl::rrr_vector< block_size, wt_type > Class Template Reference

A bit vector which compresses the input with the method from Raman, Raman, and Rao. More...

#include <rrr_vector.hpp>

List of all members.

Public Types
enum	{ rrr_block_size = block_size }
typedef bit_vector::size_type	size_type
typedef bit_vector::value_type	value_type
typedef rrr_rank_support < 1, block_size, wt_type >	rank_1_type
typedef rrr_rank_support < 0, block_size, wt_type >	rank_0_type
typedef rrr_select_support < 1, block_size, wt_type >	select_1_type
typedef rrr_select_support < 0, block_size, wt_type >	select_0_type
typedef rrr_helper< block_size >	rrr_helper_type
typedef rrr_helper_type::number_type	number_type
Public Member Functions
	rrr_vector (uint16_t sample_rate=32)
	Default constructor.
	rrr_vector (const rrr_vector &rrr)
	Copy constructor.
	rrr_vector (const bit_vector &bv, uint16_t sample_rate=32)
	Constructor.
void	swap (rrr_vector &rrr)
	Swap method.
value_type	operator[] (size_type i) const
	Accessing the i-th element of the original bit_vector.
rrr_vector &	operator= (const rrr_vector &rrr)
	Assignment operator.
size_type	size () const
	Returns the size of the original bit vector.
size_type	serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const
void	load (std::istream &in)
	Loads the data structure from the given istream.
void	print_info () const
Public Attributes
const wt_type &	bt
const bit_vector &	btnr
Friends
class	rrr_rank_support< 0, block_size, wt_type >
class	rrr_rank_support< 1, block_size, wt_type >
class	rrr_select_support< 0, block_size, wt_type >
class	rrr_select_support< 1, block_size, wt_type >

---

Detailed Description

template<uint16_t block_size = 15, class wt_type = int_vector<>>
class sdsl::rrr_vector< block_size, wt_type >

A bit vector which compresses the input with the method from Raman, Raman, and Rao.

Recently, I discovered that Rasmus Pagh was the first who presented the design of this bitvector representation. For detail see the Technical Report ,,Low redundancy in dictionaries with O(1) worst case lookup time'' ftp://ftp.cs.au.dk/BRICS/Reports/RS/98/28/BRICS-RS-98-28.pdf, Section 2.

This compact representation was presented by Rajeev Raman, V. Raman and S. Srinivasa Rao at SODA 2002 in the article: Succinct Indexable Dictionaries with Applications to representations of k-ary trees and multi-sets.

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

See also:

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

---

Constructor & Destructor Documentation

template<uint16_t block_size = 15, class wt_type = int_vector<>>

sdsl::rrr_vector< block_size, wt_type >::rrr_vector	(	const bit_vector &	bv,
		uint16_t	sample_rate = 32
	)		[inline]

Constructor.

Parameters:

block_size

Number of bits in one block.

---

Member Function Documentation

template<uint16_t block_size = 15, class wt_type = int_vector<>>

value_type sdsl::rrr_vector< block_size, wt_type >::operator[]

(

size_type

i

)

const [inline]

Accessing the i-th element of the original bit_vector.

Parameters:

i	An index i with .

Returns:

The i-th bit of the original bit_vector

template<uint16_t block_size = 15, class wt_type = int_vector<>>

size_type sdsl::rrr_vector< block_size, wt_type >::serialize	(	std::ostream &	out,
		structure_tree_node *	v = NULL,
		std::string	name = ""
	)		const [inline]

Answers select queries Serializes the data structure into the given ostream

---

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

• sdsl/include/sdsl/rrr_vector.hpp