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 | 23x 23x 23x 23x 23x 23x 23x 23x 23x 23x 23x 23x 23x 23x 23x 23x 23x 23x 23x 23x 1259x 1259x 1259x 1259x 1259x 1259x 1259x 1259x 23x 23x 52411x 52411x 23x 23x 6128x 6128x 6128x 6128x 6128x 6128x 6128x 6128x 6128x 23x 23x 15545x 15545x 23x 23x 8997x 8997x 8997x 8997x 8997x 8997x 8997x 19729x 19729x 19729x 19729x 19729x 19729x 17365x 18407x 17365x 17365x 17365x 8997x 8997x 8997x 8997x 23x 23x 6129x 6129x 6129x 6129x 6129x 6129x 20319x 20319x 20319x 19613x 19613x 19655x 19613x 19613x 6129x 6129x 6129x 6129x 23x 23x 4328x 4328x 4328x 4328x 4328x 4328x 2828x 2828x 2827x 2827x 2828x 4328x 23x 23x 3697x 3697x 3697x 3697x 3692x 3692x 3692x 3692x 3697x 23x | '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;
}
};
|