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