indexes::arbology::CompressedBitParallelTreeIndex< SymbolType > Class Template Reference

Compressed bit parallel tree index. Stores a bit vector for each symbol of the alphabet. The bit vector of symbol a contains true on index i if symbol a is on i-th position in the indexed string. The class does not check whether the bit vectors actually represent valid index. The bit vectors are compressed with run length encoding packing runs of false values. Additionally the index contains a subtree jump table representing positions after a jump over a subtree. More...

#include <CompressedBitParallelTreeIndex.h>

Inheritance diagram for indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >:

Collaboration diagram for indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >:

Public Member Functions
	CompressedBitParallelTreeIndex (ext::set< common::ranked_symbol< SymbolType > > alphabet, ext::map< common::ranked_symbol< SymbolType >, common::SparseBoolVector > vectors, ext::vector< int > jumpTable)
const ext::map< common::ranked_symbol< SymbolType >, common::SparseBoolVector > &	getData () const &
ext::map< common::ranked_symbol< SymbolType >, common::SparseBoolVector > &&	getData () &&
const ext::vector< int > &	getJumps () const &
ext::vector< int > &&	getJumps () &&
ext::vector< common::ranked_symbol< SymbolType > >	getString () const
const ext::set< common::ranked_symbol< SymbolType > > &	getAlphabet () const &
ext::set< common::ranked_symbol< SymbolType > > &&	getAlphabet () &&
void	setCompressedBitVectorForSymbol (common::ranked_symbol< SymbolType > symbol, common::SparseBoolVector data)
bool	removeSymbolFromAlphabet (const common::ranked_symbol< SymbolType > &symbol)
auto	operator<=> (const CompressedBitParallelTreeIndex &other) const
bool	operator== (const CompressedBitParallelTreeIndex &other) const
Public Member Functions inherited from core::Components< CompressedBitParallelTreeIndex< DefaultSymbolType >, ext::set< common::ranked_symbol< DefaultSymbolType > >, component::Set, GeneralAlphabet >
void	accessComponent ()

Friends
ext::ostream &	operator<< (ext::ostream &out, const CompressedBitParallelTreeIndex &instance)

Additional Inherited Members
Static Public Member Functions inherited from core::Components< CompressedBitParallelTreeIndex< DefaultSymbolType >, ext::set< common::ranked_symbol< DefaultSymbolType > >, component::Set, GeneralAlphabet >
static void	registerComponent ()
static void	unregisterComponent ()

Detailed Description

template<class SymbolType = DefaultSymbolType>
class indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >

Compressed bit parallel tree index. Stores a bit vector for each symbol of the alphabet. The bit vector of symbol a contains true on index i if symbol a is on i-th position in the indexed string. The class does not check whether the bit vectors actually represent valid index. The bit vectors are compressed with run length encoding packing runs of false values. Additionally the index contains a subtree jump table representing positions after a jump over a subtree.

The actual notation of used tree is irelevant. The index, as fas as the data structure is concerned, is not different. Of course tree in postfix notation must be queried with patterns in postfix notation, etc.

Template Parameters

SymbolType

used for the symbol part of the ranked symbol

Constructor & Destructor Documentation

CompressedBitParallelTreeIndex()

template<class SymbolType >

indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >::CompressedBitParallelTreeIndex ( ext::set< common::ranked_symbol< SymbolType > >  alphabet, ext::map< common::ranked_symbol< SymbolType >, common::SparseBoolVector >  vectors, ext::vector< int >  jumpTable  )

explicit

Creates a new instance of the index with concrete alphabet, bit vectors, and subtree jump table.

Parameters

alphabet	the alphabet of indexed string
vectors	the compressed bit vectors
jumpTable	the subtree jump table

Member Function Documentation

getAlphabet() [1/2]

template<class SymbolType = DefaultSymbolType>

ext::set< common::ranked_symbol< SymbolType > > && indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >::getAlphabet ( ) &&

inline

Getter of the alphabet of the indexed tree.

Returns

the alphabet of the indexed tree

Here is the call graph for this function:

getAlphabet() [2/2]

template<class SymbolType = DefaultSymbolType>

const ext::set< common::ranked_symbol< SymbolType > > & indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >::getAlphabet ( ) const &

inline

Getter of the alphabet of the indexed tree.

Returns

the alphabet of the indexed tree

Here is the caller graph for this function:

getData() [1/2]

template<class SymbolType = DefaultSymbolType>

ext::map< common::ranked_symbol< SymbolType >, common::SparseBoolVector > && indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >::getData

(

)

&&

Getter of the compressed bit vectors.

Returns

compressed bit vectors

getData() [2/2]

template<class SymbolType = DefaultSymbolType>

const ext::map< common::ranked_symbol< SymbolType >, common::SparseBoolVector > & indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >::getData

(

)

const &

Getter of the compressed bit vectors.

Returns

compressed bit vectors

Here is the caller graph for this function:

getJumps() [1/2]

template<class SymbolType = DefaultSymbolType>

ext::vector< int > && indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >::getJumps

(

)

&&

Getter of the subtree jump table

Returns

the subtree jump table

getJumps() [2/2]

template<class SymbolType = DefaultSymbolType>

const ext::vector< int > & indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >::getJumps

(

)

const &

Getter of the subtree jump table

Returns

the subtree jump table

Here is the caller graph for this function:

getString()

template<class SymbolType >

ext::vector< common::ranked_symbol< SymbolType > > indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >::getString

Reconstructs the indexed string from bit vectors.

Returns

the original indexed string

operator<=>()

template<class SymbolType = DefaultSymbolType>

auto indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >::operator<=> ( const CompressedBitParallelTreeIndex< SymbolType > &  other ) const

inline

The three way comparison implementation

Parameters

other

the other instance

Returns

the ordering between this object and the other.

Here is the call graph for this function:

operator==()

template<class SymbolType = DefaultSymbolType>

bool indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >::operator== ( const CompressedBitParallelTreeIndex< SymbolType > &  other ) const

inline

The equality comparison implementation.

Parameters

other

the other object to compare with.

Returns

true if this and other objects are equal, false othervise

Here is the call graph for this function:

removeSymbolFromAlphabet()

template<class SymbolType = DefaultSymbolType>

bool indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >::removeSymbolFromAlphabet ( const common::ranked_symbol< SymbolType > &  symbol )

inline

Remover of a symbol from the alphabet. The symbol can be removed if it is not used in any of bit vector keys.

Parameters

symbol

a symbol to remove.

setCompressedBitVectorForSymbol()

template<class SymbolType >

void indexes::arbology::CompressedBitParallelTreeIndex< SymbolType >::setCompressedBitVectorForSymbol	(	common::ranked_symbol< SymbolType >	symbol,
		common::SparseBoolVector	data
	)

Changes the bit vector for concrete symbol.

Parameters

symbol	the changed symbol
data	the new bit vector

Friends And Related Function Documentation

operator<<

template<class SymbolType = DefaultSymbolType>

ext::ostream & operator<< ( ext::ostream &  out, const CompressedBitParallelTreeIndex< SymbolType > &  instance  )

friend

Print this object as raw representation to ostream.

Parameters

out	ostream where to print
instance	object to print

Returns

modified output stream

---

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

• alib2data/src/indexes/arbology/CompressedBitParallelTreeIndex.h