Heap-on-Top queue implementation. More...

#include <ogdf/basic/heap/HotQueue.h>

Classes
struct	HeapComparator
	Comparator used by underlying heap. More...

Public Types
using	Handle = HotQueueHandle< V, P, HeapHandle >

Public Member Functions
	HotQueue (const P &change, std::size_t levels)
	Creates empty Heap-on-Top queue.

	~HotQueue ()
	Releases all buckets on destruction.

void	decrease (Handle &handle, const P &priority)
	Decreases value of the given `handle` to `priority`.

bool	empty () const
	Checks whether the heap is empty.

void	pop ()
	Removes the top element from the heap.

Handle	push (const V &value, const P &priority)
	Inserts a new node with given `value` and `priority` into a heap.

std::size_t	size () const
	Number of elements contained within the heap.

const V &	top () const
	Returns reference to the top element in the heap.

Private Types
using	HeapHandle = typename H< std::pair< V, P >, HeapComparator >::Handle

Private Member Functions
HotQueueNode< V, P > *&	bucketAt (std::size_t index)
	Provides access to bucket at given `index`.

std::size_t	bucketIndex (const P &priority)
	Computes bucket index of given `priority`.

Private Attributes
std::vector< HotQueueNode< V, P > * >	m_buckets
	Array of buckets.

const P	m_bucketSpan
	Length of the interval covered by each bucket.

H< std::pair< V, P >, HeapComparator >	m_heap
	Underlying heap structure.

std::size_t	m_heapedBucket
	Index of currently heaped bucket.

std::size_t	m_heapSize
	Size of underlying heap.

std::size_t	m_lastBucket
	Index of highest, non-empty bucket.

std::size_t	m_size
	Number of total elements in the heap.

Static Private Attributes
static constexpr std::size_t	NONE = std::numeric_limits<size_t>::max()

Detailed Description

template<typename V, typename P, template< typename T, typename C > class H>
class ogdf::HotQueue< V, P, H >

Heap-on-Top queue implementation.

General idea of this implementation comes from short summary provided here: http://theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html

Template Parameters

V	Denotes type of values of inserted elements.
P	Denotes type of priorities of inserted elements.
H	Denotes class of underlying heap.

Definition at line 120 of file HotQueue.h.

Member Typedef Documentation

◆ Handle

template<typename V , typename P , template< typename T, typename C > class H>

using ogdf::HotQueue< V, P, H >::Handle = HotQueueHandle<V, P, HeapHandle>

Definition at line 133 of file HotQueue.h.

◆ HeapHandle

template<typename V , typename P , template< typename T, typename C > class H>

using ogdf::HotQueue< V, P, H >::HeapHandle = typename H<std::pair<V, P>, HeapComparator>::Handle

private

Definition at line 123 of file HotQueue.h.

Constructor & Destructor Documentation

◆ HotQueue()

template<typename V , typename P , template< typename T, typename C > class H>

ogdf::HotQueue< V, P, H >::HotQueue	(	const P &	change,
		std::size_t	levels
	)

Creates empty Heap-on-Top queue.

Parameters

change	Maximum {event duration}.
levels	Number of buckets.

Definition at line 204 of file HotQueue.h.

◆ ~HotQueue()

template<typename V , typename P , template< typename T, typename C > class H>

ogdf::HotQueue< V, P, H >::~HotQueue ( )

Releases all buckets on destruction.

Definition at line 213 of file HotQueue.h.

Member Function Documentation

◆ bucketAt()

template<typename V , typename P , template< typename T, typename C > class H>

HotQueueNode< V, P > *& ogdf::HotQueue< V, P, H >::bucketAt ( std::size_t index )

inlineprivate

Provides access to bucket at given index.

Definition at line 198 of file HotQueue.h.

◆ bucketIndex()

template<typename V , typename P , template< typename T, typename C > class H>

std::size_t ogdf::HotQueue< V, P, H >::bucketIndex ( const P & priority )

inlineprivate

Computes bucket index of given priority.

Definition at line 193 of file HotQueue.h.

◆ decrease()

template<typename V , typename P , template< typename T, typename C > class H>

void ogdf::HotQueue< V, P, H >::decrease	(	Handle &	handle,
		const P &	priority
	)

Decreases value of the given handle to priority.

Behaviour of this function is undefined if referenced element does not belong to a the heap or new priority is incorrect.

