Commits

Anonymous committed aeadcf6

Using specialized classes instead of SimpleEntry etc. for readability.

  • Participants
  • Parent commits 2178af1

Comments (0)

Files changed (1)

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

 package info.lahoda.papers.code;
 
-import java.util.AbstractMap.SimpleEntry;
 import java.util.Arrays;
+import java.util.Collection;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
-import java.util.Map.Entry;
+import java.util.Objects;
 import java.util.Set;
 import java.util.Stack;
 
  * @author lahvac
  */
 public final class DPDA {
-    private final Set<Entry<Integer, Integer>> starting;
+    private final DPDAState starting;
     private final Map<DPDAKey, DPDATarget> transitionTable;
-    private final Set<Set<Entry<Integer, Integer>>> finalStates;
+    private final Set<DPDAState> finalStates;
     
-    private DPDA(Set<Entry<Integer, Integer>> state, Map<DPDAKey, DPDATarget> transitionTable, Set<Set<Entry<Integer, Integer>>> finalStates) {
+    private DPDA(DPDAState state, Map<DPDAKey, DPDATarget> transitionTable, Set<DPDAState> finalStates) {
         this.starting = state;
         this.transitionTable = transitionTable;
         this.finalStates = finalStates;
      * @return
      */
     public static DPDA create(NPDA npda) {
-        Set<Entry<Integer, Integer>> startingState = new HashSet<Entry<Integer, Integer>>(Arrays.asList(new SimpleEntry<Integer, Integer>(Constants.nostate, 0)));
-        Set<Set<Entry<Integer, Integer>>> states = new HashSet<Set<Entry<Integer, Integer>>>();
-        Set<Set<Entry<Integer, Integer>>> pushdownSymbols = new HashSet<Set<Entry<Integer, Integer>>>();
+        DPDAState startingState = new DPDAState(Arrays.asList(new DPDAStateElement(Constants.nostate, 0)));
+        Set<DPDAState> states = new HashSet<DPDAState>();
+        Set<DPDAPushDown> pushdownSymbols = new HashSet<DPDAPushDown>();
         Map<DPDAKey, DPDATarget> transitionTable = new HashMap<DPDAKey, DPDATarget>();
-        List<Set<Entry<Integer, Integer>>> todoStates = new LinkedList<Set<Entry<Integer, Integer>>>();
-        List<Set<Entry<Integer, Integer>>> todoPushdown = new LinkedList<Set<Entry<Integer, Integer>>>();
+        List<DPDAState> todoStates = new LinkedList<DPDAState>();
+        List<DPDAPushDown> todoPushdown = new LinkedList<DPDAPushDown>();
 
         todoStates.add(startingState);
         
-        int done = 0;
         boolean modified = true;
 
         while (modified) {
             modified = false;
             while (!todoStates.isEmpty()) {
-                Set<Entry<Integer, Integer>> state = todoStates.remove(0);
+                DPDAState state = todoStates.remove(0);
 
                 //call:
                 for (char a : npda.alphabet) {
                     assert a != Constants.UP; //should not currently happen
-                    Set<Entry<Integer, Integer>> targetState = new HashSet<Entry<Integer, Integer>>();
-                    Set<Entry<Integer, Integer>> targetPushdown = new HashSet<Entry<Integer, Integer>>();
+                    DPDAState targetState = new DPDAState();
+                    DPDAPushDown targetPushdown = new DPDAPushDown();
 
-                    for (Entry<Integer, Integer> pq : state) {
-                        for (PDATarget t : npda.getTarget(new PDAKey(pq.getValue(), a, Constants.epsilon))) {
-                            targetState.add(new SimpleEntry<Integer, Integer>(t.pushDown, t.state));
-                            targetPushdown.add(new SimpleEntry<Integer, Integer>(pq.getKey(), t.pushDown));
+                    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));
                         }
                     }
 
                 }
 
                 //return for currently existing pushdownSymbols:
-                for (Set<Entry<Integer, Integer>> pdE : pushdownSymbols) {
-                    Set<Entry<Integer, Integer>> stateE = state;
-                    Set<Entry<Integer, Integer>> targetState = new HashSet<Entry<Integer, Integer>>();
+                for (DPDAPushDown pdE : pushdownSymbols) {
+                    DPDAState stateE = state;
+                    DPDAState targetState = new DPDAState();
 
-                    for (Entry<Integer, Integer> pq : stateE) {
-                        for (Entry<Integer, Integer> pd : pdE) {
-                            if (pd.getValue() != pq.getKey()) continue;
+                    for (DPDAStateElement pq : stateE) {
+                        for (DPDAPushDownElement pd : pdE) {
+                            if (pd.getSecond() != pq.getPushdown()) continue;
 
-                            for (PDATarget t : npda.getTarget(new PDAKey(pq.getValue(), Constants.UP, pd.getValue()))) {
-                                targetState.add(new SimpleEntry<Integer, Integer>(pd.getKey(), t.state));
+                            for (PDATarget t : npda.getTarget(new PDAKey(pq.getState(), Constants.UP, pd.getSecond()))) {
+                                targetState.add(new DPDAStateElement(pd.getFirst(), t.state));
                             }
                         }
                     }
 
             //return for newly created pushdown symbols:
             while (!todoPushdown.isEmpty()) {
-                Set<Entry<Integer, Integer>> pdE = todoPushdown.remove(0);
-                for (Set<Entry<Integer, Integer>> stateE : new HashSet<Set<Entry<Integer, Integer>>>(states)) {
-                    Set<Entry<Integer, Integer>> targetState = new HashSet<Entry<Integer, Integer>>();
+                DPDAPushDown pdE = todoPushdown.remove(0);
+                for (DPDAState stateE : new HashSet<DPDAState>(states)) {
+                    DPDAState targetState = new DPDAState();
 
-                    for (Entry<Integer, Integer> pq : stateE) {
-                        for (Entry<Integer, Integer> pd : pdE) {
-                            if (pd.getValue() != pq.getKey()) continue;
+                    for (DPDAStateElement pq : stateE) {
+                        for (DPDAPushDownElement pd : pdE) {
+                            if (pd.getSecond() != pq.getPushdown()) continue;
 
-                            for (PDATarget t : npda.getTarget(new PDAKey(pq.getValue(), Constants.UP, pd.getValue()))) {
-                                targetState.add(new SimpleEntry<Integer, Integer>(pd.getKey(), t.state));
+                            for (PDATarget t : npda.getTarget(new PDAKey(pq.getState(), Constants.UP, pd.getSecond()))) {
+                                targetState.add(new DPDAStateElement(pd.getFirst(), t.state));
                             }
                         }
                     }
             }
         }
 
-        Set<Set<Entry<Integer, Integer>>> finalStates = new HashSet<Set<Entry<Integer, Integer>>>();
+        Set<DPDAState> finalStates = new HashSet<DPDAState>();
 
-        for (Set<Entry<Integer, Integer>> s : states) {
-            for (Entry<Integer, Integer> e : s) {
-                if (npda.isFinal(e.getValue())) {
+        for (DPDAState s : states) {
+            for (DPDAStateElement e : s) {
+                if (npda.isFinal(e.getState())) {
                     finalStates.add(s);
                     break;
                 }
 
     public List<Integer> match(TreeNode text) {
         List<Integer> result = new LinkedList<Integer>();
-        Set<Entry<Integer, Integer>> state = starting;
+        DPDAState state = starting;
         int pos = 0;
-        Stack<Set<Entry<Integer, Integer>>> pushDownStore = new Stack<Set<Entry<Integer, Integer>>>();
+        Stack<DPDAPushDown> pushDownStore = new Stack<DPDAPushDown>();
 
         for (char c : text.serialize()) {
             pos++;
             DPDATarget t = transitionTable.get(new DPDAKey(state, c, null));
 
             if (t == null) {
-                Set<Entry<Integer, Integer>> pdValue = pushDownStore.pop();
+                DPDAPushDown pdValue = pushDownStore.pop();
 
 //                System.err.println("pdValue=" + pdValue);
                 t = transitionTable.get(new DPDAKey(state, c, pdValue));
     }
 
     public static class DPDAKey {
-        private final Set<Entry<Integer, Integer>> state;
+        private final DPDAState state;
         private final char input;
-        private final Set<Entry<Integer, Integer>> pushDown;
+        private final DPDAPushDown pushDown;
 
-        public DPDAKey(Set<Entry<Integer, Integer>> state, char input, Set<Entry<Integer, Integer>> pushDown) {
+        public DPDAKey(DPDAState state, char input, DPDAPushDown pushDown) {
             this.state = state;
             this.input = input;
             this.pushDown = pushDown;
     }
 
     public static class DPDATarget {
-        public final Set<Entry<Integer, Integer>> state;
-        public final Set<Entry<Integer, Integer>> pushDown;
+        public final DPDAState state;
+        public final DPDAPushDown pushDown;
 
-        public DPDATarget(Set<Entry<Integer, Integer>> state, Set<Entry<Integer, Integer>> pushDown) {
+        public DPDATarget(DPDAState state, DPDAPushDown pushDown) {
             this.state = state;
             this.pushDown = pushDown;
         }
         public String toString() {
             return "Target{" + "state=" + state + ", pushDown=" + pushDown + '}';
         }
+    }
 
+    private static final class DPDAStateElement {
+        private final Integer pushdown;
+        private final Integer state;
+        public DPDAStateElement(Integer pushdown, Integer state) {
+            this.pushdown = pushdown;
+            this.state = state;
+        }
+
+        public Integer getPushdown() {
+            return pushdown;
+        }
+
+        public Integer 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() {
+        }
+        public DPDAState(Collection<? extends DPDAStateElement> c) {
+            super(c);
+        }
+    }
+
+    private static final class DPDAPushDownElement {
+        private final Integer first;
+        private final Integer second;
+
+        public DPDAPushDownElement(Integer first, Integer second) {
+            this.first = first;
+            this.second = second;
+        }
+
+        public Integer getFirst() {
+            return first;
+        }
+
+        public Integer 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> {}
 }