pixie::RankSelectBase< Impl > Class Template Reference

CRTP facade for immutable rank/select queries and bit access. More...

#include <rank_select.h>

Public Member Functions
std::size_t	size () const
	Return the number of valid bits.
bool	empty () const
	Check whether the bit vector is empty.
int	operator[] (std::size_t position) const
	Read a bit by zero-based position.
std::uint64_t	rank (std::size_t end_position) const
	Count one bits in the prefix [0, end_position).
std::uint64_t	rank0 (std::size_t end_position) const
	Count zero bits in the prefix [0, end_position).
std::uint64_t	select (std::size_t rank) const
	Return the position of the rank-th one bit.
std::uint64_t	select0 (std::size_t rank) const
	Return the position of the rank-th zero bit.
bool	supports_select1 () const
	Check whether select queries for one bits are enabled.
bool	supports_select0 () const
	Check whether select queries for zero bits are enabled.
std::size_t	memory_usage_bytes () const
	Return owned index memory usage when provided by the implementation.
std::string	to_string () const
	Convert the logical bits to a binary string.

Detailed Description

template<class Impl>
class pixie::RankSelectBase< Impl >

CRTP facade for immutable rank/select queries and bit access.

Template Parameters

Impl	Concrete type implementing the const *_impl() operations documented on the facade methods. No virtual dispatch is used.

Source representation, ownership, and lifetime are defined by the concrete implementation. Borrowed data must remain alive and immutable while queries use it. Rank counts half-open prefixes; select takes a one-based occurrence rank and returns a zero-based bit position.

See also

<pixie/rank_select/implementations.h> for the available concrete implementations.

Member Function Documentation

empty()

template<class Impl>

bool pixie::RankSelectBase< Impl >::empty ( ) const

inline

Check whether the bit vector is empty.

Returns

true when size() == 0.

memory_usage_bytes()

template<class Impl>

std::size_t pixie::RankSelectBase< Impl >::memory_usage_bytes ( ) const

inline

Return owned index memory usage when provided by the implementation.

Returns

Size of the object and its owned storage in bytes.

The optional Impl::memory_usage_bytes_impl() returns a value convertible to std::size_t. Include owned source copies when present; exclude borrowed storage. This reports allocation size, not resident memory or allocator bookkeeping.

operator[]()

template<class Impl>

int pixie::RankSelectBase< Impl >::operator[] ( std::size_t position ) const

inline

Read a bit by zero-based position.

Parameters

position

Position in [0, size()).

Returns

Zero or one.

Requires Impl::bit_impl(position) to return the logical bit. Positions at or beyond size() violate the precondition; no bounds check is required.

rank()

template<class Impl>

std::uint64_t pixie::RankSelectBase< Impl >::rank ( std::size_t end_position ) const

inline

Count one bits in the prefix [0, end_position).

Parameters

end_position

Prefix boundary, clamped to size().

Returns

Number of one bits in the prefix.

Requires Impl::rank_impl(end_position) to count ones in [0, min(end_position, size())), including zero for an empty prefix.

rank0()

template<class Impl>

std::uint64_t pixie::RankSelectBase< Impl >::rank0 ( std::size_t end_position ) const

inline

Count zero bits in the prefix [0, end_position).

Parameters

end_position

Prefix boundary, clamped to size().

Returns

Number of zero bits in the prefix.

An optional Impl::rank0_impl(end_position) may compute this prefix directly. It must clamp boundaries at or beyond size() to the total zero count. Otherwise the facade derives zeros from one rank.

select()

template<class Impl>

std::uint64_t pixie::RankSelectBase< Impl >::select ( std::size_t rank ) const

inline

Return the position of the rank-th one bit.

Parameters

rank	One-based occurrence rank. Rank zero returns zero.

Returns

Zero-based bit position, or size() if unavailable or absent.

Requires Impl::select_impl(rank) to return zero for rank zero, size() when one-select is disabled or rank exceeds the one population, and otherwise the unique position of that occurrence.

select0()

template<class Impl>

std::uint64_t pixie::RankSelectBase< Impl >::select0 ( std::size_t rank ) const

inline

Return the position of the rank-th zero bit.

Parameters

rank	One-based occurrence rank. Rank zero returns zero.

Returns

Zero-based bit position, or size() if unavailable or absent.

Requires Impl::select0_impl(rank) to return zero for rank zero, size() when zero-select is disabled or rank exceeds the zero population, and otherwise the unique position of that occurrence.

size()

template<class Impl>

std::size_t pixie::RankSelectBase< Impl >::size ( ) const

inline

Return the number of valid bits.

Returns

Logical bit-vector length.

Requires Impl::size_impl() to return the logical length.

supports_select0()

template<class Impl>

bool pixie::RankSelectBase< Impl >::supports_select0 ( ) const

inline

Check whether select queries for zero bits are enabled.

Returns

true when select0() is supported by this instance.

Requires Impl::supports_select0_impl() to report whether this instance enables zero-select, independently of its zero population.

supports_select1()

template<class Impl>

bool pixie::RankSelectBase< Impl >::supports_select1 ( ) const

inline

Check whether select queries for one bits are enabled.

Returns

true when select() is supported by this instance.

Requires Impl::supports_select1_impl() to report whether this instance enables one-select, independently of its one population.

to_string()

template<class Impl>

std::string pixie::RankSelectBase< Impl >::to_string ( ) const

inline

Convert the logical bits to a binary string.

Returns

A string of size() characters containing only 0 and 1.

---

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

• include/pixie/rank_select.h