annotate Implab/Parsing/DFADefinitionBase.cs @ 89:ce0171cacec4 v2

improved performance of a chained map operation
author cin
date Wed, 08 Oct 2014 02:19:45 +0400
parents c0bf853aa04f
children 97fbbf816844
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
55
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
1 using Implab;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
2 using System;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
3 using System.Collections.Generic;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
4 using System.Diagnostics;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
5 using System.Linq;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
6 using System.Text;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
7 using System.Threading.Tasks;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
8
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
9 namespace Implab.Parsing {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
10 public abstract class DFADefinitionBase : IDFADefinition {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
11 readonly List<DFAStateDescriptior> m_states;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
12
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
13 public const int INITIAL_STATE = 1;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
14 public const int UNREACHEBLE_STATE = 0;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
15
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
16 DFAStateDescriptior[] m_statesArray;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
17
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
18 public DFADefinitionBase() {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
19 m_states = new List<DFAStateDescriptior>();
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
20
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
21 m_states.Add(new DFAStateDescriptior());
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
22 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
23
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
24 public DFAStateDescriptior[] States {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
25 get {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
26 if (m_statesArray == null)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
27 m_statesArray = m_states.ToArray();
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
28 return m_statesArray;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
29 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
30 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
31
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
32 public bool InitialStateIsFinal {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
33 get {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
34 return m_states[INITIAL_STATE].final;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
35 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
36 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
37
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
38 public int AddState() {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
39 var index = m_states.Count;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
40 m_states.Add(new DFAStateDescriptior {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
41 final = false,
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
42 transitions = new int[AlphabetSize]
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
43 });
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
44
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
45 return index;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
46 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
47
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
48 public int AddState(int[] tag) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
49 var index = m_states.Count;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
50 bool final = tag == null || tag.Length == 0 ? false : true;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
51 m_states.Add(new DFAStateDescriptior {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
52 final = final,
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
53 transitions = new int[AlphabetSize],
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
54 tag = final ? tag : null
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
55 });
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
56 return index;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
57 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
58
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
59 public void DefineTransition(int s1,int s2, int symbol) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
60 Safe.ArgumentInRange(s1, 0, m_states.Count-1, "s1");
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
61 Safe.ArgumentInRange(s2, 0, m_states.Count-1, "s2");
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
62 Safe.ArgumentInRange(symbol, 0, AlphabetSize-1, "symbol");
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
63
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
64 m_states[s1].transitions[symbol] = s2;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
65 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
66
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
67 protected void Optimize<TA>(IDFADefinition minimalDFA,IAlphabet<TA> sourceAlphabet, IAlphabet<TA> minimalAlphabet) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
68 Safe.ArgumentNotNull(minimalDFA, "minimalDFA");
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
69 Safe.ArgumentNotNull(minimalAlphabet, "minimalAlphabet");
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
70
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
71 var setComparer = new CustomEqualityComparer<HashSet<int>>(
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
72 (x, y) => x.SetEquals(y),
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
73 (s) => s.Sum(x => x.GetHashCode())
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
74 );
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
75
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
76 var arrayComparer = new CustomEqualityComparer<int[]>(
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
77 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
78 (a) => a.Sum(x => x.GetHashCode())
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
79 );
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
80
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
81 var optimalStates = new HashSet<HashSet<int>>(setComparer);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
82 var queue = new HashSet<HashSet<int>>(setComparer);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
83
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
84 foreach (var g in Enumerable
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
85 .Range(INITIAL_STATE, m_states.Count-1)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
86 .Select(i => new {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
87 index = i,
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
88 descriptor = m_states[i]
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
89 })
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
90 .Where(x => x.descriptor.final)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
91 .GroupBy(x => x.descriptor.tag, arrayComparer)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
92 ) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
93 optimalStates.Add(new HashSet<int>(g.Select(x => x.index)));
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
94 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
95
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
96 var state = new HashSet<int>(
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
97 Enumerable
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
98 .Range(INITIAL_STATE, m_states.Count - 1)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
99 .Where(i => !m_states[i].final)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
100 );
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
101 optimalStates.Add(state);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
102 queue.Add(state);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
103
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
104 while (queue.Count > 0) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
105 var stateA = queue.First();
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
106 queue.Remove(stateA);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
107
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
108 for (int c = 0; c < AlphabetSize; c++) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
109 var stateX = new HashSet<int>();
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
110
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
111 for(int s = 1; s < m_states.Count; s++) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
112 if (stateA.Contains(m_states[s].transitions[c]))
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
113 stateX.Add(s);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
114 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
115
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
116 foreach (var stateY in optimalStates.ToArray()) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
117 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
118 var stateR1 = new HashSet<int>(stateY);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
119 var stateR2 = new HashSet<int>(stateY);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
120
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
121 stateR1.IntersectWith(stateX);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
122 stateR2.ExceptWith(stateX);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
123
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
124 optimalStates.Remove(stateY);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
125 optimalStates.Add(stateR1);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
126 optimalStates.Add(stateR2);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
127
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
128 if (queue.Contains(stateY)) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
129 queue.Remove(stateY);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
130 queue.Add(stateR1);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
131 queue.Add(stateR2);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
132 } else {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
133 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
134 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
135 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
136 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
137 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
138 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
139
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
140 // строим карты соотвествия оптимальных состояний с оригинальными
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
141
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
142 var initialState = optimalStates.Where(x => x.Contains(INITIAL_STATE)).Single();
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
143
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
144 // карта получения оптимального состояния по соотвествующему ему простому состоянию
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
145 int[] reveseOptimalMap = new int[m_states.Count];
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
146 // карта с индексами оптимальных состояний
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
147 HashSet<int>[] optimalMap = new HashSet<int>[optimalStates.Count + 1];
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
148 {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
149 optimalMap[0] = new HashSet<int>(); // unreachable state
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
150 optimalMap[1] = initialState; // initial state
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
151 foreach (var ss in initialState)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
152 reveseOptimalMap[ss] = 1;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
153
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
154 int i = 2;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
155 foreach (var s in optimalStates) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
156 if (s.SetEquals(initialState))
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
157 continue;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
158 optimalMap[i] = s;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
159 foreach (var ss in s)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
160 reveseOptimalMap[ss] = i;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
161 i++;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
162 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
163 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
164
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
165 // получаем минимальный алфавит
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
166
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
167 var minClasses = new HashSet<HashSet<int>>(setComparer);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
168 var alphaQueue = new Queue<HashSet<int>>();
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
169 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
170
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
171 for (int s = 1 ; s < optimalMap.Length; s++) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
172 var newQueue = new Queue<HashSet<int>>();
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
173
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
174 foreach (var A in alphaQueue) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
175 if (A.Count == 1) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
176 minClasses.Add(A);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
177 continue;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
178 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
179
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
180 // различаем классы символов, которые переводят в различные оптимальные состояния
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
181 // optimalState -> alphaClass
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
182 var classes = new Dictionary<int, HashSet<int>>();
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
183
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
184 foreach (var term in A) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
185 // ищем все переходы класса по символу term
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
186 var s2 = reveseOptimalMap[
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
187 optimalMap[s].Select(x => m_states[x].transitions[term]) // все элементарные состояния, куда переходит класс s
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
188 .Where(x => x != 0) // только допустимые
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
189 .FirstOrDefault() // первое допустимое элементарное состояние, если есть
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
190 ];
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
191
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
192 HashSet<int> A2;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
193 if (!classes.TryGetValue(s2, out A2)) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
194 A2 = new HashSet<int>();
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
195 newQueue.Enqueue(A2);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
196 classes[s2] = A2;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
197 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
198 A2.Add(term);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
199 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
200 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
201
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
202 if (newQueue.Count == 0)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
203 break;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
204 alphaQueue = newQueue;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
205 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
206
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
207 foreach (var A in alphaQueue)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
208 minClasses.Add(A);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
209
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
210 var alphabetMap = sourceAlphabet.Reclassify(minimalAlphabet, minClasses);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
211
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
212 // построение автомата
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
213
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
214 var states = new int[ optimalMap.Length ];
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
215 states[0] = UNREACHEBLE_STATE;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
216
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
217 for(var s = INITIAL_STATE; s < states.Length; s++) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
218 var tags = optimalMap[s].SelectMany(x => m_states[x].tag ?? Enumerable.Empty<int>()).Distinct().ToArray();
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
219 if (tags.Length > 0)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
220 states[s] = minimalDFA.AddState(tags);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
221 else
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
222 states[s] = minimalDFA.AddState();
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
223 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
224
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
225 Debug.Assert(states[INITIAL_STATE] == INITIAL_STATE);
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
226
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
227 for (int s1 = 1; s1 < m_states.Count; s1++) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
228 for (int c = 0; c < AlphabetSize; c++) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
229 var s2 = m_states[s1].transitions[c];
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
230 if (s2 != UNREACHEBLE_STATE) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
231 minimalDFA.DefineTransition(
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
232 reveseOptimalMap[s1],
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
233 reveseOptimalMap[s2],
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
234 alphabetMap[c]
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
235 );
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
236 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
237 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
238 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
239
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
240 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
241
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
242 protected void PrintDFA<TA>(IAlphabet<TA> alphabet) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
243
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
244 var reverseMap = alphabet.CreateReverseMap();
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
245
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
246 for (int i = 1; i < reverseMap.Length; i++) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
247 Console.WriteLine("C{0}: {1}", i, String.Join(",", reverseMap[i]));
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
248 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
249
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
250 for (int i = 1; i < m_states.Count; i++) {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
251 var s = m_states[i];
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
252 for (int c = 0; c < AlphabetSize; c++)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
253 if (s.transitions[c] != UNREACHEBLE_STATE)
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
254 Console.WriteLine("S{0} -{1}-> S{2}{3}", i, String.Join(",", reverseMap[c]), s.transitions[c], m_states[s.transitions[c]].final ? "$" : "");
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
255 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
256 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
257
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
258 public abstract int AlphabetSize {
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
259 get;
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
260 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
261 }
c0bf853aa04f Added initial JSON support
cin
parents:
diff changeset
262 }