pixie::rmq::detail::RmMPlusMinusOne< Index, HighCacheLines, LowFanout > Class Template Reference

Depth RMQ adapter over the experimental rmM btree. More...

#include <cartesian_rmm.h>

Public Member Functions
	RmMPlusMinusOne (std::span< const std::uint64_t > bits, std::size_t depth_count)
	Build an rmM-backed ±1 RMQ over external packed delta bits.
	RmMPlusMinusOne (std::span< const std::uint64_t > bits, std::size_t depth_count, std::size_t one_count)
	Build with an exact count of +1 delta bits.
void	build (std::span< const std::uint64_t > bits, std::size_t depth_count)
	Rebuild this adapter over external packed delta bits.
void	build (std::span< const std::uint64_t > bits, std::size_t depth_count, std::optional< std::size_t > one_count)
	Rebuild this adapter with an optional exact count of +1 delta bits.
std::size_t	size () const
	Return the number of indexed depth positions.
bool	empty () const
	Whether the indexed depth sequence is empty.
std::size_t	arg_min (std::size_t left, std::size_t right) const
	Return the first minimum depth position in [left, right).
std::size_t	select0 (std::size_t rank) const
	Return the one-based rank-th closing parenthesis position.
std::size_t	rank0 (std::size_t end_position) const
	Count closing parentheses in the prefix [0, end_position).
std::size_t	memory_usage_bytes () const
	Return owned auxiliary memory usage in bytes.

Static Public Attributes
static constexpr std::size_t	npos = std::numeric_limits<std::size_t>::max()
static constexpr Index	invalid_index = std::numeric_limits<Index>::max()
static constexpr std::size_t	kBlockSize

Detailed Description

template<class Index = std::size_t, std::size_t HighCacheLines = 4, std::size_t LowFanout = 32>
class pixie::rmq::detail::RmMPlusMinusOne< Index, HighCacheLines, LowFanout >

Depth RMQ adapter over the experimental rmM btree.

The input words encode adjacent depth deltas: bit 1 means +1 and bit 0 means -1. The indexed depth sequence has depth_count prefix positions, so the bit sequence has depth_count - 1 bits. Queries return the first position of the minimum depth in a half-open depth-position range.

pixie::experimental::RmMBTree::range_min_query_pos() works on inclusive bit ranges and reports extrema after consuming each bit. This adapter adds the missing left prefix boundary comparison, preserving first-minimum ties.

Constructor & Destructor Documentation

RmMPlusMinusOne() [1/2]

template<class Index = std::size_t, std::size_t HighCacheLines = 4, std::size_t LowFanout = 32>

pixie::rmq::detail::RmMPlusMinusOne< Index, HighCacheLines, LowFanout >::RmMPlusMinusOne ( std::span< const std::uint64_t > bits, std::size_t depth_count )

inline

Build an rmM-backed ±1 RMQ over external packed delta bits.

Parameters

bits	Little-endian packed delta bits.
depth_count	Number of indexed depth positions.

Exceptions

std::length_error	if Index cannot represent all positions.
std::invalid_argument	if bits is shorter than required.

RmMPlusMinusOne() [2/2]

template<class Index = std::size_t, std::size_t HighCacheLines = 4, std::size_t LowFanout = 32>

pixie::rmq::detail::RmMPlusMinusOne< Index, HighCacheLines, LowFanout >::RmMPlusMinusOne ( std::span< const std::uint64_t > bits, std::size_t depth_count, std::size_t one_count )

inline

Build with an exact count of +1 delta bits.

Cartesian BP construction knows this count exactly, which lets the nested RankSelectSupport<> allocate select samples without a second scan.

Member Function Documentation

arg_min()

template<class Index = std::size_t, std::size_t HighCacheLines = 4, std::size_t LowFanout = 32>

std::size_t pixie::rmq::detail::RmMPlusMinusOne< Index, HighCacheLines, LowFanout >::arg_min ( std::size_t left, std::size_t right ) const

inline

Return the first minimum depth position in [left, right).

Empty or invalid ranges return npos. Equal minima return the smaller depth position.

memory_usage_bytes()

template<class Index = std::size_t, std::size_t HighCacheLines = 4, std::size_t LowFanout = 32>

std::size_t pixie::rmq::detail::RmMPlusMinusOne< Index, HighCacheLines, LowFanout >::memory_usage_bytes ( ) const

inline

Return owned auxiliary memory usage in bytes.

Counts this ±1 RMQ adapter and the nested rmM support. The external packed BP words are not owned and are excluded.

Member Data Documentation

kBlockSize

template<class Index = std::size_t, std::size_t HighCacheLines = 4, std::size_t LowFanout = 32>

std::size_t pixie::rmq::detail::RmMPlusMinusOne< Index, HighCacheLines, LowFanout >::kBlockSize

staticconstexpr

Initial value:

=
      pixie::experimental::RmMBTree<HighCacheLines, LowFanout>::kBlockBits

---

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

• include/pixie/rmq/cartesian_rmm.h