PriorityQueue.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/HashArray.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/heap/PairingHeap.h>
 
#include <functional>
#include <utility>
 
namespace ogdf {
 
 
 
template<typename T, class C = std::less<T>, template<typename, class> class Impl = PairingHeap>
class PriorityQueue {
public:
    using size_type = std::size_t;
 
private:
    size_type m_size; 
    const C& m_cmp;
    using SpecImpl = Impl<T, C>;
    SpecImpl* m_impl; 
 
public:
    using value_type = T;
    using handle = typename SpecImpl::Handle;
    using reference = value_type&;
    using const_reference = const value_type&;
 
 
    explicit PriorityQueue(const C& cmp = C(), int initialSize = 128)
        : m_size(0), m_cmp(cmp), m_impl(new SpecImpl(cmp, initialSize)) { }
 
    PriorityQueue(const PriorityQueue& other)
        : m_size(other.m_size), m_impl(new SpecImpl(other.m_impl)) { }
 
    PriorityQueue(PriorityQueue&& other) : PriorityQueue(other.m_impl->comparator()) {
        other.swap(*this);
    }
 
 
    template<class InputIt>
    PriorityQueue(InputIt first, InputIt last, const C& cmp = C()) : PriorityQueue(cmp) {
        push(first, last);
    }
 
 
    PriorityQueue(std::initializer_list<value_type> init, const C& cmp = C())
        : PriorityQueue(std::begin(init), std::end(init), cmp) { }
 
    ~PriorityQueue() { delete m_impl; }
 
    PriorityQueue& operator=(PriorityQueue other) {
        other.swap(*this);
        return *this;
    }
 
 
    PriorityQueue& operator=(std::initializer_list<value_type> ilist) {
        PriorityQueue tmp(ilist);
        tmp.swap(*this);
        return *this;
    }
 
    void swap(PriorityQueue& other) {
        std::swap(m_size, other.m_size);
        std::swap(m_impl, other.m_impl);
    }
 
    friend void swap(PriorityQueue& a, PriorityQueue& b) { a.swap(b); }
 
    const T& top() const { return m_impl->top(); }
 
    /*
     * @param value A value to be inserted.
     * @return Handle to the inserted node.
     */
    handle push(const value_type& value) {
        m_size++;
        return m_impl->push(value);
    }
 
 
    template<class InputIt>
    void push(InputIt first, InputIt last) {
        while (first != last) {
            push(*(first++));
        }
    }
 
 
    void push(std::initializer_list<value_type> ilist) { push(std::begin(ilist), std::end(ilist)); }
 
 
    void pop() {
        m_size--;
        m_impl->pop();
    }
 
 
    void decrease(handle pos, const T& value) { m_impl->decrease(pos, value); }
 
 
    void merge(PriorityQueue& other) {
        m_impl->merge(*other.m_impl);
        m_size += other.m_size;
        other.m_size = 0;
    }
 
    void clear() {
        PriorityQueue tmp(m_cmp);
        tmp.swap(*this);
    }
 
    bool empty() const { return size() == 0; }
 
    size_type size() const { return m_size; }
 
    const T& value(handle pos) const { return m_impl->value(pos); }
};
 
namespace pq_internal {
 
template<typename T, typename C>
class Compare {
public:
    Compare(const C& compare = C()) : m_compare(compare) { }
 
    Compare(const Compare& other) : m_compare(other.m_compare) { }
 
    bool operator()(const T& x, const T& y) const { return m_compare(x.priority(), y.priority()); }
 
private:
    C m_compare;
};
 
template<typename E, typename P>
class PairTemplate {
public:
    PairTemplate() : m_priority(-1) { }
 
    PairTemplate(const E& element, const P& priority) : m_element(element), m_priority(priority) { }
 
    const E& element() const { return m_element; }
 
    const P& priority() const { return m_priority; }
 
private:
    E m_element;
    P m_priority;
};
 
template<typename E, typename P, class C, template<typename, class> class Impl>
using SuperQueueTemplate = PriorityQueue<PairTemplate<E, P>, Compare<PairTemplate<E, P>, C>, Impl>;
 
template<typename E, typename P, class C, template<typename, class> class Impl>
class PrioritizedQueue : public SuperQueueTemplate<E, P, C, Impl> {
private:
    using SuperQueue = SuperQueueTemplate<E, P, C, Impl>;
    using Pair = PairTemplate<E, P>;
 
    C m_comp;
 
public:
    using Handle = typename SuperQueue::handle;
 
    PrioritizedQueue(const C& cmp = C(), int initialSize = 128)
        : SuperQueue(Compare<PairTemplate<E, P>, C>(cmp), initialSize), m_comp(cmp) { }
 
    const E& topElement() const { return SuperQueue::top().element(); }
 
    const P& topPriority() const { return SuperQueue::top().priority(); }
 
    Handle push(const E& element, const P& priority) {
        Pair pair(element, priority);
        Handle result = SuperQueue::push(pair);
        return result;
    }
 
