 |
Pixie
|
|
Pixie
|
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. | |
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.
| 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. |
|
inline |
Build a ±1 RMQ index over external packed delta bits.
| bits | Little-endian packed delta bits. |
| depth_count | Number of indexed depth positions. |
| std::length_error | if Index cannot represent all positions. |
| std::invalid_argument | if bits is shorter than required. |
|
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.
|
inline |
Return the first minimum depth position in [left, right).
Empty or invalid ranges return npos. Equal depths return the smaller position.
|
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.
|
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.
1.13.2