Public Member Functions | Private Member Functions | Private Attributes | List of all members
lvr2::Meap< KeyT, ValueT > Class Template Reference

A map combined with a binary heap. More...

#include <Meap.hpp>

Public Member Functions

void clear ()
 
bool containsKey (KeyT key) const
 
boost::optional< ValueT > erase (KeyT key)
 
boost::optional< const ValueT & > get (KeyT key) const
 
boost::optional< ValueT > insert (KeyT key, const ValueT &value)
 
bool isEmpty () const
 Returns true iff the meap is empty. More...
 
 Meap ()
 Initializes an empty meap. More...
 
 Meap (size_t capacity)
 Initializes an empty meap and reserves memory for at least capacity many elements. More...
 
size_t numValues () const
 
const MeapPair< KeyT, ValueT > & peekMin () const
 Returns a reference to the minimal value with its corresponding key. More...
 
MeapPair< KeyT, ValueT > popMin ()
 Removes the minimal value with its corresponding key from the meap and returns it. More...
 
void updateValue (const KeyT &key, const ValueT &newValue)
 Updates the value of key to newValue and repairs the heap. More...
 

Private Member Functions

void bubbleDown (size_t idx)
 Performs the bubbleDown() heap operation on the node at idx. More...
 
void bubbleUp (size_t idx)
 Performs the bubbleUp heap operation on the node at idx. More...
 
void debugOutput () const
 Just for debugging purposes. Prints a bunch of information. More...
 
size_t father (size_t child) const
 Returns the index of the father of the child at index child. More...
 
size_t leftChild (size_t father) const
 Returns the index of the left child of the father at index father. More...
 
size_t rightChild (size_t father) const
 Returns the index of the right child of the father at index father. More...
 

Private Attributes

std::vector< MeapPair< KeyT, ValueT > > m_heap
 
unordered_map< KeyT, size_t > m_indices
 

Detailed Description

template<typename KeyT, typename ValueT>
class lvr2::Meap< KeyT, ValueT >

A map combined with a binary heap.

The elements in the meap are pairs of KeyT and ValueT. Only the latter is used for sorting the heap. The former can be used to lookup the value, as in a regular map. Combining both, a map and a heap, allows to implement the updateValue() method, which would otherwise be impossible with a simple binary heap. In this library, this type is often used with some kind of "cost" as value and a handle as key.

This implementation is a min heap: the smallest value sits "at the top" and can be retrieved in O(1) via popMin() or peekMin().

Definition at line 99 of file Meap.hpp.

Constructor & Destructor Documentation

◆ Meap() [1/2]

template<typename KeyT , typename ValueT >
lvr2::Meap< KeyT, ValueT >::Meap ( )
inline

Initializes an empty meap.

Definition at line 105 of file Meap.hpp.

◆ Meap() [2/2]

template<typename KeyT , typename ValueT >
lvr2::Meap< KeyT, ValueT >::Meap ( size_t  capacity)

Initializes an empty meap and reserves memory for at least capacity many elements.

Member Function Documentation

◆ bubbleDown()

template<typename KeyT , typename ValueT >
void lvr2::Meap< KeyT, ValueT >::bubbleDown ( size_t  idx)
private

Performs the bubbleDown() heap operation on the node at idx.

◆ bubbleUp()

template<typename KeyT , typename ValueT >
void lvr2::Meap< KeyT, ValueT >::bubbleUp ( size_t  idx)
private

Performs the bubbleUp heap operation on the node at idx.

As long as the father of the node at idx still has a greater value than the value of idx, both are swapped.

◆ clear()

template<typename KeyT , typename ValueT >
void lvr2::Meap< KeyT, ValueT >::clear ( )

◆ containsKey()

template<typename KeyT , typename ValueT >
bool lvr2::Meap< KeyT, ValueT >::containsKey ( KeyT  key) const

◆ debugOutput()

template<typename KeyT , typename ValueT >
void lvr2::Meap< KeyT, ValueT >::debugOutput ( ) const
private

Just for debugging purposes. Prints a bunch of information.

◆ erase()

template<typename KeyT , typename ValueT >
boost::optional<ValueT> lvr2::Meap< KeyT, ValueT >::erase ( KeyT  key)

◆ father()

template<typename KeyT , typename ValueT >
size_t lvr2::Meap< KeyT, ValueT >::father ( size_t  child) const
private

Returns the index of the father of the child at index child.

◆ get()

template<typename KeyT , typename ValueT >
boost::optional<const ValueT&> lvr2::Meap< KeyT, ValueT >::get ( KeyT  key) const

◆ insert()

template<typename KeyT , typename ValueT >
boost::optional<ValueT> lvr2::Meap< KeyT, ValueT >::insert ( KeyT  key,
const ValueT &  value 
)

◆ isEmpty()

template<typename KeyT , typename ValueT >
bool lvr2::Meap< KeyT, ValueT >::isEmpty ( ) const

Returns true iff the meap is empty.

◆ leftChild()

template<typename KeyT , typename ValueT >
size_t lvr2::Meap< KeyT, ValueT >::leftChild ( size_t  father) const
private

Returns the index of the left child of the father at index father.

◆ numValues()

template<typename KeyT , typename ValueT >
size_t lvr2::Meap< KeyT, ValueT >::numValues ( ) const

◆ peekMin()

template<typename KeyT , typename ValueT >
const MeapPair<KeyT, ValueT>& lvr2::Meap< KeyT, ValueT >::peekMin ( ) const

Returns a reference to the minimal value with its corresponding key.

◆ popMin()

template<typename KeyT , typename ValueT >
MeapPair<KeyT, ValueT> lvr2::Meap< KeyT, ValueT >::popMin ( )

Removes the minimal value with its corresponding key from the meap and returns it.

◆ rightChild()

template<typename KeyT , typename ValueT >
size_t lvr2::Meap< KeyT, ValueT >::rightChild ( size_t  father) const
private

Returns the index of the right child of the father at index father.

◆ updateValue()

template<typename KeyT , typename ValueT >
void lvr2::Meap< KeyT, ValueT >::updateValue ( const KeyT &  key,
const ValueT &  newValue 
)

Updates the value of key to newValue and repairs the heap.

The new value might be lower or greater than the old value. The heap is repaired either way. If the new value equals the old one, this method does nothing.

Member Data Documentation

◆ m_heap

template<typename KeyT , typename ValueT >
std::vector<MeapPair<KeyT, ValueT> > lvr2::Meap< KeyT, ValueT >::m_heap
private

Definition at line 153 of file Meap.hpp.

◆ m_indices

template<typename KeyT , typename ValueT >
unordered_map<KeyT, size_t> lvr2::Meap< KeyT, ValueT >::m_indices
private

Definition at line 157 of file Meap.hpp.


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


lvr2
Author(s): Thomas Wiemann , Sebastian Pütz , Alexander Mock , Lars Kiesow , Lukas Kalbertodt , Tristan Igelbrink , Johan M. von Behren , Dominik Feldschnieders , Alexander Löhr
autogenerated on Mon Feb 28 2022 22:46:12