A rank structure proposed by Christopher Pockrandt. More...

#include <rank_support_int_v.hpp>

Inheritance diagram for sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >:

Classes
struct	superblock_entry
	Stores a superblock entry in a cache friendly pattern. More...

Public Types
typedef int_vector ::size_type	size_type

typedef int_vector ::value_type	value_type

Public Types inherited from sdsl::rank_support_int< alphabet_size >
typedef int_vector ::size_type	size_type

typedef int_vector ::value_type	value_type

Public Member Functions
	rank_support_int_v (const int_vector<> *text_ptr=nullptr)
	Constructs and initialises the rank support structure for the given text.

	rank_support_int_v (const rank_support_int_v &)=default
	Defaulted copy constructor.

	rank_support_int_v (rank_support_int_v &&)=default
	Defaulted move constructor.

rank_support_int_v &	operator= (const rank_support_int_v &)=default
	Defaulted copy assignment.

rank_support_int_v &	operator= (rank_support_int_v &&)=default
	Defaulted move assignment.

	~rank_support_int_v ()=default
	Defaulted destructor.

size_type	rank (const size_type position, const value_type v) const
	Counts the occurrences of v in the prefix [0..idx-1].

size_type	operator() (const size_type position, const value_type v) const
	Alias for rank(position, v)

size_type	prefix_rank (const size_type position, const value_type v) const
	Counts the occurrences of elements smaller or equal to v in the prefix [0..idx-1].

size_type	size () const
	Returns the size of the original text.

value_type	value_at (const size_type position) const
	Returns the text value at the given position.

size_type	serialize (std::ostream &out, structure_tree_node *v=nullptr, const std::string name="") const
	Saves to the stream.

void	load (std::istream &in, const int_vector<> *)
	Loads from the stream.

template<typename archive_t >
void	CEREAL_SAVE_FUNCTION_NAME (archive_t &ar) const
	Saves to the archive.

template<typename archive_t >
void	CEREAL_LOAD_FUNCTION_NAME (archive_t &ar)
	Loads from the archive.

void	set_vector (const int_vector<> *)
	Does nothing for the rank_support_int structure.

Public Member Functions inherited from sdsl::rank_support_int< alphabet_size >
	rank_support_int (const int_vector<> *v=nullptr)
	Constructor.

	rank_support_int (const rank_support_int &)=default
	Copy constructor.

	rank_support_int (rank_support_int &&)=default

rank_support_int &	operator= (const rank_support_int &)=default

rank_support_int &	operator= (rank_support_int &&)=default

virtual	~rank_support_int ()
	Destructor.

virtual size_type	rank (const size_type i, const value_type v) const =0
	Answers rank queries for the supported int_vector.

virtual size_type	operator() (const size_type idx, const value_type v) const =0
	Alias for rank(idx, v)

virtual size_type	prefix_rank (const size_type i, const value_type v) const =0
	Answers rank queries for the supported int_vector.

virtual size_type	serialize (std::ostream &out, structure_tree_node *v, const std::string name) const =0
	Serializes rank_support_int.

virtual void	load (std::istream &in, const int_vector<> *v=nullptr)=0
	Loads the rank_support_int.

virtual void	set_vector (const int_vector<> *v=nullptr)=0
	Sets the supported int_vector to the given pointer.

Friends
bool	operator== (rank_support_int_v const &lhs, rank_support_int_v const &rhs) noexcept
	Equality operator.

bool	operator!= (rank_support_int_v const &lhs, rank_support_int_v const &rhs) noexcept
	Inequality operator.

Additional Inherited Members
Static Protected Member Functions inherited from sdsl::rank_support_int< alphabet_size >
template<typename uintX_t >
static constexpr uintX_t	bm_rec (const uintX_t w, const uint8_t length, const uint8_t max_length)
	Constructs a bit mask with the pattern w of a given length.

static std::array< uint64_t, alphabet_size >	generate_mask_array ()

static constexpr uint64_t	mask_prefix (value_type const v, uint64_t const w_even, uint64_t const w_odd) noexcept
	Mask the set prefix positions.

