A wavelet tree class for integer sequences. More...

#include <wt_ap.hpp>

Public Types
enum	{ lex_ordered = 0 }

typedef int_vector ::size_type	size_type

typedef int_vector ::value_type	value_type

typedef int_vector ::difference_type	difference_type

typedef random_access_const_iterator< wt_ap >	const_iterator

typedef const_iterator	iterator

typedef t_wt_byte	wt_byte_type

typedef t_wt_int	wt_int_type

typedef wt_tag	index_category

typedef int_alphabet_tag	alphabet_category

Public Member Functions
	wt_ap ()
	Default constructor.

template<typename t_it>
	wt_ap (t_it begin, t_it end, std::string tmp_dir=ram_file_name(""))
	Construct the wavelet tree from a sequence defined by two interators.

	wt_ap (wt_ap const &wt)
	Copy constructor.

	wt_ap (wt_ap &&wt)
	Move copy constructor.

wt_ap &	operator= (wt_ap const &wt)
	Assignment operator.

wt_ap &	operator= (wt_ap &&wt)
	Assignment move 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 i-th 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.

std::pair< size_type, value_type >	inverse_select (size_type i) const
	Calculates how many occurrences of symbol wt[i] are in the prefix [0..i-1] of the original sequence.

size_type	select (size_type i, value_type c) const
	Calculates the i-th occurrence of the symbol c in the supported vector.

size_type	serialize (std::ostream &out, structure_tree_node *v=nullptr, 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.

template<typename archive_t>
void	CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
	Serialise (save) via cereal.

template<typename archive_t>
void	CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
	Load via cereal.

iterator	begin ()

const_iterator	end ()

iterator	begin () const

const_iterator	end () const

bool	operator== (wt_ap const &other) const noexcept
	Equality operator.

bool	operator!= (wt_ap const &other) const noexcept
	Inequality operator.

Public Attributes
size_type const &	sigma = m_sigma

Protected Attributes
size_type	m_size = 0

value_type	m_sigma = 0

value_type	m_singleton_class_cnt = 0

value_type	m_class_cnt = 0

wt_byte_type	m_char2class

wt_byte_type	m_class

std::vector< wt_int_type >	m_offset

Detailed Description

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>
class sdsl::wt_ap< t_wt_byte, t_wt_int >

A wavelet tree class for integer sequences.

Space complexity: $\order{n} (H_0 + 1)$ bits, where is the size of the vector the wavelet tree was build for.1

Template Parameters

t_wt_byte	Type of the wavelet tree used for class representation.
t_wt_int	Type of the wavelet tree used for class offset representation.

References: [1] J. Barbay, F. Claude, T. Gagie, G. Navarro and Y. Nekrich: ,,Efficient Fully-Compressed Sequence Representations''

Definition at line 58 of file wt_ap.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

typedef int_alphabet_tag sdsl::wt_ap< t_wt_byte, t_wt_int >::alphabet_category

Definition at line 74 of file wt_ap.hpp.

◆ const_iterator

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

typedef random_access_const_iterator<wt_ap> sdsl::wt_ap< t_wt_byte, t_wt_int >::const_iterator

Definition at line 69 of file wt_ap.hpp.

◆ difference_type

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

typedef int_vector ::difference_type sdsl::wt_ap< t_wt_byte, t_wt_int >::difference_type

Definition at line 68 of file wt_ap.hpp.

◆ index_category

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

typedef wt_tag sdsl::wt_ap< t_wt_byte, t_wt_int >::index_category

Definition at line 73 of file wt_ap.hpp.

◆ iterator

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

typedef const_iterator sdsl::wt_ap< t_wt_byte, t_wt_int >::iterator

Definition at line 70 of file wt_ap.hpp.

◆ size_type

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

typedef int_vector ::size_type sdsl::wt_ap< t_wt_byte, t_wt_int >::size_type

Definition at line 66 of file wt_ap.hpp.

◆ value_type

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

typedef int_vector ::value_type sdsl::wt_ap< t_wt_byte, t_wt_int >::value_type

Definition at line 67 of file wt_ap.hpp.

◆ wt_byte_type

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

typedef t_wt_byte sdsl::wt_ap< t_wt_byte, t_wt_int >::wt_byte_type

Definition at line 71 of file wt_ap.hpp.

◆ wt_int_type

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

typedef t_wt_int sdsl::wt_ap< t_wt_byte, t_wt_int >::wt_int_type

Definition at line 72 of file wt_ap.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

anonymous enum

Enumerator
lex_ordered

Definition at line 75 of file wt_ap.hpp.

Constructor & Destructor Documentation

◆ wt_ap() [1/4]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

sdsl::wt_ap< t_wt_byte, t_wt_int >::wt_ap ( )

inline

Default constructor.

Definition at line 109 of file wt_ap.hpp.

◆ wt_ap() [2/4]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

template<typename t_it>

sdsl::wt_ap< t_wt_byte, t_wt_int >::wt_ap	(	t_it	begin,
		t_it	end,
		std::string	tmp_dir = ram_file_name("") )

inline

Construct the wavelet tree from a sequence defined by two interators.

Parameters

begin	Iterator to the start of the input.
end	Iterator one past the end of the input.
tmp_dir	Temporary directory for intermediate results.

Definition at line 119 of file wt_ap.hpp.

◆ wt_ap() [3/4]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

sdsl::wt_ap< t_wt_byte, t_wt_int >::wt_ap ( wt_ap< t_wt_byte, t_wt_int > const & wt )

inline

Copy constructor.

Definition at line 232 of file wt_ap.hpp.

◆ wt_ap() [4/4]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

sdsl::wt_ap< t_wt_byte, t_wt_int >::wt_ap ( wt_ap< t_wt_byte, t_wt_int > && wt )

inline

Move copy constructor.

Definition at line 243 of file wt_ap.hpp.

Member Function Documentation

◆ begin() [1/2]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

iterator sdsl::wt_ap< t_wt_byte, t_wt_int >::begin ( )

inline

Definition at line 443 of file wt_ap.hpp.

◆ begin() [2/2]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

iterator sdsl::wt_ap< t_wt_byte, t_wt_int >::begin ( ) const

inline

Definition at line 451 of file wt_ap.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

template<typename archive_t>

void sdsl::wt_ap< t_wt_byte, t_wt_int >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar )

