Template Class BasicEliasFano
Defined in File EliasFano.h
Class Documentation
-
template<bool Lazy>
class BasicEliasFano a non-decreasing sequence of integers in the Elias-Fano representation, the inventories of select of H built in the constructor if not Lazy and at the first select of each value if Lazy [see RankSelect.h]
Public Types
-
using value_type = std::uint64_t
-
using size_type = std::size_t
-
using difference_type = std::ptrdiff_t
-
using reference = std::uint64_t
-
using const_reference = std::uint64_t
-
using const_iterator = SubscriptIterator<BasicEliasFano, std::uint64_t>
-
using iterator = const_iterator
Public Functions
-
BasicEliasFano(void) = default
-
explicit BasicEliasFano(const std::vector<std::uint64_t> &x)
the sequence x in the universe [ 0 , x.back() + 1 )
- Pre:
x is non-decreasing (an audit) and x.back() < 2^64 - 1, so that the universe fits in 64 bits
-
BasicEliasFano(const std::vector<std::uint64_t> &x, std::uint64_t u)
the sequence x in the universe [ 0 , u )
- Pre:
x is non-decreasing (an audit) and its items are below u
-
std::size_t size(void) const
-
bool empty(void) const
-
std::uint64_t universe(void) const
the bound u of the items
-
std::size_t nextGEQ(std::uint64_t x) const
the place of the first item >= x, size() if there is none; the number of items < x
- Post:
the items before it are < x, the one at it is >= x
-
bool contains(std::uint64_t x) const
whether x is an item
-
int lowWidth(void) const
the number of low bits of each item, ell
-
const BasicRankSelect<Lazy> &high(void) const
the high bits, H, with their directory
-
std::size_t codeBits(void) const
the bits of L and H, without the directory of H
-
std::size_t sizeInBits(void) const
all the bits, with the directory of H
-
std::vector<std::uint64_t> decode(void) const
the items, decoded in O( n ) time
-
inline const_iterator begin(void) const
-
inline const_iterator end(void) const
-
inline const_iterator cbegin(void) const
-
inline const_iterator cend(void) const
-
using value_type = std::uint64_t