Program Listing for File PrioQueue.hpp¶

/*
 * PrioQueue.hpp
 *
 *  Created on: 02.03.2017
 *      Author: Henning
 */

#ifndef NETWORKIT_AUXILIARY_PRIO_QUEUE_HPP_
#define NETWORKIT_AUXILIARY_PRIO_QUEUE_HPP_

#include <cstdint>
#include <limits>
#include <set>
#include <vector>

#include <networkit/auxiliary/Log.hpp>

namespace Aux {

template <class Key, class Value>
class PrioQueue {
private:
    using ElemType = std::pair<Key, Value>;

    std::set<ElemType> pqset; // TODO: would std::map work and simplify things?
    std::vector<Key> mapValToKey;

    const Key undefined = std::numeric_limits<Key>::max(); // TODO: make static

protected:
    PrioQueue() = default;

    virtual void remove(const ElemType &elem);

    virtual std::set<std::pair<Key, Value>> content() const;

public:
    PrioQueue(const std::vector<Key> &keys);

    PrioQueue(uint64_t capacity);

    virtual ~PrioQueue() = default;

    virtual void insert(Key key, Value value);

    virtual ElemType peekMin(size_t n = 0);

    virtual ElemType extractMin();

    virtual void changeKey(Key newKey, Value value);

    virtual uint64_t size() const;

    virtual bool empty() const noexcept;

    virtual bool contains(const Value &value) const;

    virtual void remove(const Value &val);

    virtual void clear();

    template <typename L>
    void forElements(L handle) const;

    template <typename C, typename L>
    void forElementsWhile(C condition, L handle) const;

    virtual void print() {
        DEBUG("num entries: ", mapValToKey.size());
        for (uint64_t i = 0; i < mapValToKey.size(); ++i) {
            DEBUG("key: ", mapValToKey[i], ", val: ", i, "\n");
        }
    }
};

template <class Key, class Value>
Aux::PrioQueue<Key, Value>::PrioQueue(const std::vector<Key> &keys) {
    mapValToKey.resize(keys.size());
    uint64_t index = 0;
    for (auto key : keys) {
        insert(key, index);
        ++index;
    }
}

template <class Key, class Value>
Aux::PrioQueue<Key, Value>::PrioQueue(uint64_t capacity) {
    mapValToKey.resize(capacity);
}

template <class Key, class Value>
void Aux::PrioQueue<Key, Value>::insert(Key key, Value value) {
    if (value >= mapValToKey.size()) {
        uint64_t doubledSize = 2 * mapValToKey.size();
        assert(value < doubledSize);
        mapValToKey.resize(doubledSize);
    }
    pqset.insert(std::make_pair(key, value));
    mapValToKey.at(value) = key;
}

template <class Key, class Value>
void Aux::PrioQueue<Key, Value>::remove(const ElemType &elem) {
    remove(elem.second);
}

template <class Key, class Value>
void Aux::PrioQueue<Key, Value>::remove(const Value &val) {
    Key key = mapValToKey.at(val);
    pqset.erase(std::make_pair(key, val));
    mapValToKey.at(val) = undefined;
}

template <class Key, class Value>
std::pair<Key, Value> Aux::PrioQueue<Key, Value>::peekMin(size_t n) {
    assert(pqset.size() > n);
    ElemType elem = *std::next(pqset.begin(), n);
    return elem;
}

template <class Key, class Value>
std::pair<Key, Value> Aux::PrioQueue<Key, Value>::extractMin() {
    assert(!pqset.empty());
    ElemType elem = (*pqset.begin());
    remove(elem);
    return elem;
}

template <class Key, class Value>
void Aux::PrioQueue<Key, Value>::changeKey(Key newKey, Value value) {
    // find and remove element with given key
    remove(value);

    // insert element with new value
    insert(newKey, value);
}

template <class Key, class Value>
uint64_t Aux::PrioQueue<Key, Value>::size() const {
    return pqset.size();
}

template <class Key, class Value>
bool Aux::PrioQueue<Key, Value>::empty() const noexcept {
    return pqset.empty();
}

template <class Key, class Value>
bool Aux::PrioQueue<Key, Value>::contains(const Value &value) const {
    return value < mapValToKey.size() && mapValToKey.at(value) != undefined;
}

template <class Key, class Value>
std::set<std::pair<Key, Value>> Aux::PrioQueue<Key, Value>::content() const {
    return pqset;
}

template <class Key, class Value>
void Aux::PrioQueue<Key, Value>::clear() {
    pqset.clear();
    auto capacity = mapValToKey.size();
    mapValToKey.clear();
    mapValToKey.resize(capacity);
}

template <class Key, class Value>
template <typename L>
void Aux::PrioQueue<Key, Value>::forElements(L handle) const {
    for (auto it = pqset.begin(); it != pqset.end(); ++it) {
        ElemType elem = *it;
        handle(elem.first, elem.second);
    }
}

template <class Key, class Value>
template <typename C, typename L>
void Aux::PrioQueue<Key, Value>::forElementsWhile(C condition, L handle) const {
    for (auto it = pqset.begin(); it != pqset.end(); ++it) {
        if (!condition()) {
            break;
        }
        ElemType elem = *it;
        handle(elem.first, elem.second);
    }
}

} /* namespace Aux */
#endif // NETWORKIT_AUXILIARY_PRIO_QUEUE_HPP_