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 /// 402 @safe pure nothrow unittest 403 { 404 FibonacciHeap!int h; 405 406 h.insert(4); assert(h.minimum == 4); 407 h.insert(3); assert(h.minimum == 3); 408 h.insert(2); assert(h.minimum == 2); 409 h.insert(1); assert(h.minimum == 1); 410 411 h.removeMinimum; assert(h.minimum == 2); 412 h.removeMinimum; assert(h.minimum == 3); 413 414 h.insert(0); assert(h.minimum == 0); 415 416 h.removeMinimum; assert(h.minimum == 3); 417 h.removeMinimum; assert(h.minimum == 4); 418 h.removeMinimum; assert(h.empty); 419 } 420 421 // Write output to file X and process it with: "dot -O -Tsvg X" 422 @safe pure nothrow unittest 423 { 424 FibonacciHeap!int h; 425 generate(h); 426 } 427 428 /// 429 @safe unittest 430 { 431 FibonacciHeap!int h; 432 generate(h); 433 434 h.dumpDot(); 435 }