pixie::rmq::RmqBase< Impl, Value > Class Template Reference

CRTP facade for static range-minimum-query indexes. More...

#include <rmq.h>

Inheritance diagram for pixie::rmq::RmqBase< Impl, Value >:

Public Member Functions
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 = std::numeric_limits<std::size_t>::max()
	Sentinel returned when no valid query answer exists.

Detailed Description

template<class Impl, class Value>
class pixie::rmq::RmqBase< Impl, Value >

CRTP facade for static range-minimum-query indexes.

Implementations are non-owning indexes over an external random-access array. Queries use half-open zero-based ranges [left, right) and return the first position attaining the minimum. Invalid or empty ranges return npos.

See also

<pixie/rmq/implementations.h> for the complete implementation catalog and current benchmark comparison.

Member Function Documentation

arg_min()

template<class Impl, class Value>

std::size_t pixie::rmq::RmqBase< Impl, Value >::arg_min ( std::size_t left, std::size_t right ) const

inline

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

The query range is half-open. Ties are resolved by returning the smallest position attaining the minimum. Invalid or empty ranges return npos.

Parameters

left	First position in the query range.
right	One past the last position in the query range.

Returns

Zero-based position of the first range minimum, or npos.

empty()

template<class Impl, class Value>

bool pixie::rmq::RmqBase< Impl, Value >::empty ( ) const

inline

Whether the indexed array is empty.

Returns

true when size() == 0.

memory_usage_bytes()

template<class Impl, class Value>

std::size_t pixie::rmq::RmqBase< Impl, Value >::memory_usage_bytes ( ) const

inline

Return owned auxiliary memory usage in bytes when implemented.

Implementations opt in by exposing memory_usage_bytes_impl() const. The reported value should include the index object itself and heap buffers owned by the index, but not the external value array indexed by the RMQ.

range_min()

template<class Impl, class Value>

Value pixie::rmq::RmqBase< Impl, Value >::range_min ( std::size_t left, std::size_t right ) const

inline

Return the minimum value in [left, right).

Invalid or empty ranges return a default-constructed value.

Parameters

left	First position in the query range.
right	One past the last position in the query range.

Returns

The minimum value in the half-open range, or Value{}.

size()

template<class Impl, class Value>

std::size_t pixie::rmq::RmqBase< Impl, Value >::size ( ) const

inline

Number of indexed values.

Returns

The number of values covered by the underlying RMQ index.

---

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

• include/pixie/rmq.h