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 | return workerQueue.poll()?.task ?? null;
|
66 | }
|
67 |
|
68 | return this._sharedQueue.poll().task;
|
69 | }
|
70 |
|
71 | _getWorkerQueue(workerId) {
|
72 | let queue = this._queue[workerId];
|
73 |
|
74 | if (queue == null) {
|
75 | queue = this._queue[workerId] = new MinHeap();
|
76 | }
|
77 |
|
78 | return queue;
|
79 | }
|
80 | }
|
81 |
|
82 | exports.default = PriorityQueue;
|
83 |
|
84 | class MinHeap {
|
85 | _heap = [];
|
86 |
|
87 | peek() {
|
88 | return this._heap[0] ?? null;
|
89 | }
|
90 |
|
91 | add(item) {
|
92 | const nodes = this._heap;
|
93 | nodes.push(item);
|
94 |
|
95 | if (nodes.length === 1) {
|
96 | return;
|
97 | }
|
98 |
|
99 | let currentIndex = nodes.length - 1;
|
100 |
|
101 | while (currentIndex > 0) {
|
102 | const parentIndex = Math.floor((currentIndex + 1) / 2) - 1;
|
103 | const parent = nodes[parentIndex];
|
104 |
|
105 | if (parent.priority <= item.priority) {
|
106 | break;
|
107 | }
|
108 |
|
109 | nodes[currentIndex] = parent;
|
110 | nodes[parentIndex] = item;
|
111 | currentIndex = parentIndex;
|
112 | }
|
113 | }
|
114 |
|
115 | poll() {
|
116 | const nodes = this._heap;
|
117 | const result = nodes[0];
|
118 | const lastElement = nodes.pop();
|
119 |
|
120 | if (result == null || nodes.length === 0) {
|
121 | return result ?? null;
|
122 | }
|
123 |
|
124 | let index = 0;
|
125 | nodes[0] = lastElement ?? null;
|
126 | const element = nodes[0];
|
127 |
|
128 | while (true) {
|
129 | let swapIndex = null;
|
130 | const rightChildIndex = (index + 1) * 2;
|
131 | const leftChildIndex = rightChildIndex - 1;
|
132 | const rightChild = nodes[rightChildIndex];
|
133 | const leftChild = nodes[leftChildIndex];
|
134 |
|
135 | if (leftChild != null && leftChild.priority < element.priority) {
|
136 | swapIndex = leftChildIndex;
|
137 | }
|
138 |
|
139 |
|
140 | if (
|
141 | rightChild != null &&
|
142 | rightChild.priority < (swapIndex == null ? element : leftChild).priority
|
143 | ) {
|
144 | swapIndex = rightChildIndex;
|
145 | }
|
146 |
|
147 | if (swapIndex == null) {
|
148 | break;
|
149 | }
|
150 |
|
151 | nodes[index] = nodes[swapIndex];
|
152 | nodes[swapIndex] = element;
|
153 | index = swapIndex;
|
154 | }
|
155 |
|
156 | return result;
|
157 | }
|
158 | }
|