fork download
copy 
  1. /* package whatever; // don't place package name! */
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. import java.util.Objects;
  5. import java.util.regex.Matcher;
  6. import java.util.regex.Pattern;
  7.  
  8. class Word {
  9.  
  10.     public static void main(String[] args) {
  11.         Symbol sa = new Symbol("a");
  12.         Symbol sb = new Symbol("b");
  13.         Symbol sc = new Symbol("c");
  14.         Symbol sd = new Symbol("d");
  15.         Symbol se = new Symbol("e");
  16.         Symbol s1 = new Symbol("1");
  17.         Symbol s2 = new Symbol("2");
  18.         Symbol s3 = new Symbol("3");
  19.         Symbol s4 = new Symbol("4");
  20.         Symbol sat = new Symbol("@");
  21.         Symbol sdot = new Symbol(".");
  22.  
  23.         Symbol[] chars = {sa, sb, sc, sd, se, s1, s2, s3, s4};
  24.  
  25.         Symbol[][][] tests = {
  26.                 {
  27.                     chars,
  28.                 },
  29.                 {
  30.                     chars,
  31.                     chars,
  32.                     chars,
  33.                     {sat},
  34.                     chars,
  35.                     chars,
  36.                     chars,
  37.                     {sdot},
  38.                     chars,
  39.                     chars,
  40.                     chars,
  41.                 }
  42.         };
  43.  
  44.         Word[] testcases = new Word[tests.length];
  45.         int pos = 0;
  46.         for (Symbol[][] syms : tests) {
  47.             List<Symbol> word = new ArrayList<>();
  48.             for (Symbol[] choices : syms) {
  49.                 List<SymbolChoice> opts = new ArrayList<>();
  50.                 for (Symbol c : choices) {
  51.                     opts.add(new SymbolChoice(c));
  52.                 }
  53.                 word.add(new Symbol(choices[0].value, opts));
  54.             }
  55.             testcases[pos++] = new Word(word);
  56.         }
  57.  
  58.         long[] warmups = new long[10000];
  59.         long max = Long.MIN_VALUE;
  60.         long min = Long.MAX_VALUE;
  61.         long sum = 0;
  62.         for (int i = 0; i < warmups.length; i++) {
  63.             long start = System.nanoTime();
  64.             testcases[0].forceFitRegex("a", false);
  65.             warmups[i] = System.nanoTime() - start;
  66.             min = warmups[i] < min ? warmups[i] : min; 
  67.             max = warmups[i] > max ? warmups[i] : max;
  68.             sum += warmups[i];
  69.         }
  70.         System.out.printf("Warmups %d max %d min %d avg %.2f%n", warmups.length, max, min, sum / (double)warmups.length);
  71.  
  72.  
  73.         for (Word torun : testcases) {
  74.             long time = System.nanoTime();
  75.             List<List<SymbolChoice>> result = torun.forceFitRegex("[bcd]+@[a-z]+\\.[a-z]+", true);
  76.             time = System.nanoTime() - time;
  77.             System.out.printf("Result %d in %.3fms%n", result.size(), time / 1000000.0);
  78.  
  79.         }
  80.  
  81.     }
  82.  
  83.     private static class Symbol {
  84.  
  85.         private final String value;
  86.         private final List<SymbolChoice> choices;
  87.  
  88.         public Symbol(String value) {
  89.             this.value = value;
  90.             this.choices = null;
  91.         }
  92.  
  93.  
  94.  
  95.  
  96.         public Symbol(String value, List<SymbolChoice> choices) {
  97.             this.value = value;
  98.             this.choices = choices;
  99.         }
  100.  
  101.  
  102.         public List<SymbolChoice> getSymbolChoices() {
  103.             return choices;
  104.         }
  105.  
  106.         @Override
  107.         public String toString() {
  108.             return value;
  109.         }
  110.  
  111.     }
  112.  
  113.     private static class SymbolChoice {
  114.  
  115.         private final Symbol symbol;
  116.  
  117.         public SymbolChoice(Symbol symbol) {
  118.             this.symbol = symbol;
  119.         }
  120.  
  121.         @Override
  122.         public String toString() {
  123.             return "C:" + symbol;
  124.         }
  125.  
  126.     }
  127.  
  128.     private final List<Symbol> syms;
  129.  
  130.     public Word(List<Symbol> syms) {
  131.         super();
  132.         this.syms = syms;
  133.     }
  134.  
  135.     private List<Symbol> getSymbols() {
  136.         return syms;
  137.     }
  138.  
  139.     public List<List<SymbolChoice>> forceFitRegex(final String regex) {
  140.         return forceFitRegex(regex, false);
  141.     }
  142.  
  143.     public List<List<SymbolChoice>> forceFitRegex(final String regex, boolean debug) {
  144.         Objects.requireNonNull(regex, "regex");
  145.  
  146.         final List<Symbol> symbols = getSymbols();
  147.  
  148.         SymbolChoice[][] options = new SymbolChoice[symbols.size()][];
  149.         int pos = 0;
  150.         int combinations = 1;
  151.         final SymbolChoice[] emptyChoice = new SymbolChoice[0];
  152.         for (Symbol symbol : getSymbols()) {
  153.             options[pos] = symbol.getSymbolChoices().toArray(emptyChoice);
  154.             combinations *= options[pos].length;
  155.             pos++;
  156.         }
  157.  
  158.         Pattern pattern = Pattern.compile(regex);
  159.         int[] stack = new int[options.length];
  160.         int[] sbsize = new int[options.length + 1];
  161.  
  162.         List<List<SymbolChoice>> listOfSymbolChoices = new ArrayList<List<SymbolChoice>>();
  163.         StringBuilder sb = new StringBuilder(stack.length);
  164.         int depth = 0;
  165.         int testcnt = 0;
  166.         while (depth >= 0) {
  167.             if (stack[depth] >= options[depth].length) {
  168.                 stack[depth] = 0;
  169.                 depth--;
  170.                 if (depth >= 0) {
  171.                     sb.setLength(sbsize[depth]);
  172.                     stack[depth]++;
  173.                 }
  174.             } else {
  175.                 sb.append(options[depth][stack[depth]].symbol.value);
  176.                 Matcher matcher = pattern.matcher(sb);
  177.                 testcnt++;
  178.                 boolean found = matcher.matches();
  179.                 if (depth == options.length - 1) {
  180.                     if (found) {
  181.                         // we have a viable answer here, we can report it....
  182.                         List<SymbolChoice> match = new ArrayList<>(stack.length);
  183.                         for (int i = 0; i < stack.length; i++) {
  184.                             match.add(options[i][stack[i]]);
  185.                         }
  186.                         listOfSymbolChoices.add(match);
  187.                     }
  188.                     sb.setLength(sbsize[depth]);
  189.                     stack[depth]++;
  190.                 } else if (found || matcher.hitEnd()) {
  191.                     // we have a viable answer here, we can descend....
  192.                     depth++;
  193.                     sbsize[depth] = sb.length();
  194.                 } else {
  195.                     // nothing viable down here....
  196.                     sb.setLength(sbsize[depth]);
  197.                     stack[depth]++;
  198.                 }
  199.             }
  200.         }
  201.  
  202.         if (debug) {
  203.             System.out.println("Combinations: " + combinations + " actual tests " + testcnt);
  204.         }
  205.  
  206.         return listOfSymbolChoices;
  207.     }
  208.  
  209. }
  210.  
Success #stdin #stdout 1.67s 381632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Warmups 10000 max 9409213 min 3553 avg 10095.83
Combinations: 9 actual tests 9
Result 0 in 0.237ms
Combinations: 387420489 actual tests 952677
Result 421875 in 1484.563ms
https://ideone.com/hfg3TA
language:
Java (12.0.1)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!