Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
RadixHeap.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <array>
35#include <functional>
36#include <utility>
37#include <vector>
38
39namespace ogdf {
40
41
42template<typename V, typename P>
54
56
68template<typename V, typename P>
69class RadixHeap {
70public:
72 RadixHeap();
73
75 ~RadixHeap();
76
77
79
84 RadixHeapNode<V, P>* push(const V& value, const P& priority);
85
87
92 V pop();
93
95 std::size_t size() const { return m_size; }
96
98 bool empty() const { return size() == 0; }
99
100private:
102 static constexpr std::size_t BITS = sizeof(P) * 8;
103
104 std::size_t m_size;
105
108 std::array<Bucket, BITS + 1> m_buckets;
109
112
114 template<typename T>
115 static std::size_t msbSet(T mask) {
116 std::size_t i = 0;
117 while (mask != 0) {
118 mask >>= 1;
119 i++;
120 }
121 return i;
122 }
123
124#ifdef __has_builtin
125# if __has_builtin(__builtin_clz)
126 static std::size_t msbSet(unsigned int mask) {
127 return mask == 0 ? 0 : (BITS - __builtin_clz(mask));
128 }
129
130 static std::size_t msbSet(unsigned long mask) {
131 return mask == 0 ? 0 : (BITS - __builtin_clzl(mask));
132 }
133
134 static std::size_t msbSet(unsigned long long mask) {
135 return mask == 0 ? 0 : (BITS - __builtin_clzll(mask));
136 }
137# endif
138#endif
139};
140
141template<typename V, typename P>
142RadixHeap<V, P>::RadixHeap() : m_size(0), m_minimum(0), m_bucketMask(0) {
143 m_buckets.fill(nullptr);
144}
145
146template<typename V, typename P>
148 for (Bucket& bucket : m_buckets) {
149 auto it = bucket;
150 while (it != nullptr) {
151 auto next = it->next;
152 delete it;
153 it = next;
154 }
155 }
156}
157
158template<typename V, typename P>
159RadixHeapNode<V, P>* RadixHeap<V, P>::push(const V& value, const P& priority) {
160 m_size++;
161
162 RadixHeapNode<V, P>* heapNode = new RadixHeapNode<V, P>(value, priority);
163 insert(heapNode);
164 return heapNode;
165}
166
167template<typename V, typename P>
169 m_size--;
170
171 if (m_buckets[0] != nullptr) {
172 V result = std::move(m_buckets[0]->value);
173
174 Bucket tmp = m_buckets[0]->next;
175 delete m_buckets[0];
176 m_buckets[0] = tmp;
177
178 if (m_buckets[0] != nullptr) {
179 m_buckets[0]->prev = nullptr;
180 }
181 return result;
182 }
183
184 std::size_t ind = BITS + 1 - msbSet(m_bucketMask);
185
186 Bucket bucket = m_buckets[ind];
187 m_buckets[ind] = nullptr;
188 if (ind != 0) {
189 m_bucketMask ^= (P(1) << (8 * sizeof(P) - ind));
190 }
191
192
193 Bucket min = bucket;
194 for (Bucket it = bucket; it != nullptr; it = it->next) {
195 if (it->priority < min->priority) {
196 min = it;
197 }
198 }
199
200 if (min->prev != nullptr) {
201 min->prev->next = min->next;
202 } else {
203 bucket = min->next;
204 }
205
206 if (min->next != nullptr) {
207 min->next->prev = min->prev;
208 }
209
210 V result = std::move(min->value);
211 m_minimum = std::move(min->priority);
212 delete min;
213
214 while (bucket != nullptr) {
215 Bucket next = bucket->next;
216 bucket->prev = nullptr;
217 insert(bucket);
218
219 bucket = next;
220 }
221
222 return result;
223}
224
225template<typename V, typename P>
227 std::size_t ind = msbSet(heapNode->priority ^ m_minimum);
228
229 heapNode->next = m_buckets[ind];
230 if (m_buckets[ind] != nullptr) {
231 m_buckets[ind]->prev = heapNode;
232 }
233 m_buckets[ind] = heapNode;
234
235 if (ind != 0) {
236 m_bucketMask |= (P(1) << (BITS - ind));
237 }
238}
239
240}
Radix heap data structure implementation.
Definition RadixHeap.h:69
RadixHeapNode< V, P > * push(const V &value, const P &priority)
Inserts a new node with given value and priority into a heap.
Definition RadixHeap.h:159
static constexpr std::size_t BITS
Definition RadixHeap.h:102
~RadixHeap()
Destructs the heap.
Definition RadixHeap.h:147
V pop()
Removes the top element from the heap and returns its value.
Definition RadixHeap.h:168
void insert(RadixHeapNode< V, P > *heapNode)
Buckets with values.
Definition RadixHeap.h:226
RadixHeap()
Creates empty heap.
Definition RadixHeap.h:142
bool empty() const
Checks whether the heap is empty.
Definition RadixHeap.h:98
std::array< Bucket, BITS+1 > m_buckets
Mask describing state of buckets (for fast lookup).
Definition RadixHeap.h:108
P m_bucketMask
Priority of the lowest element so far.
Definition RadixHeap.h:107
std::size_t m_size
Definition RadixHeap.h:104
P m_minimum
Number of elements.
Definition RadixHeap.h:106
std::size_t size() const
Number of elements contained within the heap.
Definition RadixHeap.h:95
static std::size_t msbSet(T mask)
Returns most significant bit set on given mask.
Definition RadixHeap.h:115
RadixHeapNode< V, P > * next
Definition RadixHeap.h:49
RadixHeapNode(const V &nodeValue, const P &nodePriority)
Definition RadixHeap.h:51
RadixHeapNode< V, P > * prev
Definition RadixHeap.h:48
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.