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

#include <rmm_tree.h>

Public Member Functions
	RmMTree ()=default
	Construct empty structure.

	RmMTree (const std::string &bit_string, const size_t &leaf_block_bits=0, const float &max_overhead=-1.0)
	Build from a '0'/'1' string.

	RmMTree (const std::vector< std::uint64_t > &words, size_t bit_count, const size_t &leaf_block_bits=0, const float &max_overhead=-1.0)
	Build from 64-bit words (LSB-first).

size_t	rank1 (const size_t &end_position) const
	Number of ones in prefix [0, `end_position`).

size_t	rank0 (const size_t &end_position) const
	Number of zeros in prefix [0, `end_position`).

size_t	select1 (size_t target_one_rank) const
	1-based select of the `target_one_rank-th` one.

size_t	select0 (size_t target_zero_rank) const
	1-based select of the `target_zero_rank-th` zero.

size_t	rank10 (const size_t &end_position) const
	Rank of the pattern "10" (starts) within [0, `end_position`).

size_t	select10 (size_t target_pattern_rank) const
	1-based select of the `target_pattern_rank-th` "10" start.

int	excess (const size_t &end_position) const
	Prefix excess on [0, `end_position`): +1 for '1', −1 for '0'.

size_t	fwdsearch (const size_t &start_position, const int &delta) const
	Forward search: first position p ≥ `start_position` where excess(p) = excess(`start_position`) + `delta`.

size_t	bwdsearch (const size_t &start_position, const int &delta) const
	Backward search: last position p ≤ `start_position` where excess(p) = excess(`start_position`) + `delta`.

size_t	range_min_query_pos (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 (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 (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 (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 (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 (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 (const size_t &open_position) const
	close(`open_position`): matching ')' for '(' at `open_position`.

size_t	open (const size_t &close_position) const
	open(`close_position`): matching '(' for ')' at `close_position`.

size_t	enclose (const size_t &position) const
	enclose(`position`): opening '(' that strictly encloses `position`.

Static Public Attributes
static constexpr size_t	npos = std::numeric_limits<size_t>::max()
	Sentinel for "not found".

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.

Constructor & Destructor Documentation

◆ RmMTree() [1/2]

pixie::RmMTree::RmMTree	(	const std::string &	bit_string,
		const size_t &	leaf_block_bits = 0,
		const float &	max_overhead = -1.0 )

inlineexplicit

Build from a '0'/'1' string.

Parameters

bit_string	Bitstring (characters '0' and '1').
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)).

◆ RmMTree() [2/2]

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

inlineexplicit

Build from 64-bit words (LSB-first).

Parameters

words	Array 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)).

Member Function Documentation

◆ bwdsearch()

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

inline

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

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

◆ close()

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

inline

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

Returns: Position of matching ')', or npos.

◆ enclose()

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

inline

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

Returns: Position of enclosing '(', or npos.

◆ fwdsearch()

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

inline

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

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

◆ minselect()

size_t pixie::RmMTree::minselect	(	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()

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

inline

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

Returns: Position of matching '(', or npos.

◆ range_max_query_pos()

size_t pixie::RmMTree::range_max_query_pos	(	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()

size_t pixie::RmMTree::range_min_query_pos	(	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()

int pixie::RmMTree::range_min_query_val	(	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(t+1) - excess(range_begin)).

◆ rank0()

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

inline

Number of zeros in prefix [0, end_position).

Computed as end_position - rank1(end_position).

◆ rank1()

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

inline

Number of ones in prefix [0, end_position).

Returns 0 for end_position == 0.

◆ rank10()

size_t pixie::RmMTree::rank10 ( 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.

◆ select0()

size_t pixie::RmMTree::select0 ( 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.

◆ select1()

size_t pixie::RmMTree::select1 ( 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.

◆ select10()

size_t pixie::RmMTree::select10 ( 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.

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

include/pixie/rmm_tree.h

Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ RmMTree() [1/2]

◆ RmMTree() [2/2]

Member Function Documentation

◆ bwdsearch()

◆ close()

◆ enclose()

◆ fwdsearch()

◆ minselect()

◆ open()

◆ range_max_query_pos()

◆ range_min_query_pos()

◆ range_min_query_val()

◆ rank0()

◆ rank1()

◆ rank10()

◆ select0()

◆ select1()

◆ select10()