sux::bits::Rank9Sel< AT > Class Template Reference

#include <Rank9Sel.hpp>

Inheritance diagram for sux::bits::Rank9Sel< AT >:

Public Member Functions
	Rank9Sel (const uint64_t *const bits, const uint64_t num_bits)
size_t	select (const uint64_t rank)
size_t	bitCount () const
Public Member Functions inherited from sux::bits::Rank9< AT >
	Rank9 (const uint64_t *const bits, const uint64_t num_bits)
uint64_t	rank (const size_t k)
size_t	bitCount () const
size_t	size () const
Public Member Functions inherited from sux::Rank
virtual	~Rank ()=default
virtual uint64_t	rank (std::size_t pos)=0
uint64_t	rank (std::size_t from, std::size_t to)
virtual uint64_t	rankZero (std::size_t pos)
uint64_t	rankZero (std::size_t from, std::size_t to)
Public Member Functions inherited from sux::Select
virtual	~Select ()=default

Additional Inherited Members
Protected Attributes inherited from sux::bits::Rank9< AT >
const size_t	num_bits
size_t	num_ones
const uint64_t *	bits
util::Vector< uint64_t, AT >	counts

Detailed Description

template<util::AllocType AT = util::AllocType::MALLOC>
class sux::bits::Rank9Sel< AT >

A class implementing a combination of Rank9 for ranking and Select9 for selection. Select9 uses 25%-37.5% additional space (beside the 25% due to Rank9), depending on density, and provides constant-time selection.

The constructors of this class only store a reference to a provided bit vector. Should the content of the bit vector change, the results will be unpredictable.

Warning: if you plan an calling rank(size_t) with argument size(), you must have at least one additional free bit at the end of the provided bit vector.

Constructor & Destructor Documentation

Rank9Sel()

template<util::AllocType AT = util::AllocType::MALLOC>

sux::bits::Rank9Sel< AT >::Rank9Sel ( const uint64_t *const  bits, const uint64_t  num_bits  )

inline

Creates a new instance using a given bit vector.

Note that this constructor only stores a reference to the provided bit vector. Should the content of the bit vector change, the results will be unpredictable.

Warning: if you plan an calling rank(size_t) with argument size(), you must have at least one additional free bit at the end of the provided bit vector.

Parameters

bits	a bit vector of 64-bit words.
num_bits	the length (in bits) of the bit vector.

Member Function Documentation

bitCount()

template<util::AllocType AT = util::AllocType::MALLOC>

size_t sux::bits::Rank9Sel< AT >::bitCount ( ) const

inline

select()

template<util::AllocType AT = util::AllocType::MALLOC>

size_t sux::bits::Rank9Sel< AT >::select ( const uint64_t  rank )

inlinevirtual

Returns the position of the one with given rank.

Parameters

rank	the desired rank (index) of a one in the bit vector.

Returns

the position of the zero with given rank; the result is undefined if no zero of the given rank exists.

Implements sux::Select.

---

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

• sux/bits/Rank9Sel.hpp