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_ */