diff options
Diffstat (limited to 'packages/0x.js/src/utils')
-rw-r--r-- | packages/0x.js/src/utils/heap.ts | 92 |
1 files changed, 0 insertions, 92 deletions
diff --git a/packages/0x.js/src/utils/heap.ts b/packages/0x.js/src/utils/heap.ts deleted file mode 100644 index e262266d4..000000000 --- a/packages/0x.js/src/utils/heap.ts +++ /dev/null @@ -1,92 +0,0 @@ -// Based on Original JavaScript Code from Marijn Haverbeke (http://eloquentjavascript.net/1st_edition/appendix2.html) -export class Heap<T> { - private content: T[]; - private scoreFunction: (x: T) => number; - constructor(scoreFunction: (x: T) => number) { - this.content = []; - this.scoreFunction = scoreFunction; - } - public push(element: T) { - this.content.push(element); - this.bubbleUp(this.content.length - 1); - } - public size(): number { - const size = this.content.length; - return size; - } - public head(): T { - const head = this.content[0]; - return head; - } - public pop(): T { - const head = this.content[0]; - const end = this.content.pop(); - if (this.content.length > 0) { - this.content[0] = end as T; - this.sinkDown(0); - } - return head; - } - private bubbleUp(n: number) { - // Fetch the element that has to be moved. - const element = this.content[n]; - const score = this.scoreFunction(element); - // When at 0, an element can not go up any further. - while (n > 0) { - // Compute the parent element's index, and fetch it. - const parentN = Math.floor((n + 1) / 2) - 1; - const parent = this.content[parentN]; - // If the parent has a lesser score, things are in order and we - // are done. - if (score >= this.scoreFunction(parent)) { - break; - } - - // Otherwise, swap the parent with the current element and - // continue. - this.content[parentN] = element; - this.content[n] = parent; - n = parentN; - } - } - private sinkDown(n: number) { - // Look up the target element and its score. - const length = this.content.length; - const element = this.content[n]; - const elemScore = this.scoreFunction(element); - - while (true) { - // Compute the indices of the child elements. - const child2N = (n + 1) * 2; - const child1N = child2N - 1; - // This is used to store the new position of the element, if any. - let swap = n; - let child1Score; - let child2Score; - // If the first child exists (is inside the array)... - if (child1N < length) { - // Look it up and compute its score. - const child1 = this.content[child1N]; - child1Score = this.scoreFunction(child1); - // If the score is less than our element's, we need to swap. - if (child1Score < elemScore) { - swap = child1N; - } - // Do the same checks for the other child. - if (child2N < length) { - const child2 = this.content[child2N]; - child2Score = this.scoreFunction(child2); - if (child2Score < (swap == null ? elemScore : child1Score)) { - swap = child2N; - } - } - } - if (swap === n) { - break; - } - this.content[n] = this.content[swap]; - this.content[swap] = element; - n = swap; - } - } -} |