operations_research::RangeMinimumQuery< T, Compare > Class Template Reference

#include <range_minimum_query.h>

Public Member Functions
	RangeMinimumQuery ()
	RangeMinimumQuery (std::vector< T > array)
	RangeMinimumQuery implementation.
	RangeMinimumQuery (std::vector< T > array, Compare cmp)
	RangeMinimumQuery (const RangeMinimumQuery &)=delete
	This type is neither copyable nor movable.
RangeMinimumQuery &	operator= (const RangeMinimumQuery &)=delete
T	RangeMinimum (int begin, int end) const
void	PushBack (T element)
void	MakeTableFromNewElements ()
int	TableSize () const
	Returns the number of elements in sparse tables, excluding new elements.
void	Clear ()
const std::vector< T > &	array () const
	Returns the concatenated sequence of all elements in all arrays.

Detailed Description

template<typename T, typename Compare = std::less<T>>
class operations_research::RangeMinimumQuery< T, Compare >

Definition at line 87 of file range_minimum_query.h.

Constructor & Destructor Documentation

RangeMinimumQuery() [1/4]

template<typename T, typename Compare = std::less<T>>

operations_research::RangeMinimumQuery< T, Compare >::RangeMinimumQuery ( )

inline

This class uses the first two rows of cache_ to know the number of new elements, which at any moment is cache_[1].size() - cache_[0].size().

Definition at line 89 of file range_minimum_query.h.

RangeMinimumQuery() [2/4]

template<typename T, typename Compare>

operations_research::RangeMinimumQuery< T, Compare >::RangeMinimumQuery ( std::vector< T > array )

inlineexplicit

RangeMinimumQuery implementation.

Definition at line 169 of file range_minimum_query.h.

RangeMinimumQuery() [3/4]

template<typename T, typename Compare>

operations_research::RangeMinimumQuery< T, Compare >::RangeMinimumQuery	(	std::vector< T >	array,
		Compare	cmp )

This class uses the first two rows of cache_ to know the number of new elements.

Definition at line 173 of file range_minimum_query.h.

RangeMinimumQuery() [4/4]

template<typename T, typename Compare = std::less<T>>

operations_research::RangeMinimumQuery< T, Compare >::RangeMinimumQuery ( const RangeMinimumQuery< T, Compare > & )

delete

This type is neither copyable nor movable.

Member Function Documentation

array()

template<typename T, typename Compare>

const std::vector< T > & operations_research::RangeMinimumQuery< T, Compare >::array ( ) const

inline

Returns the concatenated sequence of all elements in all arrays.

Definition at line 224 of file range_minimum_query.h.

Clear()

template<typename T, typename Compare = std::less<T>>

void operations_research::RangeMinimumQuery< T, Compare >::Clear ( )

inline

Clears all tables. This invalidates all further range queries on currently existing tables. This does not release memory held by this object.

Definition at line 124 of file range_minimum_query.h.

MakeTableFromNewElements()

template<typename T, typename Compare>

void operations_research::RangeMinimumQuery< T, Compare >::MakeTableFromNewElements

(

)

Generates the sparse table for all new elements, i.e. elements that were added with PushBack() since the latest of these events: construction of this object, a previous call to MakeTableFromNewElements(), or a call to Clear(). The range of new elements [begin, end), with begin the Size() at the latest event, and end the current Size().

Reminder: The task is to fill cache_ so that for i in [begin, end), cache_[k][i] = min(arr, i, i+2^k) for every k <= Log2(n) and i <= n-2^k.

Note

cache_[k+1][i] = min(cache_[k][i], cache_[k][i+2^k]), hence every row can be efficiently computed from the previous.

This is the minimum number of rows needed to store the sequence of new elements, there may be more rows in the cache.

Record the new number of elements, wastes just size(T) space.

Definition at line 201 of file range_minimum_query.h.

operator=()

template<typename T, typename Compare = std::less<T>>

RangeMinimumQuery & operations_research::RangeMinimumQuery< T, Compare >::operator= ( const RangeMinimumQuery< T, Compare > & )

delete

PushBack()

template<typename T, typename Compare = std::less<T>>

void operations_research::RangeMinimumQuery< T, Compare >::PushBack ( T element )

inline

Definition at line 109 of file range_minimum_query.h.

RangeMinimum()

template<typename T, typename Compare>

T operations_research::RangeMinimumQuery< T, Compare >::RangeMinimum ( int begin, int end ) const

inline

Returns the minimum (w.r.t. Compare) arr[x], where x is contained in [begin_index, end_index). The range [begin_index, end_index) can only cover elements that were new at the same call to MakeTableFromNewElements(). When calling this method, there must be no pending new elements, i.e. the last method called apart from TableSize() must not have been PushBack().

Definition at line 183 of file range_minimum_query.h.

TableSize()

template<typename T, typename Compare = std::less<T>>

int operations_research::RangeMinimumQuery< T, Compare >::TableSize ( ) const

inline

Returns the number of elements in sparse tables, excluding new elements.

Definition at line 120 of file range_minimum_query.h.

---

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

• ortools/util/range_minimum_query.h