Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
HotQueue.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <cmath>
35#include <functional>
36#include <limits>
37#include <utility>
38#include <vector>
39
40namespace ogdf {
41
42
44template<typename V, typename P>
57
59
67template<typename V, typename P, typename HeapHandle>
69private:
70 enum class Type { heap, bucket } type;
71
72 union {
74 HeapHandle heapHandle;
76 std::pair<std::size_t, HotQueueNode<V, P>*> bucketHandle;
77 };
78
80 HotQueueHandle(HeapHandle handle) : type(Type::heap), heapHandle(handle) { }
81
85
86public:
88
90 type = other.type;
91 switch (type) {
92 case Type::heap:
93 heapHandle = other.heapHandle;
94 break;
95 case Type::bucket:
96 bucketHandle = other.bucketHandle;
97 break;
98 }
99
100 return *this;
101 }
102
103 template<typename V1, typename P1, template<typename T, typename C> class H1>
104 friend class HotQueue;
105};
106
108
119template<typename V, typename P, template<typename T, typename C> class H>
120class HotQueue {
121private:
122 struct HeapComparator;
124
125 std::size_t m_size;
126
128 std::size_t m_heapSize;
129
130 std::vector<HotQueueNode<V, P>*> m_buckets;
131
132public:
134
136
140 HotQueue(const P& change, std::size_t levels);
141
143 ~HotQueue();
144
146 const V& top() const;
147
149
154 Handle push(const V& value, const P& priority);
155
157
160 void pop();
161
163
171 void decrease(Handle& handle, const P& priority);
172
174 std::size_t size() const { return m_size; }
175
177 bool empty() const { return size() == 0; }
178
179private:
182 bool operator()(const std::pair<V, P>& a, const std::pair<V, P>& b) const {
183 return std::get<1>(a) < std::get<1>(b);
184 }
185 };
186
187 std::size_t m_heapedBucket;
188 std::size_t m_lastBucket;
189
191
193 std::size_t bucketIndex(const P& priority) {
194 return (std::size_t)std::round(priority / m_bucketSpan);
195 }
196
198 HotQueueNode<V, P>*& bucketAt(std::size_t index) { return m_buckets[index % m_buckets.size()]; }
199
200 static constexpr std::size_t NONE = std::numeric_limits<size_t>::max();
201};
202
203template<typename V, typename P, template<typename T, typename C> class H>
204HotQueue<V, P, H>::HotQueue(const P& change, std::size_t levels)
205 : m_size(0)
206 , m_heapSize(0)
207 , m_buckets(levels, nullptr)
208 , m_heapedBucket(NONE)
209 , m_lastBucket(0)
210 , m_bucketSpan((int)std::round(change / (levels - 1))) { }
211
212template<typename V, typename P, template<typename T, typename C> class H>
214 if (empty()) {
215 return;
216 }
217 for (auto& bucket : m_buckets) {
218 if (bucket != nullptr) {
219 for (HotQueueNode<V, P>* it = bucket; it != nullptr;) {
220 HotQueueNode<V, P>* next = it->next;
221 delete it;
222 it = next;
223 }
224 }
225 }
226}
227
228template<typename V, typename P, template<typename T, typename C> class H>
229inline const V& HotQueue<V, P, H>::top() const {
230 return std::get<0>(m_heap.top());
231}
232
233template<typename V, typename P, template<typename T, typename C> class H>
234typename HotQueue<V, P, H>::Handle HotQueue<V, P, H>::push(const V& value, const P& priority) {
235 m_size++;
236
237 std::size_t ind = bucketIndex(priority);
238
239 if (m_heapedBucket == NONE) {
240 m_heapedBucket = ind;
241 }
242
243 if (ind == m_heapedBucket) {
244 m_heapSize++;
245 HeapHandle handle = m_heap.push(std::make_pair(value, priority));
246 return Handle(handle);
247 } else {
248 HotQueueNode<V, P>* queueNode = new HotQueueNode<V, P>(value, priority);
249
250 if (bucketAt(ind) != nullptr) {
251 bucketAt(ind)->prev = queueNode;
252 }
253 queueNode->next = bucketAt(ind);
254 bucketAt(ind) = queueNode;
255
256 m_lastBucket = std::max(m_lastBucket, ind);
257 return Handle(ind, queueNode);
258 }
259}
260
261template<typename V, typename P, template<typename T, typename C> class H>
263 m_size--;
264
265 m_heap.pop();
266 m_heapSize--;
267
268 /*
269 * If the heap became empty and there is non-empty bucket afterwards
270 * we need to heapify first non-empty bucket. If the heap became empty
271 * but there is no non-empty bucket afterwards it may be the case that
272 * element will be inserted into the current heap (therefore, do nothing).
273 */
274 if (!(m_heapSize == 0 && m_heapedBucket != m_lastBucket)) {
275 return;
276 }
277
278 // Find first non-empty bucket.
279 do {
280 m_heapedBucket++;
281 } while (bucketAt(m_heapedBucket) == nullptr);
282
283 // Move bucket contents into a heap.
284 for (HotQueueNode<V, P>* it = bucketAt(m_heapedBucket); it != nullptr;) {
285 m_heapSize++;
286 m_heap.push(std::make_pair(it->value, it->priority));
287
288 HotQueueNode<V, P>* next = it->next;
289 delete it;
290 it = next;
291 }
292 bucketAt(m_heapedBucket) = nullptr;
293}
294
295template<typename V, typename P, template<typename T, typename C> class H>
296void HotQueue<V, P, H>::decrease(typename HotQueue<V, P, H>::Handle& handle, const P& priority) {
297 switch (handle.type) {
298 case Handle::Type::heap: {
299 // Simple case, just use native heap decrease key.
300 const HeapHandle& elem = handle.heapHandle;
301 m_heap.decrease(elem, std::make_pair(std::get<0>(m_heap.value(elem)), priority));
302 break;
303 }
304 case Handle::Type::bucket:
305 // Remove element from bucket (as with ordinary linked-list)...
306 HotQueueNode<V, P>* queueNode = std::get<1>(handle.bucketHandle);
307 if (queueNode->next != nullptr) {
308 queueNode->next->prev = queueNode->prev;
309 }
310 if (queueNode->prev != nullptr) {
311 queueNode->prev->next = queueNode->next;
312 } else {
313 m_buckets[std::get<0>(handle.bucketHandle)] = queueNode->next;
314 }
315
316 // ... and push it again with new priority, releasing the memory.
317 m_size--;
318 handle = push(queueNode->value, priority);
319 delete queueNode;
320 break;
321 }
322}
323
324}
Heap-on-Top queue implementation.
Definition HotQueue.h:120
std::size_t bucketIndex(const P &priority)
Computes bucket index of given priority.
Definition HotQueue.h:193
std::size_t m_lastBucket
Index of highest, non-empty bucket.
Definition HotQueue.h:188
static constexpr std::size_t NONE
Definition HotQueue.h:200
HotQueueNode< V, P > *& bucketAt(std::size_t index)
Provides access to bucket at given index.
Definition HotQueue.h:198
bool empty() const
Checks whether the heap is empty.
Definition HotQueue.h:177
H< std::pair< V, P >, HeapComparator > m_heap
Underlying heap structure.
Definition HotQueue.h:127
HotQueue(const P &change, std::size_t levels)
Creates empty Heap-on-Top queue.
Definition HotQueue.h:204
typename H< std::pair< V, P >, HeapComparator >::Handle HeapHandle
Definition HotQueue.h:123
~HotQueue()
Releases all buckets on destruction.
Definition HotQueue.h:213
std::size_t m_heapedBucket
Index of currently heaped bucket.
Definition HotQueue.h:187
const P m_bucketSpan
Length of the interval covered by each bucket.
Definition HotQueue.h:190
const V & top() const
Returns reference to the top element in the heap.
Definition HotQueue.h:229
std::size_t m_heapSize
Size of underlying heap.
Definition HotQueue.h:128
void pop()
Removes the top element from the heap.
Definition HotQueue.h:262
std::vector< HotQueueNode< V, P > * > m_buckets
Array of buckets.
Definition HotQueue.h:130
void decrease(Handle &handle, const P &priority)
Decreases value of the given handle to priority.
Definition HotQueue.h:296
Handle push(const V &value, const P &priority)
Inserts a new node with given value and priority into a heap.
Definition HotQueue.h:234
std::size_t m_size
Number of total elements in the heap.
Definition HotQueue.h:125
HotQueueHandle< V, P, HeapHandle > Handle
Definition HotQueue.h:133
std::size_t size() const
Number of elements contained within the heap.
Definition HotQueue.h:174
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
Definition GML.h:110
Comparator used by underlying heap.
Definition HotQueue.h:181
bool operator()(const std::pair< V, P > &a, const std::pair< V, P > &b) const
Definition HotQueue.h:182
Heap-on-Top handle to inserted items.
Definition HotQueue.h:68
std::pair< std::size_t, HotQueueNode< V, P > * > bucketHandle
Handle to bucket element (bucket index and list iterator).
Definition HotQueue.h:76
HeapHandle heapHandle
Handle to underlying heap.
Definition HotQueue.h:74
HotQueueHandle & operator=(const HotQueueHandle &other)
Definition HotQueue.h:89
HotQueueHandle(const HotQueueHandle &other)
Definition HotQueue.h:87
HotQueueHandle(HeapHandle handle)
Creates heap-type handle.
Definition HotQueue.h:80
HotQueueHandle(std::size_t index, HotQueueNode< V, P > *queueNode)
Creates bucket-type handle.
Definition HotQueue.h:83
enum ogdf::HotQueueHandle::Type type
Union tag.
Heap-on-Top bucket element.
Definition HotQueue.h:45
HotQueueNode< V, P > * prev
Definition HotQueue.h:49
HotQueueNode< V, P > * next
Definition HotQueue.h:50
HotQueueNode(const V &val, const P &pr)
Definition HotQueue.h:54