A class to support range minimum or range maximum queries on a random access container. More...

Public Types
typedef bit_vector::size_type	size_type
typedef bit_vector::size_type	value_type
typedef Bp_support	bp_support_type
typedef Rank_support10	rank_support10_type
typedef Select_support10	select_support10_type
Public Member Functions
	rmq_succinct_sada ()
	Default Constructor.
template<class RandomAccessContainer >
	rmq_succinct_sada (const RandomAccessContainer *v=NULL)
	Constructor.
	rmq_succinct_sada (const rmq_succinct_sada &rm)
	Copy constructor.
	~rmq_succinct_sada ()
	Destructor.
rmq_succinct_sada &	operator= (const rmq_succinct_sada &rm)
void	swap (const rmq_succinct_sada &rm)
	Swap operator.
size_type	operator() (const size_type l, const size_type r) const
	Range minimum/maximum query for the supported random access container v.
size_type	size () const
size_type	serialize (std::ostream &out, structure_tree_node *v=NULL, std::string name="") const
void	load (std::istream &in)
Public Attributes
const bit_vector &	ect_bp
const Bp_support &	ect_bp_support
const Rank_support10 &	ect_bp_rank10
const Select_support10 &	ect_bp_select10

Detailed Description

A class to support range minimum or range maximum queries on a random access container.

This class takes five template parameters:

minumum specifies whether the data structure should answer range minimum queries (mimumum=true) of range maximum queries (maximum=false), and
Bp_support is the support structure for the balanced parentheses sequence of the balanced parentheses sequence of the extended Cartesian tree used internal in the class.
Rank_support10 is the rank structure which supports rank queries for the bit pattern "10".
- Select_support10 is the select structure which supports select queries for the bit pattern "10".
  Time complexity
  $\Order{1}$ for the range minimum/maximum queries if the balanced parentheses support structure supports constant time operations.
  
  Space complexity:
  bits for the data structure ( ).
  TODO: implement test

Member Function Documentation

template<bool Minimum, class Bp_support , class Rank_support10 , class Select_support10 >

size_type sdsl::rmq_succinct_sada< Minimum, Bp_support, Rank_support10, Select_support10 >::operator()	(	const size_type	l,
		const size_type	r
	)		const `[inline]`

Range minimum/maximum query for the supported random access container v.

Parameters:

l	Leftmost position of the interval $[\ell..r]$ .
r	Rightmost position of the interval $[\ell..r]$ .

Returns:: The minimal index i with $\ell \leq i \leq r$ for which is minimal/maximal.

Precondition:

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