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 | 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 20x 736x 736x 736x 736x 736x 20x 20x 6208x 6208x 6208x 6208x 6208x 6208x 6208x 6208x 6208x 20x 20x 16574x 16574x 20x 20x 9311x 9311x 9311x 9311x 9311x 9311x 9311x 19667x 19667x 19667x 19667x 19667x 19667x 17350x 18392x 17350x 17350x 17350x 9311x 9311x 9311x 9311x 20x 20x 6209x 6209x 6209x 6209x 6209x 6209x 20337x 20337x 20337x 19621x 19621x 19663x 19621x 19621x 6209x 6209x 6209x 6209x 20x 20x 4549x 4549x 4549x 4549x 4549x 4549x 2839x 2839x 2838x 2838x 2839x 4549x 20x 20x 3912x 3912x 3912x 3912x 3907x 3907x 3907x 3907x 3912x 20x | 'use strict';
const {
Array,
} = primordials;
// 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 {
#compare = (a, b) => a - b;
#heap = new Array(64);
#setPosition;
#size = 0;
constructor(comparator, setPosition) {
if (comparator !== undefined)
this.#compare = comparator;
if (setPosition !== undefined)
this.#setPosition = setPosition;
}
insert(value) {
const heap = this.#heap;
const pos = ++this.#size;
heap[pos] = value;
if (heap.length === pos)
heap.length *= 2;
this.percolateUp(pos);
}
peek() {
return this.#heap[1];
}
percolateDown(pos) {
const compare = this.#compare;
const setPosition = this.#setPosition;
const heap = this.#heap;
const size = this.#size;
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.#heap;
const compare = this.#compare;
const setPosition = this.#setPosition;
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.#heap;
const size = --this.#size;
heap[pos] = heap[size + 1];
heap[size + 1] = undefined;
if (size > 0 && pos <= size) {
if (pos > 1 && this.#compare(heap[pos / 2 | 0], heap[pos]) > 0)
this.percolateUp(pos);
else
this.percolateDown(pos);
}
}
shift() {
const heap = this.#heap;
const value = heap[1];
if (value === undefined)
return;
this.removeAt(1);
return value;
}
};
|