Commits

Anonymous committed 367e36e

Trying to optimize the determinization algorithm to run faster in less memory.

Comments (0)

Files changed (1)

src/info/lahoda/papers/code/DPDA.java

 package info.lahoda.papers.code;
 
-import java.util.Arrays;
-import java.util.Collection;
+import java.util.BitSet;
 import java.util.HashMap;
 import java.util.HashSet;
+import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
      * @return
      */
     public static DPDA create(NPDA npda) {
-        DPDAState startingState = new DPDAState(Arrays.asList(new DPDAStateElement(Constants.nostate, 0)));
+        DPDAState emptyState = DPDAState.createEmpty(npda.states.size());
+        DPDAPushDown emptyPushDown = DPDAPushDown.createEmpty(npda.states.size());
+        DPDAState startingState = emptyState.add(Constants.nostate, 0);
         Set<DPDAState> states = new HashSet<DPDAState>();
         Set<DPDAPushDown> pushdownSymbols = new HashSet<DPDAPushDown>();
         Map<DPDAKey, DPDATarget> transitionTable = new HashMap<DPDAKey, DPDATarget>();
                 //call:
                 for (char a : npda.alphabet) {
                     assert a != Constants.UP; //should not currently happen
-                    DPDAState targetState = new DPDAState();
-                    DPDAPushDown targetPushdown = new DPDAPushDown();
+                    DPDAState targetState = emptyState;
+                    DPDAPushDown targetPushdown = emptyPushDown;
 
                     for (DPDAStateElement pq : state) {
                         for (PDATarget t : npda.getTarget(new PDAKey(pq.getState(), a, Constants.epsilon))) {
-                            targetState.add(new DPDAStateElement(t.pushDown, t.state));
-                            targetPushdown.add(new DPDAPushDownElement(pq.getPushdown(), t.pushDown));
+                            targetState = targetState.add(t.pushDown, t.state);
+                            targetPushdown = targetPushdown.add(pq.getPushdown(), t.pushDown);
                         }
                     }
 
                 //return for currently existing pushdownSymbols:
                 for (DPDAPushDown pdE : pushdownSymbols) {
                     DPDAState stateE = state;
-                    DPDAState targetState = new DPDAState();
+                    DPDAState targetState = emptyState;
 
                     for (DPDAStateElement pq : stateE) {
                         for (DPDAPushDownElement pd : pdE) {
                             if (pd.getSecond() != pq.getPushdown()) continue;
 
                             for (PDATarget t : npda.getTarget(new PDAKey(pq.getState(), Constants.UP, pd.getSecond()))) {
-                                targetState.add(new DPDAStateElement(pd.getFirst(), t.state));
+                                targetState = targetState.add(pd.getFirst(), t.state);
                             }
                         }
                     }
             while (!todoPushdown.isEmpty()) {
                 DPDAPushDown pdE = todoPushdown.remove(0);
                 for (DPDAState stateE : new HashSet<DPDAState>(states)) {
-                    DPDAState targetState = new DPDAState();
+                    DPDAState targetState = emptyState;
 
                     for (DPDAStateElement pq : stateE) {
                         for (DPDAPushDownElement pd : pdE) {
                             if (pd.getSecond() != pq.getPushdown()) continue;
 
                             for (PDATarget t : npda.getTarget(new PDAKey(pq.getState(), Constants.UP, pd.getSecond()))) {
-                                targetState.add(new DPDAStateElement(pd.getFirst(), t.state));
+                                targetState = targetState.add(pd.getFirst(), t.state);
                             }
                         }
                     }
             if (t == null) {
                 DPDAPushDown pdValue = pushDownStore.pop();
 
-//                System.err.println("pdValue=" + pdValue);
                 t = transitionTable.get(new DPDAKey(state, c, pdValue));
             }
 
                 pushDownStore.push(t.pushDown);
             }
 
-//            System.err.println("state=" + state);
             if (finalStates.contains(state)) {
                 result.add(pos);
             }
     }
 
     private static final class DPDAStateElement {
-        private final Integer pushdown;
-        private final Integer state;
-        public DPDAStateElement(Integer pushdown, Integer state) {
+        private final int pushdown;
+        private final int state;
+        private DPDAStateElement(int pushdown, int state) {
             this.pushdown = pushdown;
             this.state = state;
         }
 
-        public Integer getPushdown() {
+        public int getPushdown() {
             return pushdown;
         }
 
-        public Integer getState() {
+        public int getState() {
             return state;
         }
 
         @Override
-        public boolean equals(Object obj) {
-            if (obj == null) {
-                return false;
-            }
-            if (getClass() != obj.getClass()) {
-                return false;
-            }
-            final DPDAStateElement other = (DPDAStateElement) obj;
-            if (!Objects.equals(this.pushdown, other.pushdown)) {
-                return false;
-            }
-            if (!Objects.equals(this.state, other.state)) {
-                return false;
-            }
-            return true;
-        }
-
-        @Override
-        public int hashCode() {
-            int hash = 7;
-            hash = 79 * hash + Objects.hashCode(this.pushdown);
-            hash = 79 * hash + Objects.hashCode(this.state);
-            return hash;
-        }
-
-        @Override
         public String toString() {
             return "DPDAStateElement{" + "pushdown=" + pushdown + "state=" + state + '}';
         }
         
     }
 
-    private static final class DPDAState extends HashSet<DPDAStateElement> {
-        public DPDAState() {
+    private static final class DPDAState implements Iterable<DPDAStateElement> {
+        private final DPDAState empty;
+        private final int maxStates;
+        private final BitSet elements;
+        private final Map<BitSet, DPDAState> bitset2State;
+        
+        private DPDAState(int maxStates) {
+            this.empty = this;
+            this.maxStates = maxStates;
+            this.elements = new BitSet(0);
+            this.bitset2State = new HashMap<BitSet, DPDAState>();
         }
-        public DPDAState(Collection<? extends DPDAStateElement> c) {
-            super(c);
+        
+        private DPDAState(DPDAState empty, BitSet elements) {
+            this.empty = empty;
+            this.maxStates = empty.maxStates;
+            this.elements = elements;
+            this.bitset2State = null;
+        }
+
+        public Iterator<DPDAStateElement> iterator() {
+            return new Iterator<DPDAStateElement>() {
+                private int bit = elements.nextSetBit(0);
+                public boolean hasNext() {
+                    return bit >= 0;
+                }
+                public DPDAStateElement next() {
+                    DPDAStateElement res = new DPDAStateElement(bit / maxStates - 1, bit % maxStates);
+                    
+                    bit = elements.nextSetBit(bit + 1);
+                    
+                    return res;
+                }
+                public void remove() {
+                    throw new UnsupportedOperationException("");
+                }
+            };
+        }
+        
+        public DPDAState add(int pushDown, int state) {
+            int el = (pushDown + 1) * maxStates + state;
+            
+            if (!elements.get(el)) {
+                BitSet bs = new BitSet(Math.max(elements.length(), el));
+
+                bs.or(elements);
+                bs.set(el);
+                DPDAState stateObj = empty.bitset2State.get(bs);
+                
+                if (stateObj == null) {
+                    empty.bitset2State.put(bs, stateObj = new DPDAState(empty, bs));
+                }
+                
+                return stateObj;
+            }
+            
+            return this;
+        }
+
+        public static DPDAState createEmpty(int maxStates) {
+            return new DPDAState(maxStates);
         }
     }
 
     private static final class DPDAPushDownElement {
-        private final Integer first;
-        private final Integer second;
+        private final int first;
+        private final int second;
 
-        public DPDAPushDownElement(Integer first, Integer second) {
+        public DPDAPushDownElement(int first, int second) {
             this.first = first;
             this.second = second;
         }
 
-        public Integer getFirst() {
+        public int getFirst() {
             return first;
         }
 
-        public Integer getSecond() {
+        public int getSecond() {
             return second;
         }
 
         @Override
-        public boolean equals(Object obj) {
-            if (obj == null) {
-                return false;
-            }
-            if (getClass() != obj.getClass()) {
-                return false;
-            }
-            final DPDAPushDownElement other = (DPDAPushDownElement) obj;
-            if (!Objects.equals(this.first, other.first)) {
-                return false;
-            }
-            if (!Objects.equals(this.second, other.second)) {
-                return false;
-            }
-            return true;
-        }
-
-        @Override
-        public int hashCode() {
-            int hash = 7;
-            hash = 71 * hash + Objects.hashCode(this.first);
-            hash = 71 * hash + Objects.hashCode(this.second);
-            return hash;
-        }
-
-        @Override
         public String toString() {
             return "DPDAPushDownElement{" + "first=" + first + "second=" + second + '}';
         }
         
     }
 
-    private static final class DPDAPushDown extends HashSet<DPDAPushDownElement> {}
+    private static final class DPDAPushDown implements Iterable<DPDAPushDownElement> {
+        private final DPDAPushDown empty;
+        private final int maxPushdown;
+        private final BitSet elements;
+        private final Map<BitSet, DPDAPushDown> bitset2PushDown;
+        
+        private DPDAPushDown(int maxPushdown) {
+            this.empty = this;
+            this.maxPushdown = maxPushdown;
+            this.elements = new BitSet(0);
+            this.bitset2PushDown = new HashMap<BitSet, DPDAPushDown>();
+        }
+        
+        private DPDAPushDown(DPDAPushDown empty, BitSet elements) {
+            this.empty = empty;
+            this.maxPushdown = empty.maxPushdown;
+            this.elements = elements;
+            this.bitset2PushDown = null;
+        }
+
+        public Iterator<DPDAPushDownElement> iterator() {
+            return new Iterator<DPDAPushDownElement>() {
+                private int bit = elements.nextSetBit(0);
+                public boolean hasNext() {
+                    return bit >= 0;
+                }
+                public DPDAPushDownElement next() {
+                    DPDAPushDownElement res = new DPDAPushDownElement(bit / (maxPushdown + 1) - 1, (bit % (maxPushdown + 1)) - 1);
+                    
+                    bit = elements.nextSetBit(bit + 1);
+                    
+                    return res;
+                }
+                public void remove() {
+                    throw new UnsupportedOperationException("");
+                }
+            };
+        }
+        
+        public DPDAPushDown add(int first, int second) {
+            int el = (first + 1) * (maxPushdown + 1) + second + 1;
+            
+            if (!elements.get(el)) {
+                BitSet bs = new BitSet(Math.max(elements.length(), el));
+
+                bs.or(elements);
+                bs.set(el);
+
+                DPDAPushDown stateObj = empty.bitset2PushDown.get(bs);
+                
+                if (stateObj == null) {
+                    empty.bitset2PushDown.put(bs, stateObj = new DPDAPushDown(empty, bs));
+                }
+                
+                return stateObj;
+            }
+            
+            return this;
+        }
+
+        public static DPDAPushDown createEmpty(int maxPushdown) {
+            return new DPDAPushDown(maxPushdown);
+        }
+    }
 }