A wavelet tree class for sequences of big alphabet size (like integer alphabet) More...

#include <wt_int.hpp>

Public Types
typedef RandomAccessContainer::size_type	size_type
typedef RandomAccessContainer::value_type	value_type
typedef BitVector	bit_vector_type
typedef RankSupport	rank_1_type
typedef SelectSupport	select_1_type
typedef SelectSupportZero	select_0_type
Public Member Functions
	wt_int ()
	Default constructor.
	wt_int (const RandomAccessContainer &rac, uint32_t logn=0)
	Constructor.
template<uint8_t int_width>
	wt_int (int_vector_file_buffer< int_width > &buf, uint32_t logn=0, std::string dir="./")
	Semi-external constructor.
template<uint8_t int_width>
void	construct (int_vector_file_buffer< int_width > &buf, uint32_t logn=0, std::string dir="./")
	wt_int (const wt_int &wt)
	Copy constructor.
wt_int &	operator= (const wt_int &wt)
	Assignment operator.
void	swap (wt_int &wt)
	Swap operator.
size_type	size () const
	Returns the size of the original vector.
bool	empty () const
	Returns whether the wavelet tree contains no data.
value_type	operator[] (size_type i) const
	Recovers the ith symbol of the original vector.
size_type	rank (size_type i, value_type c) const
	Calculates how many symbols c are in the prefix [0..i-1] of the supported vector.
size_type	select (size_type i, value_type c) const
	Calculates the ith occurence of the symbol c in the supported vector.
size_type	range_search_2d (size_type lb, size_type rb, value_type vlb, value_type vrb, std::vector< size_type > idx_result=NULL, std::vector< value_type > val_result=NULL) const
	range_search_2d searches points in the index interval [lb..rb] and value interval [vlb..vrb].
void	_range_search_2d (size_type lb, size_type rb, value_type vlb, value_type vrb, size_type depth, size_type ilb, size_type node_size, size_type offsets[], size_type ones_before_os[], size_type path, std::vector< size_type > idx_result, std::vector< size_type > val_result, size_type &cnt_answers) const
size_type	serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const
	Serializes the data structure into the given ostream.
void	load (std::istream &in)
	Loads the data structure from the given istream.
Public Attributes
const size_type &	sigma
	Effective alphabet size of the wavelet tree.
const bit_vector_type &	tree
	A concatenation of all bit vectors of the wavelet tree.
Protected Member Functions
void	copy (const wt_int &wt)
Protected Attributes
size_type	m_size
size_type	m_sigma
bit_vector_type	m_tree
rank_1_type	m_tree_rank
select_1_type	m_tree_select1
select_0_type	m_tree_select0
uint32_t	m_logn

Detailed Description

template<class RandomAccessContainer = int_vector<>, class BitVector = bit_vector, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class SelectSupportZero = typename BitVector::select_0_type>
class sdsl::wt_int< RandomAccessContainer, BitVector, RankSupport, SelectSupport, SelectSupportZero >

A wavelet tree class for sequences of big alphabet size (like integer alphabet)

A wavelet tree is build for a vector of characters over the alphabet $\Sigma$ . The wavelet tree $wt$ consists of a tree of bit vector and provides three efficient methods:

The "[]"-operator: returns the ith symbol of vector for which the wavelet tree was build for.
The rank method: returns the number of occurences of symbol in the prefix [0..i-1] in the vector for which the wavelet tree was build for.

The select method: $wt.select(j,c)$ returns the index $i\in [0..size()-1]$ of the jth occurence of symbol $c$ .

Space complexity: $\Order{n\log|\Sigma|}$ bits, where is the size of the vector the wavelet tree was build for.

Template Parameters:

RandomAccessContainer	Type of the input sequence.
BitVector	Type of the bitvector used for representing the wavelet tree.
RankSupport	Type of the support structure for rank on ones.
SelectSupport	Type of the support structure for select on ones.
SelectSupport	Type of the support structure for select on ones.

Constructor & Destructor Documentation

template<class RandomAccessContainer = int_vector<>, class BitVector = bit_vector, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class SelectSupportZero = typename BitVector::select_0_type>

sdsl::wt_int< RandomAccessContainer, BitVector, RankSupport, SelectSupport, SelectSupportZero >::wt_int	(	const RandomAccessContainer &	rac,
		uint32_t	logn = `0`
	)		`[inline]`

