HotQueue.h

Go to the documentation of this file.

 
#pragma once
 
#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iterator>
#include <limits>
#include <utility>
#include <vector>
 
namespace ogdf {
 
 
template<typename V, typename P>
struct HotQueueNode {
    V value;
    P priority;
 
    HotQueueNode<V, P>* prev;
    HotQueueNode<V, P>* next;
 
    HotQueueNode() : prev(nullptr), next(nullptr) { }
 
    HotQueueNode(const V& val, const P& pr)
        : value(val), priority(pr), prev(nullptr), next(nullptr) { }
};
 
 
template<typename V, typename P, typename HeapHandle>
struct HotQueueHandle {
private:
    enum class Type { heap, bucket } type; 
 
    union {
        HeapHandle heapHandle;
        std::pair<std::size_t, HotQueueNode<V, P>*> bucketHandle;
    };
 
    HotQueueHandle(HeapHandle handle) : type(Type::heap), heapHandle(handle) { }
 
    HotQueueHandle(std::size_t index, HotQueueNode<V, P>* queueNode)
        : type(Type::bucket), bucketHandle(index, queueNode) { }
 
public:
    HotQueueHandle(const HotQueueHandle& other) { operator=(other); }
 
    HotQueueHandle& operator=(const HotQueueHandle& other) {
        type = other.type;
        switch (type) {
        case Type::heap:
            heapHandle = other.heapHandle;
            break;
        case Type::bucket:
            bucketHandle = other.bucketHandle;
            break;
        }
 
        return *this;
    }
 
    template<typename V1, typename P1, template<typename T, typename C> class H1>
    friend class HotQueue;
};
 
 
template<typename V, typename P, template<typename T, typename C> class H>
class HotQueue {
private:
    struct HeapComparator;
 
    using HeapHandle = typename H<std::pair<V, P>, HeapComparator>::Handle;
 
    std::size_t m_size; 
 
    H<std::pair<V, P>, HeapComparator> m_heap; 
    std::size_t m_heapSize; 
 
    std::vector<HotQueueNode<V, P>*> m_buckets; 
 
public:
    using Handle = HotQueueHandle<V, P, HeapHandle>;
 
 
    HotQueue(const P& change, std::size_t levels);
 
    ~HotQueue();
 
    const V& top() const;
 
 
    Handle push(const V& value, const P& priority);
 
 
    void pop();
 
 
    void decrease(Handle& handle, const P& priority);
 
    std::size_t size() const { return m_size; }
 
    bool empty() const { return size() == 0; }
 
private:
    struct HeapComparator {
        bool operator()(const std::pair<V, P>& a, const std::pair<V, P>& b) const {
            return std::get<1>(a) < std::get<1>(b);
        }
    };
 
    std::size_t m_heapedBucket; 
    std::size_t m_lastBucket; 
 
    const P m_bucketSpan; 
 
    std::size_t bucketIndex(const P& priority) {
        return (std::size_t)std::round(priority / m_bucketSpan);
    }
 
    HotQueueNode<V, P>*& bucketAt(std::size_t index) { return m_buckets[index % m_buckets.size()]; }
 
    static constexpr std::size_t NONE = std::numeric_limits<size_t>::max();
};
 
template<typename V, typename P, template<typename T, typename C> class H>
HotQueue<V, P, H>::HotQueue(const P& change, std::size_t levels)
    : m_size(0)
    , m_heapSize(0)
    , m_buckets(levels, nullptr)
    , m_heapedBucket(NONE)
    , m_lastBucket(0)
    , m_bucketSpan((int)std::round(change / (levels - 1))) { }
 
template<typename V, typename P, template<typename T, typename C> class H>
HotQueue<V, P, H>::~HotQueue() {
    if (empty()) {
        return;
    }
    for (auto& bucket : m_buckets) {
        if (bucket != nullptr) {
            for (HotQueueNode<V, P>* it = bucket; it != nullptr;) {
                HotQueueNode<V, P>* next = it->next;
                delete it;
                it = next;
            }
        }
    }
}
 
template<typename V, typename P, template<typename T, typename C> class H>
inline const V& HotQueue<V, P, H>::top() const {
    return std::get<0>(m_heap.top());
}
 
template<typename V, typename P, template<typename T, typename C> class H>
typename HotQueue<V, P, H>::Handle HotQueue<V, P, H>::push(const V& value, const P& priority) {
    m_size++;
 
    std::size_t ind = bucketIndex(priority);
 
    if (m_heapedBucket == NONE) {
        m_heapedBucket = ind;
    }
 
    if (ind == m_heapedBucket) {
        m_heapSize++;
        HeapHandle handle = m_heap.push(std::make_pair(value, priority));
        return Handle(handle);
    } else {
        HotQueueNode<V, P>* queueNode = new HotQueueNode<V, P>(value, priority);
 
        if (bucketAt(ind) != nullptr) {
            bucketAt(ind)->prev = queueNode;
        }
        queueNode->next = bucketAt(ind);
        bucketAt(ind) = queueNode;
 
        m_lastBucket = std::max(m_lastBucket, ind);
        return Handle(ind, queueNode);
    }
}
 
template<typename V, typename P, template<typename T, typename C> class H>
void HotQueue<V, P, H>::pop() {
    m_size--;
 
    m_heap.pop();
    m_heapSize--;
 
    /*
     * If the heap became empty and there is non-empty bucket afterwards
     * we need to heapify first non-empty bucket. If the heap became empty
     * but there is no non-empty bucket afterwards it may be the case that
     * element will be inserted into the current heap (therefore, do nothing).
     */
    if (!(m_heapSize == 0 && m_heapedBucket != m_lastBucket)) {
        return;
    }
 
    // Find first non-empty bucket.
    do {
        m_heapedBucket++;
    } while (bucketAt(m_heapedBucket) == nullptr);
 
    // Move bucket contents into a heap.
    for (HotQueueNode<V, P>* it = bucketAt(m_heapedBucket); it != nullptr;) {
        m_heapSize++;
        m_heap.push(std::make_pair(it->value, it->priority));
 
        HotQueueNode<V, P>* next = it->next;
        delete it;
        it = next;
    }
    bucketAt(m_heapedBucket) = nullptr;
}
 
template<typename V, typename P, template<typename T, typename C> class H>
void HotQueue<V, P, H>::decrease(typename HotQueue<V, P, H>::Handle& handle, const P& priority) {
    switch (handle.type) {
    case Handle::Type::heap: {
        // Simple case, just use native heap decrease key.
        const HeapHandle& elem = handle.heapHandle;
        m_heap.decrease(elem, std::make_pair(std::get<0>(m_heap.value(elem)), priority));
        break;
    }
    case Handle::Type::bucket:
        // Remove element from bucket (as with ordinary linked-list)...
        HotQueueNode<V, P>* queueNode = std::get<1>(handle.bucketHandle);
        if (queueNode->next != nullptr) {
            queueNode->next->prev = queueNode->prev;
        }
        if (queueNode->prev != nullptr) {
            queueNode->prev->next = queueNode->next;
        } else {
            m_buckets[std::get<0>(handle.bucketHandle)] = queueNode->next;
        }
 
        // ... and push it again with new priority, releasing the memory.
        m_size--;
        handle = push(queueNode->value, priority);
        delete queueNode;
        break;
    }
}
 
}