|
|
| HybridBTree ()=default |
| | Construct an empty RMQ index.
|
| |
|
| HybridBTree (const HybridBTree &)=default |
| | Copy an RMQ index while preserving its non-owning value span.
|
| |
|
| HybridBTree (HybridBTree &&) noexcept=default |
| | Move an RMQ index while preserving selector and cache storage.
|
| |
|
HybridBTree & | operator= (const HybridBTree &)=default |
| | Copy-assign an RMQ index and its cached metadata.
|
| |
|
HybridBTree & | operator= (HybridBTree &&) noexcept=default |
| | Move-assign an RMQ index and its cached metadata.
|
| |
| | HybridBTree (std::span< const T > values, Compare compare=Compare()) |
| | Build a hybrid B-tree RMQ index over values.
|
| |
|
std::size_t | size_impl () const |
| | Return the number of indexed values.
|
| |
|
T | value_at_impl (std::size_t position) const |
| | Return the value at an indexed position.
|
| |
| std::size_t | arg_min_impl (std::size_t left, std::size_t right) const |
| | Return the first minimum position in [left, right).
|
| |
|
std::size_t | top_sparse_block_size () const |
| | Return the current top sparse-table block width.
|
| |
|
std::size_t | top_sparse_block_count () const |
| | Return the current number of top sparse-table blocks.
|
| |
| std::size_t | memory_usage_bytes_impl () const |
| | Return owned auxiliary memory usage in bytes.
|
| |
| std::size_t | size () const |
| | Number of indexed values.
|
| |
| bool | empty () const |
| | Whether the indexed array is empty.
|
| |
| std::size_t | arg_min (std::size_t left, std::size_t right) const |
| | Return the first minimum position in [left, right).
|
| |
| Value | range_min (std::size_t left, std::size_t right) const |
| | Return the minimum value in [left, right).
|
| |
| std::size_t | memory_usage_bytes () const |
| | Return owned auxiliary memory usage in bytes when implemented.
|
| |
template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t LeafSize = 496, std::size_t Fanout = 256,
HybridBTreeLeafSelector LeafSelectorKind = HybridBTreeLeafSelector::PrefixSuffix>
class pixie::rmq::HybridBTree< T, Compare, Index, LeafSize, Fanout, LeafSelectorKind >
Hybrid B-tree RMQ with compact per-level selectors.
This is a static, non-owning value-RMQ index over an external value array. Values are split into leaves, leaves are grouped into a B-tree, and each node stores a selector over the minima of its immediate children. Query ranges use the library-wide half-open convention [left, right), invalid ranges return npos, and equal values resolve to the smaller original position.
The default low level uses 496-value prefix/suffix mask leaves. A leaf stores one bit for each prefix/suffix record position plus a 16-bit local-minimum offset in one 64-byte object. Prefix or suffix ranges can be answered from this mask; interior partial ranges fall back to a linear scan of the original values. The same implementation also supports 248-value mask leaves and 252-value BP leaves for controlled experiments.
Internal nodes use 192-way fanout. Their selector is a 512-bit local Cartesian-tree balanced-parentheses encoding over child minima: 384 BP bits, a 64-bit absolute subtree-minimum position, and 64 bits of zero-rank prefix metadata. Node minimum values are cached in a side vector so comparing candidates does not require repeatedly descending to leaves.
Wide queries first try a single coarse sparse table over original-value block minima. The sparse table uses at least 4096-value blocks and grows the block width when needed so the top layer has at most 2^14 blocks. If the padded block-cover candidate lies inside the query, it is returned immediately; on a miss, the sparse table answers the fully covered middle block range and the B-tree handles the two border ranges.
value array, n entries
|
+-- L0: leaves
| ceil(n / 496) nodes by default
| each leaf covers <=496 values and stores one 64-byte selector
|
+-- T: value-block sparse overlay
| block width >=4096 values, at most 2^14 blocks
| stores one original-value minimum position per sparse-table cell
|
+-- L1..Lm: internal levels
| fanout 192
| each node stores one 512-bit BP selector over child minima
Examples with default 496-value leaves:
n = 2^24:
33,826 leaves -> 177 internal nodes -> 1 root
n = 2^26:
135,301 leaves -> 705 internal nodes -> 4 internal nodes -> 1 root
Querying starts at the lowest node that covers both endpoint leaves. At each internal node, the selector is asked for the best child over the intersecting child-slot range. If that child is fully covered, or its stored subtree minimum lies inside the query, that candidate is final for the node. Otherwise only the affected border child is corrected recursively and compared with the middle full-child range. All comparisons use (value, position) semantics so traversal order cannot change tie-breaking.
- Template Parameters
-
| T | Value type in the indexed array. |
| Compare | Strict weak ordering used to choose minima. |
| Index | Unsigned integer type used for stored positions. |
| LeafSize | Number of original values per leaf. This backend currently supports 252 with BP leaves and 248 or 496 with mask leaves. |
| Fanout | Template parameter kept fixed at 256 for the current layout; internal tree nodes use fixed 192-way fanout. |
| LeafSelectorKind | Compile-time low-level selector kind. |
Public Member Functions inherited from pixie::rmq::RmqBase< Impl, Value >
1.13.2