Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::HotQueue< V, P, H > Class Template Reference

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. More...
 
 ~HotQueue ()
 Releases all buckets on destruction. More...
 
void decrease (Handle &handle, const P &priority)
 Decreases value of the given handle to priority. More...
 
bool empty () const
 Checks whether the heap is empty. More...
 
void pop ()
 Removes the top element from the heap. More...
 
Handle push (const V &value, const P &priority)
 Inserts a new node with given value and priority into a heap. More...
 
std::size_t size () const
 Number of elements contained within the heap. More...
 
const V & top () const
 Returns reference to the top element in the heap. More...
 

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. More...
 
std::size_t bucketIndex (const P &priority)
 Computes bucket index of given priority. More...
 

Private Attributes

std::vector< HotQueueNode< V, P > * > m_buckets
 Array of buckets. More...
 
const P m_bucketSpan
 Length of the interval covered by each bucket. More...
 
H< std::pair< V, P >, HeapComparatorm_heap
 Underlying heap structure. More...
 
std::size_t m_heapedBucket
 Index of currently heaped bucket. More...
 
std::size_t m_heapSize
 Size of underlying heap. More...
 
std::size_t m_lastBucket
 Index of highest, non-empty bucket. More...
 
std::size_t m_size
 Number of total elements in the heap. More...
 

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
VDenotes type of values of inserted elements.
PDenotes type of priorities of inserted elements.
HDenotes 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
changeMaximum {event duration}.
levelsNumber 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
handleA handle to the element for which the priority is to be decreased.
priorityA 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
valueA value of inserted element.
priorityA 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
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: