A prefix code-shaped wavelet. More...

#include <wt_pc.hpp>

Public Types
enum	{ lex_ordered = shape_type::lex_ordered }

typedef t_tree_strat::template type< wt_pc >	tree_strat_type

typedef int_vector ::size_type	size_type

typedef tree_strat_type::value_type	value_type

typedef t_bitvector::difference_type	difference_type

typedef random_access_const_iterator< wt_pc >	const_iterator

typedef const_iterator	iterator

typedef t_bitvector	bit_vector_type

typedef t_rank	rank_1_type

typedef t_select	select_1_type

typedef t_select_zero	select_0_type

typedef wt_tag	index_category

typedef tree_strat_type::alphabet_category	alphabet_category

typedef t_shape::template type< wt_pc >	shape_type

using	node_type = typename tree_strat_type::node_type

Public Member Functions
	wt_pc ()

template<typename t_it>
	wt_pc (t_it begin, t_it end)
	Construct the wavelet tree from a sequence defined by two interators.

template<typename t_it>
	wt_pc (t_it begin, t_it end, std::string)

	wt_pc (wt_pc const &wt)
	Copy constructor.

	wt_pc (wt_pc &&wt)

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

wt_pc &	operator= (wt_pc &&wt)
	Move assignment 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].

std::pair< size_type, value_type >	inverse_select (size_type i) const
	Calculates how many times symbol wt[i] occurs in the prefix [0..i-1].

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

void	interval_symbols (size_type i, size_type j, size_type &k, std::vector< value_type > &cs, std::vector< size_type > &rank_c_i, std::vector< size_type > &rank_c_j) const
	For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).

template<class t_ret_type = std::tuple<size_type, size_type, size_type>>
std::enable_if< shape_type::lex_ordered, t_ret_type >::type	lex_count (size_type i, size_type j, value_type c) const
	How many symbols are lexicographic smaller/greater than c in [i..j-1].

template<class t_ret_type = std::tuple<size_type, size_type>>
std::enable_if< shape_type::lex_ordered, t_ret_type >::type	lex_smaller_count (size_type i, value_type c) const
	How many symbols are lexicographic smaller than c in [0..i-1].

const_iterator	begin () const
	Returns a const_iterator to the first element.

const_iterator	end () const
	Returns a const_iterator to the element after the last element.

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.

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

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

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)

auto	bit_vec (node_type const &v) const -> node_bv_container< t_bitvector >
	Random access container to bitvector of node v.

auto	seq (node_type const &v) const -> random_access_container< std::function< value_type(size_type)> >
	Random access container to sequence of node v.

bool	is_leaf (node_type const &v) const
	Checks if the node is a leaf node.

value_type	sym (node_type const &v) const
	Symbol for a leaf.

bool	empty (node_type const &v) const
	Indicates if node v is empty.

auto	size (node_type const &v) const -> decltype(m_tree.size(v))
	Return the size of node v.

node_type	root () const
	Returns the root node.

std::array< node_type, 2 >	expand (node_type const &v) const
	Returns the two child nodes of an inner node.

std::array< range_vec_type, 2 >	expand (node_type const &v, range_vec_type const &ranges) const
	Returns for each range its left and right child ranges.

std::array< range_vec_type, 2 >	expand (node_type const &v, range_vec_type &&ranges) const
	Returns for each range its left and right child ranges.

std::array< range_type, 2 >	expand (node_type const &v, range_type const &r) const
	Returns for a range its left and right child ranges.

std::pair< uint64_t, uint64_t >	path (value_type c) const
	return the path to the leaf for a given symbol

std::pair< bool, value_type >	symbol_gte (value_type c) const
	Returns for a symbol c the next larger or equal symbol in the WT.

std::pair< bool, value_type >	symbol_lte (value_type c) const
	Returns for a symbol c the previous smaller or equal symbol in the WT.

Public Attributes
size_type const &	sigma = m_sigma

