1 package org.simantics.scl.compiler.parser.regexp.automata;
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;
11 import java.util.ArrayList;
13 public class NFA implements Automata {
15 private static class State {
16 TIntObjectHashMap<TIntArrayList> transitions = new TIntObjectHashMap<TIntArrayList>();
17 TIntArrayList epsilonTransitions = new TIntArrayList();
20 private void addTransition(int symbol, int target) {
21 TIntArrayList l = transitions.get(symbol);
23 l = new TIntArrayList();
25 transitions.put(symbol, l);
27 else if(!l.contains(target))
31 private void addEpsilonTransition(int target) {
32 if(!epsilonTransitions.contains(target))
33 epsilonTransitions.add(target);
37 private ArrayList<State> states = new ArrayList<State>();
38 private int initialState;
44 public void setInitialState(int initialState) {
45 this.initialState = initialState;
48 public int getInitialState() {
52 public int newState() {
53 int id = states.size();
54 states.add(new State());
58 public void setAccepts(int id, boolean accepts) {
59 states.get(id).accepts = accepts;
62 public boolean getAccepts(int id) {
63 return states.get(id).accepts;
66 public void addTransition(int source, int symbol, int target) {
67 states.get(source).addTransition(symbol, target);
70 public void forEachTransition(int source, final TIntIntProcedure proc) {
71 states.get(source).transitions.forEachEntry(new TIntObjectProcedure<TIntArrayList>() {
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)))
82 public void addEpsilonTransition(int source, int target) {
83 states.get(source).addEpsilonTransition(target);
86 public void forEachEpsilonTransition(int source, final TIntProcedure proc) {
87 states.get(source).epsilonTransitions.forEach(proc);
90 private TIntArrayList closure(final TIntHashSet stateSet) {
91 final TIntArrayList result = new TIntArrayList(stateSet);
92 TIntProcedure proc = new TIntProcedure() {
94 public boolean execute(int value) {
95 if(stateSet.add(value))
100 for(int i=0;i<result.size();++i)
101 forEachEpsilonTransition(result.get(i), proc);
106 public DFA determinize() {
107 final DFA aut = new DFA();
109 final ArrayList<TIntArrayList> stack = new ArrayList<TIntArrayList>();
110 final TObjectIntHashMap<TIntArrayList> map = new TObjectIntHashMap<TIntArrayList>();
112 TIntHashSet initialSet = new TIntHashSet(4);
113 initialSet.add(getInitialState());
114 TIntArrayList stateList = closure(initialSet);
116 int stateId = aut.newState();
117 map.put(stateList, stateId);
118 aut.setInitialState(stateId);
120 stack.add(stateList);
123 while(!stack.isEmpty()) {
124 TIntArrayList curList = stack.remove(stack.size()-1);
125 int[] stateArray = curList.toArray();
126 final int id = map.get(curList);
129 final TIntObjectHashMap<TIntHashSet> transitions =
130 new TIntObjectHashMap<TIntHashSet>();
131 TIntIntProcedure proc = new TIntIntProcedure() {
133 public boolean execute(int symbol, int b) {
134 TIntHashSet set = transitions.get(symbol);
136 set = new TIntHashSet();
137 transitions.put(symbol, set);
143 for(int s : stateArray)
144 forEachTransition(s, proc);
146 // Create transition targets
147 transitions.forEachEntry(new TIntObjectProcedure<TIntHashSet>() {
149 public boolean execute(int symbol, TIntHashSet b) {
150 TIntArrayList stateList = closure(b);
152 if(map.containsKey(stateList))
153 aut.addTransition(id, symbol, map.get(stateList));
155 int stateId = aut.newState();
156 map.put(stateList, stateId);
157 stack.add(stateList);
159 aut.addTransition(id, symbol, stateId);
166 for(int s : stateArray)
168 aut.setAccepts(id, true);