Program Listing for File BucketPriorityQueue.hpp¶

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

#ifndef NETWORKIT_AUXILIARY_BUCKET_PRIORITY_QUEUE_HPP_
#define NETWORKIT_AUXILIARY_BUCKET_PRIORITY_QUEUE_HPP_

#include <algorithm>
#include <concepts>
#include <cstdint>
#include <limits>
#include <ranges>
#include <span>
#include <stdexcept>
#include <type_traits>
#include <vector>

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

namespace Aux {

using index = NetworKit::index;
using count = NetworKit::count;

template <typename T>
concept SignedIntegral = std::integral<T> && std::is_signed_v<T>;

template <typename T>
concept IntegralValue = std::integral<T> && !std::same_as<std::remove_cvref_t<T>, bool>;

template <SignedIntegral KeyType = int64_t, IntegralValue ValueType = index>
class BucketPriorityQueue : public PrioQueue<KeyType, ValueType> {
private:
    using BucketIndex = index;

    static constexpr KeyType noneKey = std::numeric_limits<KeyType>::max();
    static constexpr ValueType noneValue = std::numeric_limits<ValueType>::max();
    static constexpr BucketIndex noneBucket = std::numeric_limits<BucketIndex>::max();

    std::vector<ValueType> bucketHead;
    std::vector<ValueType> previous;
    std::vector<ValueType> next;
    std::vector<BucketIndex> myBucket; // keeps track of current bucket for each value
    KeyType currentMinKey;             // current min key
    KeyType currentMaxKey;             // current max key
    KeyType minAdmissibleKey;          // minimum admissible key
    KeyType maxAdmissibleKey;          // maximum admissible key
    count numElems;                    // number of elements stored
    KeyType offset;                    // offset from minAdmissibleKeys to 0

    static index valueToIndex(ValueType value) {
        if constexpr (std::is_signed_v<ValueType>) {
            assert(value >= 0);
        }
        return static_cast<index>(value);
    }

    static void assureCapacityFitsValueType(uint64_t capacity) {
        if (capacity > static_cast<uint64_t>(noneValue)) {
            throw std::invalid_argument("capacity cannot be represented by ValueType");
        }
    }

    BucketPriorityQueue(std::span<const KeyType>) {}

    BucketPriorityQueue(uint64_t) {}

    void construct(uint64_t capacity);

public:
    BucketPriorityQueue(std::span<const KeyType> keys, KeyType minAdmissibleKey,
                        KeyType maxAdmissibleKey);

    BucketPriorityQueue(uint64_t capacity, KeyType minAdmissibleKey, KeyType maxAdmissibleKey);

    ~BucketPriorityQueue() override = default;

    void insert(KeyType key, ValueType value) override;

    std::pair<KeyType, ValueType> getMin();

    std::pair<KeyType, ValueType> extractMin() override;

    void changeKey(KeyType newKey, ValueType value) override;

    uint64_t size() const override;

    bool empty() const noexcept override;

    bool contains(const ValueType &value) const override;

    void remove(const ValueType &value) override;

    void clear() override;

    virtual KeyType getKey(const ValueType &val);
};

using BucketPQ = BucketPriorityQueue<int64_t, index>;

} /* namespace Aux */

#include <networkit/auxiliary/BucketPriorityQueueImpl.hpp>

#endif // NETWORKIT_AUXILIARY_BUCKET_PRIORITY_QUEUE_HPP_