summary patch for Nov->Jan work

[sbp.git] / src / edu / berkeley / sbp / Reduction.java

diff --git a/src/edu/berkeley/sbp/Reduction.java b/src/edu/berkeley/sbp/Reduction.java
new file mode 100644 (file)
index 0000000..e845764
--- /dev/null
+++ b/src/edu/berkeley/sbp/Reduction.java
@@ -0,0 +1,92 @@
+// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
+
+package edu.berkeley.sbp;
+import edu.berkeley.sbp.*;
+import edu.berkeley.sbp.util.*;
+import edu.berkeley.sbp.Parser.Table.*;
+import edu.berkeley.sbp.Sequence.Position;
+import java.io.*;
+import java.util.*;
+import java.lang.reflect.*;
+
+final class Reduction implements Comparable<Reduction> {
+
+    public Position position;
+    public GSS.Phase phase;
+    public Forest result;
+    public Node node;
+    boolean done = false;
+    
+    public Reduction(Node node, Position position, Forest result, GSS.Phase target) {
+        this.position = position;
+        this.result = result;
+        this.phase = target;
+        this.node = node;
+    }
+
+    public void perform() {
+        if (done) return;
+        done = true;
+        node.finish(position, result, phase);
+    }
+
+    public String toString() { return position+""; }
+
+    public int compareTo(Reduction r) {
+        int ret = compareTo0(r);
+        if (ret == 0) {
+            Walk.Cache cache = node.state().cache();
+            if (canKill(cache, position, r.position) && canKill(cache, r.position, position)) throw new Error();
+            if      (canKill(cache, position,   r.position)) ret =  1;
+            else if (canKill(cache, r.position, position)) ret = -1;
+            if      (canNeed(cache, position,   r.position)) ret =  1;
+            else if (canNeed(cache, r.position, position)) ret = -1;
+        }
+        return -1 * ret;
+    }
+
+    private boolean isRightNullable(Walk.Cache c, Position p) {
+        if (p.isLast()) return true;
+        if (!c.possiblyEpsilon(p.element())) return false;
+        return isRightNullable(c, p.next());
+    }
+
+    public boolean canKill(Walk.Cache cache, Position mep, Position himp) {
+        if (!isRightNullable(cache, mep))  return false;
+        if (!isRightNullable(cache, himp)) return false;
+        Sequence me  = mep.owner();
+        Sequence him = himp.owner();
+        for(Sequence killer : him.hates()) {
+            HashSet<Sequence> eq2 = new Walk.EquivalentTo(killer, cache).walk();
+            if (eq2.contains(me)) return true;
+        }
+        return false;
+    }
+
+    public static final int LESS_THAN = -1;
+    public static final int EQUAL_TO = 0;
+    public static final int GREATER_THAN = 1;
+
+    public int compareTo0(Reduction n) {
+        if (targetPhase()==null && n.targetPhase()==null) return EQUAL_TO;
+        if (targetPhase()==null) return LESS_THAN;
+        if (n.targetPhase()==null) return GREATER_THAN;
+        if (targetPhase().pos < n.targetPhase().pos) return LESS_THAN;
+        if (targetPhase().pos > n.targetPhase().pos) return GREATER_THAN;
+        return 0;
+    }
+    public int pos() { return targetPhase()==null ? 0 : targetPhase().pos; }
+    public GSS.Phase targetPhase() { return node.phase(); }
+
+    public boolean canNeed(Walk.Cache cache, Position mep, Position himp) {
+        if (!isRightNullable(cache, mep))  return false;
+        if (!isRightNullable(cache, himp)) return false;
+        Sequence me  = mep.owner();
+        Sequence him = himp.owner();
+        for(Sequence needer : him.needs()) {
+            HashSet<Sequence> eq2 = new Walk.EquivalentTo(needer, cache).walk();
+            if (eq2.contains(me)) return true;
+        }
+        return false;
+    }
+}