Merged changes from feature/scl to master.

[simantics/platform.git] / bundles / org.simantics.scl.compiler / src / org / simantics / scl / compiler / elaboration / chr / planning / PlanPriorityQueue.java

diff --git a/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/elaboration/chr/planning/PlanPriorityQueue.java b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/elaboration/chr/planning/PlanPriorityQueue.java
new file mode 100644 (file)
index 0000000..7eb8ae5
--- /dev/null
+++ b/bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/elaboration/chr/planning/PlanPriorityQueue.java
@@ -0,0 +1,86 @@
+package org.simantics.scl.compiler.elaboration.chr.planning;\r
+\r
+import java.util.Arrays;\r
+\r
+public class PlanPriorityQueue {\r
+    PrePlanItem[] items = new PrePlanItem[16];\r
+    int size = 0;\r
+\r
+    public PrePlanItem head() {\r
+        return items[0];\r
+    }\r
+\r
+    public void pop() {\r
+        items[0].queuePos = -1;\r
+        --size;\r
+        if (size > 0) {\r
+            PrePlanItem e = items[size];\r
+            items[0] = e;\r
+            e.queuePos = 0;\r
+            adjustDown(e);\r
+        }\r
+        items[size] = null;\r
+    }\r
+\r
+    public void add(PrePlanItem e) {\r
+        if (size == items.length)\r
+            items = Arrays.copyOf(items, size + size / 2);\r
+        items[size] = e;\r
+        e.queuePos = size;\r
+        ++size;\r
+        adjustUp(e);\r
+    }\r
+\r
+    private boolean adjustUp(PrePlanItem e) {\r
+        int pos = e.queuePos;\r
+        while (pos > 0) {\r
+            int upId = (pos - 1) / 2;\r
+            PrePlanItem upE = items[upId];\r
+            if (e.compare(upE) >= 0)\r
+                break;\r
+            items[pos] = upE;\r
+            upE.queuePos = pos;\r
+            pos = upId;\r
+        }\r
+        if (e.queuePos != pos) {\r
+            items[pos] = e;\r
+            e.queuePos = pos;\r
+            return true;\r
+        } else\r
+            return false;\r
+    }\r
+\r
+    private void adjustDown(PrePlanItem e) {\r
+        int pos = e.queuePos;\r
+        while (true) {\r
+            int downId = pos * 2 + 1;\r
+            if (downId >= size)\r
+                break;\r
+            if (downId + 1 < size\r
+                    && items[downId].compare(items[downId + 1]) > 0)\r
+                ++downId;\r
+            PrePlanItem downE = items[downId];\r
+            if (e.compare(downE) > 0) {\r
+                items[pos] = downE;\r
+                downE.queuePos = pos;\r
+                pos = downId;\r
+            } else\r
+                break;\r
+        }\r
+        if (e.queuePos != pos) {\r
+            items[pos] = e;\r
+            e.queuePos = pos;\r
+        }\r
+    }\r
+\r
+    public void adjust(PrePlanItem e) {\r
+        if(e.queuePos == -1)\r
+            return;\r
+        if (!adjustUp(e))\r
+            adjustDown(e);\r
+    }\r
+\r
+    public boolean isEmpty() {\r
+        return size == 0;\r
+    }\r
+}\r