|
|
| CartesianHybridBTree ()=default |
| | Construct an empty Cartesian-tree RMQ index.
|
| |
| | CartesianHybridBTree (std::span< const T > values, Compare compare=Compare()) |
| | Build a Cartesian-tree RMQ index over values.
|
| |
| void | serialize_impl (BinaryWriter &writer) const |
| | Serialize the complete owning RMQ metadata.
|
| |
|
| CartesianHybridBTree (const CartesianHybridBTree &other) |
| | Copy an RMQ index and rebuild internal non-owning views.
|
| |
|
CartesianHybridBTree & | operator= (const CartesianHybridBTree &other) |
| | Copy-assign an RMQ index and rebuild internal non-owning views.
|
| |
|
| CartesianHybridBTree (CartesianHybridBTree &&other) noexcept |
| | Move an RMQ index and rebuild internal non-owning views.
|
| |
|
CartesianHybridBTree & | operator= (CartesianHybridBTree &&other) noexcept |
| | Move-assign an RMQ index and rebuild internal non-owning views.
|
| |
|
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 | bp_bit_count () const |
| | Return the number of BP bits in the Cartesian-tree RMQ encoding.
|
| |
|
std::span< const std::uint64_t > | bp_words () const |
| | Return the packed BP words used by the RMQ encoding.
|
| |
|
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.
|
| |
|
void | serialize (BinaryWriter &writer) const |
| | Serialize this value through its concrete implementation.
|
| |
|
| static Self | deserialize_impl (BinaryReader &reader, std::span< const std::int64_t > values, DeserializationValidation validation=DeserializationValidation::kQuick) |
| | Restore owning RMQ metadata over caller-owned values.
|
| |
|
static std::size_t | top_sparse_block_size_for (std::size_t value_count) |
| | Return the top sparse-table block width chosen for a value count.
|
| |
|
static std::size_t | top_sparse_block_count_for (std::size_t value_count) |
| | Return the number of top sparse-table blocks for a value count.
|
| |
template<class... Context>
requires requires(BinaryReader& input, Context&&... arguments) { { Derived::deserialize_impl(input, std::forward<Context>(arguments)...) } -> std::same_as<Derived>; } |
| static Derived | deserialize (BinaryReader &reader, Context &&... context) |
| | Restore exactly Derived and advance reader on success.
|
| |
template<class... Context>
requires requires(BinaryReader& input, Context&&... arguments) { { Derived::deserialize_impl(input, std::forward<Context>(arguments)...) } -> std::same_as<Derived>; } |
| static Derived | deserialize (std::span< const std::byte > &data, Context &&... context) |
| | Restore exactly Derived and advance a mutable byte span.
|
| |
|
|
static constexpr std::size_t | npos = RmqBase<Self, T>::npos |
| |
|
static constexpr Index | invalid_index = std::numeric_limits<Index>::max() |
| |
|
static constexpr std::size_t | kMinTopSparseBlockSize = 4096 |
| |
|
static constexpr std::size_t | kMaxTopSparseBlocks = std::size_t{1} << 14 |
| |
|
static constexpr bool | kUseTopSparseOverlay = UseTopSparseOverlay |
| |
| static constexpr bool | kSerializationSupported |
| |
|
static constexpr std::size_t | npos = std::numeric_limits<std::size_t>::max() |
| | Sentinel returned when no valid query answer exists.
|
| |
template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t LeafSize = 512, bool UseTopSparseOverlay = true>
class pixie::rmq::CartesianHybridBTree< T, Compare, Index, LeafSize, UseTopSparseOverlay >
Cartesian-tree value RMQ using HybridBTree-style LCA.
This class follows the same public value-RMQ specification as the other value RMQ backends. It builds a stable Ferrada-Navarro BP Cartesian-tree encoding, uses RankSelectSupport<> for close-parenthesis rank/select, and delegates the BP-depth minimum query to detail::HybridBTreePlusMinusOne. The BP-depth backend keeps a configurable low-level leaf size, fixed 192-entry middle nodes with embedded minima, and fixed 256-entry high nodes. A single coarse value-level sparse table is checked first; it uses at least 4096-value blocks and grows the block width when needed so the top layer has at most 2^14 blocks. Wide queries whose padded block-cover minimum lies inside the requested range return from this top table without touching the global BP rank/select path. BP construction uses a succinct monotone bit-stack, preserving the same stable Cartesian-tree shape without an n-entry index stack.
This implementation is included from pixie/rmq.h as the compact Cartesian-tree reduction backed by a HybridBTree-shaped ±1 RMQ index.
template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t LeafSize = 512, bool UseTopSparseOverlay = true>
Restore owning RMQ metadata over caller-owned values.
Available only for the exact default CartesianHybridBTree<std::int64_t> specialization. The result retains a non-owning view of values, which must remain alive and immutable. On success, reader advances past exactly one artifact; on failure it is unchanged. validation selects quick structural checks or exact source-derived metadata validation.
- Parameters
-
| reader | Input cursor, advanced only after successful validation. |
| values | Non-owning values retained by the result. |
| validation | Quick structural or full source-derived validation. |
- Exceptions
-
| std::invalid_argument | for malformed, incompatible, truncated, or structurally inconsistent metadata. |
| std::length_error | when an encoded size is not representable. |
template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t LeafSize = 512, bool UseTopSparseOverlay = true>
Return owned auxiliary memory usage in bytes.
Counts this value-RMQ object, packed Cartesian BP words, the top sparse overlay, and nested BP rank/select and ±1 RMQ indexes. The external input values are not owned and are excluded.
template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t LeafSize = 512, bool UseTopSparseOverlay = true>
Serialize the complete owning RMQ metadata.
Available only for the exact default CartesianHybridBTree<std::int64_t> specialization. The external values are not serialized. The artifact is versioned, canonical little-endian, and padded to an eight-byte boundary.
Public Member Functions inherited from pixie::rmq::RmqBase< Impl, Value >
1.13.2