Constructor.

   \param rac Reference a random access container of integer values for which the wavelet tree should be build.
   \param logn Let x > 0 be the biggest value in rac. logn should be bit_magic::l1BP(x-1)+1 to represent all values of rac.
   \par Time complexity

$\Order{n\log|\Sigma|}$ , where $n=size$ I.e. we nee {n n} if rac is a permutation of 0..n-1.

Space complexity: $3n\log|\Sigma|$ bits, where . I.e. we need $3n\log n$ if rac is a permutation of 0..n-1.

template<class RandomAccessContainer = int_vector<>, class BitVector = bit_vector, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class SelectSupportZero = typename BitVector::select_0_type>

template<uint8_t int_width>

sdsl::wt_int< RandomAccessContainer, BitVector, RankSupport, SelectSupport, SelectSupportZero >::wt_int	(	int_vector_file_buffer< int_width > &	buf,
		uint32_t	logn = `0`,
		std::string	dir = `"./"`
	)		`[inline]`

Semi-external constructor.

   \param buf      int_vector_file_buffer which contains the vector v for which a wt_int should be build.
   \param logn Let x > 0 be the biggest value in v. logn should be bit_magic::l1BP(x-1)+1 to represent all values of v.
   \param dir      Directory in which temporary files should be stored during the construction.
   \par Time complexity

$\Order{n\log|\Sigma|}$ , where $n=size$ I.e. we nee {n n} if rac is a permutation of 0..n-1.

Space complexity: $n\log|\Sigma| + O(1)$ bits, where .

Member Function Documentation

template<class RandomAccessContainer = int_vector<>, class BitVector = bit_vector, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class SelectSupportZero = typename BitVector::select_0_type>

value_type sdsl::wt_int< RandomAccessContainer, BitVector, RankSupport, SelectSupport, SelectSupportZero >::operator[] ( size_type i ) const [inline]

Recovers the ith symbol of the original vector.

Parameters:

i	The index of the symbol in the original vector. $i \in [0..size()-1]$

Returns:: The ith symbol of the original vector.

template<class RandomAccessContainer = int_vector<>, class BitVector = bit_vector, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class SelectSupportZero = typename BitVector::select_0_type>

size_type sdsl::wt_int< RandomAccessContainer, BitVector, RankSupport, SelectSupport, SelectSupportZero >::range_search_2d	(	size_type	lb,
		size_type	rb,
		value_type	vlb,
		value_type	vrb,
		std::vector< size_type > *	idx_result = `NULL`,
		std::vector< value_type > *	val_result = `NULL`
	)		const `[inline]`

range_search_2d searches points in the index interval [lb..rb] and value interval [vlb..vrb].

Parameters:

lb	Left bound of index interval (inclusive)
rb	Right bound of index interval (inclusive)
vlb	Left bound of value interval (inclusive)
vrb	Right bound of value interval (inclusive)
idx_result	Reference to a vector to which the resulting indices should be added
val_result	Reference to a vector to which the resulting values should be added

template<class RandomAccessContainer = int_vector<>, class BitVector = bit_vector, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class SelectSupportZero = typename BitVector::select_0_type>

size_type sdsl::wt_int< RandomAccessContainer, BitVector, RankSupport, SelectSupport, SelectSupportZero >::rank	(	size_type	i,
		value_type	c
	)		const `[inline]`

Calculates how many symbols c are in the prefix [0..i-1] of the supported vector.

Parameters:

i	The exclusive index of the prefix range [0..i-1], so $i\in[0..size()]$ .
c	The symbol to count the occurences in the prefix.

Returns:: The number of occurences of symbol c in the prefix [0..i-1] of the supported vector.

Time complexity: $\Order{\log |\Sigma|}$

template<class RandomAccessContainer = int_vector<>, class BitVector = bit_vector, class RankSupport = typename BitVector::rank_1_type, class SelectSupport = typename BitVector::select_1_type, class SelectSupportZero = typename BitVector::select_0_type>

size_type sdsl::wt_int< RandomAccessContainer, BitVector, RankSupport, SelectSupport, SelectSupportZero >::select	(	size_type	i,
		value_type	c
	)		const `[inline]`

Calculates the ith occurence of the symbol c in the supported vector.

Parameters:

i	The ith occurence. $i\in [1..rank(size(),c)]$ .
c	The symbol c.

Time complexity: $\Order{\log |\Sigma|}$

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

sdsl/include/sdsl/wt_int.hpp

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation