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

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

diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index df94e83..adf24c4 100644 (file)
--- 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) {