static constexpr uint64_t	set_positions_prefix (const uint64_t w, const value_type v) noexcept
	Count how often value v or smaller occurs in the word w.

static constexpr uint64_t	set_positions (const uint64_t w, const value_type v) noexcept
	Count how often value v occurs in the word w.

template<typename... value_t>
static constexpr std::array< uint64_t, sizeof...(value_t)>	word_prefix_rank (const uint64_t word, const size_type bit_pos, const value_t... values) noexcept
	Counts the occurrences of elements smaller or equal to v in the word starting at data up to position idx.

static constexpr uint32_t	word_rank (const uint64_t word, const size_type bit_pos, const value_type v) noexcept
	Counts the occurrences of elements smaller or equal to v in the word starting at data up to position idx.

static constexpr uint32_t	full_word_prefix_rank (const uint64_t word, const value_type v) noexcept
	Counts the occurrences of v in the word starting at data up to position idx.

static constexpr uint32_t	full_word_rank (const uint64_t word, const value_type v) noexcept
	Counts the occurrences of v in the word starting at data up to position idx.

static constexpr uint64_t	extract_word (const uint64_t *data, const size_type word_position) noexcept
	Returns the word a the given word position.

Protected Attributes inherited from sdsl::rank_support_int< alphabet_size >
const int_vector *	m_v
	Pointer to the rank supported bit_vector.

Static Protected Attributes inherited from sdsl::rank_support_int< alphabet_size >
static constexpr uint8_t	sigma { alphabet_size }

static constexpr uint8_t	sigma_bits { ceil_log2(alphabet_size) }

static constexpr uint8_t	bits_per_word { (64 / sigma_bits) * sigma_bits }

static constexpr uint64_t	even_mask { bm_rec<uint64_t>(bits::lo_set[sigma_bits], sigma_bits * 2, 64) }

static constexpr uint64_t	carry_select_mask { bm_rec<uint64_t>(1ULL << sigma_bits, sigma_bits * 2, 64) }

static const std::array< uint64_t, alphabet_size >	masks = generate_mask_array()

Detailed Description

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>
class sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >

A rank structure proposed by Christopher Pockrandt.

This data structure is similar to rank data structures on bit vectors. It supports constant time rank and prefix_rank queries on int vectors.

Template Parameters

alphabet_size	Size of the alphabet represented in the int_vector, i.e., largest value + 1.
words_per_block	Words per block (equivalent to the number of popcount operations in the worst-case per rank query).
blocks_per_superblock	Blocks per superblock.

Reference: Christopher Pockrandt: EPR-Dictionaries: A practical and fast data structure for constant time searches in unidirectional and bidirectional FM-indices. WEA 2008: 154-168

Definition at line 156 of file rank_support_int_v.hpp.

Member Typedef Documentation

◆ size_type

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

typedef int_vector ::size_type sdsl::rank_support_int< alphabet_size >::size_type

Definition at line 42 of file rank_support_int.hpp.

◆ value_type

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

typedef int_vector ::value_type sdsl::rank_support_int< alphabet_size >::value_type

Definition at line 43 of file rank_support_int.hpp.

Constructor & Destructor Documentation

◆ rank_support_int_v() [1/3]

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::rank_support_int_v ( const int_vector<> * text_ptr = nullptr )

inlineexplicit

Constructs and initialises the rank support structure for the given text.

Parameters

[in] text_ptr The pointer to the text to build the rank support for.

The text will be copied into the superblock structure to utilise better cache locality when computing the prefix rank for a given symbol and prefix length. Accordingly, the pointer to the text of the base class will always be a nullptr.

Definition at line 200 of file rank_support_int_v.hpp.

◆ rank_support_int_v() [2/3]

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::rank_support_int_v ( const rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > & )

default

Defaulted copy constructor.

◆ rank_support_int_v() [3/3]

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::rank_support_int_v ( rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > && )

default

Defaulted move constructor.

◆ ~rank_support_int_v()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::~rank_support_int_v ( )

default

Defaulted destructor.

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

template<typename archive_t >

void sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::CEREAL_LOAD_FUNCTION_NAME ( archive_t & ar )

inline

Loads from the archive.

