Use ordinal pre-sorting rather than on-the-fly compares

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

diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java
index d3d8d8a..a029274 100644 (file)
--- a/src/edu/berkeley/sbp/Sequence.java
+++ b/src/edu/berkeley/sbp/Sequence.java
@@ -16,7 +16,10 @@ public abstract class Sequence implements Iterable<Element>, SequenceOrElement {
 
     public boolean needed_or_hated = false;
 
-    final HashSet<Sequence> hated  = new HashSet<Sequence>();
+    public HashMap<Sequence,Boolean> canNeed = new HashMap<Sequence,Boolean>();
+    public HashMap<Sequence,Boolean> canKill = new HashMap<Sequence,Boolean>();
+
+    final HashSet<Sequence> hated   = new HashSet<Sequence>();
 
     final HashSet<Sequence> needs  = new HashSet<Sequence>();
     final HashSet<Sequence> hates  = new HashSet<Sequence>();
@@ -109,6 +112,20 @@ public abstract class Sequence implements Iterable<Element>, SequenceOrElement {
     /** the imaginary position before or after an element of a sequence; corresponds to an "LR item" */
     class Position implements IntegerMappable {
 
+        public int ord = -1;
+        public int compareTo(Position p, Walk.Cache cache) {
+            Position position = this;
+            Position rposition = p;
+            int ret = 0;
+            if (Reduction.canKill(cache, position, rposition) &&
+                Reduction.canKill(cache, rposition, position)) throw new Error();
+            if      (Reduction.canKill(cache, position,   rposition)) ret =  1;
+            else if (Reduction.canKill(cache, rposition, position)) ret = -1;
+            if      (Reduction.canNeed(cache, position,   rposition)) ret =  1;
+            else if (Reduction.canNeed(cache, rposition, position)) ret = -1;
+            return ret;
+        }
+
         private Forest zero = null;
         public Forest zero(Input.Region reg) {
             if (zero != null) return zero;