pixie::RmMTree Class Reference

Range min–max tree over a bitvector (LSB-first) tailored for balanced-parentheses (BP). More...

#include <rmm_tree.h>

Inheritance diagram for pixie::RmMTree:

Public Member Functions
	RmMTree ()=default
	Construct empty structure.
	RmMTree (std::span< const std::uint64_t > words, size_t bit_count, const size_t &leaf_block_bits=0, const float &max_overhead=-1.0)
	Build from a non-owning view of 64-bit words (LSB-first).
size_t	size_impl () const
size_t	rank1_impl (const size_t &end_position) const
	Number of ones in prefix [0, end_position).
size_t	rank0_impl (const size_t &end_position) const
	Number of zeros in prefix [0, end_position).
size_t	select1_impl (size_t target_one_rank) const
	1-based select of the target_one_rank-th one.
size_t	select0_impl (size_t target_zero_rank) const
	1-based select of the target_zero_rank-th zero.
size_t	rank10_impl (const size_t &end_position) const
	Rank of the pattern "10" (starts) within [0, end_position).
size_t	select10_impl (size_t target_pattern_rank) const
	1-based select of the target_pattern_rank-th "10" start.
int	excess_impl (const size_t &end_position) const
	Prefix excess on [0, end_position): +1 for '1', −1 for '0'.
size_t	fwdsearch_impl (const size_t &start_position, const int &delta) const
	Forward search: first position p ≥ start_position where excess_impl(p) = excess_impl(start_position) + delta.
size_t	bwdsearch_impl (const size_t &start_position, const int &delta) const
	Backward search: last position p ≤ start_position where excess_impl(p) = excess_impl(start_position) + delta.
size_t	range_min_query_pos_impl (const size_t &range_begin, const size_t &range_end) const
	Position of the first minimum of excess on [range_begin, range_end] (inclusive).
int	range_min_query_val_impl (const size_t &range_begin, const size_t &range_end) const
	Value of the minimum prefix excess on [range_begin, range_end] relative to range_begin.
size_t	range_max_query_pos_impl (const size_t &range_begin, const size_t &range_end) const
	Position of the first maximum of excess on [range_begin, range_end] (inclusive).
int	range_max_query_val_impl (const size_t &range_begin, const size_t &range_end) const
	Value of the maximum prefix excess on [range_begin, range_end] relative to range_begin.
size_t	mincount_impl (const size_t &range_begin, const size_t &range_end) const
	How many times the minimum prefix excess occurs on [range_begin, range_end].
size_t	minselect_impl (const size_t &range_begin, const size_t &range_end, size_t target_min_rank) const
	Position of the target_min_rank-th (1-based) occurrence of the minimum on [range_begin, range_end].
size_t	close_impl (const size_t &open_position) const
	close_impl(open_position): matching ')' for '(' at open_position.
size_t	open_impl (const size_t &close_position) const
	open_impl(close_position): matching '(' for ')' at close_position.
size_t	enclose_impl (const size_t &position) const
	enclose_impl(position): opening '(' that strictly encloses position.
int	bit (const size_t &position) const noexcept
	Read bit at position position (LSB-first across words).
Public Member Functions inherited from pixie::RmMBase< RmMTree >
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 size_t	npos = std::numeric_limits<size_t>::max()
	Sentinel for "not found".
Static Public Attributes inherited from pixie::RmMBase< RmMTree >
static constexpr std::size_t	npos
	Sentinel returned by position queries when no valid answer exists.

Detailed Description

Range min–max tree over a bitvector (LSB-first) tailored for balanced-parentheses (BP).

Implements the classic rmq/rMq family and BP navigation in O(log n) using a perfectly balanced binary tree of blocks. Supported queries:

• rank1 / rank0
• select1 / select0
• rank10 / select10 (starts of "10")
• excess (prefix +1 for '1', −1 for '0')
• fwdsearch / bwdsearch (prefix–sum search)
• range_min_query_pos / range_min_query_val (first minimum within a range)
• range_max_query_pos / range_max_query_val (first maximum within a range)
• mincount / minselect (count/selection of minima)
• close / open / enclose (BP navigation)

The bitvector is LSB-first inside each 64-bit word. RmMTree stores a non-owning view of those words; callers must keep the backing storage alive and immutable for the lifetime of the tree.

Constructor & Destructor Documentation

RmMTree()

pixie::RmMTree::RmMTree ( std::span< const std::uint64_t > words, size_t bit_count, const size_t & leaf_block_bits = 0, const float & max_overhead = -1.0 )

