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 | 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 26x 740x 740x 740x 740x 740x 26x 26x 6202x 6202x 6202x 6202x 6202x 6202x 6202x 6202x 6202x 26x 26x 15867x 15867x 26x 26x 8950x 8950x 8950x 8950x 8950x 8950x 8950x 19641x 19641x 19641x 19641x 19641x 19641x 17362x 18404x 17362x 17362x 17362x 8950x 8950x 8950x 8950x 26x 26x 6203x 6203x 6203x 6203x 6203x 6203x 20309x 20309x 20309x 19587x 19587x 19629x 19587x 19587x 6203x 6203x 6203x 6203x 26x 26x 4550x 4550x 4550x 4550x 4550x 4550x 2836x 2836x 2835x 2835x 2836x 4550x 26x 26x 3914x 3914x 3914x 3914x 3909x 3909x 3909x 3909x 3914x 26x | '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;
}
};
|