Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 1247x 1247x 1247x 1247x 1247x 1247x 1247x 1247x 26x 26x 52411x 52411x 26x 26x 6114x 6114x 6114x 6114x 6114x 6114x 6114x 6114x 6114x 26x 26x 15730x 15730x 26x 26x 9089x 9089x 9089x 9089x 9089x 9089x 9089x 19646x 19646x 19646x 19646x 19646x 19646x 17356x 18398x 17356x 17356x 17356x 9089x 9089x 9089x 9089x 26x 26x 6115x 6115x 6115x 6115x 6115x 6115x 20306x 20306x 20306x 19593x 19593x 19635x 19593x 19593x 6115x 6115x 6115x 6115x 26x 26x 4330x 4330x 4330x 4330x 4330x 4330x 2834x 2834x 2833x 2833x 2834x 4330x 26x 26x 3707x 3707x 3707x 3707x 3702x 3702x 3702x 3702x 3707x 26x | 'use strict';
const {
Array,
Symbol,
} = primordials;
const kCompare = Symbol('compare');
const kHeap = Symbol('heap');
const kSetPosition = Symbol('setPosition');
const kSize = Symbol('size');
// The PriorityQueue is a basic implementation of a binary heap that accepts
// a custom sorting function via its constructor. This function is passed
// the two nodes to compare, similar to the native Array#sort. Crucially
// this enables priority queues that are based on a comparison of more than
// just a single criteria.
module.exports = class PriorityQueue {
constructor(comparator, setPosition) {
if (comparator !== undefined)
this[kCompare] = comparator;
if (setPosition !== undefined)
this[kSetPosition] = setPosition;
this[kHeap] = new Array(64);
this[kSize] = 0;
}
[kCompare](a, b) {
return a - b;
}
insert(value) {
const heap = this[kHeap];
const pos = ++this[kSize];
heap[pos] = value;
if (heap.length === pos)
heap.length *= 2;
this.percolateUp(pos);
}
peek() {
return this[kHeap][1];
}
percolateDown(pos) {
const compare = this[kCompare];
const setPosition = this[kSetPosition];
const heap = this[kHeap];
const size = this[kSize];
const item = heap[pos];
while (pos * 2 <= size) {
let childIndex = pos * 2 + 1;
if (childIndex > size || compare(heap[pos * 2], heap[childIndex]) < 0)
childIndex = pos * 2;
const child = heap[childIndex];
if (compare(item, child) <= 0)
break;
if (setPosition !== undefined)
setPosition(child, pos);
heap[pos] = child;
pos = childIndex;
}
heap[pos] = item;
if (setPosition !== undefined)
setPosition(item, pos);
}
percolateUp(pos) {
const heap = this[kHeap];
const compare = this[kCompare];
const setPosition = this[kSetPosition];
const item = heap[pos];
while (pos > 1) {
const parent = heap[pos / 2 | 0];
if (compare(parent, item) <= 0)
break;
heap[pos] = parent;
if (setPosition !== undefined)
setPosition(parent, pos);
pos = pos / 2 | 0;
}
heap[pos] = item;
if (setPosition !== undefined)
setPosition(item, pos);
}
removeAt(pos) {
const heap = this[kHeap];
const size = --this[kSize];
heap[pos] = heap[size + 1];
heap[size + 1] = undefined;
if (size > 0 && pos <= size) {
if (pos > 1 && this[kCompare](heap[pos / 2 | 0], heap[pos]) > 0)
this.percolateUp(pos);
else
this.percolateDown(pos);
}
}
shift() {
const heap = this[kHeap];
const value = heap[1];
if (value === undefined)
return;
this.removeAt(1);
return value;
}
};
|