1 module nxt.fibonacci_heap;
2
3 struct Node(V)
4 {
5 @safe pure nothrow @nogc:
6
7 inout(Node*) getPrev() inout { return prev; }
8 inout(Node*) getNext() inout { return next; }
9 inout(Node*) getChild() inout { return child; }
10 inout(Node*) getParent() inout { return parent; }
11
12 V getValue() const { return value; }
13
14 bool isMarked() const { return marked; }
15
16 bool hasChildren() const { return child !is null; }
17 bool hasParent() const { return parent !is null; }
18 private:
19 Node* prev; // also called left
20 Node* next; // also called right
21 Node* child;
22 Node* parent;
23 int degree;
24 bool marked; // also called mark
25
26 V value;
27 };
28
29 /** Fibonacci Heap Container.
30 See_Also: http://www.codeproject.com/Articles/42561/Dijkstra-s-Algorithm-for-Network-Optimization-Usin
31 See_Also: http://www.sanfoundry.com/cpp-program-implement-fibonacci-heap/
32 */
33 struct FibonacciHeap(V)
34 {
35 @safe pure nothrow:
36
37 alias N = Node!V;
38
39 protected:
40 N* root = null; // root node
41
42 public:
43
44 // this()
45 // {
46 // heap = _empty();
47 // }
48
49 /*virtual*/
50 ~this() @nogc
51 {
52 if (root)
53 {
54 _deleteAll(root);
55 }
56 }
57
58 N* insert(V value)
59 {
60 N* ret = _singleton(value);
61 root = _merge(root, ret);
62 return ret;
63 }
64
65 void merge(FibonacciHeap other)
66 {
67 root = _merge(root, other.root);
68 other.root = _empty();
69 }
70
71 bool empty() const @nogc
72 {
73 return root is null;
74 }
75
76 inout(V) minimum() inout @nogc
77 {
78 return root.value;
79 }
80
81 V removeMinimum()
82 {
83 N* old = root;
84 root = _removeMinimum(root);
85 V ret = old.value;
86 delete old;
87 return ret;
88 }
89
90 void decreaseKey(N* n, V value)
91 {
92 root = _decreaseKey(root, n, value);
93 }
94
95 N* find(V value) @nogc
96 {
97 return _find(root, value);
98 }
99
100 private:
101 N* _empty() @nogc
102 {
103 return null;
104 }
105
106 N* _singleton(V value)
107 {
108 N* n = new N; // TODO use std.allocator instead
109 n.value = value;
110 n.prev = n.next = n;
111 n.degree = 0;
112 n.marked = false;
113 n.child = null;
114 n.parent = null;
115 return n;
116 }
117
118 N* _merge(N* a, N* b) @nogc
119 {
120 if (a is null) return b;
121 if (b is null) return a;
122 if (a.value > b.value)
123 {
124 N* temp = a;
125 a = b;
126 b = temp;
127 }
128 N* an = a.next;
129 N* bp = b.prev;
130 a.next = b;
131 b.prev = a;
132 an.prev = bp;
133 bp.next = an;
134 return a;
135 }
136
137 void _deleteAll(N* n)
138 {
139 if (n !is null)
140 {
141 N* c = n;
142 do
143 {
144 N* d = c;
145 c = c.next;
146 _deleteAll(d.child);
147 delete d; // TODO use std.allocator instead
148 }
149 while (c !is n);
150 }
151 }
152
153 void _addChild(N* parent, N* child) @nogc
154 {
155 child.prev = child.next = child;
156 child.parent = parent;
157 parent.degree++;
158 parent.child = _merge(parent.child, child);
159 }
160
161 void _unMarkAndUnParentAll(N* n) @nogc
162 {
163 if (n is null) return;
164 N* c = n;
165 do
166 {
167 c.marked = false;
168 c.parent = null;
169 c = c.next;
170 }
171 while (c !is n);
172 }
173
174 N* _removeMinimum(N* n)
175 {
176 _unMarkAndUnParentAll(n.child);
177 if (n.next == n)
178 {
179 n = n.child;
180 }
181 else
182 {
183 n.next.prev = n.prev;
184 n.prev.next = n.next;
185 n = _merge(n.next, n.child);
186 }
187
188 if (n is null) return n;
189 N*[64] trees; // = { null };
190
191 while (true)
192 {
193 if (trees[n.degree] !is null)
194 {
195 N* t = trees[n.degree];
196 if (t == n)
197 break;
198 trees[n.degree] = null;
199 if (n.value < t.value)
200 {
201 t.prev.next = t.next;
202 t.next.prev = t.prev;
203 _addChild(n, t);
204 }
205 else
206 {
207 t.prev.next = t.next;
208 t.next.prev = t.prev;
209 if (n.next == n)
210 {
211 t.next = t.prev = t;
212 _addChild(t, n);
213 n = t;
214 }
215 else
216 {
217 n.prev.next = t;
218 n.next.prev = t;
219 t.next = n.next;
220 t.prev = n.prev;
221 _addChild(t, n);
222 n = t;
223 }
224 }
225 continue;
226 }
227 else
228 {
229 trees[n.degree] = n;
230 }
231 n = n.next;
232 }
233 N* min = n;
234 do
235 {
236 if (n.value < min.value) min = n;
237 n = n.next;
238 }
239 while (n !is n);
240 return min;
241 }
242
243 N* _cut(N* heap, N* n) @nogc
244 {
245 if (n.next == n)
246 {
247 n.parent.child = null;
248 }
249 else
250 {
251 n.next.prev = n.prev;
252 n.prev.next = n.next;
253 n.parent.child = n.next;
254 }
255 n.next = n.prev = n;
256 n.marked = false;
257 return _merge(heap, n);
258 }
259
260 N* _decreaseKey(N* heap, N* n, V value) @nogc
261 {
262 if (n.value < value) return heap;
263 n.value = value;
264 if (n.value < n.parent.value)
265 {
266 heap = _cut(heap, n);
267 N* parent = n.parent;
268 n.parent = null;
269
270 while (parent !is null && parent.marked)
271 {
272 heap = _cut(heap, parent);
273 n = parent;
274 parent = n.parent;
275 n.parent = null;
276 }
277
278 if (parent !is null &&
279 parent.parent !is null)
280 {
281 parent.marked = true;
282 }
283 }
284 return heap;
285 }
286
287 N* _find(N* heap, V value) @nogc
288 {
289 N* n = heap;
290
291 if (n is null)
292 return null;
293
294 do
295 {
296 if (n.value == value) return n;
297 N* ret = _find(n.child, value);
298 if (ret) return ret;
299 n = n.next;
300 }
301 while (n !is heap);
302
303 return null;
304 }
305 };
306
307 void dumpDot(V)(ref FibonacciHeap!V _fh) @safe
308 {
309 import std.stdio: writeln, writefln;
310
311 writeln(`digraph G {`);
312 if (_fh.root is null)
313 {
314 writeln(`empty;\n}`);
315 return;
316 }
317 writefln(`minimum -> "%x" [constraint = false];`, _fh.root);
318 Node!int* c = _fh.root;
319
320 do
321 {
322 dumpDotChildren(c);
323 c = c.getNext();
324 }
325 while (c !is _fh.root);
326
327 writeln(`}`);
328 }
329
330 void dumpDotChildren(ref Node!int* n) @safe
331 {
332 import std.stdio: writeln, writefln;
333
334 writefln(`"%x" -> "%x" [constraint = false, arrowhead = lnormal];`, n, n.getNext());
335 writefln(`"%x" -> "%x" [constraint = false, arrowhead = ornormal];`, n, n.getPrev());
336
337 if (n.isMarked())
338 writefln(`"%x" [style = filled, fillcolor = grey];`, n);
339
340 if (n.hasParent())
341 {
342 writefln(`"%x" -> "%x" [constraint = false, arrowhead = onormal];`, n, n.getParent());
343 }
344
345 writefln(`"%x" [label = %d];`, n, n.getValue());
346
347 if (n.hasChildren())
348 {
349 Node!int* c = n.getChild();
350 do
351 {
352 writefln(`"%x" -> "%x";`, n,c);
353 dumpDotChildren(c);
354 c = c.getNext();
355 }
356 while (c !is n.getChild());
357 }
358 }
359
360 version(unittest)
361 void generate(ref FibonacciHeap!int h) @safe pure nothrow
362 {
363 h.insert(2);
364 h.insert(3);
365 h.insert(1);
366 h.insert(4);
367
368 h.removeMinimum();
369 h.removeMinimum();
370
371 h.insert(5);
372 h.insert(7);
373
374 h.removeMinimum();
375
376 h.insert(2);
377
378 Node!int* nine = h.insert(90);
379
380 h.removeMinimum();
381 h.removeMinimum();
382 h.removeMinimum();
383
384 for (int i = 0; i < 20; i += 2)
385 h.insert(30-i);
386 for (int i = 0; i < 4; i++)
387 h.removeMinimum();
388 for (int i = 0; i < 20; i+= 2)
389 h.insert(30-i);
390
391 h.insert(23);
392
393 for (int i = 0; i < 7; i++)
394 h.removeMinimum();
395
396 h.decreaseKey(nine, 1);
397 h.decreaseKey(h.find(28), 2);
398 h.decreaseKey(h.find(23), 3);
399 }
400
401 @safe pure nothrow unittest
402 {
403 FibonacciHeap!int h;
404
405 h.insert(4); assert(h.minimum == 4);
406 h.insert(3); assert(h.minimum == 3);
407 h.insert(2); assert(h.minimum == 2);
408 h.insert(1); assert(h.minimum == 1);
409
410 h.removeMinimum; assert(h.minimum == 2);
411 h.removeMinimum; assert(h.minimum == 3);
412
413 h.insert(0); assert(h.minimum == 0);
414
415 h.removeMinimum; assert(h.minimum == 3);
416 h.removeMinimum; assert(h.minimum == 4);
417 h.removeMinimum; assert(h.empty);
418 }
419
420 // Write output to file X and process it with: "dot -O -Tsvg X"
421 @safe pure nothrow unittest
422 {
423 FibonacciHeap!int h;
424 generate(h);
425 }
426
427 @safe unittest
428 {
429 FibonacciHeap!int h;
430 generate(h);
431
432 h.dumpDot();
433 }