Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::HeapBase< IMPL, H, T, C > Class Template Referenceabstract

Common interface for all heap classes. More...

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

Public Types

using Handle = H *
 The type of handle used to identify stored values. More...
 

Public Member Functions

 HeapBase (C const &comp=C())
 
virtual const C & comparator () const
 Returns the comparator used to sort the values in the heap. More...
 
virtual void decrease (Handle handle, const T &value)=0
 Decreases a single value. More...
 
virtual void merge (IMPL &other)
 Merges in values of other heap. More...
 
virtual void pop ()=0
 Removes the topmost value from the heap. More...
 
virtual Handle push (const T &value)=0
 Inserts a value into the heap. More...
 
virtual const T & top () const =0
 Returns the topmost value in the heap. More...
 
virtual const T & value (const Handle handle) const =0
 Returns the value of that handle. More...
 

Private Attributes

m_comp
 

Detailed Description

template<typename IMPL, typename H, typename T, typename C>
class ogdf::HeapBase< IMPL, H, T, C >

Common interface for all heap classes.

Template Parameters
IMPLThe type of heap.
HThe type of handle to use. Such a handle will be given to the user for each pushed value.
TThe type of values to be stored.
CThe comparator used to order the stored values.

Definition at line 55 of file HeapBase.h.

Member Typedef Documentation

◆ Handle

template<typename IMPL , typename H , typename T , typename C >
using ogdf::HeapBase< IMPL, H, T, C >::Handle = H*

The type of handle used to identify stored values.

The handle type accessible from outside of the heap will always be a pointer.

Definition at line 66 of file HeapBase.h.

Constructor & Destructor Documentation

◆ HeapBase()

template<typename IMPL , typename H , typename T , typename C >
ogdf::HeapBase< IMPL, H, T, C >::HeapBase ( C const &  comp = C())
inlineexplicit

Definition at line 68 of file HeapBase.h.

Member Function Documentation

◆ comparator()

template<typename IMPL , typename H , typename T , typename C >
virtual const C& ogdf::HeapBase< IMPL, H, T, C >::comparator ( ) const
inlinevirtual

Returns the comparator used to sort the values in the heap.

Returns
The comparator for sorting the heaps values

Definition at line 75 of file HeapBase.h.

◆ decrease()

template<typename IMPL , typename H , typename T , typename C >
virtual void ogdf::HeapBase< IMPL, H, T, C >::decrease ( Handle  handle,
const T &  value 
)
pure virtual

Decreases a single value.

Parameters
handleThe handle of the value to be decreased
valueThe decreased value. This must be less than the former value

Implemented in ogdf::BinaryHeap< T, C >.

◆ merge()

template<typename IMPL , typename H , typename T , typename C >
void ogdf::HeapBase< IMPL, H, T, C >::merge ( IMPL &  other)
virtual

Merges in values of other heap.

After merge other heap becomes empty and is valid for further usage.

Parameters
otherA heap to be merged in.

Reimplemented in ogdf::PairingHeap< T, C >.

Definition at line 131 of file HeapBase.h.

◆ pop()

template<typename IMPL , typename H , typename T , typename C >
virtual void ogdf::HeapBase< IMPL, H, T, C >::pop ( )
pure virtual

◆ push()

template<typename IMPL , typename H , typename T , typename C >
virtual Handle ogdf::HeapBase< IMPL, H, T, C >::push ( const T &  value)
pure virtual

Inserts a value into the heap.

Parameters
valueThe value to be inserted
Returns
A handle to access and modify the value

Implemented in ogdf::FibonacciHeap< T, C >, ogdf::RMHeap< T, C >, ogdf::BinomialHeap< T, C >, ogdf::PairingHeap< T, C >, and ogdf::BinaryHeap< T, C >.

◆ top()

template<typename IMPL , typename H , typename T , typename C >
virtual const T& ogdf::HeapBase< IMPL, H, T, C >::top ( ) const
pure virtual

Returns the topmost value in the heap.

Returns
the topmost value

◆ value()

template<typename IMPL , typename H , typename T , typename C >
virtual const T& ogdf::HeapBase< IMPL, H, T, C >::value ( const Handle  handle) const
pure virtual

Returns the value of that handle.

Parameters
handleThe handle
Returns
The value

Implemented in ogdf::BinaryHeap< T, C >.

Member Data Documentation

◆ m_comp

template<typename IMPL , typename H , typename T , typename C >
C ogdf::HeapBase< IMPL, H, T, C >::m_comp
private

Definition at line 58 of file HeapBase.h.


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