bundles/org.simantics.scl.compiler/src/org/simantics/scl/compiler/parser/regexp/automata/NFA.java

   1 package org.simantics.scl.compiler.parser.regexp.automata;
   2
   3 import gnu.trove.list.array.TIntArrayList;
   4 import gnu.trove.map.hash.TIntObjectHashMap;
   5 import gnu.trove.map.hash.TObjectIntHashMap;
   6 import gnu.trove.procedure.TIntIntProcedure;
   7 import gnu.trove.procedure.TIntObjectProcedure;
   8 import gnu.trove.procedure.TIntProcedure;
   9 import gnu.trove.set.hash.TIntHashSet;
  10
  11 import java.util.ArrayList;
  12
  13 public class NFA implements Automata {
  14
  15     private static class State {
  16         TIntObjectHashMap<TIntArrayList> transitions = new TIntObjectHashMap<TIntArrayList>();
  17         TIntArrayList epsilonTransitions = new TIntArrayList();
  18         boolean accepts;
  19
  20         private void addTransition(int symbol, int target) {
  21             TIntArrayList l = transitions.get(symbol);
  22             if(l == null) {
  23                 l = new TIntArrayList();
  24                 l.add(target);
  25                 transitions.put(symbol, l);
  26             }
  27             else if(!l.contains(target))
  28                 l.add(target);
  29         }
  30
  31         private void addEpsilonTransition(int target) {
  32             if(!epsilonTransitions.contains(target))
  33                 epsilonTransitions.add(target);
  34         }
  35     }
  36
  37     private ArrayList<State> states = new ArrayList<State>();
  38     private int initialState;
  39
  40     public int size() {
  41         return states.size();
  42     }
  43
  44     public void setInitialState(int initialState) {
  45         this.initialState = initialState;
  46     }
  47
  48     public int getInitialState() {
  49         return initialState;
  50     }
  51
  52     public int newState() {
  53         int id = states.size();
  54         states.add(new State());
  55         return id;
  56     }
  57
  58     public void setAccepts(int id, boolean accepts) {
  59         states.get(id).accepts = accepts;
  60     }
  61
  62     public boolean getAccepts(int id) {
  63         return states.get(id).accepts;
  64     }
  65
  66     public void addTransition(int source, int symbol, int target) {
  67         states.get(source).addTransition(symbol, target);
  68     }
  69
  70     public void forEachTransition(int source, final TIntIntProcedure proc) {
  71         states.get(source).transitions.forEachEntry(new TIntObjectProcedure<TIntArrayList>() {
  72             @Override
  73             public boolean execute(int a, TIntArrayList b) {
  74                 for(int i=0;i<b.size();++i)
  75                     if(!proc.execute(a, b.get(i)))
  76                         return false;
  77                 return true;
  78             }
  79         });
  80     }
  81
  82     public void addEpsilonTransition(int source, int target) {
  83         states.get(source).addEpsilonTransition(target);
  84     }
  85
  86     public void forEachEpsilonTransition(int source, final TIntProcedure proc) {
  87         states.get(source).epsilonTransitions.forEach(proc);
  88     }
  89
  90     private TIntArrayList closure(final TIntHashSet stateSet) {
  91         final TIntArrayList result = new TIntArrayList(stateSet);
  92         TIntProcedure proc = new TIntProcedure() {
  93             @Override
  94             public boolean execute(int value) {
  95                 if(stateSet.add(value))
  96                     result.add(value);
  97                 return true;
  98             }
  99         };
 100         for(int i=0;i<result.size();++i)
 101             forEachEpsilonTransition(result.get(i), proc);
 102         result.sort();
 103         return result;
 104     }
 105
 106     public DFA determinize() {
 107         final DFA aut = new DFA();
 108
 109         final ArrayList<TIntArrayList> stack = new ArrayList<TIntArrayList>();
 110         final TObjectIntHashMap<TIntArrayList> map = new TObjectIntHashMap<TIntArrayList>();
 111         {
 112             TIntHashSet initialSet = new TIntHashSet(4);
 113             initialSet.add(getInitialState());
 114             TIntArrayList stateList = closure(initialSet);
 115
 116             int stateId = aut.newState();
 117             map.put(stateList, stateId);
 118             aut.setInitialState(stateId);
 119
 120             stack.add(stateList);
 121         }
 122
 123         while(!stack.isEmpty()) {
 124             TIntArrayList curList = stack.remove(stack.size()-1);
 125             int[] stateArray = curList.toArray();
 126             final int id = map.get(curList);
 127
 128             // Transitions
 129             final TIntObjectHashMap<TIntHashSet> transitions =
 130                     new TIntObjectHashMap<TIntHashSet>();
 131             TIntIntProcedure proc = new TIntIntProcedure() {
 132                 @Override
 133                 public boolean execute(int symbol, int b) {
 134                     TIntHashSet set = transitions.get(symbol);
 135                     if(set == null) {
 136                         set = new TIntHashSet();
 137                         transitions.put(symbol, set);
 138                     }
 139                     set.add(b);
 140                     return true;
 141                 }
 142             };
 143             for(int s : stateArray)
 144                 forEachTransition(s, proc);
 145
 146             // Create transition targets
 147             transitions.forEachEntry(new TIntObjectProcedure<TIntHashSet>() {
 148                 @Override
 149                 public boolean execute(int symbol, TIntHashSet b) {
 150                     TIntArrayList stateList = closure(b);
 151
 152                     if(map.containsKey(stateList))
 153                         aut.addTransition(id, symbol, map.get(stateList));
 154                     else {
 155                         int stateId = aut.newState();
 156                         map.put(stateList, stateId);
 157                         stack.add(stateList);
 158
 159                         aut.addTransition(id, symbol, stateId);
 160                     }
 161                     return true;
 162                 }
 163             });
 164
 165             // Accepts
 166             for(int s : stateArray)
 167                 if(getAccepts(s)) {
 168                     aut.setAccepts(id, true);
 169                     break;
 170                 }
 171         }
 172
 173         return aut;
 174     }
 175
 176 }