BucketPriorityQueue.h

Go to the documentation of this file.

#pragma once
 
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <vector>
 
#include "storm-dft/builder/DftExplorationHeuristic.h"
 
namespace storm::dft {
namespace storage {
 
template<class PriorityType>
class BucketPriorityQueue {
    using PriorityTypePointer = std::shared_ptr<PriorityType>;
 
   public:
    explicit BucketPriorityQueue(size_t nrBuckets, double lowerValue, double ratio, bool higher);
 
    BucketPriorityQueue(BucketPriorityQueue const& queue) = default;
 
    virtual ~BucketPriorityQueue() = default;
 
    void fix();
 
    bool empty() const;
 
    std::size_t size() const;
 
    PriorityTypePointer const& top() const;
 
    void push(PriorityTypePointer const& item);
 
    void update(PriorityTypePointer const& item, double oldPriority);
 
    PriorityTypePointer pop();
 
    void print(std::ostream& out) const;
 
    void printSizes(std::ostream& out) const;
 
   private:
    size_t getBucket(double priority) const;
 
    // List of buckets
    std::vector<std::vector<PriorityTypePointer>> buckets;
 
    // Bucket containing all items which should be considered immediately
    std::vector<PriorityTypePointer> immediateBucket;
 
    // Index of first bucket which contains items
    size_t currentBucket;
 
    // Number of unsorted items in current bucket
    size_t nrUnsortedItems;
 
    // Comparison function for priorities
    std::function<bool(PriorityTypePointer, PriorityTypePointer)> compare;
 
    // Minimal value
    double lowerValue;
 
    bool higher;
 
    bool AUTOSORT = false;
 
    double logBase;
 
    // Number of available buckets
    size_t nrBuckets;
};
 
}  // namespace storage
}  // namespace storm::dft