operations_research::IntegerPriorityQueue< Element, Compare > Class Template Reference

#include <integer_pq.h>

Public Member Functions
	IntegerPriorityQueue (int n=0, Compare comp=Compare())
	Starts with an empty queue and reserve space for n elements.
void	Reserve (int n)
int	Size () const
	Returns the number of elements currently present.
bool	IsEmpty () const
void	Clear ()
bool	Contains (int index) const
	Returns true if the element with given index is currently in the queue.
void	Add (Element element)
Element	Top () const
void	Pop ()
void	Remove (int index)
void	ChangePriority (Element element)
void	IncreasePriority (Element element)
	Optimized version of ChangePriority() when we know the direction.
void	DecreasePriority (Element element)
Element	GetElement (int index) const
	Returns the element with given index.
Element	QueueElement (int i) const

Detailed Description

template<typename Element, class Compare = std::less<Element>>
class operations_research::IntegerPriorityQueue< Element, Compare >

Classic asjustable priority queue implementation. It behaves exactly the same as AdjustablePriorityQueue regarding identical elements, but it uses less memory and is in general slightly faster.

Definition at line 37 of file integer_pq.h.

Constructor & Destructor Documentation

IntegerPriorityQueue()

template<typename Element , class Compare = std::less<Element>>

operations_research::IntegerPriorityQueue< Element, Compare >::IntegerPriorityQueue ( int n = 0, Compare comp = Compare() )

inlineexplicit

Starts with an empty queue and reserve space for n elements.

Definition at line 40 of file integer_pq.h.

Member Function Documentation

Add()

template<typename Element , class Compare = std::less<Element>>

void operations_research::IntegerPriorityQueue< Element, Compare >::Add ( Element element )

inline

Adds the given element to the queue and set its priority. Preconditions: Contains(element) must be false.

Definition at line 71 of file integer_pq.h.

ChangePriority()

template<typename Element , class Compare = std::less<Element>>

void operations_research::IntegerPriorityQueue< Element, Compare >::ChangePriority ( Element element )

inline

Change the priority of the given element and adjust the queue.

Preconditions: Contains(element) must be true.

Definition at line 105 of file integer_pq.h.

Clear()

template<typename Element , class Compare = std::less<Element>>

void operations_research::IntegerPriorityQueue< Element, Compare >::Clear ( )

inline

Removes all elements from the queue.

Todo

(user): we could make this sparse if it is needed.

Definition at line 61 of file integer_pq.h.

Contains()

template<typename Element , class Compare = std::less<Element>>

bool operations_research::IntegerPriorityQueue< Element, Compare >::Contains ( int index ) const

inline

Returns true if the element with given index is currently in the queue.

Definition at line 67 of file integer_pq.h.

DecreasePriority()

template<typename Element , class Compare = std::less<Element>>

void operations_research::IntegerPriorityQueue< Element, Compare >::DecreasePriority ( Element element )

inline

Definition at line 119 of file integer_pq.h.

GetElement()

template<typename Element , class Compare = std::less<Element>>

Element operations_research::IntegerPriorityQueue< Element, Compare >::GetElement ( int index ) const

inline

Returns the element with given index.

Definition at line 124 of file integer_pq.h.

IncreasePriority()

template<typename Element , class Compare = std::less<Element>>

void operations_research::IntegerPriorityQueue< Element, Compare >::IncreasePriority ( Element element )

inline

Optimized version of ChangePriority() when we know the direction.

Definition at line 116 of file integer_pq.h.

IsEmpty()

template<typename Element , class Compare = std::less<Element>>

bool operations_research::IntegerPriorityQueue< Element, Compare >::IsEmpty ( ) const

inline

Definition at line 57 of file integer_pq.h.

Pop()

template<typename Element , class Compare = std::less<Element>>

void operations_research::IntegerPriorityQueue< Element, Compare >::Pop ( )

inline

Definition at line 79 of file integer_pq.h.

QueueElement()

template<typename Element , class Compare = std::less<Element>>

Element operations_research::IntegerPriorityQueue< Element, Compare >::QueueElement ( int i ) const

inline

For i in [0, Size()) returns an element currently in the queue. This can be used to get a random element from the queue for instance.

Definition at line 128 of file integer_pq.h.

Remove()

template<typename Element , class Compare = std::less<Element>>

void operations_research::IntegerPriorityQueue< Element, Compare >::Remove ( int index )

inline

Removes the element with given index from the queue. Preconditions: Contains(index) must be true.

Definition at line 88 of file integer_pq.h.

Reserve()

template<typename Element , class Compare = std::less<Element>>

void operations_research::IntegerPriorityQueue< Element, Compare >::Reserve ( int n )

inline

Increases the space reservation to n elements indices in [0, n). All elements passed to the other functions must have an Index() smaller than this n.

The heap_ starts at 1 for faster left/right child indices computation. This also allow us to use position 0 for element not in the queue.

Definition at line 48 of file integer_pq.h.

Size()

template<typename Element , class Compare = std::less<Element>>

int operations_research::IntegerPriorityQueue< Element, Compare >::Size ( ) const

inline

Returns the number of elements currently present.

Definition at line 56 of file integer_pq.h.

Top()

template<typename Element , class Compare = std::less<Element>>

Element operations_research::IntegerPriorityQueue< Element, Compare >::Top ( ) const

inline

Top() returns the top element and Pop() remove it from the queue. Preconditions: IsEmpty() must be false.

Definition at line 78 of file integer_pq.h.

---

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

• ortools/util/integer_pq.h