Meap.hpp

Go to the documentation of this file.

 
/*
 * Meap.hpp
 */
 
#ifndef LVR2_UTIL_MEAP_H_
#define LVR2_UTIL_MEAP_H_
 
#include <vector>
#include <utility>
#include <unordered_map>
 
#include <boost/optional.hpp>
 
#include "lvr2/attrmaps/AttributeMap.hpp"
 
using std::unordered_map;
using std::pair;
 
 
namespace lvr2
{
 
template<typename KeyT, typename ValueT>
class MeapPair
{
public:
    MeapPair(KeyT key, ValueT value)
    :m_key(key)
    ,m_value(value)
    {}
 
    inline KeyT& key() {
        return m_key;
    }
 
    inline const KeyT& key() const {
        return m_key;
    }
 
    inline ValueT& value() {
        return m_value;
    }
 
    inline const ValueT& value() const {
        return m_value;
    }
private:
    KeyT m_key;
    ValueT m_value;
};
 
template<typename KeyT, typename ValueT>
class Meap
{
public:
    Meap() {}
 
    Meap(size_t capacity);
 
 
    // =======================================================================
    // These methode work exactly like the ones from `AttributeMap`
    // =======================================================================
    bool containsKey(KeyT key) const;
    boost::optional<ValueT> insert(KeyT key, const ValueT& value);
    boost::optional<ValueT> erase(KeyT key);
    void clear();
    boost::optional<const ValueT&> get(KeyT key) const;
    size_t numValues() const;
 
 
    const MeapPair<KeyT, ValueT>& peekMin() const;
 
    MeapPair<KeyT, ValueT> popMin();
 
    void updateValue(const KeyT& key, const ValueT& newValue);
 
    bool isEmpty() const;
 
private:
    // This is the main heap which stores the costs as well as all keys.
    std::vector<MeapPair<KeyT, ValueT>> m_heap;
 
    // This is a map to quickly look up the index within `m_heap` at which a
    // specific key lives.
    unordered_map<KeyT, size_t> m_indices;
 
    size_t father(size_t child) const;
 
    size_t leftChild(size_t father) const;
 
    size_t rightChild(size_t father) const;
 
    void bubbleUp(size_t idx);
 
    void bubbleDown(size_t idx);
 
    void debugOutput() const;
};
 
} // namespace lvr2
 
#include "lvr2/util/Meap.tcc"
 
#endif /* LVR2_UTIL_MEAP_H_ */