PriorityQueue.js 4.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
  1. 'use strict';
  2. Object.defineProperty(exports, '__esModule', {
  3. value: true
  4. });
  5. exports.default = void 0;
  6. function _defineProperty(obj, key, value) {
  7. if (key in obj) {
  8. Object.defineProperty(obj, key, {
  9. value: value,
  10. enumerable: true,
  11. configurable: true,
  12. writable: true
  13. });
  14. } else {
  15. obj[key] = value;
  16. }
  17. return obj;
  18. }
  19. /**
  20. * Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
  21. *
  22. * This source code is licensed under the MIT license found in the
  23. * LICENSE file in the root directory of this source tree.
  24. */
  25. /**
  26. * Priority queue that processes tasks in natural ordering (lower priority first)
  27. * accoridng to the priority computed by the function passed in the constructor.
  28. *
  29. * FIFO ordering isn't guaranteed for tasks with the same priority.
  30. *
  31. * Worker specific tasks with the same priority as a non-worker specific task
  32. * are always processed first.
  33. */
  34. class PriorityQueue {
  35. constructor(_computePriority) {
  36. _defineProperty(this, '_queue', []);
  37. _defineProperty(this, '_sharedQueue', new MinHeap());
  38. this._computePriority = _computePriority;
  39. }
  40. enqueue(task, workerId) {
  41. if (workerId == null) {
  42. this._enqueue(task, this._sharedQueue);
  43. } else {
  44. const queue = this._getWorkerQueue(workerId);
  45. this._enqueue(task, queue);
  46. }
  47. }
  48. _enqueue(task, queue) {
  49. const item = {
  50. priority: this._computePriority(task.request[2], ...task.request[3]),
  51. task
  52. };
  53. queue.add(item);
  54. }
  55. dequeue(workerId) {
  56. const workerQueue = this._getWorkerQueue(workerId);
  57. const workerTop = workerQueue.peek();
  58. const sharedTop = this._sharedQueue.peek(); // use the task from the worker queue if there's no task in the shared queue
  59. // or if the priority of the worker queue is smaller or equal to the
  60. // priority of the top task in the shared queue. The tasks of the
  61. // worker specific queue are preferred because no other worker can pick this
  62. // specific task up.
  63. if (
  64. sharedTop == null ||
  65. (workerTop != null && workerTop.priority <= sharedTop.priority)
  66. ) {
  67. var _workerQueue$poll$tas, _workerQueue$poll;
  68. return (_workerQueue$poll$tas =
  69. (_workerQueue$poll = workerQueue.poll()) === null ||
  70. _workerQueue$poll === void 0
  71. ? void 0
  72. : _workerQueue$poll.task) !== null && _workerQueue$poll$tas !== void 0
  73. ? _workerQueue$poll$tas
  74. : null;
  75. }
  76. return this._sharedQueue.poll().task;
  77. }
  78. _getWorkerQueue(workerId) {
  79. let queue = this._queue[workerId];
  80. if (queue == null) {
  81. queue = this._queue[workerId] = new MinHeap();
  82. }
  83. return queue;
  84. }
  85. }
  86. exports.default = PriorityQueue;
  87. class MinHeap {
  88. constructor() {
  89. _defineProperty(this, '_heap', []);
  90. }
  91. peek() {
  92. var _this$_heap$;
  93. return (_this$_heap$ = this._heap[0]) !== null && _this$_heap$ !== void 0
  94. ? _this$_heap$
  95. : null;
  96. }
  97. add(item) {
  98. const nodes = this._heap;
  99. nodes.push(item);
  100. if (nodes.length === 1) {
  101. return;
  102. }
  103. let currentIndex = nodes.length - 1; // Bubble up the added node as long as the parent is bigger
  104. while (currentIndex > 0) {
  105. const parentIndex = Math.floor((currentIndex + 1) / 2) - 1;
  106. const parent = nodes[parentIndex];
  107. if (parent.priority <= item.priority) {
  108. break;
  109. }
  110. nodes[currentIndex] = parent;
  111. nodes[parentIndex] = item;
  112. currentIndex = parentIndex;
  113. }
  114. }
  115. poll() {
  116. const nodes = this._heap;
  117. const result = nodes[0];
  118. const lastElement = nodes.pop(); // heap was empty or removed the last element
  119. if (result == null || nodes.length === 0) {
  120. return result !== null && result !== void 0 ? result : null;
  121. }
  122. let index = 0;
  123. nodes[0] =
  124. lastElement !== null && lastElement !== void 0 ? lastElement : null;
  125. const element = nodes[0];
  126. while (true) {
  127. let swapIndex = null;
  128. const rightChildIndex = (index + 1) * 2;
  129. const leftChildIndex = rightChildIndex - 1;
  130. const rightChild = nodes[rightChildIndex];
  131. const leftChild = nodes[leftChildIndex]; // if the left child is smaller, swap with the left
  132. if (leftChild != null && leftChild.priority < element.priority) {
  133. swapIndex = leftChildIndex;
  134. } // If the right child is smaller or the right child is smaller than the left
  135. // then swap with the right child
  136. if (
  137. rightChild != null &&
  138. rightChild.priority < (swapIndex == null ? element : leftChild).priority
  139. ) {
  140. swapIndex = rightChildIndex;
  141. }
  142. if (swapIndex == null) {
  143. break;
  144. }
  145. nodes[index] = nodes[swapIndex];
  146. nodes[swapIndex] = element;
  147. index = swapIndex;
  148. }
  149. return result;
  150. }
  151. }