    void decrease(Handle pos, const P& priority) {
        OGDF_ASSERT(m_comp(priority, this->value(pos).priority()));
        Pair pair(this->value(pos).element(), priority);
        SuperQueue::decrease(pos, pair);
    }
};
 
template<typename E, typename P, class C, template<typename, class> class Impl, typename Map>
class PrioritizedArrayQueueBase : public PrioritizedQueue<E, P, C, Impl> {
protected:
    using SuperQueue = PrioritizedQueue<E, P, C, Impl>;
    using Handle = typename PrioritizedQueue<E, P, C, Impl>::Handle;
 
public:
    bool contains(const E& element) const { return m_handles[element] != nullptr; }
 
    /*
     * Returns the priority of the key.
     * Note, that the behaviour is undefined if the key is not present.
     */
    const P& priority(const E& element) const {
        OGDF_ASSERT(contains(element));
        return this->value(m_handles[element]).priority();
    }
 
    void push(const E& element, const P& priority) {
        OGDF_ASSERT(m_handles[element] == nullptr);
        m_handles[element] = SuperQueue::push(element, priority);
    }
 
    void pop() {
        m_handles[SuperQueue::topElement()] = nullptr;
        SuperQueue::pop();
    }
 
    void decrease(const E& element, const P& priority) {
        Handle pos = m_handles[element];
        SuperQueue::decrease(pos, priority);
    }
 
    void clear() {
        SuperQueue::clear();
        m_handles.clear();
    }
 
protected:
    PrioritizedArrayQueueBase(const C& cmp, int initialSize, const Map& map)
        : SuperQueue(cmp, initialSize), m_handles(map) { }
 
    Map m_handles;
};
 
}
 
 
template<typename E, typename P, class C = std::less<P>, template<typename, class> class Impl = PairingHeap>
using PrioritizedQueue = pq_internal::PrioritizedQueue<E, P, C, Impl>;
 
 
template<typename E, typename P, class C = std::less<P>,
        template<typename, class> class Impl = PairingHeap, template<typename> class HashFunc = DefHashFunc>
class PrioritizedMapQueue
    : public pq_internal::PrioritizedArrayQueueBase<E, P, C, Impl,
              HashArray<E, typename PrioritizedQueue<E, P, C, Impl>::Handle, HashFunc<E>>> {
private:
    using CustomHashArray =
            HashArray<E, typename PrioritizedQueue<E, P, C, Impl>::Handle, HashFunc<E>>;
    using SuperQueue = pq_internal::PrioritizedArrayQueueBase<E, P, C, Impl, CustomHashArray>;
 
public:
    PrioritizedMapQueue(const C& cmp = C(), int initialSize = 128)
        : SuperQueue(cmp, initialSize, CustomHashArray(nullptr)) { }
};
 
template<typename P, class C, template<typename, class> class Impl, template<typename> class HashFunc>
class PrioritizedMapQueue<node, P, C, Impl, HashFunc>
    : public pq_internal::PrioritizedArrayQueueBase<node, P, C, Impl,
              NodeArray<typename PrioritizedQueue<node, P, C, Impl>::Handle>> {
private:
    using Handle = typename PrioritizedQueue<node, P, C, Impl>::Handle;
    using SuperQueue = pq_internal::PrioritizedArrayQueueBase<node, P, C, Impl, NodeArray<Handle>>;
 
public:
    PrioritizedMapQueue(const Graph& G, const C& cmp = C(), int initialSize = -1)
        : SuperQueue(cmp, initialSize == -1 ? G.numberOfNodes() : initialSize,
                NodeArray<Handle>(G, nullptr)) { }
 
    void clear() {
        SuperQueue::SuperQueue::clear();
        this->m_handles.init(*this->m_handles.graphOf(), nullptr);
    }
};
 
template<typename P, class C, template<typename, class> class Impl, template<typename> class HashFunc>
class PrioritizedMapQueue<edge, P, C, Impl, HashFunc>
    : public pq_internal::PrioritizedArrayQueueBase<edge, P, C, Impl,
              EdgeArray<typename PrioritizedQueue<edge, P, C, Impl>::Handle>> {
private:
    using Handle = typename PrioritizedQueue<edge, P, C, Impl>::Handle;
    using SuperQueue = pq_internal::PrioritizedArrayQueueBase<edge, P, C, Impl,
            EdgeArray<typename PrioritizedQueue<edge, P, C, Impl>::Handle>>;
 
public:
    PrioritizedMapQueue(const Graph& G, const C& cmp = C(), int initialSize = -1)
        : SuperQueue(cmp, initialSize == -1 ? G.numberOfEdges() : initialSize,
                EdgeArray<Handle>(G, nullptr)) { }
 
    void clear() {
        SuperQueue::SuperQueue::clear();
        this->m_handles.init(*this->m_handles.graphOf(), nullptr);
    }
};
 
 
}