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 | 25x 25x 25x 25x 25x 25x 25x 25x 25x 25x 25x 25x 25x 31x 31x 31x 31x 31x 31x 1259x 1259x 1259x 1259x 1259x 31x 31x 6140x 6140x 6140x 6140x 6140x 6140x 6140x 6140x 6140x 31x 31x 19857x 19857x 31x 31x 11154x 11154x 11154x 11154x 11154x 11154x 11154x 19812x 19812x 19812x 19812x 19812x 19812x 17367x 18409x 17367x 17367x 17367x 11154x 11154x 11154x 11154x 31x 31x 6141x 6141x 6141x 6141x 6141x 6141x 20324x 20324x 20324x 19615x 19615x 19657x 19615x 19615x 6141x 6141x 6141x 6141x 31x 31x 4330x 4330x 4330x 4330x 4330x 4330x 2829x 2829x 2828x 2828x 2829x 4330x 31x 31x 3701x 3701x 3701x 3701x 3696x 3696x 3696x 3696x 3701x 25x | '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;
}
};
|