Remove custom heap and use bintrees

5 files changed, 25 insertions, 103 deletions

diff --git a/packages/0x.js/package.json b/packages/0x.js/package.json
index 6839e6513..539a78f37 100644
--- a/packages/0x.js/package.json
+++ b/packages/0x.js/package.json
@@ -49,6 +49,7 @@
     "node": ">=6.0.0"
   },
   "devDependencies": {
+    "@types/bintrees": "^1.0.2",
     "@types/jsonschema": "^1.1.1",
     "@types/lodash": "^4.14.64",
     "@types/mocha": "^2.2.41",
@@ -87,9 +88,10 @@
     "webpack": "^3.1.0"
   },
   "dependencies": {
-    "@0xproject/assert": "0.0.3",
     "0x-json-schemas": "^0.6.1",
+    "@0xproject/assert": "0.0.3",
     "bignumber.js": "~4.1.0",
+    "bintrees": "^1.0.2",
     "compare-versions": "^3.0.1",
     "es6-promisify": "^5.0.0",
     "ethereumjs-abi": "^0.6.4",
diff --git a/packages/0x.js/src/order_watcher/expiration_watcher.ts b/packages/0x.js/src/order_watcher/expiration_watcher.ts
index 71199e75f..7d6f8df65 100644
--- a/packages/0x.js/src/order_watcher/expiration_watcher.ts
+++ b/packages/0x.js/src/order_watcher/expiration_watcher.ts
@@ -1,9 +1,9 @@
 import * as _ from 'lodash';
 import {BigNumber} from 'bignumber.js';
+import {RBTree} from 'bintrees';
 import {utils} from '../utils/utils';
 import {intervalUtils} from '../utils/interval_utils';
 import {SignedOrder, ZeroExError} from '../types';
-import {Heap} from '../utils/heap';
 import {ZeroEx} from '../0x';
 
 const DEFAULT_EXPIRATION_MARGIN_MS = 0;
@@ -14,7 +14,7 @@ const DEFAULT_ORDER_EXPIRATION_CHECKING_INTERVAL_MS = 50;
  * It stores them in a min heap by expiration time and checks for expired ones every `orderExpirationCheckingIntervalMs`
  */
 export class ExpirationWatcher {
-    private orderHashHeapByExpiration: Heap<string>;
+    private orderHashRBTreeByExpiration: RBTree<string>;
     private expiration: {[orderHash: string]: BigNumber} = {};
     private callbackIfExists?: (orderHash: string) => void;
     private orderExpirationCheckingIntervalMs: number;
@@ -27,7 +27,8 @@ export class ExpirationWatcher {
         this.orderExpirationCheckingIntervalMs = expirationMarginIfExistsMs ||
                                                  DEFAULT_ORDER_EXPIRATION_CHECKING_INTERVAL_MS;
         const scoreFunction = (orderHash: string) => this.expiration[orderHash].toNumber();
-        this.orderHashHeapByExpiration = new Heap(scoreFunction);
+        const comparator = (lhs: string, rhs: string) => scoreFunction(lhs) - scoreFunction(rhs);
+        this.orderHashRBTreeByExpiration = new RBTree(comparator);
     }
     public subscribe(callback: (orderHash: string) => void): void {
         if (!_.isUndefined(this.callbackIfExists)) {
@@ -48,20 +49,23 @@ export class ExpirationWatcher {
     }
     public addOrder(orderHash: string, expirationUnixTimestampMs: BigNumber): void {
         this.expiration[orderHash] = expirationUnixTimestampMs;
-        // We don't remove hashes from the heap on order remove because it's slow (linear).
-        // We just skip them later if the order was already removed from the order watcher.
-        this.orderHashHeapByExpiration.push(orderHash);
+        this.orderHashRBTreeByExpiration.insert(orderHash);
+    }
+    public removeOrder(orderHash: string): void {
+        this.orderHashRBTreeByExpiration.remove(orderHash);
+        delete this.expiration[orderHash];
     }
     private pruneExpiredOrders(): void {
         const currentUnixTimestampMs = utils.getCurrentUnixTimestampMs();
         while (
-            this.orderHashHeapByExpiration.size() !== 0 &&
-            this.expiration[this.orderHashHeapByExpiration.head()].lessThan(
+            this.orderHashRBTreeByExpiration.size !== 0 &&
+            this.expiration[this.orderHashRBTreeByExpiration.min()].lessThan(
                 currentUnixTimestampMs.plus(this.expirationMarginMs),
             ) &&
             !_.isUndefined(this.callbackIfExists)
         ) {
-            const orderHash = this.orderHashHeapByExpiration.pop();
+            const orderHash = this.orderHashRBTreeByExpiration.min();
+            this.orderHashRBTreeByExpiration.remove(orderHash);
             delete this.expiration[orderHash];
             this.callbackIfExists(orderHash);
         }
diff --git a/packages/0x.js/src/order_watcher/order_state_watcher.ts b/packages/0x.js/src/order_watcher/order_state_watcher.ts
index 3659fc6e2..975679f57 100644
--- a/packages/0x.js/src/order_watcher/order_state_watcher.ts
+++ b/packages/0x.js/src/order_watcher/order_state_watcher.ts
@@ -95,7 +95,6 @@ export class OrderStateWatcher {
         assert.isValidSignature(orderHash, signedOrder.ecSignature, signedOrder.maker);
         this._orderByOrderHash[orderHash] = signedOrder;
         this.addToDependentOrderHashes(signedOrder, orderHash);
-        // We don't remove orders from expirationWatcher because heap removal is linear. We just skip it later
         const expirationUnixTimestampMs = signedOrder.expirationUnixTimestampSec.times(1000);
         this._expirationWatcher.addOrder(orderHash, expirationUnixTimestampMs);
     }
@@ -111,6 +110,7 @@ export class OrderStateWatcher {
         }
         delete this._orderByOrderHash[orderHash];
         this.removeFromDependentOrderHashes(signedOrder.maker, signedOrder.makerTokenAddress, orderHash);
+        this._expirationWatcher.removeOrder(orderHash);
     }
     /**
      * Starts an orderStateWatcher subscription. The callback will be called every time a watched order's
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;
-        }
-    }
-}
diff --git a/yarn.lock b/yarn.lock
index 7eb98bc97..0c87f3257 100644
--- a/yarn.lock
+++ b/yarn.lock
@@ -9,6 +9,10 @@
     jsonschema "^1.2.0"
     lodash.values "^4.3.0"
 
+"@types/bintrees@^1.0.2":
+  version "1.0.2"
+  resolved "https://registry.yarnpkg.com/@types/bintrees/-/bintrees-1.0.2.tgz#0dfdce4eeebdf90427bd35b0e79dc248b3d157a6"
+
 "@types/fs-extra@^4.0.0":
   version "4.0.4"
   resolved "https://registry.yarnpkg.com/@types/fs-extra/-/fs-extra-4.0.4.tgz#72947e108f2cbeda5ab288a927399fdf6d02bd42"
@@ -830,6 +834,10 @@ bindings@^1.2.1:
   version "1.3.0"
   resolved "https://registry.yarnpkg.com/bindings/-/bindings-1.3.0.tgz#b346f6ecf6a95f5a815c5839fc7cdb22502f1ed7"
 
+bintrees@^1.0.2:
+  version "1.0.2"
+  resolved "https://registry.yarnpkg.com/bintrees/-/bintrees-1.0.2.tgz#49f896d6e858a4a499df85c38fb399b9aff840f8"
+
 bip39@^2.2.0:
   version "2.4.0"
   resolved "https://registry.yarnpkg.com/bip39/-/bip39-2.4.0.tgz#a0b8adbf163f53495f00f05d9ede7c25369ccf13"