#include <EliasFano.hpp>
Public Member Functions | |
| EliasFano (const uint64_t *const bits, const uint64_t num_bits) | |
| EliasFano (const std::vector< uint64_t > ones, const uint64_t num_bits) | |
| uint64_t | rank (const size_t k) |
| size_t | select (const uint64_t rank) |
| uint64_t | select (const uint64_t rank, uint64_t *const next) |
| size_t | size () const |
| uint64_t | bitCount () |
 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 |
Detailed Description
template<util::AllocType AT = util::AllocType::MALLOC>
class sux::bits::EliasFano< AT >
An implementation of selection and ranking based on the Elias-Fano representation of monotone sequences.
Instances of this class can be built using a bit vector or an explicit list of positions for the ones in a vector. In every case, the bit vector or the list are not necessary after construction.
- Template Parameters
-
AT a type of memory allocation out of sux::util::AllocType.
Constructor & Destructor Documentation
◆ EliasFano() [1/2]
|
inline |
Creates a new instance using a given bit vector.
Note that the bit vector is read only at construction time.
- Parameters
-
bits a bit vector of 64-bit words. num_bits the length (in bits) of the bit vector.
◆ EliasFano() [2/2]
|
inline |
Creates a new instance using an explicit list of positions for the ones in a bit vector.
Note that the list is read only at construction time.
In practice this constructor builds an Elias-Fano representation of the given list. select(const uint64_t rank) will retrieve an element of the list, and rank(const size_t pos) will return how many element of the list are smaller than the argument.
- Parameters
-
ones a list of positions of the ones in a bit vector. num_bits the length (in bits) of the bit vector.
Member Function Documentation
◆ bitCount()
|
inline |
Returns an estimate of the size in bits of this structure.
◆ rank()
|
inline |
◆ select() [1/2]
|
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.
◆ select() [2/2]
|
inline |
◆ size()
|
inlinevirtual |
Returns the size in bits of the underlying bit vector.
Implements sux::Rank.
The documentation for this class was generated from the following file:
- sux/bits/EliasFano.hpp