bit_vector_type const &	bv = m_bv

Detailed Description

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>
class sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >

A prefix code-shaped wavelet.

Template Parameters

t_shape	Shape of the tree ().
t_bitvector	Underlying bitvector structure.
t_rank	Rank support for pattern `1` on the bitvector.
t_select	Select support for pattern `1` on the bitvector.
t_select_zero	Select support for pattern `0` on the bitvector.
t_tree_strat	Tree strategy determines alphabet and the tree class used to navigate the WT.

Definition at line 59 of file wt_pc.hpp.

Member Typedef Documentation

◆ alphabet_category

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef tree_strat_type::alphabet_category sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::alphabet_category

Definition at line 73 of file wt_pc.hpp.

◆ bit_vector_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef t_bitvector sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::bit_vector_type

Definition at line 68 of file wt_pc.hpp.

◆ const_iterator

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef random_access_const_iterator<wt_pc> sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::const_iterator

Definition at line 66 of file wt_pc.hpp.

◆ difference_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef t_bitvector::difference_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::difference_type

Definition at line 65 of file wt_pc.hpp.

◆ index_category

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef wt_tag sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::index_category

Definition at line 72 of file wt_pc.hpp.

◆ iterator

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef const_iterator sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::iterator

Definition at line 67 of file wt_pc.hpp.

◆ node_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

using sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::node_type = typename tree_strat_type::node_type

Definition at line 79 of file wt_pc.hpp.

◆ rank_1_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef t_rank sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::rank_1_type

Definition at line 69 of file wt_pc.hpp.

◆ select_0_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef t_select_zero sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::select_0_type

Definition at line 71 of file wt_pc.hpp.

◆ select_1_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef t_select sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::select_1_type

Definition at line 70 of file wt_pc.hpp.

◆ shape_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef t_shape::template type<wt_pc> sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::shape_type

Definition at line 74 of file wt_pc.hpp.

◆ size_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef int_vector ::size_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::size_type

Definition at line 63 of file wt_pc.hpp.

◆ tree_strat_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef t_tree_strat::template type<wt_pc> sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::tree_strat_type

Definition at line 62 of file wt_pc.hpp.

◆ value_type

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

typedef tree_strat_type::value_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::value_type

Definition at line 64 of file wt_pc.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

anonymous enum

Enumerator
lex_ordered

Definition at line 75 of file wt_pc.hpp.

Constructor & Destructor Documentation

◆ wt_pc() [1/5]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::wt_pc ( )

inline

Definition at line 184 of file wt_pc.hpp.

◆ wt_pc() [2/5]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

template<typename t_it>

sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::wt_pc	(	t_it	begin,
		t_it	end )

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.

Time complexity: $\Order{n\log|\Sigma|}$ , where

Definition at line 194 of file wt_pc.hpp.

◆ wt_pc() [3/5]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

template<typename t_it>

sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::wt_pc	(	t_it	begin,
		t_it	end,
		std::string	)

inline

Definition at line 251 of file wt_pc.hpp.

◆ wt_pc() [4/5]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::wt_pc ( wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > const & wt )

inline

Copy constructor.

Definition at line 255 of file wt_pc.hpp.

◆ wt_pc() [5/5]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::wt_pc ( wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > && wt )

inline

Definition at line 269 of file wt_pc.hpp.

Member Function Documentation

◆ begin()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

const_iterator sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::begin ( ) const

inline

Returns a const_iterator to the first element.

Definition at line 701 of file wt_pc.hpp.

◆ bit_vec()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

auto sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::bit_vec ( node_type const & v ) const -> node_bv_container<t_bitvector>

inline

Random access container to bitvector of node v.

Definition at line 782 of file wt_pc.hpp.

◆ CEREAL_LOAD_FUNCTION_NAME()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

template<typename archive_t>

void sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar )

inline

Definition at line 767 of file wt_pc.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

template<typename archive_t>

void sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar ) const

inline

Definition at line 755 of file wt_pc.hpp.

◆ empty() [1/2]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

bool sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::empty ( ) const

inline

Returns whether the wavelet tree contains no data.

Definition at line 320 of file wt_pc.hpp.

◆ empty() [2/2]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

bool sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::empty ( node_type const & v ) const

inline

Indicates if node v is empty.

Definition at line 820 of file wt_pc.hpp.

◆ end()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

const_iterator sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::end ( ) const

inline

Returns a const_iterator to the element after the last element.

Definition at line 707 of file wt_pc.hpp.

◆ expand() [1/4]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

std::array< node_type, 2 > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::expand ( node_type const & v ) const

inline

Returns the two child nodes of an inner node.

Parameters

v	An inner node of a wavelet tree.

Returns: Return a pair of nodes (left child, right child).

Precondition: !is_leaf(v)

Definition at line 859 of file wt_pc.hpp.

◆ expand() [2/4]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

std::array< range_type, 2 > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::expand	(	node_type const &	v,
		range_type const &	r ) const

inline

Returns for a range its left and right child ranges.

Parameters

v	An inner node of an wavelet tree.
r	A ranges [s,e], such that [s,e] is contained in v=[v_s,v_e].

Returns: A range pair. The first element of the range pair correspond to the original range mapped to the left child of v; the second element to the range mapped to the right child of v.

Precondition: !is_leaf(v) and s>=v_s and e<=v_e

Definition at line 920 of file wt_pc.hpp.

◆ expand() [3/4]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

std::array< range_vec_type, 2 > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::expand	(	node_type const &	v,
		range_vec_type &&	ranges ) const

inline

Returns for each range its left and right child ranges.

Parameters

v	An inner node of an wavelet tree.
ranges	A vector of ranges. Each range [s,e] has to be contained in v=[v_s,v_e].

Returns: A vector a range pairs. The first element of each range pair correspond to the original range mapped to the left child of v; the second element to the range mapped to the right child of v.

Precondition: !is_leaf(v) and s>=v_s and e<=v_e

Definition at line 890 of file wt_pc.hpp.

◆ expand() [4/4]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

std::array< range_vec_type, 2 > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::expand	(	node_type const &	v,
		range_vec_type const &	ranges ) const

inline

Returns for each range its left and right child ranges.

Parameters

v	An inner node of an wavelet tree.
ranges	A vector of ranges. Each range [s,e] has to be contained in v=[v_s,v_e].

Returns: A vector a range pairs. The first element of each range pair correspond to the original range mapped to the left child of v; the second element to the range mapped to the right child of v.

Precondition: !is_leaf(v) and s>=v_s and e<=v_e

Definition at line 874 of file wt_pc.hpp.

◆ interval_symbols()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

void sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::interval_symbols	(	size_type	i,
		size_type	j,
		size_type &	k,
		std::vector< value_type > &	cs,
		std::vector< size_type > &	rank_c_i,
		std::vector< size_type > &	rank_c_j ) const

inline

For each symbol c in wt[i..j-1] get rank(i,c) and rank(j,c).

Parameters

i	The start index (inclusive) of the interval.
j	The end index (exclusive) of the interval.
k	Reference for number of different symbols in [i..j-1].
cs	Reference to a vector that will contain in cs[0..k-1] all symbols that occur in [i..j-1] in arbitrary order (if lex_ordered = false) and ascending order (if lex_ordered = true).
rank_c_i	Reference to a vector which equals rank_c_i[p] = rank(i,cs[p]), for $0 \leq p < k$ .
rank_c_j	Reference to a vector which equals rank_c_j[p] = rank(j,cs[p]), for $0 \leq p < k$ .

Time complexity: $\Order{\min{\sigma, k \log \sigma}}$

Precondition: $i \leq j \leq size()$ $cs.size() \geq \sigma$ $rank_{c_i}.size() \geq \sigma$ $rank_{c_j}.size() \geq \sigma$