Parameters

handle	A handle to the element for which the priority is to be decreased.
priority	A new priority for the element.

Definition at line 296 of file HotQueue.h.

◆ empty()

template<typename V , typename P , template< typename T, typename C > class H>

bool ogdf::HotQueue< V, P, H >::empty ( ) const

inline

Checks whether the heap is empty.

Definition at line 177 of file HotQueue.h.

◆ pop()

template<typename V , typename P , template< typename T, typename C > class H>

void ogdf::HotQueue< V, P, H >::pop ( )

Removes the top element from the heap.

Behaviour of this function is undefined if the heap is empty.

Definition at line 262 of file HotQueue.h.

◆ push()

template<typename V , typename P , template< typename T, typename C > class H>

HotQueue< V, P, H >::Handle ogdf::HotQueue< V, P, H >::push	(	const V &	value,
		const P &	priority
	)

Inserts a new node with given value and priority into a heap.

Parameters

value	A value of inserted element.
priority	A priority of inserted element.

Returns: Handle to the inserted node.

Definition at line 234 of file HotQueue.h.

◆ size()

template<typename V , typename P , template< typename T, typename C > class H>

std::size_t ogdf::HotQueue< V, P, H >::size ( ) const

inline

Number of elements contained within the heap.

Definition at line 174 of file HotQueue.h.

◆ top()

template<typename V , typename P , template< typename T, typename C > class H>

const V & ogdf::HotQueue< V, P, H >::top ( ) const

inline

Returns reference to the top element in the heap.

Definition at line 229 of file HotQueue.h.

Member Data Documentation

◆ m_buckets

template<typename V , typename P , template< typename T, typename C > class H>

std::vector<HotQueueNode<V, P>*> ogdf::HotQueue< V, P, H >::m_buckets

private

Array of buckets.

Definition at line 130 of file HotQueue.h.

◆ m_bucketSpan

template<typename V , typename P , template< typename T, typename C > class H>

const P ogdf::HotQueue< V, P, H >::m_bucketSpan

private

Length of the interval covered by each bucket.

Definition at line 190 of file HotQueue.h.

◆ m_heap

template<typename V , typename P , template< typename T, typename C > class H>

H<std::pair<V, P>, HeapComparator> ogdf::HotQueue< V, P, H >::m_heap

private

Underlying heap structure.

Definition at line 127 of file HotQueue.h.

◆ m_heapedBucket

template<typename V , typename P , template< typename T, typename C > class H>

std::size_t ogdf::HotQueue< V, P, H >::m_heapedBucket

private

Index of currently heaped bucket.

Definition at line 187 of file HotQueue.h.

◆ m_heapSize

template<typename V , typename P , template< typename T, typename C > class H>

std::size_t ogdf::HotQueue< V, P, H >::m_heapSize

private

Size of underlying heap.

Definition at line 128 of file HotQueue.h.

◆ m_lastBucket

template<typename V , typename P , template< typename T, typename C > class H>

std::size_t ogdf::HotQueue< V, P, H >::m_lastBucket

private

Index of highest, non-empty bucket.

Definition at line 188 of file HotQueue.h.

◆ m_size

template<typename V , typename P , template< typename T, typename C > class H>

std::size_t ogdf::HotQueue< V, P, H >::m_size

private

Number of total elements in the heap.

Definition at line 125 of file HotQueue.h.

◆ NONE

template<typename V , typename P , template< typename T, typename C > class H>

constexpr std::size_t ogdf::HotQueue< V, P, H >::NONE = std::numeric_limits<size_t>::max()

staticconstexprprivate

Definition at line 200 of file HotQueue.h.

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

include/ogdf/basic/heap/HotQueue.h

OpenGraph DrawingFramework

Classes

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Handle

◆ HeapHandle

Constructor & Destructor Documentation

◆ HotQueue()

◆ ~HotQueue()

Member Function Documentation

◆ bucketAt()

◆ bucketIndex()

◆ decrease()

◆ empty()

◆ pop()

◆ push()

◆ size()

◆ top()

Member Data Documentation

◆ m_buckets

◆ m_bucketSpan

◆ m_heap

◆ m_heapedBucket

◆ m_heapSize

◆ m_lastBucket

◆ m_size

◆ NONE

Open
Graph Drawing
Framework