X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=7c1fb19f1e8bab3c2ac62ea828f7e5953790dca9;hb=93b9f1a57460257f71a4cef17419a723e294550d;hp=5c1b92f41f83ff066c676ae4be667a2630d444f5;hpb=a60fa7d36f9039881c6eac2b771bd53943d997b7;p=sbp.git

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index 5c1b92f..7c1fb19 100644
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -1,10 +1,11 @@
-// Copyright 2006 all rights reserved; see LICENSE file for BSD-style license
+// Copyright 2006-2007 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 edu.berkeley.sbp.Sequence.Pos;
+import edu.berkeley.sbp.Sequence.Pos;
 import java.io.*;
 import java.util.*;
 import java.lang.reflect.*;
@@ -26,7 +27,7 @@ class GSS {
     class Phase<Tok> implements Invokable<State, Result>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
 
         // FIXME: right now, these are the performance bottleneck
-        private HashMapBag<Integer,Sequence>       performed       = new HashMapBag<Integer,Sequence>();
+        private HashMapBag<Integer,Integer>       performed       = new HashMapBag<Integer,Integer>();
 
         public Forest.Many finalResult;
         private PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
@@ -52,7 +53,6 @@ class GSS {
         private Phase prev;
         private Input.Location location;
         private Input.Location nextLocation;
-        private Input.Location prevLocation;
         
         private Forest forest;
 
@@ -62,18 +62,16 @@ class GSS {
             newNode(primordealResult, startState, true);
         }
         public Phase(Phase prev, Forest forest) throws ParseFailed, IOException {
-            this.prevLocation = input.getLocation();
-            this.token = (Tok)input.next();
             this.location = input.getLocation();
+            this.token = (Tok)input.next();
+            this.nextLocation = input.getLocation();
             this.prev = prev;
             this.forest = forest;
             this.pos = prev==null ? 0 : prev.pos+1;
-            this.nextLocation = input.getLocation();
             if (prev != null) prev.shift(this, forest);
             numReductions = 0;
 
             int minPhasePos = Integer.MAX_VALUE;
-            int maxOrd = -1;
             Reduction best = null;
             //System.out.println("==============================================================================");
             while(!reductionQueue.isEmpty()) {
@@ -86,7 +84,6 @@ class GSS {
                 if (r.parentPhase() != null) {
                     if (r.parentPhase().pos < minPhasePos) {
                         minPhasePos = r.parentPhase().pos;
-                        maxOrd = r.reduction().ord;
                         best = r;
                     } else if (r.parentPhase().pos == minPhasePos) {
                         /*
@@ -95,7 +92,6 @@ class GSS {
                                             Parser.mastercache.comparePositions(r.reduction(), best.reduction())+"\n"+r.compareTo(best)+
                                             "\n"+(r.reduction().ord-best.reduction().ord));
                         */
-                        maxOrd = r.reduction().ord;
                         best = r;
                     }
                 }
@@ -112,9 +108,7 @@ class GSS {
             return true;
         }
 
-        public Input.Location getPrevLocation() { return prevLocation; }
         public Input.Location getLocation() { return location; }
-        public Input.Region getRegion() { return prevLocation.createRegion(location); }
         public Input.Location getNextLocation() { return nextLocation; }
         public boolean        isFrontier() { return hash!=null; }
 
@@ -126,8 +120,7 @@ class GSS {
                 IntPairMap<Node> h = prev.hash;
                 prev.hash = null;
                 prev.performed = null;
-                for(Node n : h)
-                    n.check();
+                for(Node n : h) n.check();
             }
             numOldNodes = hash.size();
             for(Node n : hash.values()) {
@@ -161,19 +154,22 @@ class GSS {
             for(Node n : hash) n.check();
         }
 
-        void newNodeFromReduction(Result result, State state, Position reduction) {
+        Input.Region getRegionFromThisToNext() {
+            return getLocation().createRegion(getNextLocation());
+        }
+
+        void newNodeFromReduction(Result result, State state, Pos reduction) {
             int pos = result.phase().pos;
-            Sequence owner = reduction.owner();
-            for(Sequence s : owner.hates())
+            for(int s : reduction.hates())
                 if (performed.contains(pos, s))
                     return;
-            for(Sequence s : owner.needs())
+            for(int s : reduction.needs())
                 if (!performed.contains(pos, s))
                     return;
-            if (owner.needed_or_hated && !performed.contains(pos, owner))
-                performed.add(pos, owner);
+            if (reduction.owner_needed_or_hated() && !performed.contains(pos, reduction.provides()))
+                performed.add(pos, reduction.provides());
             if (state!=null)
-                newNode(result, state, reduction.pos<=0);
+                newNode(result, state, reduction.numPops()<=0);
         }
 
         /** add a new node (merging with existing nodes if possible)
@@ -185,7 +181,7 @@ class GSS {
          */
         private boolean newNode(Result result, State state, boolean fromEmptyReduction) {
             Node p = hash.get(state, result.phase());
-            if (p != null) { p.addResult(result); return true; }
+            if (p != null) { p.addResult(result); return !state.doomed(); }
             do {
                 if (token != null && state.canShift(token)) break;
                 if (state.isAccepting()) break;
@@ -195,7 +191,7 @@ class GSS {
             Node n = new Node(Phase.this, result, state, fromEmptyReduction);  // ALLOC
             for(Object s : state.conjunctStates)
                 newNode(new Result(null, n, null), (State)s, fromEmptyReduction);
-            return true;
+            return !n.state().doomed();
         }
 
         public int toInt() { return pos+1; }