GSS: use PriorityQueue, remove ugly debugging garbage

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

diff --git a/src/edu/berkeley/sbp/GSS.java b/src/edu/berkeley/sbp/GSS.java
index be4276f..f222fe5 100644 (file)
--- 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)
@@ -94,34 +95,8 @@ class GSS {
 
         /** 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) {