PQ.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/PriorityQueue.h>
#include <ogdf/graphalg/matching_blossom/utils.h>
 
#include <limits>
#include <unordered_map>
 
namespace ogdf {
namespace matching_blossom {
 
template<typename E, typename TWeight, typename C = std::less<TWeight>,
        template<typename, class> class Impl = PairingHeap>
class BlossomPQ
    : public PrioritizedQueue<E, TWeight, C, Impl>,
      public KeyIteratorContainer<E, typename PrioritizedQueue<E, TWeight, C, Impl>::Handle> {
protected:
    using ThisQueue = BlossomPQ<E, TWeight, C, Impl>;
    using SuperQueue = PrioritizedQueue<E, TWeight, C, Impl>;
    using Handle = typename SuperQueue::Handle;
 
    std::unordered_map<E, Handle> m_handles;
 
public:
    BlossomPQ() : KeyIteratorContainer<E, Handle>(m_handles) { }
 
    bool contains(const E& element) const { return m_handles.find(element) != m_handles.end(); }
 
    /*
     * Returns the priority of the key.
     * Note that the behaviour is undefined if the key is not present.
     */
    TWeight priority(const E& element) const {
        auto it = m_handles.find(element);
        OGDF_ASSERT(it != m_handles.end());
        return this->value(it->second).priority();
    }
 
    void push(const E& element, const TWeight priority) {
        OGDF_ASSERT(!contains(element));
        m_handles[element] = SuperQueue::push(element, priority);
    }
 
    void pop() {
        m_handles.erase(SuperQueue::topElement());
        SuperQueue::pop();
    }
 
    void decrease(const E& element, const TWeight priority) {
        Handle pos = m_handles[element];
        SuperQueue::decrease(pos, priority);
    }
 
    void merge(ThisQueue& other) {
        SuperQueue::merge(other);
        for (auto entry : other.m_handles) {
            m_handles[entry.first] = entry.second;
        }
        other.m_handles.clear();
    }
 
    void clear() {
        SuperQueue::clear();
        m_handles.clear();
    }
 
    void remove(const E& e) {
        OGDF_ASSERT(this->contains(e));
        this->decrease(e, -infinity<TWeight>());
        OGDF_ASSERT(this->topElement() == e);
        this->pop();
    }
};
 
}
}