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 | 27x 27x 27x 27x 27x 27x 27x 27x 27x 27x 27x 27x 27x 27x 27x 27x 27x 27x 27x 27x 1248x 1248x 1248x 1248x 1248x 1248x 1248x 1248x 27x 27x 52411x 52411x 27x 27x 5769x 5769x 5769x 5769x 5769x 5769x 5769x 5769x 5769x 27x 27x 14998x 14998x 27x 27x 8705x 8705x 8705x 8705x 8705x 8705x 8705x 19366x 19366x 19366x 19366x 19366x 19366x 17211x 18253x 17211x 17211x 17211x 8705x 8705x 8705x 8705x 27x 27x 5770x 5770x 5770x 5770x 5770x 5770x 19856x 19856x 19856x 19253x 19253x 19295x 19253x 19253x 5770x 5770x 5770x 5770x 27x 27x 4237x 4237x 4237x 4237x 4237x 4237x 2731x 2731x 2730x 2730x 2731x 4237x 27x 27x 3614x 3614x 3614x 3614x 3609x 3609x 3609x 3609x 3614x 27x | '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;
}
};
|