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 32x 32x 32x 32x 32x 32x 1261x 1261x 1261x 1261x 1261x 32x 32x 6154x 6154x 6154x 6154x 6154x 6154x 6154x 6154x 6154x 32x 32x 17069x 17069x 32x 32x 9760x 9760x 9760x 9760x 9760x 9760x 9760x 19745x 19745x 19745x 19745x 19745x 19745x 17352x 18394x 17352x 17352x 17352x 9760x 9760x 9760x 9760x 32x 32x 6155x 6155x 6155x 6155x 6155x 6155x 20318x 20318x 20318x 19602x 19602x 19644x 19602x 19602x 6155x 6155x 6155x 6155x 32x 32x 4346x 4346x 4346x 4346x 4346x 4346x 2842x 2842x 2841x 2841x 2842x 4346x 32x 32x 3717x 3717x 3717x 3717x 3712x 3712x 3712x 3712x 3717x 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;
}
};
|