pixie::rmq::SdslSct< T, Compare, Index > Class Template Reference

Optional value-RMQ adapter over sdsl::rmq_succinct_sct. More...

#include <sdsl_sct.h>

Inheritance diagram for pixie::rmq::SdslSct< T, Compare, Index >:

Public Member Functions
	SdslSct ()=default
	Construct an empty SDSL SCT RMQ adapter.
	SdslSct (std::span< const T > values, Compare compare=Compare())
	Build the SDSL SCT 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	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 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>
class pixie::rmq::SdslSct< T, Compare, Index >

Optional value-RMQ adapter over sdsl::rmq_succinct_sct.

SDSL's SCT implementation builds a global Super-Cartesian-tree balanced-parentheses sequence (BPS-SCT) over the indexed values. It then answers inclusive range queries with balanced-parentheses navigation operations such as select, find_close, rr_enclose, and rank.

SDSL's helper comments attribute the Super-Cartesian-tree BP construction to Ohlebusch and Gog in a compressed enhanced suffix-array context. That is not the canonical RMQ citation. For the succinct RMQ result behind this style of representation, see:

Johannes Fischer, "Optimal Succinctness for Range Minimum Queries", LATIN 2010; arXiv:0812.2775.

This adapter exposes the Pixie value-RMQ interface specification: half-open ranges [left, right), invalid ranges returning npos, and first-minimum tie semantics.

The SDSL structure does not retain values after construction, so this adapter keeps a non-owning span for range_min(). The indexed values must outlive the adapter. SDSL SCT supports min/max through a boolean template parameter, not arbitrary comparators; this wrapper currently exposes only std::less<T>.

Template Parameters

T	Value type in the indexed array.
Compare	Must be std::less<T>.
Index	Interface compatibility parameter for benchmark templates.

Constructor & Destructor Documentation

SdslSct()

template<class T, class Compare = std::less<T>, class Index = std::size_t>

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

inlineexplicit

Build the SDSL SCT index over values.

The values are not copied and must outlive this object. Equal values keep the smaller index as the RMQ answer.

Parameters

values	Values to index.
compare	Must be the default std::less<T> comparator.

Member Function Documentation

arg_min_impl()

template<class T, class Compare = std::less<T>, class Index = std::size_t>

std::size_t pixie::rmq::SdslSct< T, Compare, Index >::arg_min_impl ( std::size_t left, std::size_t right ) const

inline

Return the first minimum position in [left, right).

SDSL's query is inclusive, so the adapter translates the Pixie half-open range to [left, right - 1].

memory_usage_bytes_impl()

template<class T, class Compare = std::less<T>, class Index = std::size_t>

std::size_t pixie::rmq::SdslSct< T, Compare, Index >::memory_usage_bytes_impl ( ) const

inline

Return owned auxiliary memory usage in bytes.

Counts the wrapper object plus SDSL's serialized SCT byte count. 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 pixie::rmq::SdslSct< T, Compare, Index >::npos

staticconstexpr

Initial value:

=
      RmqBase<SdslSct<T, Compare, Index>, T>::npos

---

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

• include/pixie/rmq/sdsl_sct.h