Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::RMHeap< T, C > Class Template Reference

Randomized meldable heap implementation. More...

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

+ Inheritance diagram for ogdf::RMHeap< T, C >:

Public Member Functions

 RMHeap (const C &cmp=C(), int initialSize=-1)
 Creates empty randomized meldable heap. More...
 
virtual ~RMHeap ()
 Destructs the heap. More...
 
void decrease (RMHeapNode< T > *heapNode, const T &value) override
 Decreases value of the given heapNode to value. More...
 
void merge (RMHeap< T, C > &other) override
 Merges in values of other heap. More...
 
void pop () override
 Removes the top element from the heap. More...
 
RMHeapNode< T > * push (const T &value) override
 Inserts a new node with given value into a heap. More...
 
const T & top () const override
 Returns reference to the top element in the heap. More...
 
const T & value (RMHeapNode< T > *heapNode) const override
 Returns the value of the node. More...
 
- Public Member Functions inherited from ogdf::HeapBase< RMHeap< T, std::less< T > >, RMHeapNode< T >, T, std::less< T > >
 HeapBase (std::less< T > const &comp=std::less< T >())
 
virtual const std::less< T > & 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 (RMHeap< T, std::less< T > > &other)
 Merges in values of other 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 Types

using base_type = HeapBase< RMHeap< T, C >, RMHeapNode< T >, T, C >
 

Private Member Functions

RMHeapNode< T > * merge (RMHeapNode< T > *a, RMHeapNode< T > *b)
 Recursively merges heaps a and b. Returns resulting heap. More...
 
void remove (RMHeapNode< T > *heapNode)
 Removes given heapNode from the main tree (does not free memory!). More...
 

Static Private Member Functions

static void release (RMHeapNode< T > *heapNode)
 Recursively releases memory occupied by heap pointed by heapNode. More...
 

Private Attributes

std::default_random_engine m_rand
 Random values generator. More...
 
RMHeapNode< T > * m_root
 Root node of the heap. More...
 

Additional Inherited Members

- Public Types inherited from ogdf::HeapBase< RMHeap< T, std::less< T > >, RMHeapNode< T >, T, std::less< T > >
using Handle = RMHeapNode< T > *
 The type of handle used to identify stored values. More...
 

Detailed Description

template<typename T, typename C = std::less<T>>
class ogdf::RMHeap< T, C >

Randomized meldable heap implementation.

Code of meld (also known as merge) operation is solely based on Wikipedia article. Other methods are based on my intuitions and make use of melding.

For random number generation it uses default generator provided by the C++11 standard. In the future, it should be possible to provide custom random device, generator and seed.

Template Parameters
TDenotes value type of inserted elements.
CDenotes comparison functor determining value ordering.

Definition at line 77 of file RMHeap.h.

Member Typedef Documentation

◆ base_type

template<typename T , typename C = std::less<T>>
using ogdf::RMHeap< T, C >::base_type = HeapBase<RMHeap<T, C>, RMHeapNode<T>, T, C>
private

Definition at line 80 of file RMHeap.h.

Constructor & Destructor Documentation

◆ RMHeap()

template<typename T , typename C >
ogdf::RMHeap< T, C >::RMHeap ( const C &  cmp = C(),
int  initialSize = -1 
)
explicit

Creates empty randomized meldable heap.

Parameters
cmpComparison functor determining value ordering.
initialSizeignored by this implementation.

Definition at line 163 of file RMHeap.h.

◆ ~RMHeap()

template<typename T , typename C >
ogdf::RMHeap< T, C >::~RMHeap
virtual

Destructs the heap.

If the heap is not empty, destructors of contained elements are called and used storage is deallocated.

Definition at line 168 of file RMHeap.h.

Member Function Documentation

◆ decrease()

template<typename T , typename C >
void ogdf::RMHeap< T, C >::decrease ( RMHeapNode< T > *  heapNode,
const T &  value 
)
override

Decreases value of the given heapNode to value.

Behaviour of this function is undefined if node does not belong to a the heap or new value is greater than old one.

Parameters
heapNodeA node for which the value is to be decreased.
valueA new value for the node.

Definition at line 204 of file RMHeap.h.

◆ merge() [1/2]

template<typename T , typename C >
void ogdf::RMHeap< T, C >::merge ( RMHeap< T, C > &  other)
override

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.

Definition at line 221 of file RMHeap.h.

◆ merge() [2/2]

template<typename T , typename C >
RMHeapNode< T > * ogdf::RMHeap< T, C >::merge ( RMHeapNode< T > *  a,
RMHeapNode< T > *  b 
)
private

Recursively merges heaps a and b. Returns resulting heap.

Definition at line 229 of file RMHeap.h.

◆ pop()

template<typename T , typename C >
void ogdf::RMHeap< T, C >::pop
overridevirtual

Removes the top element from the heap.

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

Implements ogdf::HeapBase< RMHeap< T, std::less< T > >, RMHeapNode< T >, T, std::less< T > >.

Definition at line 192 of file RMHeap.h.

◆ push()

template<typename T , typename C >
RMHeapNode< T > * ogdf::RMHeap< T, C >::push ( const T &  value)
overridevirtual

Inserts a new node with given value into a heap.

Parameters
valueA value to be inserted.
Returns
Handle to the inserted node.

Implements ogdf::HeapBase< RMHeap< T, std::less< T > >, RMHeapNode< T >, T, std::less< T > >.

Definition at line 182 of file RMHeap.h.

◆ release()

template<typename T , typename C >
void ogdf::RMHeap< T, C >::release ( RMHeapNode< T > *  heapNode)
staticprivate

Recursively releases memory occupied by heap pointed by heapNode.

Definition at line 284 of file RMHeap.h.

◆ remove()

template<typename T , typename C >
void ogdf::RMHeap< T, C >::remove ( RMHeapNode< T > *  heapNode)
private

Removes given heapNode from the main tree (does not free memory!).

Definition at line 269 of file RMHeap.h.

◆ top()

template<typename T , typename C >
const T & ogdf::RMHeap< T, C >::top
override

Returns reference to the top element in the heap.

Definition at line 175 of file RMHeap.h.

◆ value()

template<typename T , typename C = std::less<T>>
const T& ogdf::RMHeap< T, C >::value ( RMHeapNode< T > *  heapNode) const
inlineoverride

Returns the value of the node.

Parameters
heapNodeThe nodes handle
Returns
the value of the node

Definition at line 144 of file RMHeap.h.

Member Data Documentation

◆ m_rand

template<typename T , typename C = std::less<T>>
std::default_random_engine ogdf::RMHeap< T, C >::m_rand
private

Random values generator.

Definition at line 149 of file RMHeap.h.

◆ m_root

template<typename T , typename C = std::less<T>>
RMHeapNode<T>* ogdf::RMHeap< T, C >::m_root
private

Root node of the heap.

Definition at line 150 of file RMHeap.h.


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