RadixHeap.h

Go to the documentation of this file.

 
#pragma once
 
#include <array>
#include <functional>
#include <utility>
#include <vector>
 
namespace ogdf {
 
 
template<typename V, typename P>
class RadixHeapNode {
public:
    V value;
    P priority;
 
    RadixHeapNode<V, P>* prev;
    RadixHeapNode<V, P>* next;
 
    RadixHeapNode(const V& nodeValue, const P& nodePriority)
        : value(nodeValue), priority(nodePriority), prev(nullptr), next(nullptr) { }
};
 
 
template<typename V, typename P>
class RadixHeap {
public:
    RadixHeap();
 
    ~RadixHeap();
 
 
 
    RadixHeapNode<V, P>* push(const V& value, const P& priority);
 
 
    V pop();
 
    std::size_t size() const { return m_size; }
 
    bool empty() const { return size() == 0; }
 
private:
    using Bucket = RadixHeapNode<V, P>*;
    static constexpr std::size_t BITS = sizeof(P) * 8;
 
    std::size_t m_size; 
 
    P m_minimum; 
    P m_bucketMask; 
    std::array<Bucket, BITS + 1> m_buckets; 
 
    void insert(RadixHeapNode<V, P>* heapNode);
 
    template<typename T>
    static std::size_t msbSet(T mask) {
        std::size_t i = 0;
        while (mask != 0) {
            mask >>= 1;
            i++;
        }
        return i;
    }
 
#ifdef __has_builtin
#   if __has_builtin(__builtin_clz)
    static std::size_t msbSet(unsigned int mask) {
        return mask == 0 ? 0 : (BITS - __builtin_clz(mask));
    }
 
    static std::size_t msbSet(unsigned long mask) {
        return mask == 0 ? 0 : (BITS - __builtin_clzl(mask));
    }
 
    static std::size_t msbSet(unsigned long long mask) {
        return mask == 0 ? 0 : (BITS - __builtin_clzll(mask));
    }
#   endif
#endif
};
 
template<typename V, typename P>
RadixHeap<V, P>::RadixHeap() : m_size(0), m_minimum(0), m_bucketMask(0) {
    m_buckets.fill(nullptr);
}
 
template<typename V, typename P>
RadixHeap<V, P>::~RadixHeap() {
    for (Bucket& bucket : m_buckets) {
        auto it = bucket;
        while (it != nullptr) {
            auto next = it->next;
            delete it;
            it = next;
        }
    }
}
 
template<typename V, typename P>
RadixHeapNode<V, P>* RadixHeap<V, P>::push(const V& value, const P& priority) {
    m_size++;
 
    RadixHeapNode<V, P>* heapNode = new RadixHeapNode<V, P>(value, priority);
    insert(heapNode);
    return heapNode;
}
 
template<typename V, typename P>
V RadixHeap<V, P>::pop() {
    m_size--;
 
    if (m_buckets[0] != nullptr) {
        V result = std::move(m_buckets[0]->value);
 
        Bucket tmp = m_buckets[0]->next;
        delete m_buckets[0];
        m_buckets[0] = tmp;
 
        if (m_buckets[0] != nullptr) {
            m_buckets[0]->prev = nullptr;
        }
        return result;
    }
 
    std::size_t ind = BITS + 1 - msbSet(m_bucketMask);
 
    Bucket bucket = m_buckets[ind];
    m_buckets[ind] = nullptr;
    if (ind != 0) {
        m_bucketMask ^= (P(1) << (8 * sizeof(P) - ind));
    }
 
 
    Bucket min = bucket;
    for (Bucket it = bucket; it != nullptr; it = it->next) {
        if (it->priority < min->priority) {
            min = it;
        }
    }
 
    if (min->prev != nullptr) {
        min->prev->next = min->next;
    } else {
        bucket = min->next;
    }
 
    if (min->next != nullptr) {
        min->next->prev = min->prev;
    }
 
    V result = std::move(min->value);
    m_minimum = std::move(min->priority);
    delete min;
 
    while (bucket != nullptr) {
        Bucket next = bucket->next;
        bucket->prev = nullptr;
        insert(bucket);
 
        bucket = next;
    }
 
    return result;
}
 
template<typename V, typename P>
inline void RadixHeap<V, P>::insert(RadixHeapNode<V, P>* heapNode) {
    std::size_t ind = msbSet(heapNode->priority ^ m_minimum);
 
    heapNode->next = m_buckets[ind];
    if (m_buckets[ind] != nullptr) {
        m_buckets[ind]->prev = heapNode;
    }
    m_buckets[ind] = heapNode;
 
    if (ind != 0) {
        m_bucketMask |= (P(1) << (BITS - ind));
    }
}
 
}