pixie::rmq::detail::HybridBTreePlusMinusOne< Index, LeafSize, UseHighSparseLayout, HighSparseLayoutLevels > Class Template Reference

HybridBTree-style RMQ backend for ±1 depth sequences. More...

#include <cartesian_hybrid_btree.h>

Public Member Functions
	HybridBTreePlusMinusOne ()=default
	Construct an empty ±1 RMQ index.
	HybridBTreePlusMinusOne (std::span< const std::uint64_t > bits, std::size_t depth_count)
	Build a ±1 RMQ index over external packed delta bits.
	HybridBTreePlusMinusOne (std::span< const std::uint64_t > bits, std::size_t depth_count, const RankSelectSupport<> &rank_index)
	Build a ±1 RMQ index over external packed bits and rank support.
void	build (std::span< const std::uint64_t > bits, std::size_t depth_count)
	Rebuild this index over external packed delta bits.
void	build (std::span< const std::uint64_t > bits, std::size_t depth_count, const RankSelectSupport<> &rank_index)
	Rebuild this index using non-owning rank support for the same 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	memory_usage_bytes () const
	Return owned auxiliary memory usage in bytes.
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 zero delta bit position.

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	kLeafSize = LeafSize
static constexpr std::size_t	kHighLevelFanout = 256
static constexpr std::size_t	kMiddleFanout = 192
static constexpr bool	kUseHighSparseLayout = UseHighSparseLayout
static constexpr std::size_t	kHighSparseLayoutLevels = HighSparseLayoutLevels

Friends
template<class, class, class, std::size_t, bool>
class	::pixie::rmq::CartesianHybridBTree

Detailed Description

template<class Index = std::size_t, std::size_t LeafSize = 512, bool UseHighSparseLayout = true, std::size_t HighSparseLayoutLevels = 2>
class pixie::rmq::detail::HybridBTreePlusMinusOne< Index, LeafSize, UseHighSparseLayout, HighSparseLayoutLevels >

HybridBTree-style RMQ backend for ±1 depth sequences.

The input words encode adjacent depth deltas: bit 1 means +1 and bit 0 means -1. The indexed sequence has depth_count prefix positions, so the bit sequence has depth_count - 1 deltas. Public ranges are half-open over depth positions, and ties return the smaller depth position.

This backend mirrors the high-level query shape of HybridBTree: depth positions are split into configurable-size leaves, leaves are grouped into a B-tree, and every internal node stores a local Cartesian/BP selector over the minima of its immediate children. Middle levels are fixed at 192 child slots: their selector uses 384 BP bits and reserves the remaining 128 bits for the embedded subtree minimum position/depth. A configurable number of top levels additionally keep sparse tables over child-minimum slots. Unlike value HybridBTree, leaves do not store another local Cartesian selector or cached minima. Leaf minima are recomputed from the original BP delta bits with the 128-bit excess primitives from bits.h, using rank support to recover the absolute base depth at the leaf start.

Template Parameters

Index	Unsigned integer type used for stored positions.
LeafSize	Number of depth positions per low-level leaf; must be a multiple of 512.
UseHighSparseLayout	Whether top levels use sparse tables instead of local BP selectors.
HighSparseLayoutLevels	Number of top tree levels using that sparse layout when enabled.

Constructor & Destructor Documentation

HybridBTreePlusMinusOne() [1/2]

template<class Index = std::size_t, std::size_t LeafSize = 512, bool UseHighSparseLayout = true, std::size_t HighSparseLayoutLevels = 2>

pixie::rmq::detail::HybridBTreePlusMinusOne< Index, LeafSize, UseHighSparseLayout, HighSparseLayoutLevels >::HybridBTreePlusMinusOne ( std::span< const std::uint64_t > bits, std::size_t depth_count )

inline

Build a ±1 RMQ index 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.

HybridBTreePlusMinusOne() [2/2]

template<class Index = std::size_t, std::size_t LeafSize = 512, bool UseHighSparseLayout = true, std::size_t HighSparseLayoutLevels = 2>

pixie::rmq::detail::HybridBTreePlusMinusOne< Index, LeafSize, UseHighSparseLayout, HighSparseLayoutLevels >::HybridBTreePlusMinusOne ( std::span< const std::uint64_t > bits, std::size_t depth_count, const RankSelectSupport<> & rank_index )

inline

Build a ±1 RMQ index over external packed bits and rank support.

The supplied rank index is non-owning and must outlive this RMQ object. This is used by CartesianHybridBTree to reuse its BP rank/select index.

Member Function Documentation

arg_min()

template<class Index = std::size_t, std::size_t LeafSize = 512, bool UseHighSparseLayout = true, std::size_t HighSparseLayoutLevels = 2>

std::size_t pixie::rmq::detail::HybridBTreePlusMinusOne< Index, LeafSize, UseHighSparseLayout, HighSparseLayoutLevels >::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 depths return the smaller position.

memory_usage_bytes()

template<class Index = std::size_t, std::size_t LeafSize = 512, bool UseHighSparseLayout = true, std::size_t HighSparseLayoutLevels = 2>

std::size_t pixie::rmq::detail::HybridBTreePlusMinusOne< Index, LeafSize, UseHighSparseLayout, HighSparseLayoutLevels >::memory_usage_bytes ( ) const

inline

Return owned auxiliary memory usage in bytes.

Counts this ±1 RMQ object and all selector/metadata buffers. The external packed delta bits are not owned and are excluded.

select0()

template<class Index = std::size_t, std::size_t LeafSize = 512, bool UseHighSparseLayout = true, std::size_t HighSparseLayoutLevels = 2>

std::size_t pixie::rmq::detail::HybridBTreePlusMinusOne< Index, LeafSize, UseHighSparseLayout, HighSparseLayoutLevels >::select0 ( std::size_t rank ) const

inline

Return the one-based rank-th zero delta bit position.

This is the select operation needed by the Cartesian wrapper to map value endpoints to close-parenthesis positions. The returned position is a delta-bit position in [0, size() - 1), or npos when rank is out of range.

---

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

• include/pixie/rmq/cartesian_hybrid_btree.h