Definition at line 498 of file wt_pc.hpp.

◆ inverse_select()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

std::pair< size_type, value_type > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::inverse_select ( size_type i ) const

inline

Calculates how many times symbol wt[i] occurs in the prefix [0..i-1].

Parameters

i	The index of the symbol.

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

Time complexity: $\Order{H_0}$

Precondition

Definition at line 411 of file wt_pc.hpp.

◆ is_leaf()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

bool sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::is_leaf ( node_type const & v ) const

inline

Checks if the node is a leaf node.

Definition at line 808 of file wt_pc.hpp.

◆ lex_count()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

template<class t_ret_type = std::tuple<size_type, size_type, size_type>>

std::enable_if< shape_type::lex_ordered, t_ret_type >::type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::lex_count	(	size_type	i,
		size_type	j,
		value_type	c ) const

inline

How many symbols are lexicographic smaller/greater than c in [i..j-1].

Parameters

i	Start index (inclusive) of the interval.
j	End index (exclusive) of the interval.
c	Symbol c.

Returns

A triple containing:

rank(i,c)
#symbols smaller than c in [i..j-1]
#symbols greater than c in [i..j-1]

Precondition: $i \leq j \leq size()$

Note: This method is only available if lex_ordered = true

Definition at line 575 of file wt_pc.hpp.

◆ lex_smaller_count()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

template<class t_ret_type = std::tuple<size_type, size_type>>

std::enable_if< shape_type::lex_ordered, t_ret_type >::type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::lex_smaller_count	(	size_type	i,
		value_type	c ) const

inline

How many symbols are lexicographic smaller than c in [0..i-1].

Parameters

i	Exclusive right bound of the range.
c	Symbol c.

Returns

A tuple containing:

rank(i,c)
#symbols smaller than c in [0..i-1]

Precondition: $i \leq size()$

Note: This method is only available if lex_ordered = true

Definition at line 647 of file wt_pc.hpp.

◆ load()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

void sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::load ( std::istream & in )

inline

Loads the data structure from the given istream.

Definition at line 729 of file wt_pc.hpp.

◆ operator!=()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

bool sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::operator!= ( wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > const & other ) const

inlinenoexcept

Inequality operator.

Definition at line 749 of file wt_pc.hpp.

◆ operator=() [1/2]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

wt_pc & sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::operator= ( wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > && wt )

inline

Move assignment operator.

Definition at line 295 of file wt_pc.hpp.

◆ operator=() [2/2]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

wt_pc & sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::operator= ( wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > const & wt )

inline

Assignment operator.

Definition at line 284 of file wt_pc.hpp.

◆ operator==()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

bool sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::operator== ( wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat > const & other ) const

inlinenoexcept

Equality operator.

Definition at line 741 of file wt_pc.hpp.

◆ operator[]()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

value_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::operator[] ( size_type i ) const

inline

Recovers the i-th symbol of the original vector.

Parameters

i	Index in the original vector.

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

Time complexity: $\Order{H_0}$ on average, where is the zero order entropy of the sequence

Precondition

Definition at line 336 of file wt_pc.hpp.

◆ path()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

std::pair< uint64_t, uint64_t > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::path ( value_type c ) const

inline

return the path to the leaf for a given symbol

Definition at line 934 of file wt_pc.hpp.

◆ rank()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

size_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::rank	(	size_type	i,
		value_type	c ) const

inline

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

Parameters

i	Exclusive right bound of the range.
c	Symbol c.

Returns: Number of occurrences of symbol c in the prefix [0..i-1].

Time complexity: $\Order{H_0}$ on average, where is the zero order entropy of the sequence

Precondition: $i \leq size()$

Definition at line 371 of file wt_pc.hpp.

◆ root()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

node_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::root ( ) const

inline

Returns the root node.

Definition at line 849 of file wt_pc.hpp.

◆ select()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

size_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::select	(	size_type	i,
		value_type	c ) const

