PairingHeap.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/heap/HeapBase.h>
 
#include <functional>
 
namespace ogdf {
 
 
template<typename T>
struct PairingHeapNode {
    template<typename, typename>
    friend class PairingHeap;
 
protected:
    T value; 
 
    PairingHeapNode<T>* prev; 
    PairingHeapNode<T>* next; 
    PairingHeapNode<T>* child; 
 
    explicit PairingHeapNode(const T& valueOfNode)
        : value(valueOfNode), prev(nullptr), next(nullptr), child(nullptr) { }
};
 
 
template<typename T, typename C>
class PairingHeap : public HeapBase<PairingHeap<T, C>, PairingHeapNode<T>, T, C> {
    using base_type = HeapBase<PairingHeap<T, C>, PairingHeapNode<T>, T, C>;
 
public:
    explicit PairingHeap(const C& cmp = C(), int initialSize = -1);
 
    virtual ~PairingHeap();
 
    const T& top() const override;
 
    PairingHeapNode<T>* push(const T& value) override;
 
    void pop() override;
 
    void decrease(PairingHeapNode<T>* heapNode, const T& value) override;
 
    void merge(PairingHeap<T, C>& other) override;
 
    const T& value(PairingHeapNode<T>* heapNode) const override { return heapNode->value; }
 
private:
    PairingHeapNode<T>* m_root; 
 
    PairingHeapNode<T>* pair(PairingHeapNode<T>* heapNode);
    PairingHeapNode<T>* merge(PairingHeapNode<T>* a, PairingHeapNode<T>* b);
 
    static void link(PairingHeapNode<T>* parent, PairingHeapNode<T>* child);
    static void unlink(PairingHeapNode<T>* heapNode);
 
    static void release(PairingHeapNode<T>* heapNode);
};
 
template<typename T, typename C>
PairingHeap<T, C>::PairingHeap(const C& cmp, int /* unused parameter */)
    : base_type(cmp), m_root(nullptr) { }
 
template<typename T, typename C>
PairingHeap<T, C>::~PairingHeap() {
    release(m_root);
    m_root = nullptr;
}
 
template<typename T, typename C>
inline const T& PairingHeap<T, C>::top() const {
    OGDF_ASSERT(m_root != nullptr);
    return m_root->value;
}
 
template<typename T, typename C>
PairingHeapNode<T>* PairingHeap<T, C>::push(const T& value) {
    PairingHeapNode<T>* heapNode = new PairingHeapNode<T>(value);
 
    m_root = m_root == nullptr ? heapNode : merge(m_root, heapNode);
    return heapNode;
}
 
template<typename T, typename C>
void PairingHeap<T, C>::pop() {
    PairingHeapNode<T>* children = m_root->child;
    delete m_root;
 
    m_root = pair(children);
}
 
template<typename T, typename C>
void PairingHeap<T, C>::decrease(PairingHeapNode<T>* heapNode, const T& value) {
    heapNode->value = value;
    if (heapNode->prev != nullptr) {
        unlink(heapNode);
        m_root = merge(m_root, heapNode);
    }
}
 
template<typename T, typename C>
void PairingHeap<T, C>::merge(PairingHeap<T, C>& other) {
    m_root = merge(m_root, other.m_root);
    other.m_root = nullptr;
}
 
template<typename T, typename C>
inline PairingHeapNode<T>* PairingHeap<T, C>::pair(PairingHeapNode<T>* heapNode) {
    if (heapNode == nullptr) {
        return nullptr;
    }
 
    /*
     * We move towards the end of list counting elements along the way. We do
     * this for two reasons: to know whether the list has even or odd number of
     * elements and for possible speed up of going-back through the list (loop
     * unrolling is not applicable for iterators but works for integers).
     */
    size_t children = 1;
    PairingHeapNode<T>* it = heapNode;
    while (it->next != nullptr) {
        it = it->next;
        children++;
    }
 
    PairingHeapNode<T>* result;
 
    if (children % 2 == 1) {
        PairingHeapNode<T>* a = it;
        it = it->prev;
        a->prev = a->next = nullptr;
        result = a;
    } else {
        PairingHeapNode<T>*a = it, *b = it->prev;
        it = it->prev->prev;
        a->prev = a->next = b->prev = b->next = nullptr;
        result = merge(a, b);
    }
 
    for (size_t i = 0; i < (children - 1) / 2; i++) {
        PairingHeapNode<T>*a = it, *b = it->prev;
        it = it->prev->prev;
        a->prev = a->next = b->prev = b->next = nullptr;
        result = merge(merge(a, b), result);
    }
 
    return result;
}
 
template<typename T, typename C>
inline PairingHeapNode<T>* PairingHeap<T, C>::merge(PairingHeapNode<T>* a, PairingHeapNode<T>* b) {
    if (a == nullptr) {
        return b;
    }
    if (b == nullptr) {
        return a;
    }
    if (this->comparator()(a->value, b->value)) {
        link(a, b);
        return a;
    } else {
        link(b, a);
        return b;
    }
}
 
template<typename T, typename C>
inline void PairingHeap<T, C>::link(PairingHeapNode<T>* root, PairingHeapNode<T>* child) {
    if (root->child != nullptr) {
        child->next = root->child;
        root->child->prev = child;
    }
    child->prev = root;
    root->child = child;
}
 
template<typename T, typename C>
inline void PairingHeap<T, C>::unlink(PairingHeapNode<T>* heapNode) {
    if (heapNode->prev->child == heapNode) {
        heapNode->prev->child = heapNode->next;
    } else {
        heapNode->prev->next = heapNode->next;
    }
    if (heapNode->next != nullptr) {
        heapNode->next->prev = heapNode->prev;
    }
    heapNode->prev = nullptr;
    heapNode->next = nullptr;
}
 
template<typename T, typename C>
inline void PairingHeap<T, C>::release(PairingHeapNode<T>* heapNode) {
    /*
     * Recursive version of this function is infinitely prettier than that
     * abomination. Please, make it prettier if you can.
     */
    PairingHeapNode<T>* it = heapNode;
 
    if (it == nullptr) {
        return;
    }
 
    for (;;) {
        // Slide down as long as possible.
        if (it->child != nullptr) {
            it = it->child;
            continue;
        }
        if (it->next != nullptr) {
            it = it->next;
            continue;
        }
 
        // Climb up until you find first non-visited node.
        for (;;) {
            PairingHeapNode<T>*curr = it, *prev = it->prev;
            delete it;
 
            if (prev == nullptr) {
                return;
            }
            if (curr == prev->child && prev->next != nullptr) {
                it = prev->next;
                break;
            } else {
                it = prev;
            }
        }
    }
}
 
}