Detailed description

template< typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>
struct nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >

A shallow Wavelet Tree class, holding iterators to a bit-string representing the different bit-planes of the output Wavelet Tree, and the tree structure itself, a binary heap, recording the sequence split of each node.

Template Parameters

BitStreamIterator	the output bit-string type: must possess an iterator interface, and define a valid implementation of nvbio::assign(); iterator_system<BitStreamIterator>::type is used to determine whether to apply host or device algorithms
IndexIterator	an iterator to an integer array representing the sequence splits of the Wavelet Tree's nodes, encoded as a full binary heap; the array must contain at least (2^SYMBOL_SIZE) - 1 entries
SymbolType	the unsigned integer type used to encode symbols (e.g. uint8, uint16, uint32...)

Definition at line 77 of file wavelet_tree.h.

#include <wavelet_tree.h>

Public Types
typedef iterator_system < BitStreamIterator >::type	system_tag

typedef stream_traits < BitStreamIterator > ::index_type	index_type

typedef SymbolType	symbol_type

typedef SymbolType	value_type

typedef BitStreamIterator	bit_iterator

typedef IndexIterator	index_iterator

typedef WaveletTree < BitStreamIterator, IndexIterator >	text_type

typedef vector_type < index_type, 2 >::type	range_type

typedef null_type	vector_type

Public Methods
NVBIO_HOST_DEVICE	WaveletTree (const uint32 _symbol_size=0, const index_type _size=0, const BitStreamIterator _bits=BitStreamIterator(), const IndexIterator _nodes=IndexIterator(), const IndexIterator _occ=IndexIterator())

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	resize (const uint32 _size, const uint32 _symbol_size)

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32	symbol_count () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32	symbol_size () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type	size () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE BitStreamIterator	bits () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE IndexIterator	splits () const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE IndexIterator	occ () const

NVBIO_HOST_DEVICE index_type	rank (const uint32 l, const uint32 node, const index_type node_begin, const index_type r, const uint8 b) const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE SymbolType	operator[] (const index_type i) const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE SymbolType	operator() (const index_type i) const

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE text_type &	text ()

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const text_type &	text () const

Public Members
uint32	m_symbol_size

index_type	m_size

BitStreamIterator	m_bits

IndexIterator	m_nodes

IndexIterator	m_occ

Related Functions
(Note that these are not member functions.)
template<typename BitStreamIterator , typename IndexIterator , typename IndexType , typename SymbolType >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE SymbolType	text (const WaveletTree< BitStreamIterator, IndexIterator, SymbolType > &tree, const IndexType i)

template<typename BitStreamIterator , typename IndexIterator , typename SymbolType >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE WaveletTree < BitStreamIterator, IndexIterator, SymbolType > ::index_type	rank (const WaveletTree< BitStreamIterator, IndexIterator, SymbolType > &tree, const typename WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::index_type i, const uint32 c)

template<typename BitStreamIterator , typename IndexIterator , typename SymbolType >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE WaveletTree < BitStreamIterator, IndexIterator, SymbolType > ::range_type	rank (const WaveletTree< BitStreamIterator, IndexIterator, SymbolType > &tree, const typename WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::range_type range, const uint32 c)

Member Typedef Documentation

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

typedef BitStreamIterator nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::bit_iterator

Definition at line 84 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

typedef IndexIterator nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::index_iterator

Definition at line 85 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

typedef stream_traits<BitStreamIterator>::index_type nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::index_type

Definition at line 81 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

typedef vector_type<index_type,2>::type nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::range_type

Definition at line 88 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

typedef SymbolType nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::symbol_type

Definition at line 82 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

typedef iterator_system<BitStreamIterator>::type nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::system_tag

Definition at line 80 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

typedef WaveletTree<BitStreamIterator,IndexIterator> nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::text_type

Definition at line 86 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

typedef SymbolType nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::value_type

Definition at line 83 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

typedef null_type nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::vector_type

Definition at line 89 of file wavelet_tree.h.

Constructor & Destructor Documentation

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

NVBIO_HOST_DEVICE nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::WaveletTree	(	const uint32	_symbol_size = `0`,
		const index_type	_size = `0`,
		const BitStreamIterator	_bits = `BitStreamIterator()`,
		const IndexIterator	_nodes = `IndexIterator()`,
		const IndexIterator	_occ = `IndexIterator()`
	)

inline

constructor

Definition at line 94 of file wavelet_tree.h.

Member Function Documentation

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE BitStreamIterator nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::bits ( ) const

inline

return the bit string

Definition at line 133 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE IndexIterator nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::occ ( ) const

inline

return the occurrences

Definition at line 143 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE SymbolType nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::operator() ( const index_type i) const

inline

return the i-th symbol - unary functor form

Definition at line 158 of file wavelet_tree.h.

template<typename BitStreamIterator , typename IndexIterator , typename SymbolType >

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE SymbolType nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::operator[] ( const index_type i) const

return the i-th symbol

Definition at line 334 of file wavelet_tree_inl.h.

template<typename BitStreamIterator , typename IndexIterator , typename SymbolType >

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::index_type nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::rank	(	const uint32	l,
		const uint32	node,
		const index_type	node_begin,
		const index_type	r,
		const uint8	b
	)		const

return the number of bits set to b in the range [0,r] within node n at level l

Definition at line 344 of file wavelet_tree_inl.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::resize	(	const uint32	_size,
		const uint32	_symbol_size
	)

inline

resize the tree

Definition at line 109 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE index_type nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::size ( void ) const

inline

return the number of symbols

Definition at line 128 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE IndexIterator nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::splits ( ) const

inline

return the node splits

Definition at line 138 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::symbol_count ( ) const

inline

return the number of bits per symbol

Definition at line 118 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE uint32 nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::symbol_size ( ) const

inline

return the number of bits per symbol

Definition at line 123 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE text_type& nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::text ( )

inline

Definition at line 160 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE const text_type& nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::text ( ) const

inline

Definition at line 161 of file wavelet_tree.h.

Member Data Documentation

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

BitStreamIterator nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::m_bits

Definition at line 165 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

IndexIterator nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::m_nodes

Definition at line 166 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

IndexIterator nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::m_occ

Definition at line 167 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

index_type nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::m_size

Definition at line 164 of file wavelet_tree.h.

template<typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>

uint32 nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >::m_symbol_size

Definition at line 163 of file wavelet_tree.h.

The documentation for this struct was generated from the following files:

E:/git/nvbio/nvbio/strings/wavelet_tree.h
E:/git/nvbio/nvbio/strings/wavelet_tree_inl.h

Detailed description

template< typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8> struct nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >

Public Types

Public Methods

Public Members

Related Functions

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template< typename BitStreamIterator, typename IndexIterator, typename SymbolType = uint8>
struct nvbio::WaveletTree< BitStreamIterator, IndexIterator, SymbolType >