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

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