pixie::RmMBase< Impl > Class Template Reference

CRTP facade for rank/select and range min-max tree operations. More...

#include <rmm_base.h>

Public Member Functions
std::size_t	size () const
	Number of bits in the represented sequence.
std::size_t	rank1 (std::size_t end_position) const
	Count 1 bits in the prefix [0, end_position).
std::size_t	rank0 (std::size_t end_position) const
	Count 0 bits in the prefix [0, end_position).
std::size_t	select1 (std::size_t rank) const
	Return the zero-based position of the rank-th 1 bit.
std::size_t	select0 (std::size_t rank) const
	Return the zero-based position of the rank-th 0 bit.
std::size_t	rank10 (std::size_t end_position) const
	Count "10" bit patterns fully contained in [0, end_position).
std::size_t	select10 (std::size_t rank) const
	Return the zero-based start position of the rank-th "10" pattern.
int	excess (std::size_t end_position) const
	Prefix excess on [0, end_position): +1 for 1 bits, -1 for 0 bits.
std::size_t	fwdsearch (std::size_t start_position, int delta) const
	Forward excess search from a prefix boundary.
std::size_t	bwdsearch (std::size_t start_position, int delta) const
	Backward excess search from a prefix boundary.
std::size_t	range_min_query_pos (std::size_t range_begin, std::size_t range_end) const
	Position of the first minimum relative excess in [range_begin, range_end].
int	range_min_query_val (std::size_t range_begin, std::size_t range_end) const
	Minimum relative excess value over [range_begin, range_end].
std::size_t	range_max_query_pos (std::size_t range_begin, std::size_t range_end) const
	Position of the first maximum relative excess in [range_begin, range_end].
int	range_max_query_val (std::size_t range_begin, std::size_t range_end) const
	Maximum relative excess value over [range_begin, range_end].
std::size_t	mincount (std::size_t range_begin, std::size_t range_end) const
	Count positions attaining the minimum relative excess in [range_begin, range_end].
std::size_t	minselect (std::size_t range_begin, std::size_t range_end, std::size_t rank) const
	Select a position attaining the minimum relative excess in [range_begin, range_end].
std::size_t	close (std::size_t open_position) const
	Matching closing parenthesis for the parenthesis at open_position.
std::size_t	open (std::size_t close_position) const
	Matching opening parenthesis for the parenthesis at close_position.
std::size_t	enclose (std::size_t open_position) const
	Closest opening parenthesis strictly enclosing position.
int	bit (const size_t &position) const noexcept
	Read bit at position position (LSB-first across words).

Static Public Attributes
static constexpr std::size_t	npos = std::numeric_limits<std::size_t>::max()
	Sentinel returned by position queries when no valid answer exists.

Detailed Description

template<class Impl>
class pixie::RmMBase< Impl >

CRTP facade for rank/select and range min-max tree operations.

Positions are zero-based unless explicitly documented otherwise. Operations returning positions use npos when the requested value does not exist or the query is outside the valid domain. Balanced-parentheses navigation follows SDSL-style zero-based parenthesis indexing: close/open/enclose accept and return bit positions, not prefix-boundary positions.

Member Function Documentation

bwdsearch()

template<class Impl>

std::size_t pixie::RmMBase< Impl >::bwdsearch ( std::size_t start_position, int delta ) const

inline

Backward excess search from a prefix boundary.

Finds the greatest prefix boundary p < start_position such that excess(p) == excess(start_position) + delta.

close()

template<class Impl>

std::size_t pixie::RmMBase< Impl >::close ( std::size_t open_position ) const

inline

Matching closing parenthesis for the parenthesis at open_position.

Uses SDSL-style zero-based indexing. If open_position refers to a closing parenthesis, the expected result is open_position.

enclose()

template<class Impl>

std::size_t pixie::RmMBase< Impl >::enclose ( std::size_t open_position ) const

inline

Closest opening parenthesis strictly enclosing position.

Uses SDSL-style zero-based indexing. If position refers to a closing parenthesis, this is equivalent to open(position).

fwdsearch()

template<class Impl>

std::size_t pixie::RmMBase< Impl >::fwdsearch ( std::size_t start_position, int delta ) const

inline

Forward excess search from a prefix boundary.

Finds the first bit position p >= start_position such that excess(p + 1) == excess(start_position) + delta.

minselect()

template<class Impl>

std::size_t pixie::RmMBase< Impl >::minselect ( std::size_t range_begin, std::size_t range_end, std::size_t rank ) const

inline

Select a position attaining the minimum relative excess in [range_begin, range_end].

Parameters

rank	One-based rank among positions attaining the range minimum.

open()

template<class Impl>

std::size_t pixie::RmMBase< Impl >::open ( std::size_t close_position ) const

inline

Matching opening parenthesis for the parenthesis at close_position.

Uses SDSL-style zero-based indexing. If close_position refers to an opening parenthesis, the expected result is close_position.

range_max_query_pos()

template<class Impl>

std::size_t pixie::RmMBase< Impl >::range_max_query_pos ( std::size_t range_begin, std::size_t range_end ) const

inline

Position of the first maximum relative excess in [range_begin, range_end].

Relative excess is accumulated from zero over the inclusive bit range.

range_max_query_val()

template<class Impl>

int pixie::RmMBase< Impl >::range_max_query_val ( std::size_t range_begin, std::size_t range_end ) const

inline

Maximum relative excess value over [range_begin, range_end].

Relative excess is accumulated from zero over the inclusive bit range.

range_min_query_pos()

template<class Impl>

std::size_t pixie::RmMBase< Impl >::range_min_query_pos ( std::size_t range_begin, std::size_t range_end ) const

inline

Position of the first minimum relative excess in [range_begin, range_end].

Relative excess is accumulated from zero over the inclusive bit range.

range_min_query_val()

template<class Impl>

int pixie::RmMBase< Impl >::range_min_query_val ( std::size_t range_begin, std::size_t range_end ) const

inline

Minimum relative excess value over [range_begin, range_end].

Relative excess is accumulated from zero over the inclusive bit range.

rank10()

template<class Impl>

std::size_t pixie::RmMBase< Impl >::rank10 ( std::size_t end_position ) const

inline

Count "10" bit patterns fully contained in [0, end_position).

The returned count is the number of start positions p such that p + 1 < end_position, bit[p] == 1, and bit[p + 1] == 0.

select0()

template<class Impl>

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

inline

Return the zero-based position of the rank-th 0 bit.

Parameters

rank	One-based rank of the requested 0 bit.

select1()

template<class Impl>

std::size_t pixie::RmMBase< Impl >::select1 ( std::size_t rank ) const

inline

Return the zero-based position of the rank-th 1 bit.

Parameters

rank	One-based rank of the requested 1 bit.

select10()

template<class Impl>

std::size_t pixie::RmMBase< Impl >::select10 ( std::size_t rank ) const

inline

Return the zero-based start position of the rank-th "10" pattern.

Parameters

rank	One-based rank of the requested pattern.

---

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

• include/pixie/rmm_base.h