Heap-on-Top queue implementation.
More...
#include <ogdf/basic/heap/HotQueue.h>
|
| 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...
|
|
|
static constexpr std::size_t | NONE = std::numeric_limits<size_t>::max() |
|
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.
◆ Handle
template<typename V , typename P , template< typename T, typename C > class H>
◆ HeapHandle
template<typename V , typename P , template< typename T, typename C > class H>
◆ HotQueue()
template<typename V , typename P , template< typename T, typename C > class H>
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>
Releases all buckets on destruction.
Definition at line 213 of file HotQueue.h.
◆ bucketAt()
template<typename V , typename P , template< typename T, typename C > class H>
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>
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>
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>
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>
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>
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>
Returns reference to the top element in the heap.
Definition at line 229 of file HotQueue.h.
◆ m_buckets
template<typename V , typename P , template< typename T, typename C > class H>
◆ m_bucketSpan
template<typename V , typename P , template< typename T, typename C > class H>
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>
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>
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>
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>
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>
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 |
The documentation for this class was generated from the following file: