X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Fedu%2Fberkeley%2Fsbp%2FGSS.java;h=91ef7652187e7b7f2ee88c4d0fe112cb79e74eba;hb=b7cd03704a32c751575472eadfd433ce15694fce;hp=be4276fb0725d56393a7332b3dca6037d8c7f05a;hpb=e84029a8b861075d6d0ed5040f919b2e4da4c98f;p=sbp.git

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index be4276f..91ef765 100644
--- a/src/edu/berkeley/sbp/GSS.java
+++ b/src/edu/berkeley/sbp/GSS.java
@@ -25,7 +25,7 @@ class GSS {
     /** corresponds to a positions <i>between tokens</i> the input stream; same as Tomita's U_i's */
     class Phase<Tok> implements Invokable<State, Result, Object>, IntegerMappable, GraphViz.ToGraphViz, Iterable<Node> {
 
-        public ArrayList<Reduction> reductionQueue = new ArrayList<Reduction>();
+        public PriorityQueue<Reduction> reductionQueue = new PriorityQueue<Reduction>();
 
         public void invoke(State st, Result result, Object o) {
             //shifts++;
@@ -38,7 +38,7 @@ class GSS {
 
         public IntPairMap<Node> hash;  /* ALLOC */
         private boolean good;
-         Phase next = null;
+        private Phase next = null;
         private Phase prev;
         private Input.Location location;
         private Input.Location nextLocation;
@@ -61,7 +61,8 @@ class GSS {
             finalResult = null;
             if (prev != null) prev.shift(this, forest);
         }
-      
+
+        public boolean isFrontier() { return next==null; }
         public boolean isDone() throws ParseFailed {
             if (token != null) return false;
             if (token==null && finalResult==null)
@@ -88,40 +89,15 @@ class GSS {
                 if (token == null) continue;
                 n.state().invokeShifts(token, this, new Result(result, n, null), null);
             }
+            for(Node n : hash.values()) n.check();
             if (!good && token!=null) ParseFailed.error("unexpected character", this);
             if (token==null && finalResult==null) ParseFailed.error("unexpected end of file", this);
         }
 
         /** perform all reduction operations */
         public void reduce() throws ParseFailed {
-            Reduction last = null;
-            while(!reductionQueue.isEmpty()) {
-                Reduction r = null;
-
-                // ugly
-                OUTER: for(int i=0; i<reductionQueue.size(); i++) {
-                    for(int j=0; j<reductionQueue.size(); j++) {
-                        if (i==j) continue;
-                        if (reductionQueue.get(i).compareTo(reductionQueue.get(j)) > 0)
-                            continue OUTER;
-                    }
-                    r = reductionQueue.get(i);
-                    reductionQueue.remove(r);
-                    break;
-                }
-
-                /*
-                if (last == null) last = r;
-                else if (r.compareTo(last) > 0) last = r;
-                else if (r.compareTo(last) < 0) {
-                    if (r.targetPhase() != null)
-                        System.out.println("err " + last.compareTo(r) + " " + last.targetPhase().pos() +
-                                           " "    + r.targetPhase().pos() + " " + pos);
-                }
-                */
-
-                r.perform();
-            }
+            while(!reductionQueue.isEmpty())
+                reductionQueue.poll().perform();
         }
 
         public void newNodeFromReduction(Result result, State state, boolean fromEmptyReduction, Position reduction) {