Definition at line 388 of file rank_support_int_v.hpp.

◆ CEREAL_SAVE_FUNCTION_NAME()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

template<typename archive_t >

void sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::CEREAL_SAVE_FUNCTION_NAME ( archive_t & ar ) const

inline

Saves to the archive.

Definition at line 380 of file rank_support_int_v.hpp.

◆ load()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

void sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::load	(	std::istream &	in,
		const int_vector<> *
	)

inlinevirtual

Loads from the stream.

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 359 of file rank_support_int_v.hpp.

◆ operator()()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::operator()	(	const size_type	position,
		const value_type	v
	)		const

inlinevirtual

Alias for rank(position, v)

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 304 of file rank_support_int_v.hpp.

◆ operator=() [1/2]

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

rank_support_int_v & sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::operator= ( const rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > & )

default

Defaulted copy assignment.

◆ operator=() [2/2]

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

rank_support_int_v & sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::operator= ( rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > && )

default

Defaulted move assignment.

◆ prefix_rank()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::prefix_rank	(	const size_type	position,
		const value_type	v
	)		const

inlinevirtual

Counts the occurrences of elements smaller or equal to v in the prefix [0..idx-1].

Parameters

position	The position of the symbol to get the prefix rank for (corresponds to length of the prefix: `[0..position - 1]`).
v	The alphabet symbol to get the rank for.

See also: rank

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 312 of file rank_support_int_v.hpp.

◆ rank()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::rank	(	const size_type	position,
		const value_type	v
	)		const

inlinevirtual

Counts the occurrences of v in the prefix [0..idx-1].

Parameters

position	The position of the symbol to get the prefix rank for (corresponds to length of the prefix: `[0..position - 1]`).
v	The alphabet symbol to get the rank for.

See also: prefix_rank

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 293 of file rank_support_int_v.hpp.

◆ serialize()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::serialize	(	std::ostream &	out,
		structure_tree_node *	v = `nullptr`,
		const std::string	name = `""`
	)		const

inlinevirtual

Saves to the stream.

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 349 of file rank_support_int_v.hpp.

◆ set_vector()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

void sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::set_vector ( const int_vector<> * )

inlinevirtual

Does nothing for the rank_support_int structure.

Implements sdsl::rank_support_int< alphabet_size >.

Definition at line 395 of file rank_support_int_v.hpp.

◆ size()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

size_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::size ( ) const

inline

Returns the size of the original text.

Definition at line 337 of file rank_support_int_v.hpp.

◆ value_at()

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

value_type sdsl::rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock >::value_at ( const size_type position ) const

inline

Returns the text value at the given position.

Parameters

[in] position The text position to get the value from.

Definition at line 342 of file rank_support_int_v.hpp.

Friends And Related Function Documentation

◆ operator!=

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

bool operator!=	(	rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > const &	lhs,
		rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > const &	rhs
	)

friend

Inequality operator.

Definition at line 373 of file rank_support_int_v.hpp.

◆ operator==

template<uint8_t alphabet_size, uint8_t words_per_block = 1, uint8_t blocks_per_superblock = 4>

bool operator==	(	rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > const &	lhs,
		rank_support_int_v< alphabet_size, words_per_block, blocks_per_superblock > const &	rhs
	)

friend

Equality operator.

Definition at line 367 of file rank_support_int_v.hpp.

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

/builddir/build/BUILD/sdsl-lite-3.0.1/include/sdsl/rank_support_int_v.hpp

Classes

Public Types

Public Member Functions

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ size_type

◆ value_type

Constructor & Destructor Documentation

◆ rank_support_int_v() [1/3]

◆ rank_support_int_v() [2/3]

◆ rank_support_int_v() [3/3]

◆ ~rank_support_int_v()

Member Function Documentation

◆ CEREAL_LOAD_FUNCTION_NAME()

◆ CEREAL_SAVE_FUNCTION_NAME()

◆ load()

◆ operator()()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ prefix_rank()

◆ rank()

◆ serialize()

◆ set_vector()

◆ size()

◆ value_at()

Friends And Related Function Documentation

◆ operator!=

◆ operator==