From: adam <adam@megacz.com>
Date: Mon, 26 Feb 2007 01:31:00 +0000 (-0500)
Subject: Use ordinal pre-sorting rather than on-the-fly compares
X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=0620c2d97d6df986d74dbe13160afb1435096431

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

darcs-hash:20070226013100-5007d-abd1a29d67900dd808080e90efb0b87ccb36d600.gz
---

diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index df94e83..adf24c4 100644
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -162,11 +162,29 @@ public abstract class Parser<Token, NodeType> {
                     if (p.element() != null && p.element() instanceof Atom)
                         state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()).getTokenTopology()));
                 }
+
             if (top instanceof IntegerTopology)
                 for(State<Token> state : all_states) {
                     state.oreductions = state.reductions.optimize(((IntegerTopology)top).functor());
                     state.oshifts = state.shifts.optimize(((IntegerTopology)top).functor());
                 }
+
+            // crude algorithm to assing an ordinal ordering to every position
+            ArrayList<Sequence.Position> al = new ArrayList<Sequence.Position>();
+            for(State s : all_states) {
+                for(Object po : s) {
+                    Sequence.Position p = (Sequence.Position)po;
+                    if (al.contains(p)) continue;
+                    int i=0;
+                    for(; i<al.size(); i++) {
+                        if (p.compareTo(al.get(i), cache) > 0)
+                            break;
+                    }
+                    al.add(i, p);
+                }
+            }
+            for(int i=0; i<al.size(); i++)
+                al.get(i).ord = i;
         }
 
         private boolean isRightNullable(Position p) {
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;
     }
 }
diff --git a/src/edu/berkeley/sbp/Sequence.java b/src/edu/berkeley/sbp/Sequence.java
index d3d8d8a..a029274 100644
--- 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;