Go to the documentation of this file.
32 #ifndef LVR2_UTIL_MEAP_H_
33 #define LVR2_UTIL_MEAP_H_
37 #include <unordered_map>
39 #include <boost/optional.hpp>
43 using std::unordered_map;
56 template<
typename KeyT,
typename ValueT>
69 inline const KeyT&
key()
const {
77 inline const ValueT&
value()
const {
98 template<
typename KeyT,
typename ValueT>
111 Meap(
size_t capacity);
118 boost::optional<ValueT>
insert(KeyT key,
const ValueT& value);
119 boost::optional<ValueT>
erase(KeyT key);
121 boost::optional<const ValueT&>
get(KeyT key)
const;
144 void updateValue(
const KeyT& key,
const ValueT& newValue);
153 std::vector<MeapPair<KeyT, ValueT>>
m_heap;
162 size_t father(
size_t child)
const;
195 #include "lvr2/util/Meap.tcc"
Element in a meap, consisting of a key and a value.
size_t rightChild(size_t father) const
Returns the index of the right child of the father at index father.
void bubbleUp(size_t idx)
Performs the bubbleUp heap operation on the node at idx.
void updateValue(const KeyT &key, const ValueT &newValue)
Updates the value of key to newValue and repairs the heap.
Meap()
Initializes an empty meap.
void debugOutput() const
Just for debugging purposes. Prints a bunch of information.
const ValueT & value() const
MeapPair(KeyT key, ValueT value)
size_t leftChild(size_t father) const
Returns the index of the left child of the father at index father.
boost::optional< const ValueT & > get(KeyT key) const
const MeapPair< KeyT, ValueT > & peekMin() const
Returns a reference to the minimal value with its corresponding key.
boost::optional< ValueT > erase(KeyT key)
A map combined with a binary heap.
boost::optional< ValueT > insert(KeyT key, const ValueT &value)
std::vector< MeapPair< KeyT, ValueT > > m_heap
bool containsKey(KeyT key) const
bool isEmpty() const
Returns true iff the meap is empty.
void bubbleDown(size_t idx)
Performs the bubbleDown() heap operation on the node at idx.
size_t father(size_t child) const
Returns the index of the father of the child at index child.
MeapPair< KeyT, ValueT > popMin()
Removes the minimal value with its corresponding key from the meap and returns it.
unordered_map< KeyT, size_t > m_indices
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 Wed Mar 2 2022 00:37:24