A toolkit for working with phylogenetic data.
v0.20.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 (std::vector< IntType > const &array)
 Constructor that takes a vector of integer values by copying it. More...
 
 RangeMinimumQuery (std::vector< IntType > &&array)
 Constructor that takes a vector of integer values by moving it. More...
 
 RangeMinimumQuery (RangeMinimumQuery const &)=default
 
 RangeMinimumQuery (RangeMinimumQuery &&)=default
 
 ~RangeMinimumQuery ()=default
 
RangeMinimumQueryoperator= (RangeMinimumQuery const &)=default
 
RangeMinimumQueryoperator= (RangeMinimumQuery &&)=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 ( )
default
RangeMinimumQuery ( std::vector< IntType > const &  array)

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

Definition at line 135 of file range_minimum_query.cpp.

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

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

Definition at line 144 of file range_minimum_query.cpp.

~RangeMinimumQuery ( )
default
RangeMinimumQuery ( RangeMinimumQuery const &  )
default

Member Function Documentation

RangeMinimumQuery& operator= ( RangeMinimumQuery const &  )
default
RangeMinimumQuery& operator= ( RangeMinimumQuery &&  )
default
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

using BlockTypeType = unsigned short

Definition at line 78 of file range_minimum_query.hpp.

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.

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: