bundles/org.simantics.scl.runtime/src/org/simantics/scl/runtime/chr/FactActivationQueue.java

   1 package org.simantics.scl.runtime.chr;
   2
   3 import java.util.Arrays;
   4
   5 public class FactActivationQueue {
   6     public static final boolean TRACE = false;
   7
   8     private final PriorityContainer[] containers;
   9     private PriorityContainer[] activeContainers = new PriorityContainer[8];
  10     private int activeContainerCount;
  11
  12     public FactActivationQueue(int priorityCount) {
  13         if(TRACE)
  14             System.out.println("priorityCount = " + priorityCount);
  15         containers = new PriorityContainer[priorityCount];
  16         for(int i=0;i<priorityCount;++i)
  17             containers[i] = new PriorityContainer(i);
  18     }
  19
  20     /**
  21      * Adds a new fact with a given priority
  22      */
  23     public void add(int priority, Fact item) {
  24         if(TRACE)
  25             System.out.println("FactActivationQueue.add " + priority + "@" + item);
  26         PriorityContainer container = containers[priority];
  27         if(container.size == 0)
  28             activateContainer(container);
  29         container.push(item);
  30     }
  31
  32     private void activateContainer(PriorityContainer container) {
  33         if(TRACE)
  34             System.out.println("FactActivationQueue.activate priority " + container.priority);
  35         if(activeContainers.length == activeContainerCount)
  36             activeContainers = Arrays.copyOf(activeContainers, activeContainerCount*2);
  37         adjustUpwards(activeContainerCount, container);
  38         ++activeContainerCount;
  39     }
  40
  41     private void deactivateContainer() {
  42         --activeContainerCount;
  43         adjustDownwards(0, activeContainers[activeContainerCount]);
  44         activeContainers[activeContainerCount] = null;
  45     }
  46
  47     private void adjustDownwards(int pos, PriorityContainer item) {
  48         int priority = item.priority;
  49         while(true) {
  50             int npos = 2*pos+1;
  51             if(npos+1 >= activeContainerCount) {
  52                 if(npos >= activeContainerCount)
  53                     break;
  54                 PriorityContainer item1 = activeContainers[npos];
  55                 if(priority > item1.priority) {
  56                     activeContainers[pos] = item1;
  57                     activeContainers[npos] = item;
  58                     return;
  59                 }
  60                 else
  61                     break;
  62             }
  63             PriorityContainer item1 = activeContainers[npos];
  64             PriorityContainer item2 = activeContainers[npos+1];
  65             if(priority < item1.priority) {
  66                 if(priority < item2.priority)
  67                     break;
  68             }
  69             else {
  70                 if(item1.priority < item2.priority) {
  71                     activeContainers[pos] = item1;
  72                     pos = npos;
  73                     continue;
  74                 }
  75             }
  76             activeContainers[pos] = item2;
  77             pos = npos+1;
  78         }
  79         activeContainers[pos] = item;
  80     }
  81
  82     private void adjustUpwards(int pos, PriorityContainer item) {
  83         int priority = item.priority;
  84         while(pos > 0) {
  85             int npos = (pos-1)/2;
  86             PriorityContainer item1 = activeContainers[npos];
  87             if(item1.priority > priority) {
  88                 activeContainers[pos] = item1;
  89                 pos = npos;
  90             }
  91             else
  92                 break;
  93         }
  94         activeContainers[pos] = item;
  95     }
  96
  97     /**
  98      * Activates all facts with priority less than the current priority
  99      */
 100     public void activate(Object context, int currentPriority) {
 101         if(TRACE)
 102             System.out.println("FactActivationQueue.activate " + currentPriority);
 103         while(activeContainerCount > 0) {
 104             PriorityContainer topContainer = activeContainers[0];
 105             int priority = topContainer.priority;
 106             if(priority >= currentPriority)
 107                 return;
 108
 109             Fact fact = topContainer.pop();
 110             if(topContainer.size == 0)
 111                 deactivateContainer();
 112
 113             int newPriority = fact.activate(context, priority);
 114             if(TRACE)
 115                 System.out.println("    [" + currentPriority + "] " + fact + " oldPriority=" + priority + ", newPriority=" + newPriority);
 116             if(newPriority >= 0)
 117                 add(newPriority, fact);
 118         }
 119     }
 120 }