pixie::rmq::CartesianRmM< T, Compare, Index, HighCacheLines, LowFanout > Class Template Reference

Ferrada-Navarro Cartesian-tree RMQ using rmM support. More...

#include <cartesian_rmm.h>

Inheritance diagram for pixie::rmq::CartesianRmM< T, Compare, Index, HighCacheLines, LowFanout >:

Public Member Functions
	CartesianRmM (std::span< const T > values, Compare compare=Compare())
	Build a Cartesian-tree RMQ index over values.
	CartesianRmM (const CartesianRmM &other)
CartesianRmM &	operator= (const CartesianRmM &other)
	CartesianRmM (CartesianRmM &&other) noexcept
CartesianRmM &	operator= (CartesianRmM &&other) noexcept
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	memory_usage_bytes_impl () const
	Return owned auxiliary memory usage in bytes.
Public Member Functions inherited from pixie::rmq::RmqBase< Impl, Value >
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.

Static Public Attributes
static constexpr std::size_t	npos
static constexpr Index	invalid_index = std::numeric_limits<Index>::max()
Static Public Attributes inherited from pixie::rmq::RmqBase< Impl, Value >
static constexpr std::size_t	npos = std::numeric_limits<std::size_t>::max()
	Sentinel returned when no valid query answer exists.

Detailed Description

template<class T, class Compare = std::less<T>, class Index = std::size_t, std::size_t HighCacheLines = 4, std::size_t LowFanout = 32>
class pixie::rmq::CartesianRmM< T, Compare, Index, HighCacheLines, LowFanout >

Ferrada-Navarro Cartesian-tree RMQ using rmM support.

This class follows the same public value-RMQ specification as the other value RMQ backends, but replaces the usual balanced-parentheses rank/select and depth-RMQ support with detail::RmMPlusMinusOne, which in turn uses the experimental range min-max btree over the BP excess sequence. 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 rmM-backed Cartesian-tree reduction.

Constructor & Destructor Documentation

CartesianRmM()

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

pixie::rmq::CartesianRmM< T, Compare, Index, HighCacheLines, LowFanout >::CartesianRmM ( std::span< const T > values, Compare compare = Compare() )

inlineexplicit

Build a Cartesian-tree RMQ index over values.

The values are not copied and must outlive this object. Equal values stay stable: the smaller index remains the first minimum.

Member Function Documentation

memory_usage_bytes_impl()

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

std::size_t pixie::rmq::CartesianRmM< T, Compare, Index, HighCacheLines, LowFanout >::memory_usage_bytes_impl ( ) const

inline

Return owned auxiliary memory usage in bytes.

Counts this value-RMQ object, packed Cartesian BP words, and nested BP rmM support. The external input values are not owned and are excluded.

Member Data Documentation

npos

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

std::size_t pixie::rmq::CartesianRmM< T, Compare, Index, HighCacheLines, LowFanout >::npos

staticconstexpr

Initial value:

=
      RmqBase<CartesianRmM<T, Compare, Index, HighCacheLines, LowFanout>,
              T>::npos

---

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

• include/pixie/rmq/cartesian_rmm.h