| FazBrowse GitHub Viewer | Trending | | Home |
| Tools: [Download Repo ZIP] [Original HTTPS Page] |
1 parent 1256c4d commit 0b5dbb2
1 file changed
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -2,38 +2,30 @@ | |||
| 2 | 2 | ||
| 3 | 3 | const { | |
| 4 | 4 | Array, | |
| 5 | - Symbol, | ||
| 6 | 5 | } = primordials; | |
| 7 | 6 | ||
| 8 | - const kCompare = Symbol('compare'); | ||
| 9 | - const kHeap = Symbol('heap'); | ||
| 10 | - const kSetPosition = Symbol('setPosition'); | ||
| 11 | - const kSize = Symbol('size'); | ||
| 12 | - | ||
| 13 | 7 | // The PriorityQueue is a basic implementation of a binary heap that accepts | |
| 14 | 8 | // a custom sorting function via its constructor. This function is passed | |
| 15 | 9 | // the two nodes to compare, similar to the native Array#sort. Crucially | |
| 16 | 10 | // this enables priority queues that are based on a comparison of more than | |
| 17 | 11 | // just a single criteria. | |
| 18 | 12 | ||
| 19 | 13 | module.exports = class PriorityQueue { | |
| 14 | + #compare = (a, b) => a - b; | ||
| 15 | + #heap = new Array(64); | ||
| 16 | + #setPosition; | ||
| 17 | + #size = 0; | ||
| 18 | + | ||
| 20 | 19 | constructor(comparator, setPosition) { | |
| 21 | 20 | if (comparator !== undefined) | |
| 22 | - this[kCompare] = comparator; | ||
| 21 | + this.#compare = comparator; | ||
| 23 | 22 | if (setPosition !== undefined) | |
| 24 | - this[kSetPosition] = setPosition; | ||
| 25 | - | ||
| 26 | - this[kHeap] = new Array(64); | ||
| 27 | - this[kSize] = 0; | ||
| 28 | - } | ||
| 29 | - | ||
| 30 | - [kCompare](a, b) { | ||
| 31 | - return a - b; | ||
| 23 | + this.#setPosition = setPosition; | ||
| 32 | 24 | } | |
| 33 | 25 | ||
| 34 | 26 | insert(value) { | |
| 35 | - const heap = this[kHeap]; | ||
| 36 | - const pos = ++this[kSize]; | ||
| 27 | + const heap = this.#heap; | ||
| 28 | + const pos = ++this.#size; | ||
| 37 | 29 | heap[pos] = value; | |
| 38 | 30 | ||
| 39 | 31 | if (heap.length === pos) | |
@@ -43,14 +35,14 @@ module.exports = class PriorityQueue { | |||
| 43 | 35 | } | |
| 44 | 36 | ||
| 45 | 37 | peek() { | |
| 46 | - return this[kHeap][1]; | ||
| 38 | + return this.#heap[1]; | ||
| 47 | 39 | } | |
| 48 | 40 | ||
| 49 | 41 | percolateDown(pos) { | |
| 50 | - const compare = this[kCompare]; | ||
| 51 | - const setPosition = this[kSetPosition]; | ||
| 52 | - const heap = this[kHeap]; | ||
| 53 | - const size = this[kSize]; | ||
| 42 | + const compare = this.#compare; | ||
| 43 | + const setPosition = this.#setPosition; | ||
| 44 | + const heap = this.#heap; | ||
| 45 | + const size = this.#size; | ||
| 54 | 46 | const item = heap[pos]; | |
| 55 | 47 | ||
| 56 | 48 | while (pos * 2 <= size) { | |
@@ -71,9 +63,9 @@ module.exports = class PriorityQueue { | |||
| 71 | 63 | } | |
| 72 | 64 | ||
| 73 | 65 | percolateUp(pos) { | |
| 74 | - const heap = this[kHeap]; | ||
| 75 | - const compare = this[kCompare]; | ||
| 76 | - const setPosition = this[kSetPosition]; | ||
| 66 | + const heap = this.#heap; | ||
| 67 | + const compare = this.#compare; | ||
| 68 | + const setPosition = this.#setPosition; | ||
| 77 | 69 | const item = heap[pos]; | |
| 78 | 70 | ||
| 79 | 71 | while (pos > 1) { | |
@@ -91,21 +83,21 @@ module.exports = class PriorityQueue { | |||
| 91 | 83 | } | |
| 92 | 84 | ||
| 93 | 85 | removeAt(pos) { | |
| 94 | - const heap = this[kHeap]; | ||
| 95 | - const size = --this[kSize]; | ||
| 86 | + const heap = this.#heap; | ||
| 87 | + const size = --this.#size; | ||
| 96 | 88 | heap[pos] = heap[size + 1]; | |
| 97 | 89 | heap[size + 1] = undefined; | |
| 98 | 90 | ||
| 99 | 91 | if (size > 0 && pos <= size) { | |
| 100 | - if (pos > 1 && this[kCompare](heap[pos / 2 | 0], heap[pos]) > 0) | ||
| 92 | + if (pos > 1 && this.#compare(heap[pos / 2 | 0], heap[pos]) > 0) | ||
| 101 | 93 | this.percolateUp(pos); | |
| 102 | 94 | else | |
| 103 | 95 | this.percolateDown(pos); | |
| 104 | 96 | } | |
| 105 | 97 | } | |
| 106 | 98 | ||
| 107 | 99 | shift() { | |
| 108 | - const heap = this[kHeap]; | ||
| 100 | + const heap = this.#heap; | ||
| 109 | 101 | const value = heap[1]; | |
| 110 | 102 | if (value === undefined) | |
| 111 | 103 | return; | |
| Back | FazBrowse Home | New Git URL |
0 commit comments