RangeMinimumQuery Class Reference

#include <genesis/utils/math/range_minimum_query.hpp>

Detailed Description

Class that allows to efficiently find the index of the minimum element within an interval of an array of integer values.

The implementation is based on the Succinct RMQ implementation (https://www.bio.ifi.lmu.de/forschung/succinct/#software) by Johannes Fischer, with the author's explicit permission to use this code here. See also Acknowledgements. Most of the original implementation is used as-is.

We added some convenience by introducing the ability to use data with only a few elements. The original code expected input data with > 100 elements. Furthermore, we adapted the code to C++11, by replacing manually allocated data (new ...) with std::vector and utils::Matrix, and by replacing C-style casts with proper C++-casts. The functions, variables and typedefs were renamed and the code reformatted in order to fit our code guidelines.

Definition at line 61 of file range_minimum_query.hpp.

Public Member Functions
	RangeMinimumQuery ()=default
	RangeMinimumQuery (RangeMinimumQuery &&)=default
	RangeMinimumQuery (RangeMinimumQuery const &)=default
	RangeMinimumQuery (std::vector< IntType > &&array)
	Constructor that takes a vector of integer values by moving it. More...
	RangeMinimumQuery (std::vector< IntType > const &array)
	Constructor that takes a vector of integer values by copying it. More...
	~RangeMinimumQuery ()=default
RangeMinimumQuery &	operator= (RangeMinimumQuery &&)=default
RangeMinimumQuery &	operator= (RangeMinimumQuery const &)=default
size_t	query (size_t i, size_t j) const
	Main function for the Range Minimum Query. More...

Public Types
using	BlockTypeType = unsigned short
using	IntType = int32_t
	Data type of the array for which we want to run RMQ queries. More...
using	SuccinctType = unsigned char

Constructor & Destructor Documentation

RangeMinimumQuery() [1/5]

RangeMinimumQuery ( )

default

RangeMinimumQuery() [2/5]

RangeMinimumQuery ( std::vector< IntType > const &  array )

explicit

Constructor that takes a vector of integer values by copying it.

Definition at line 135 of file range_minimum_query.cpp.

RangeMinimumQuery() [3/5]

RangeMinimumQuery ( std::vector< IntType > &&  array )

explicit

Constructor that takes a vector of integer values by moving it.

Definition at line 144 of file range_minimum_query.cpp.

~RangeMinimumQuery()

~RangeMinimumQuery ( )

default

RangeMinimumQuery() [4/5]

RangeMinimumQuery ( RangeMinimumQuery const &  )

default

RangeMinimumQuery() [5/5]

RangeMinimumQuery ( RangeMinimumQuery &&  )

default

Member Function Documentation

operator=() [1/2]

RangeMinimumQuery& operator= ( RangeMinimumQuery &&  )

default

operator=() [2/2]

RangeMinimumQuery& operator= ( RangeMinimumQuery const &  )

default

query()

size_t query	(	size_t	i,
		size_t	j
	)		const

Main function for the Range Minimum Query.

The function returns the index of the minimum element in the given vector of integers (see RangeMinimumQuery()) that lies between the indices i and j.

Caveat: Both given indices are inclusive, i.e., the interval is [ i, j ]. If j < i, the function throws an std::invalid_argument.

Definition at line 163 of file range_minimum_query.cpp.

Member Typedef Documentation

BlockTypeType

using BlockTypeType = unsigned short

Definition at line 78 of file range_minimum_query.hpp.

IntType

using IntType = int32_t

Data type of the array for which we want to run RMQ queries.

Currently, this is fixed to a signed 32-bit integer. If a wider range is needed, many internal functions need to be adapted first.

Definition at line 75 of file range_minimum_query.hpp.

SuccinctType

using SuccinctType = unsigned char

Definition at line 77 of file range_minimum_query.hpp.

---

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

• range_minimum_query.hpp
• range_minimum_query.cpp