Commits

Anonymous committed 4d27fba

Adding tests for performance.

Comments (0)

Files changed (2)

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

  * @author lahvac
  */
 public final class DPDA {
+    private final Set<DPDAState> states;
+    private final Set<DPDAPushDown> pushDownSymbols;
     private final DPDAState starting;
     private final Map<DPDAKey, DPDATarget> transitionTable;
     private final Set<DPDAState> finalStates;
     
-    private DPDA(DPDAState state, Map<DPDAKey, DPDATarget> transitionTable, Set<DPDAState> finalStates) {
-        this.starting = state;
+    private DPDA(Set<DPDAState> states, Set<DPDAPushDown> pushDownSymbols, DPDAState starting, Map<DPDAKey, DPDATarget> transitionTable, Set<DPDAState> finalStates) {
+        this.states = states;
+        this.pushDownSymbols = pushDownSymbols;
+        this.starting = starting;
         this.transitionTable = transitionTable;
         this.finalStates = finalStates;
     }
             }
         }
 
-//        System.err.println("states=" + states.size());
-
-        return new DPDA(startingState, transitionTable, finalStates);
+        return new DPDA(states, pushdownSymbols, startingState, transitionTable, finalStates);
     }
 
     public List<Integer> match(TreeNode text) {
         return result;
     }
 
+    public int getStateCount() {
+        return states.size();
+    }
+
+    public int getPushDownSymbolsCount() {
+        return pushDownSymbols.size();
+    }
+    
     public static class DPDAKey {
         private final DPDAState state;
         private final char input;

test/info/lahoda/papers/code/DPDATest.java

 package info.lahoda.papers.code;
 
 import java.util.Arrays;
+import java.util.regex.Matcher;
+import java.util.regex.Pattern;
 import junit.framework.Assert;
 import org.junit.Test;
 
         Assert.assertEquals(Arrays.asList(15, 22, 33), dpda.match(text));
     }
 
+//    @Test
+//    public void testComplexity2a() {
+//        testComplexity2();
+//    }
+//
+    private static void testComplexity(String start, NextTestCase next) {
+        String pattern = start;
+        int previousStateCount = 0;
+        int previousPushDownCount = 0;
+
+        do {
+            System.err.println("pattern=" + pattern);
+            NPDA npda = TPM.create(TreeNode.fromPrefixRanked(pattern), '0', '1', '2');
+            System.err.println("nfa states: " + npda.states.size() + ", pushdown symbols=" + npda.pushdownSymbols.size());
+            DPDA dpda = DPDA.create(npda);
+            System.err.print("dpda states: " + dpda.getStateCount());
+            if (previousStateCount > 0) System.err.print(", from previous: " + ((double) dpda.getStateCount()) / previousStateCount);
+            System.err.print("; pushdown symbols: " + dpda.getPushDownSymbolsCount());
+            if (previousPushDownCount > 0) System.err.print(", from previous: " + ((double) dpda.getPushDownSymbolsCount()) / previousPushDownCount);
+            System.err.println();
+            previousStateCount = dpda.getStateCount();
+            previousPushDownCount = dpda.getPushDownSymbolsCount();
+        } while ((pattern = next.next(pattern)) != null);
+    }
+
+    public static void main(String[] args) {
+        testComplexity("200", new NextTestCase() {
+            public String next(String current) {
+                return current.length() < 20 ? current.replaceFirst(Pattern.quote("0"), Matcher.quoteReplacement("200")) : null;
+            }
+        });
+        testComplexity("2++", new NextTestCase() {
+            public String next(String current) {
+                return current.length() < 10 ? current.replaceAll(Pattern.quote("+") + "$", Matcher.quoteReplacement("2++")) : null;
+            }
+        });
+        testComplexity("2++", new NextTestCase() {
+            public String next(String current) {
+                return current.length() < 9 ? current.replaceFirst(Pattern.quote("+"), Matcher.quoteReplacement("2++")) : null;
+            }
+        });
+    }
+
+    public interface NextTestCase {
+        public String next(String current);
+    }
+
 }