Meap.hpp
Go to the documentation of this file.
1 
28 /*
29  * Meap.hpp
30  */
31 
32 #ifndef LVR2_UTIL_MEAP_H_
33 #define LVR2_UTIL_MEAP_H_
34 
35 #include <vector>
36 #include <utility>
37 #include <unordered_map>
38 
39 #include <boost/optional.hpp>
40 
42 
43 using std::unordered_map;
44 using std::pair;
45 
46 
47 namespace lvr2
48 {
49 
56 template<typename KeyT, typename ValueT>
57 class MeapPair
58 {
59 public:
60  MeapPair(KeyT key, ValueT value)
61  :m_key(key)
62  ,m_value(value)
63  {}
64 
65  inline KeyT& key() {
66  return m_key;
67  }
68 
69  inline const KeyT& key() const {
70  return m_key;
71  }
72 
73  inline ValueT& value() {
74  return m_value;
75  }
76 
77  inline const ValueT& value() const {
78  return m_value;
79  }
80 private:
81  KeyT m_key;
82  ValueT m_value;
83 };
84 
98 template<typename KeyT, typename ValueT>
99 class Meap
100 {
101 public:
105  Meap() {}
106 
111  Meap(size_t capacity);
112 
113 
114  // =======================================================================
115  // These methode work exactly like the ones from `AttributeMap`
116  // =======================================================================
117  bool containsKey(KeyT key) const;
118  boost::optional<ValueT> insert(KeyT key, const ValueT& value);
119  boost::optional<ValueT> erase(KeyT key);
120  void clear();
121  boost::optional<const ValueT&> get(KeyT key) const;
122  size_t numValues() const;
123 
124 
129  const MeapPair<KeyT, ValueT>& peekMin() const;
130 
136 
144  void updateValue(const KeyT& key, const ValueT& newValue);
145 
149  bool isEmpty() const;
150 
151 private:
152  // This is the main heap which stores the costs as well as all keys.
153  std::vector<MeapPair<KeyT, ValueT>> m_heap;
154 
155  // This is a map to quickly look up the index within `m_heap` at which a
156  // specific key lives.
157  unordered_map<KeyT, size_t> m_indices;
158 
162  size_t father(size_t child) const;
163 
168  size_t leftChild(size_t father) const;
169 
174  size_t rightChild(size_t father) const;
175 
182  void bubbleUp(size_t idx);
183 
187  void bubbleDown(size_t idx);
188 
190  void debugOutput() const;
191 };
192 
193 } // namespace lvr2
194 
195 #include "lvr2/util/Meap.tcc"
196 
197 #endif /* LVR2_UTIL_MEAP_H_ */
lvr2::MeapPair
Element in a meap, consisting of a key and a value.
Definition: Meap.hpp:57
lvr2::Meap::rightChild
size_t rightChild(size_t father) const
Returns the index of the right child of the father at index father.
lvr2::Meap::bubbleUp
void bubbleUp(size_t idx)
Performs the bubbleUp heap operation on the node at idx.
lvr2::Meap::updateValue
void updateValue(const KeyT &key, const ValueT &newValue)
Updates the value of key to newValue and repairs the heap.
lvr2::MeapPair::value
ValueT & value()
Definition: Meap.hpp:73
lvr2::MeapPair::key
const KeyT & key() const
Definition: Meap.hpp:69
lvr2::Meap::Meap
Meap()
Initializes an empty meap.
Definition: Meap.hpp:105
lvr2::Meap::debugOutput
void debugOutput() const
Just for debugging purposes. Prints a bunch of information.
lvr2::MeapPair::value
const ValueT & value() const
Definition: Meap.hpp:77
lvr2::MeapPair::MeapPair
MeapPair(KeyT key, ValueT value)
Definition: Meap.hpp:60
lvr2::Meap::leftChild
size_t leftChild(size_t father) const
Returns the index of the left child of the father at index father.
lvr2::Meap::get
boost::optional< const ValueT & > get(KeyT key) const
lvr2::Meap::peekMin
const MeapPair< KeyT, ValueT > & peekMin() const
Returns a reference to the minimal value with its corresponding key.
lvr2::Meap::erase
boost::optional< ValueT > erase(KeyT key)
lvr2::Meap
A map combined with a binary heap.
Definition: Meap.hpp:99
lvr2::Meap::insert
boost::optional< ValueT > insert(KeyT key, const ValueT &value)
lvr2::Meap::m_heap
std::vector< MeapPair< KeyT, ValueT > > m_heap
Definition: Meap.hpp:153
lvr2::Meap::numValues
size_t numValues() const
AttributeMap.hpp
lvr2::Meap::containsKey
bool containsKey(KeyT key) const
lvr2::Meap::isEmpty
bool isEmpty() const
Returns true iff the meap is empty.
lvr2::Meap::bubbleDown
void bubbleDown(size_t idx)
Performs the bubbleDown() heap operation on the node at idx.
lvr2::Meap::father
size_t father(size_t child) const
Returns the index of the father of the child at index child.
lvr2::MeapPair::m_value
ValueT m_value
Definition: Meap.hpp:82
lvr2
Definition: BaseBufferManipulators.hpp:39
lvr2::Meap::popMin
MeapPair< KeyT, ValueT > popMin()
Removes the minimal value with its corresponding key from the meap and returns it.
lvr2::MeapPair::m_key
KeyT m_key
Definition: Meap.hpp:81
lvr2::Meap::m_indices
unordered_map< KeyT, size_t > m_indices
Definition: Meap.hpp:157
lvr2::Meap::clear
void clear()
lvr2::MeapPair::key
KeyT & key()
Definition: Meap.hpp:65


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