inline

Load via cereal.

Definition at line 432 of file wt_ap.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

template<typename archive_t>

void sdsl::wt_ap< t_wt_byte, t_wt_int >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar ) const

inline

Serialise (save) via cereal.

Definition at line 419 of file wt_ap.hpp.

◆ empty()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

bool sdsl::wt_ap< t_wt_byte, t_wt_int >::empty ( ) const

inline

Returns whether the wavelet tree contains no data.

Definition at line 282 of file wt_ap.hpp.

◆ end() [1/2]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

const_iterator sdsl::wt_ap< t_wt_byte, t_wt_int >::end ( )

inline

Definition at line 447 of file wt_ap.hpp.

◆ end() [2/2]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

const_iterator sdsl::wt_ap< t_wt_byte, t_wt_int >::end ( ) const

inline

Definition at line 455 of file wt_ap.hpp.

◆ inverse_select()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

std::pair< size_type, value_type > sdsl::wt_ap< t_wt_byte, t_wt_int >::inverse_select ( size_type i ) const

inline

Calculates how many occurrences of symbol wt[i] are in the prefix [0..i-1] of the original sequence.

Parameters

i	The index of the symbol.

Returns: Pair (rank(wt[i],i),wt[i])

Precondition

Definition at line 340 of file wt_ap.hpp.

◆ load()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

void sdsl::wt_ap< t_wt_byte, t_wt_int >::load ( std::istream & in )

inline

Loads the data structure from the given istream.

Definition at line 401 of file wt_ap.hpp.

◆ operator!=()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

bool sdsl::wt_ap< t_wt_byte, t_wt_int >::operator!= ( wt_ap< t_wt_byte, t_wt_int > const & other ) const

inlinenoexcept

Inequality operator.

Definition at line 469 of file wt_ap.hpp.

◆ operator=() [1/2]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

wt_ap & sdsl::wt_ap< t_wt_byte, t_wt_int >::operator= ( wt_ap< t_wt_byte, t_wt_int > && wt )

inline

Assignment move operator.

Definition at line 260 of file wt_ap.hpp.

◆ operator=() [2/2]

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

wt_ap & sdsl::wt_ap< t_wt_byte, t_wt_int >::operator= ( wt_ap< t_wt_byte, t_wt_int > const & wt )

inline

Assignment operator.

Definition at line 249 of file wt_ap.hpp.

◆ operator==()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

bool sdsl::wt_ap< t_wt_byte, t_wt_int >::operator== ( wt_ap< t_wt_byte, t_wt_int > const & other ) const

inlinenoexcept

