Merge pull request #71 from Soopyboo32/Babel

1 files changed, 83 insertions, 0 deletions

diff --git a/src/datastructures/flatqueue.js b/src/datastructures/flatqueue.js
new file mode 100644
index 0000000..a011476
--- /dev/null
+++ b/src/datastructures/flatqueue.js
@@ -0,0 +1,83 @@
+
+//SEE https://github.com/mourner/flatqueue
+
+export default class FlatQueue {
+
+    constructor() {
+        this.ids = [];
+        this.values = [];
+        this.length = 0;
+    }
+
+    clear() {
+        this.length = 0;
+    }
+
+    push(id, value) {
+        let pos = this.length++;
+
+        while (pos > 0) {
+            let parent = ((pos + 1) >>> 1) - 1;
+            let parentValue = this.values[parent];
+            if (value >= parentValue) break;
+            this.ids[pos] = this.ids[parent];
+            this.values[pos] = parentValue;
+            pos = parent;
+        }
+
+        this.ids[pos] = id;
+        this.values[pos] = value;
+    }
+
+    pop() {
+        if (this.length === 0) return undefined;
+
+        let top = this.ids[0];
+        this.length--;
+
+        if (this.length > 0) {
+            let id = this.ids[0] = this.ids[this.length];
+            let value = this.values[0] = this.values[this.length];
+            let halfLength = this.length >> 1;
+            let pos = 0;
+
+            while (pos < halfLength) {
+                let left = (pos << 1) + 1;
+                let right = left + 1;
+                let bestIndex = this.ids[left];
+                let bestValue = this.values[left];
+                let rightValue = this.values[right];
+
+                if (right < this.length && rightValue < bestValue) {
+                    left = right;
+                    bestIndex = this.ids[right];
+                    bestValue = rightValue;
+                }
+                if (bestValue >= value) break;
+
+                this.ids[pos] = bestIndex;
+                this.values[pos] = bestValue;
+                pos = left;
+            }
+
+            this.ids[pos] = id;
+            this.values[pos] = value;
+        }
+
+        return top;
+    }
+
+    peek() {
+        if (this.length === 0) return undefined;
+        return this.ids[0];
+    }
+
+    peekValue() {
+        if (this.length === 0) return undefined;
+        return this.values[0];
+    }
+
+    shrink() {
+        this.ids.length = this.values.length = this.length;
+    }
+}
\ No newline at end of file