X-Git-Url: http://git.megacz.com/?p=sbp.git;a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FReduction.java;fp=src%2Fedu%2Fberkeley%2Fsbp%2FReduction.java;h=684fbf8b51424ff6492a353277ff4d2b40d1d7de;hp=a6d599f6a7337db4322d1d0e2fd52b0affa11450;hb=0620c2d97d6df986d74dbe13160afb1435096431;hpb=a16fa9866b4bd4fabd4082f1a81f31a352a8f4c2

diff --git a/src/edu/berkeley/sbp/Reduction.java b/src/edu/berkeley/sbp/Reduction.java
index a6d599f..684fbf8 100644
--- a/src/edu/berkeley/sbp/Reduction.java
+++ b/src/edu/berkeley/sbp/Reduction.java
@@ -33,15 +33,8 @@ final class Reduction implements Comparable<Reduction> {
 
     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;
+        if (ret != 0) return -1 * ret;
+        return (position.ord - r.position.ord);
     }
 
     private static boolean isRightNullable(Walk.Cache c, Position p) {
@@ -55,10 +48,13 @@ final class Reduction implements Comparable<Reduction> {
         if (!isRightNullable(cache, himp)) return false;
         Sequence me  = mep.owner();
         Sequence him = himp.owner();
+        Boolean b = me.canKill.get(him);
+        if (b!=null) return b;
         for(Sequence killer : him.hates()) {
             HashSet<Sequence> eq2 = new Walk.EquivalentTo(killer, cache).walk();
-            if (eq2.contains(me)) return true;
+            if (eq2.contains(me)) { me.canKill.put(him, true); return true; }
         }
+        me.canKill.put(him, false);
         return false;
     }
 
@@ -82,10 +78,13 @@ final class Reduction implements Comparable<Reduction> {
         if (!isRightNullable(cache, himp)) return false;
         Sequence me  = mep.owner();
         Sequence him = himp.owner();
+        Boolean b = me.canNeed.get(him);
+        if (b!=null) return b;
         for(Sequence needer : him.needs()) {
             HashSet<Sequence> eq2 = new Walk.EquivalentTo(needer, cache).walk();
-            if (eq2.contains(me)) return true;
+            if (eq2.contains(me)) { me.canNeed.put(him, true); return true; }
         }
+        me.canNeed.put(him, false);
         return false;
     }
 }