inline

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

Parameters

i	The ith occurrence.
c	The symbol c.

Time complexity: $\Order{H_0}$ on average, where is the zero order entropy of the sequence

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

Definition at line 443 of file wt_pc.hpp.

◆ seq()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

auto sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::seq ( node_type const & v ) const -> random_access_container<std::function<value_type(size_type)>>

inline

Random access container to sequence of node v.

Definition at line 788 of file wt_pc.hpp.

◆ serialize()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

size_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::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 713 of file wt_pc.hpp.

◆ size() [1/2]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

size_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::size ( ) const

inline

Returns the size of the original vector.

Definition at line 314 of file wt_pc.hpp.

◆ size() [2/2]

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

auto sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::size ( node_type const & v ) const -> decltype(m_tree.size(v))

inline

Return the size of node v.

Definition at line 826 of file wt_pc.hpp.

◆ sym()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

value_type sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::sym ( node_type const & v ) const

inline

Symbol for a leaf.

Definition at line 814 of file wt_pc.hpp.

◆ symbol_gte()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

std::pair< bool, value_type > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::symbol_gte ( value_type c ) const

inline

Returns for a symbol c the next larger or equal symbol in the WT.

Parameters

c	the symbol

Returns: A pair. The first element of the pair consititues if a valid answer was found (true) or no valid answer (false) could be found. The second element contains the found symbol.

Definition at line 950 of file wt_pc.hpp.

◆ symbol_lte()

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

std::pair< bool, value_type > sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::symbol_lte ( value_type c ) const

inline

Returns for a symbol c the previous smaller or equal symbol in the WT.

Parameters

c	the symbol

Returns: A pair. The first element of the pair consititues if a valid answer was found (true) or no valid answer (false) could be found. The second element contains the found symbol.

Definition at line 961 of file wt_pc.hpp.

Member Data Documentation

◆ bv

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

bit_vector_type const& sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::bv = m_bv

Definition at line 181 of file wt_pc.hpp.

◆ sigma

template<class t_shape, class t_bitvector = bit_vector, class t_rank = typename t_bitvector::rank_1_type, class t_select = typename t_bitvector::select_1_type, class t_select_zero = typename t_bitvector::select_0_type, class t_tree_strat = byte_tree<>>

size_type const& sdsl::wt_pc< t_shape, t_bitvector, t_rank, t_select, t_select_zero, t_tree_strat >::sigma = m_sigma

Definition at line 180 of file wt_pc.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_pc.hpp

Public Types

Public Member Functions

Public Attributes

Detailed Description

Member Typedef Documentation

◆ alphabet_category

◆ bit_vector_type

◆ const_iterator

◆ difference_type

◆ index_category

◆ iterator

◆ node_type

◆ rank_1_type

◆ select_0_type

◆ select_1_type

◆ shape_type

◆ size_type

◆ tree_strat_type

◆ value_type

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ wt_pc() [1/5]

◆ wt_pc() [2/5]

◆ wt_pc() [3/5]

◆ wt_pc() [4/5]

◆ wt_pc() [5/5]

Member Function Documentation

◆ begin()

◆ bit_vec()

◆ CEREAL_LOAD_FUNCTION_NAME()

◆ CEREAL_SAVE_FUNCTION_NAME()

◆ empty() [1/2]

◆ empty() [2/2]

◆ end()

◆ expand() [1/4]

◆ expand() [2/4]

◆ expand() [3/4]

◆ expand() [4/4]

◆ interval_symbols()

◆ inverse_select()

◆ is_leaf()

◆ lex_count()

◆ lex_smaller_count()

◆ load()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]()

◆ path()

◆ rank()

◆ root()

◆ select()

◆ seq()

◆ serialize()

◆ size() [1/2]

◆ size() [2/2]

◆ sym()

◆ symbol_gte()

◆ symbol_lte()

Member Data Documentation

◆ bv

◆ sigma