inlineexplicit

Build from a non-owning view of 64-bit words (LSB-first).

Parameters

words	Non-owning view of words holding bits LSB-first.
bit_count	Number of valid bits.
leaf_block_bits	Desired leaf size (power of two, 0 = auto).
max_overhead	Max allowed overhead fraction (<0 to disable constraint).

Block size priority: (1) respect max_overhead, (2) explicit leaf_block_bits, (3) set to ceil_pow2(log2(num_bits)).

The caller must keep words alive and immutable for the lifetime of this tree.

Member Function Documentation

bwdsearch_impl()

size_t pixie::RmMTree::bwdsearch_impl ( const size_t & start_position, const int & delta ) const

inline

Backward search: last position p ≤ start_position where excess_impl(p) = excess_impl(start_position) + delta.

Scans inside the leaf to the left, then climbs to examine left siblings. Returns npos if no such position exists.

close_impl()

size_t pixie::RmMTree::close_impl ( const size_t & open_position ) const

inline

close_impl(open_position): matching ')' for '(' at open_position.

Returns

Position of matching ')', or npos.

enclose_impl()

size_t pixie::RmMTree::enclose_impl ( const size_t & position ) const

inline

enclose_impl(position): opening '(' that strictly encloses position.

Returns

Position of enclosing '(', or npos.

fwdsearch_impl()

size_t pixie::RmMTree::fwdsearch_impl ( const size_t & start_position, const int & delta ) const

inline

Forward search: first position p ≥ start_position where excess_impl(p) = excess_impl(start_position) + delta.

Scans remainder of current leaf, then descends using precomputed bounds. Returns npos if no such position exists.

minselect_impl()

size_t pixie::RmMTree::minselect_impl ( const size_t & range_begin, const size_t & range_end, size_t target_min_rank ) const

inline

Position of the target_min_rank-th (1-based) occurrence of the minimum on [range_begin, range_end].

Returns

Position or npos if target_min_rank exceeds the number of minima.

open_impl()

size_t pixie::RmMTree::open_impl ( const size_t & close_position ) const

inline

open_impl(close_position): matching '(' for ')' at close_position.

Returns

Position of matching '(', or npos.

range_max_query_pos_impl()

size_t pixie::RmMTree::range_max_query_pos_impl ( const size_t & range_begin, const size_t & range_end ) const

inline

Position of the first maximum of excess on [range_begin, range_end] (inclusive).

Returns

Position of first occurrence of maximum, or npos on invalid range.

range_min_query_pos_impl()

size_t pixie::RmMTree::range_min_query_pos_impl ( const size_t & range_begin, const size_t & range_end ) const

inline

Position of the first minimum of excess on [range_begin, range_end] (inclusive).

Returns

Position of first occurrence of minimum, or npos on invalid range.

range_min_query_val_impl()

int pixie::RmMTree::range_min_query_val_impl ( const size_t & range_begin, const size_t & range_end ) const

inline

Value of the minimum prefix excess on [range_begin, range_end] relative to range_begin.

Equivalent to min_{t in [range_begin..range_end]} (excess_impl(t+1) - excess_impl(range_begin)).

rank0_impl()

size_t pixie::RmMTree::rank0_impl ( const size_t & end_position ) const

inline

Number of zeros in prefix [0, end_position).

Computed as end_position - rank1_impl(end_position).

rank10_impl()

size_t pixie::RmMTree::rank10_impl ( const size_t & end_position ) const

inline

Rank of the pattern "10" (starts) within [0, end_position).

Counts p where bit[p]==1 and bit[p+1]==0 with p+1<end_position.

rank1_impl()

size_t pixie::RmMTree::rank1_impl ( const size_t & end_position ) const

inline

Number of ones in prefix [0, end_position).

Returns 0 for end_position == 0.

select0_impl()

size_t pixie::RmMTree::select0_impl ( size_t target_zero_rank ) const

inline

1-based select of the target_zero_rank-th zero.

Returns

Position of target_zero_rank-th '0' or npos if not found.

select10_impl()

size_t pixie::RmMTree::select10_impl ( size_t target_pattern_rank ) const

inline

1-based select of the target_pattern_rank-th "10" start.

Returns

Position p such that bits[p..p+1]=="10", or npos if not found.

select1_impl()

size_t pixie::RmMTree::select1_impl ( size_t target_one_rank ) const

inline

1-based select of the target_one_rank-th one.

Returns

Position of target_one_rank-th '1' or npos if not found.

---

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

• include/pixie/rmm_tree.h