Program Listing for File BucketPQ.hpp¶

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

#ifndef NETWORKIT_AUXILIARY_BUCKET_PQ_HPP_
#define NETWORKIT_AUXILIARY_BUCKET_PQ_HPP_

#include <limits>
#include <list>

#include <networkit/Globals.hpp>
#include <networkit/auxiliary/PrioQueue.hpp>

namespace Aux {

using index = NetworKit::index;
using count = NetworKit::count;
using Bucket = std::list<index>;
constexpr int64_t none = std::numeric_limits<int64_t>::max();

class BucketPQ : public PrioQueue<int64_t, index> {
private:
    std::vector<Bucket> buckets; // the actual buckets
    static Bucket dummyBucket;
    static const Bucket::iterator invalidPtr;

    struct OptionalIterator {
        bool valid;
        Bucket::iterator iter;

        void reset() {
            valid = false;
            iter = invalidPtr;
        }
        OptionalIterator() { reset(); }
        OptionalIterator(bool valid, Bucket::iterator iter) : valid(valid), iter(iter) {}
    };

    std::vector<OptionalIterator> nodePtr; // keeps track of node positions
    std::vector<index> myBucket;           // keeps track of current bucket for each value
    int64_t currentMinKey;                 // current min key
    int64_t currentMaxKey;                 // current max key
    int64_t minAdmissibleKey;              // minimum admissible key
    int64_t maxAdmissibleKey;              // maximum admissible key
    count numElems;                        // number of elements stored
    int64_t offset;                        // offset from minAdmissibleKeys to 0

    BucketPQ(const std::vector<int64_t> &) {}

    BucketPQ(uint64_t) {}

    void construct(uint64_t capacity);

public:
    BucketPQ(const std::vector<int64_t> &keys, int64_t minAdmissibleKey, int64_t maxAdmissibleKey);

    BucketPQ(uint64_t capacity, int64_t minAdmissibleKey, int64_t maxAdmissibleKey);

    ~BucketPQ() override = default;

    void insert(int64_t key, index value) override;

    std::pair<int64_t, index> getMin();

    std::pair<int64_t, index> extractMin() override;

    void changeKey(int64_t newKey, index value) override;

    uint64_t size() const override;

    bool empty() const noexcept override;

    bool contains(const index &value) const override;

    void remove(const index &val) override;

    virtual int64_t getKey(const index &val);
};

} /* namespace Aux */
#endif // NETWORKIT_AUXILIARY_BUCKET_PQ_HPP_