1"use strict";
2
3Object.defineProperty(exports, "__esModule", {
4    value: true
5});
6// Binary min-heap implementation used for priority queue.
7// Implementation is stable, i.e. push time is considered for equal priorities
8class Heap {
9    constructor() {
10        this.heap = [];
11        this.pushCount = Number.MIN_SAFE_INTEGER;
12    }
13
14    get length() {
15        return this.heap.length;
16    }
17
18    empty() {
19        this.heap = [];
20        return this;
21    }
22
23    percUp(index) {
24        let p;
25
26        while (index > 0 && smaller(this.heap[index], this.heap[p = parent(index)])) {
27            let t = this.heap[index];
28            this.heap[index] = this.heap[p];
29            this.heap[p] = t;
30
31            index = p;
32        }
33    }
34
35    percDown(index) {
36        let l;
37
38        while ((l = leftChi(index)) < this.heap.length) {
39            if (l + 1 < this.heap.length && smaller(this.heap[l + 1], this.heap[l])) {
40                l = l + 1;
41            }
42
43            if (smaller(this.heap[index], this.heap[l])) {
44                break;
45            }
46
47            let t = this.heap[index];
48            this.heap[index] = this.heap[l];
49            this.heap[l] = t;
50
51            index = l;
52        }
53    }
54
55    push(node) {
56        node.pushCount = ++this.pushCount;
57        this.heap.push(node);
58        this.percUp(this.heap.length - 1);
59    }
60
61    unshift(node) {
62        return this.heap.push(node);
63    }
64
65    shift() {
66        let [top] = this.heap;
67
68        this.heap[0] = this.heap[this.heap.length - 1];
69        this.heap.pop();
70        this.percDown(0);
71
72        return top;
73    }
74
75    toArray() {
76        return [...this];
77    }
78
79    *[Symbol.iterator]() {
80        for (let i = 0; i < this.heap.length; i++) {
81            yield this.heap[i].data;
82        }
83    }
84
85    remove(testFn) {
86        let j = 0;
87        for (let i = 0; i < this.heap.length; i++) {
88            if (!testFn(this.heap[i])) {
89                this.heap[j] = this.heap[i];
90                j++;
91            }
92        }
93
94        this.heap.splice(j);
95
96        for (let i = parent(this.heap.length - 1); i >= 0; i--) {
97            this.percDown(i);
98        }
99
100        return this;
101    }
102}
103
104exports.default = Heap;
105function leftChi(i) {
106    return (i << 1) + 1;
107}
108
109function parent(i) {
110    return (i + 1 >> 1) - 1;
111}
112
113function smaller(x, y) {
114    if (x.priority !== y.priority) {
115        return x.priority < y.priority;
116    } else {
117        return x.pushCount < y.pushCount;
118    }
119}
120module.exports = exports["default"];