All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
PrioQueue.h
Go to the documentation of this file.
1 /*
2  * PrioQueue.h
3  *
4  * Created on: 02.03.2017
5  * Author: Henning
6  */
7 
8 #ifndef PRIORITYQUEUE_H_
9 #define PRIORITYQUEUE_H_
10 
11 #include "../auxiliary/Log.h"
12 #include <vector>
13 #include <set>
14 
15 namespace Aux {
16 
22 template<class Key, class Value>
23 class PrioQueue {
24 private:
25  typedef std::pair<Key, Value> ElemType;
26 
27  std::set<ElemType> pqset; // TODO: would std::map work and simplify things?
28  std::vector<Key> mapValToKey;
29 
30  const Key undefined = std::numeric_limits<Key>::max(); // TODO: make static
31 
32 
33 protected:
34 
38  PrioQueue() = default;
39 
43  virtual void remove(const ElemType& elem);
44 
48  virtual std::set<std::pair<Key, Value>> content() const;
49 
50 
51 public:
52 
57  PrioQueue(const std::vector<Key>& keys);
58 
62  PrioQueue(uint64_t capacity);
63 
67  virtual ~PrioQueue() = default;
68 
72  virtual void insert(Key key, Value value);
73 
77  virtual ElemType extractMin();
78 
84  virtual void changeKey(Key newKey, Value value);
85 
86  [[deprecated]]
87  virtual void decreaseKey(Key newKey, Value value) {
88  changeKey(newKey, value);
89  }
90 
94  virtual uint64_t size() const;
95 
99  virtual void remove(const Value& val);
100 
104  virtual void print() {
105  DEBUG("num entries: ", mapValToKey.size());
106  for (uint64_t i = 0; i < mapValToKey.size(); ++i) {
107  DEBUG("key: ", mapValToKey[i], ", val: ", i, "\n");
108  }
109  }
110 };
111 
112 
113 template<class Key, class Value>
114 Aux::PrioQueue<Key, Value>::PrioQueue(const std::vector<Key>& keys) {
115  mapValToKey.resize(keys.size());
116  uint64_t index = 0;
117  for (auto key: keys) {
118  insert(key, index);
119  ++index;
120  }
121 }
122 
123 template<class Key, class Value>
125  mapValToKey.resize(capacity);
126 }
127 
128 template<class Key, class Value>
129 inline void Aux::PrioQueue<Key, Value>::insert(Key key, Value value) {
130  if (value >= mapValToKey.size()) {
131  uint64_t doubledSize = 2 * mapValToKey.size();
132  assert(value < doubledSize);
133  mapValToKey.resize(doubledSize);
134  }
135  pqset.insert(std::make_pair(key, value));
136  mapValToKey.at(value) = key;
137 }
138 
139 template<class Key, class Value>
140 inline void Aux::PrioQueue<Key, Value>::remove(const ElemType& elem) {
141  remove(elem.second);
142 }
143 
144 template<class Key, class Value>
145 inline void Aux::PrioQueue<Key, Value>::remove(const Value& val) {
146  Key key = mapValToKey.at(val);
147 // DEBUG("key: ", key);
148  pqset.erase(std::make_pair(key, val));
149  mapValToKey.at(val) = undefined;
150 }
151 
152 template<class Key, class Value>
153 std::pair<Key, Value> Aux::PrioQueue<Key, Value>::extractMin() {
154  assert(pqset.size() > 0);
155  ElemType elem = (* pqset.begin());
156  remove(elem);
157  return elem;
158 }
159 
160 template<class Key, class Value>
161 inline void Aux::PrioQueue<Key, Value>::changeKey(Key newKey, Value value) {
162  // find and remove element with given key
163  remove(value);
164 
165  // insert element with new value
166  insert(newKey, value);
167 }
168 
169 template<class Key, class Value>
170 inline uint64_t Aux::PrioQueue<Key, Value>::size() const {
171  return pqset.size();
172 }
173 
174 template<class Key, class Value>
175 inline std::set<std::pair<Key, Value>> Aux::PrioQueue<Key, Value>::content() const {
176  return pqset;
177 }
178 
179 
180 } /* namespace Aux */
181 #endif /* PRIORITYQUEUE_H_ */
virtual ~PrioQueue()=default
Default destructor.
virtual void insert(Key key, Value value)
Inserts key-value pair stored in elem.
Definition: PrioQueue.h:129
NetworKit::index index
Definition: BloomFilter.h:16
virtual void remove(const ElemType &elem)
Removes key-value pair given by elem.
Definition: PrioQueue.h:140
virtual void decreaseKey(Key newKey, Value value)
Definition: PrioQueue.h:87
#define DEBUG(...)
Definition: Log.h:82
virtual ElemType extractMin()
Removes the element with minimum key and returns it.
Definition: PrioQueue.h:153
PrioQueue()=default
Default constructor without functionality.
virtual void print()
DEBUGGING.
Definition: PrioQueue.h:104
class deprecated("Use MaximalCliques instead.")]] MaxClique
Exact algorithm for computing the size of the largest clique in a graph.
Definition: MaxClique.h:24
virtual void changeKey(Key newKey, Value value)
Modifies entry with value value.
Definition: PrioQueue.h:161
virtual std::set< std::pair< Key, Value > > content() const
Definition: PrioQueue.h:175
Priority queue with extract-min and decrease-key.
Definition: PrioQueue.h:23
virtual uint64_t size() const
Definition: PrioQueue.h:170