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

#include <range_minimum_query.h>

Public Member Functions
	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	GetMinimumFromRange (int from, int to) const
const std::vector< T > &	array () const

Detailed Description

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

Definition at line 46 of file range_minimum_query.h.

Constructor & Destructor Documentation

RangeMinimumQuery() [1/3]

template<typename T , typename Compare >

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

inlineexplicit

RangeMinimumQuery implementation.

Definition at line 99 of file range_minimum_query.h.

RangeMinimumQuery() [2/3]

template<typename T , typename Compare >

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

Reminder: The task is to fill cache_ so that 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.

Definition at line 107 of file range_minimum_query.h.

RangeMinimumQuery() [3/3]

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

Definition at line 138 of file range_minimum_query.h.

GetMinimumFromRange()

template<typename T , typename Compare >

T operations_research::RangeMinimumQuery< T, Compare >::GetMinimumFromRange ( int from, int to ) const

inline

Returns the minimum (w.r.t. Compare) arr[x], where x is contained in [from, to).

Definition at line 126 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

---

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

• ortools/util/range_minimum_query.h