1 | 'use strict';
|
2 |
|
3 | Object.defineProperty(exports, '__esModule', {
|
4 | value: true
|
5 | });
|
6 | exports.default = void 0;
|
7 |
|
8 |
|
9 |
|
10 |
|
11 |
|
12 |
|
13 |
|
14 |
|
15 |
|
16 |
|
17 |
|
18 |
|
19 |
|
20 |
|
21 |
|
22 |
|
23 |
|
24 | class PriorityQueue {
|
25 | _queue = [];
|
26 | _sharedQueue = new MinHeap();
|
27 |
|
28 | constructor(_computePriority) {
|
29 | this._computePriority = _computePriority;
|
30 | }
|
31 |
|
32 | enqueue(task, workerId) {
|
33 | if (workerId == null) {
|
34 | this._enqueue(task, this._sharedQueue);
|
35 | } else {
|
36 | const queue = this._getWorkerQueue(workerId);
|
37 |
|
38 | this._enqueue(task, queue);
|
39 | }
|
40 | }
|
41 |
|
42 | _enqueue(task, queue) {
|
43 | const item = {
|
44 | priority: this._computePriority(task.request[2], ...task.request[3]),
|
45 | task
|
46 | };
|
47 | queue.add(item);
|
48 | }
|
49 |
|
50 | dequeue(workerId) {
|
51 | const workerQueue = this._getWorkerQueue(workerId);
|
52 |
|
53 | const workerTop = workerQueue.peek();
|
54 |
|
55 | const sharedTop = this._sharedQueue.peek();
|
56 |
|
57 |
|
58 |
|
59 |
|
60 |
|
61 | if (
|
62 | sharedTop == null ||
|
63 | (workerTop != null && workerTop.priority <= sharedTop.priority)
|
64 | ) {
|
65 | var _workerQueue$poll$tas, _workerQueue$poll;
|
66 |
|
67 | return (_workerQueue$poll$tas =
|
68 | (_workerQueue$poll = workerQueue.poll()) === null ||
|
69 | _workerQueue$poll === void 0
|
70 | ? void 0
|
71 | : _workerQueue$poll.task) !== null && _workerQueue$poll$tas !== void 0
|
72 | ? _workerQueue$poll$tas
|
73 | : null;
|
74 | }
|
75 |
|
76 | return this._sharedQueue.poll().task;
|
77 | }
|
78 |
|
79 | _getWorkerQueue(workerId) {
|
80 | let queue = this._queue[workerId];
|
81 |
|
82 | if (queue == null) {
|
83 | queue = this._queue[workerId] = new MinHeap();
|
84 | }
|
85 |
|
86 | return queue;
|
87 | }
|
88 | }
|
89 |
|
90 | exports.default = PriorityQueue;
|
91 |
|
92 | class MinHeap {
|
93 | _heap = [];
|
94 |
|
95 | peek() {
|
96 | var _this$_heap$;
|
97 |
|
98 | return (_this$_heap$ = this._heap[0]) !== null && _this$_heap$ !== void 0
|
99 | ? _this$_heap$
|
100 | : null;
|
101 | }
|
102 |
|
103 | add(item) {
|
104 | const nodes = this._heap;
|
105 | nodes.push(item);
|
106 |
|
107 | if (nodes.length === 1) {
|
108 | return;
|
109 | }
|
110 |
|
111 | let currentIndex = nodes.length - 1;
|
112 |
|
113 | while (currentIndex > 0) {
|
114 | const parentIndex = Math.floor((currentIndex + 1) / 2) - 1;
|
115 | const parent = nodes[parentIndex];
|
116 |
|
117 | if (parent.priority <= item.priority) {
|
118 | break;
|
119 | }
|
120 |
|
121 | nodes[currentIndex] = parent;
|
122 | nodes[parentIndex] = item;
|
123 | currentIndex = parentIndex;
|
124 | }
|
125 | }
|
126 |
|
127 | poll() {
|
128 | const nodes = this._heap;
|
129 | const result = nodes[0];
|
130 | const lastElement = nodes.pop();
|
131 |
|
132 | if (result == null || nodes.length === 0) {
|
133 | return result !== null && result !== void 0 ? result : null;
|
134 | }
|
135 |
|
136 | let index = 0;
|
137 | nodes[0] =
|
138 | lastElement !== null && lastElement !== void 0 ? lastElement : null;
|
139 | const element = nodes[0];
|
140 |
|
141 | while (true) {
|
142 | let swapIndex = null;
|
143 | const rightChildIndex = (index + 1) * 2;
|
144 | const leftChildIndex = rightChildIndex - 1;
|
145 | const rightChild = nodes[rightChildIndex];
|
146 | const leftChild = nodes[leftChildIndex];
|
147 |
|
148 | if (leftChild != null && leftChild.priority < element.priority) {
|
149 | swapIndex = leftChildIndex;
|
150 | }
|
151 |
|
152 |
|
153 | if (
|
154 | rightChild != null &&
|
155 | rightChild.priority < (swapIndex == null ? element : leftChild).priority
|
156 | ) {
|
157 | swapIndex = rightChildIndex;
|
158 | }
|
159 |
|
160 | if (swapIndex == null) {
|
161 | break;
|
162 | }
|
163 |
|
164 | nodes[index] = nodes[swapIndex];
|
165 | nodes[swapIndex] = element;
|
166 | index = swapIndex;
|
167 | }
|
168 |
|
169 | return result;
|
170 | }
|
171 | }
|