bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/elaboration/chr/planning/PlanPriorityQueue.java

   1 package org.simantics.scl.compiler.elaboration.chr.planning;\r
   2 \r
   3 import java.util.Arrays;\r
   4 \r
   5 public class PlanPriorityQueue {\r
   6     PrePlanItem[] items = new PrePlanItem[16];\r
   7     int size = 0;\r
   8 \r
   9     public PrePlanItem head() {\r
  10         return items[0];\r
  11     }\r
  12 \r
  13     public void pop() {\r
  14         items[0].queuePos = -1;\r
  15         --size;\r
  16         if (size > 0) {\r
  17             PrePlanItem e = items[size];\r
  18             items[0] = e;\r
  19             e.queuePos = 0;\r
  20             adjustDown(e);\r
  21         }\r
  22         items[size] = null;\r
  23     }\r
  24 \r
  25     public void add(PrePlanItem e) {\r
  26         if (size == items.length)\r
  27             items = Arrays.copyOf(items, size + size / 2);\r
  28         items[size] = e;\r
  29         e.queuePos = size;\r
  30         ++size;\r
  31         adjustUp(e);\r
  32     }\r
  33 \r
  34     private boolean adjustUp(PrePlanItem e) {\r
  35         int pos = e.queuePos;\r
  36         while (pos > 0) {\r
  37             int upId = (pos - 1) / 2;\r
  38             PrePlanItem upE = items[upId];\r
  39             if (e.compare(upE) >= 0)\r
  40                 break;\r
  41             items[pos] = upE;\r
  42             upE.queuePos = pos;\r
  43             pos = upId;\r
  44         }\r
  45         if (e.queuePos != pos) {\r
  46             items[pos] = e;\r
  47             e.queuePos = pos;\r
  48             return true;\r
  49         } else\r
  50             return false;\r
  51     }\r
  52 \r
  53     private void adjustDown(PrePlanItem e) {\r
  54         int pos = e.queuePos;\r
  55         while (true) {\r
  56             int downId = pos * 2 + 1;\r
  57             if (downId >= size)\r
  58                 break;\r
  59             if (downId + 1 < size\r
  60                     && items[downId].compare(items[downId + 1]) > 0)\r
  61                 ++downId;\r
  62             PrePlanItem downE = items[downId];\r
  63             if (e.compare(downE) > 0) {\r
  64                 items[pos] = downE;\r
  65                 downE.queuePos = pos;\r
  66                 pos = downId;\r
  67             } else\r
  68                 break;\r
  69         }\r
  70         if (e.queuePos != pos) {\r
  71             items[pos] = e;\r
  72             e.queuePos = pos;\r
  73         }\r
  74     }\r
  75 \r
  76     public void adjust(PrePlanItem e) {\r
  77         if(e.queuePos == -1)\r
  78             return;\r
  79         if (!adjustUp(e))\r
  80             adjustDown(e);\r
  81     }\r
  82 \r
  83     public boolean isEmpty() {\r
  84         return size == 0;\r
  85     }\r
  86 }\r