All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
BucketPQ.h
Go to the documentation of this file.
1 /*
2  * BucketPQ.h
3  *
4  * Created on: 02.03.2017
5  * Author: Henning
6  */
7 
8 #ifndef BUCKETPQ_H_
9 #define BUCKETPQ_H_
10 
11 #include "Log.h"
12 #include "../Globals.h"
13 #include "PrioQueue.h"
14 #include <list>
15 #include <limits>
16 
17 namespace Aux {
18 
19 typedef NetworKit::index index;
20 typedef NetworKit::count count;
21 typedef std::list<index> Bucket;
22 constexpr int64_t none = std::numeric_limits<int64_t>::max();
23 
31 class BucketPQ: public PrioQueue<int64_t, index> {
32 private:
33  std::vector<Bucket> buckets; // the actual buckets
34  std::vector<Bucket::iterator> nodePtr; // keeps track of node positions
35  std::vector<index> myBucket; // keeps track of current bucket for each value
36  int64_t currentMinKey; // current min key
37  int64_t currentMaxKey; // current max key
38  int64_t minAdmissibleKey; // minimum admissible key
39  int64_t maxAdmissibleKey; // maximum admissible key
40  count numElems; // number of elements stored
41  int64_t offset; // offset from minAdmissibleKeys to 0
42 
43 private:
47  BucketPQ(const std::vector<int64_t>& keys) {}
48 
52  BucketPQ(uint64_t capacity) {}
53 
57  void construct(uint64_t capacity);
58 
59 public:
60 
68  BucketPQ(const std::vector<int64_t>& keys, int64_t minAdmissibleKey, int64_t maxAdmissibleKey);
69 
73  BucketPQ(uint64_t capacity, int64_t minAdmissibleKey, int64_t maxAdmissibleKey);
74 
78  virtual ~BucketPQ() = default;
79 
83  virtual void insert(int64_t key, index value) override;
84 
88  virtual std::pair<int64_t, index> extractMin() override;
89 
95  virtual void changeKey(int64_t newKey, index value) override;
96 
100  virtual uint64_t size() const override;
101 
105  virtual void remove(const index& val) override;
106 
107 };
108 
109 } /* namespace Aux */
110 #endif /* BUCKETPQ_H_ */
constexpr int64_t none
Definition: BucketPQ.h:22
virtual std::pair< int64_t, index > extractMin() override
Removes the element with minimum key and returns the key-value pair.
Definition: BucketPQ.cpp:95
NetworKit::index index
Definition: BloomFilter.h:16
std::list< index > Bucket
Definition: BucketPQ.h:21
uint64_t index
Typedefs.
Definition: Globals.h:20
NetworKit::count count
Definition: BloomFilter.h:17
uint64_t count
Definition: Globals.h:21
virtual void changeKey(int64_t newKey, index value) override
Modifies entry with value value.
Definition: BucketPQ.cpp:110
Addressable priority queue for values in the range [0,n) and integer keys (= priorities) in the range...
Definition: BucketPQ.h:31
virtual uint64_t size() const override
Definition: BucketPQ.cpp:115
Priority queue with extract-min and decrease-key.
Definition: PrioQueue.h:23
virtual ~BucketPQ()=default
Default destructor.
virtual void insert(int64_t key, index value) override
Inserts key-value pair (, ).
Definition: BucketPQ.cpp:48