Equality operator.

Definition at line 461 of file wt_ap.hpp.

◆ operator[]()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

value_type sdsl::wt_ap< t_wt_byte, t_wt_int >::operator[] ( size_type i ) const

inline

Recovers the i-th symbol of the original vector.

Parameters

i	The index of the symbol in the original vector.

Returns: The i-th symbol of the original vector.

Worst case time complexity: $\Order{\log \log |\Sigma|}$

Average case time complexity: $\Order{\log H_0}$

Precondition

Definition at line 297 of file wt_ap.hpp.

◆ rank()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

size_type sdsl::wt_ap< t_wt_byte, t_wt_int >::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 occurrences in the prefix.

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

Worst case time complexity: $\Order{\log \log |\Sigma|}$

Average case time complexity: $\Order{\log H_0}$

Precondition: $i \leq size()$

Definition at line 319 of file wt_ap.hpp.

◆ select()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

size_type sdsl::wt_ap< t_wt_byte, t_wt_int >::select	(	size_type	i,
		value_type	c ) const

inline

Calculates the i-th occurrence of the symbol c in the supported vector.

Parameters

i	The i-th occurrence.
c	The symbol c.

Worst case time complexity: $\Order{\log \log |\Sigma|}$

Average case time complexity: $\Order{\log H_0}$

Precondition: $1 \leq i \leq rank(size(), c)$

Definition at line 366 of file wt_ap.hpp.

◆ serialize()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

size_type sdsl::wt_ap< t_wt_byte, t_wt_int >::serialize	(	std::ostream &	out,
		structure_tree_node *	v = nullptr,
		std::string	name = "" ) const

inline

Serializes the data structure into the given ostream.

Definition at line 382 of file wt_ap.hpp.

◆ size()

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

size_type sdsl::wt_ap< t_wt_byte, t_wt_int >::size ( ) const

inline

Returns the size of the original vector.

Definition at line 276 of file wt_ap.hpp.

Member Data Documentation

◆ m_char2class

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

wt_byte_type sdsl::wt_ap< t_wt_byte, t_wt_int >::m_char2class

protected

Definition at line 85 of file wt_ap.hpp.

◆ m_class

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

wt_byte_type sdsl::wt_ap< t_wt_byte, t_wt_int >::m_class

protected

Definition at line 86 of file wt_ap.hpp.

◆ m_class_cnt

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

value_type sdsl::wt_ap< t_wt_byte, t_wt_int >::m_class_cnt = 0

protected

Definition at line 84 of file wt_ap.hpp.

◆ m_offset

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

std::vector<wt_int_type> sdsl::wt_ap< t_wt_byte, t_wt_int >::m_offset

protected

Definition at line 87 of file wt_ap.hpp.

◆ m_sigma

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

value_type sdsl::wt_ap< t_wt_byte, t_wt_int >::m_sigma = 0

protected

Definition at line 82 of file wt_ap.hpp.

◆ m_singleton_class_cnt

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

value_type sdsl::wt_ap< t_wt_byte, t_wt_int >::m_singleton_class_cnt = 0

protected

Definition at line 83 of file wt_ap.hpp.

◆ m_size

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

size_type sdsl::wt_ap< t_wt_byte, t_wt_int >::m_size = 0

protected

Definition at line 81 of file wt_ap.hpp.

◆ sigma

template<class t_wt_byte = wt_huff<bit_vector, rank_support_v5<>>, class t_wt_int = wm_int<>>

size_type const& sdsl::wt_ap< t_wt_byte, t_wt_int >::sigma = m_sigma

Definition at line 106 of file wt_ap.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/wt_ap.hpp

Public Types

Public Member Functions

Public Attributes

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ alphabet_category

◆ const_iterator

◆ difference_type

◆ index_category

◆ iterator

◆ size_type

◆ value_type

◆ wt_byte_type

◆ wt_int_type

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ wt_ap() [1/4]

◆ wt_ap() [2/4]

◆ wt_ap() [3/4]

◆ wt_ap() [4/4]

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ CEREAL_LOAD_FUNCTION_NAME()

◆ CEREAL_SAVE_FUNCTION_NAME()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ inverse_select()

◆ load()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]()

◆ rank()

◆ select()

◆ serialize()

◆ size()

Member Data Documentation

◆ m_char2class

◆ m_class

◆ m_class_cnt

◆ m_offset

◆ m_sigma

◆ m_singleton_class_cnt

◆ m_size

◆ sigma