##// END OF EJS Templates
implab » ImplabNet
RSS
Working on regular DFA
cin -
r171:0f70905b4652 ref20160224
parent child
Show More
Show file before | Show file after | Hide comments
@@ -0,0 +1,23
1 using System;
2
3 namespace Implab.Automaton.RegularExpressions {
4 public struct DFAStateDescriptorT<T> {
5 public readonly bool final;
6
7 public readonly int[] transitions;
8
9 public readonly T[] tags;
10
11 public DFAStateDescriptorT(int size, bool final, T[] tags) {
12 Safe.ArgumentAssert(size >= 0, "size");
13 this.final = final;
14 this.tags = tags;
15
16 transitions = new int[size];
17
18 for (int i = 0; i < size; i++)
19 transitions[i] = DFAConst.UNREACHABLE_STATE;
20 }
21 }
22 }
23
Show file before | Show file after | Hide comments
@@ -1,280 +1,291
1 1 using Implab;
2 2 using System;
3 3 using System.Collections.Generic;
4 4 using System.Linq;
5 5
6 6 namespace Implab.Automaton {
7 7 public class DFATable : IDFATableBuilder {
8 DFAStateDescriptior[] m_dfaTable;
9
10 8 int m_stateCount;
11 9 int m_symbolCount;
12 10 int m_initialState;
13 11
14 12 readonly HashSet<int> m_finalStates = new HashSet<int>();
15 13 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
16 14
17 void AssertNotReadOnly() {
18 if (m_dfaTable != null)
19 throw new InvalidOperationException("The object is readonly");
20 }
21
22 15
23 16 #region IDFADefinition implementation
24 17
25 public DFAStateDescriptior[] GetTransitionTable() {
26 if (m_dfaTable == null) {
27 if (m_stateCount <= 0)
28 throw new InvalidOperationException("Invalid automaton definition: states count = {0}", m_stateCount);
29 if (m_symbolCount <= 0)
30 throw new InvalidOperationException("Invalid automaton definition: symbols count = {0}", m_symbolCount);
31
32 m_dfaTable = ConstructTransitionTable();
33 }
34 return m_dfaTable;
35 }
36
37 18 public bool IsFinalState(int s) {
38 19 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
39 20
40 return m_dfaTable != null ? m_dfaTable[s].final : m_finalStates.Contains(s);
21 return m_finalStates.Contains(s);
41 22 }
42 23
43 24 public IEnumerable<int> FinalStates {
44 25 get {
45 26 return m_finalStates;
46 27 }
47 28 }
48 29
49 30 public int StateCount {
50 31 get { return m_stateCount; }
51 32 }
52 33
53 34 public int AlphabetSize {
54 35 get { return m_symbolCount; }
55 36 }
56 37
57 38 public int InitialState {
58 39 get { return m_initialState; }
59 40 }
60 41
61 42 #endregion
62 43
63 protected virtual DFAStateDescriptior[] ConstructTransitionTable() {
64 var dfaTable = new DFAStateDescriptior[m_stateCount];
65
66
67 foreach (var t in m_transitions) {
68 if (dfaTable[t.s1].transitions == null)
69 dfaTable[t.s1] = new DFAStateDescriptior(m_symbolCount, m_finalStates.Contains(t.s1));
70
71 dfaTable[t.s1].transitions[t.edge] = t.s2;
72 }
73
74 foreach (var s in m_finalStates)
75 if (!dfaTable[s].final)
76 m_dfaTable[s] = new DFAStateDescriptior(m_symbolCount, true);
77
78 }
79
80 44 public void SetInitialState(int s) {
81 45 Safe.ArgumentAssert(s >= 0, "s");
82 46 m_initialState = s;
83 47 }
84 48
85 49 public void MarkFinalState(int state) {
86 AssertNotReadOnly();
87 50 m_finalStates.Add(state);
88 51 }
89 52
90 53 public void Add(AutomatonTransition item) {
91 AssertNotReadOnly();
92 54 Safe.ArgumentAssert(item.s1 >= 0, "item");
93 55 Safe.ArgumentAssert(item.s2 >= 0, "item");
94 56 Safe.ArgumentAssert(item.edge >= 0, "item");
95 57
96 58 m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1);
97 59 m_symbolCount = Math.Max(m_symbolCount, item.edge);
98 60
99 61 m_transitions.Add(item);
100 62 }
101 63
102 64 public void Clear() {
103 AssertNotReadOnly();
104
105 65 m_stateCount = 0;
106 66 m_symbolCount = 0;
107 67 m_finalStates.Clear();
108 68 m_transitions.Clear();
109 69 }
110 70
111 71 public bool Contains(AutomatonTransition item) {
112 72 return m_transitions.Contains(item);
113 73 }
114 74
115 75 public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
116 76 m_transitions.CopyTo(array, arrayIndex);
117 77 }
118 78
119 79 public bool Remove(AutomatonTransition item) {
120 AssertNotReadOnly();
121 80 m_transitions.Remove(item);
122 81 }
123 82
124 83 public int Count {
125 84 get {
126 85 return m_transitions.Count;
127 86 }
128 87 }
129 88
130 89 public bool IsReadOnly {
131 90 get {
132 return m_dfaTable != null;
91 return false;
133 92 }
134 93 }
135 94
136 95 public IEnumerator<AutomatonTransition> GetEnumerator() {
137 96 return m_transitions.GetEnumerator();
138 97 }
139 98
140 99 System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
141 100 return GetEnumerator();
142 101 }
143 102
144 103 /// <summary>Π€ΠΎΡ€ΠΌΠΈΡ€ΡƒΠ΅Ρ‚ мноТСства ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹Ρ… состояний ΠΏΠ΅Ρ€Π΅Π΄ Π½Π°Ρ‡Π°Π»ΠΎΠΌ Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° ΠΌΠΈΠ½ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ.</summary>
145 104 /// <remarks>
146 105 /// Π’ процСссС построСния минимального Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π° трСбуСтся Ρ€Π°Π·Π΄Π΅Π»ΠΈΡ‚ΡŒ мноТСство состояний,
147 106 /// Π½Π° Π΄Π²Π° подмноТСства - ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹Π΅ состояния ΠΈ всС ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Π΅, послС Ρ‡Π΅Π³ΠΎ эти подмноТСства
148 107 /// Π±ΡƒΠ΄ΡƒΡ‚ Ρ€Π΅Π·Π΄Π΅Π»Π΅Π½Ρ‹ Π½Π° Π±ΠΎΠ»Π΅Π΅ ΠΌΠ΅Π»ΠΊΠΈΠ΅. Иногда трСбуСтся Π³Π°Ρ€Π°Π½Ρ‚ΠΈΡ€ΠΎΠ²Π°Ρ‚ΡŒ различия ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹Ρ… сосотяний,
149 108 /// для этого Π½Π΅ΠΎΠ±Ρ…ΠΎΠ΄ΠΈΠΌΠΎ ΠΏΠ΅Ρ€Π΅ΠΎΠΏΡ€Π΅Π΄Π΅Π»ΠΈΡ‚ΡŒ Π΄Π°Π½Π½Ρ†ΡŽ Ρ„ΡƒΠΊΠ½Ρ†ΠΈΡŽ, для получСния мноТСств ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹Ρ… состояний.
150 109 /// </remarks>
151 110 /// <returns>The final states.</returns>
152 111 protected virtual IEnumerable<HashSet<int>> GroupFinalStates() {
153 112 return new HashSet<int>[] { m_finalStates };
154 113 }
155 114
156 protected void Optimize<TInput, TState>(
115 protected void Optimize(
157 116 IDFATableBuilder optimalDFA,
158 IAlphabet<TInput> inputAlphabet,
159 IAlphabetBuilder<TInput> optimalInputAlphabet,
160 IAlphabet<TState> stateAlphabet,
161 IAlphabetBuilder<TState> optimalStateAlphabet
117 IDictionary<int,int> alphabetMap,
118 IDictionary<int,int> stateMap
162 119 ) {
163 120 Safe.ArgumentNotNull(optimalDFA, "dfa");
164 Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
165 Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
166 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
167 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
121 Safe.ArgumentNotNull(alphabetMap, "alphabetMap");
122 Safe.ArgumentNotNull(stateMap, "stateMap");
168 123
169 if (inputAlphabet.Count != m_symbolCount)
170 throw new InvalidOperationException("The input symbols aphabet mismatch");
171 if (stateAlphabet.Count != m_stateCount)
172 throw new InvalidOperationException("The states alphabet mismatch");
173 124
174 125 var setComparer = new CustomEqualityComparer<HashSet<int>>(
175 126 (x, y) => x.SetEquals(y),
176 127 s => s.Sum(x => x.GetHashCode())
177 128 );
178 129
179 130 var optimalStates = new HashSet<HashSet<int>>(setComparer);
180 131 var queue = new HashSet<HashSet<int>>(setComparer);
181 132
182 133 // ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹Π΅ состояния, сгруппированныС ΠΏΠΎ ΠΌΠ°Ρ€ΠΊΠ΅Ρ€Π°ΠΌ
183 134 optimalStates.UnionWith(
184 135 GroupFinalStates()
185 136 );
186 137
187 138 var state = new HashSet<int>(
188 139 Enumerable
189 140 .Range(0, m_stateCount - 1)
190 141 .Where(i => !m_finalStates.Contains(i))
191 142 );
192 143
193 144 optimalStates.Add(state);
194 145 queue.Add(state);
195 146
196 147 var rmap = m_transitions
197 148 .GroupBy(t => t.s2)
198 149 .ToLookup(
199 150 g => g.Key, // s2
200 151 g => g.ToLookup(t => t.edge, t => t.s1)
201 152 );
202 153
203 154 while (queue.Count > 0) {
204 155 var stateA = queue.First();
205 156 queue.Remove(stateA);
206 157
207 158 for (int c = 0; c < m_symbolCount; c++) {
208 159 var stateX = new HashSet<int>();
209 160 foreach(var a in stateA)
210 161 stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
211 162
212 163 foreach (var stateY in optimalStates.ToArray()) {
213 164 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
214 165 var stateR1 = new HashSet<int>(stateY);
215 166 var stateR2 = new HashSet<int>(stateY);
216 167
217 168 stateR1.IntersectWith(stateX);
218 169 stateR2.ExceptWith(stateX);
219 170
220 171 optimalStates.Remove(stateY);
221 172 optimalStates.Add(stateR1);
222 173 optimalStates.Add(stateR2);
223 174
224 175 if (queue.Contains(stateY)) {
225 176 queue.Remove(stateY);
226 177 queue.Add(stateR1);
227 178 queue.Add(stateR2);
228 179 } else {
229 180 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
230 181 }
231 182 }
232 183 }
233 184 }
234 185 }
235 186
236 187 // ΠΊΠ°Ρ€Ρ‚Π° получСния ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния ΠΏΠΎ ΡΠΎΠΎΡ‚Π²Π΅ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΌΡƒ Π΅ΠΌΡƒ простому ΡΠΎΡΡ‚ΠΎΡΠ½ΠΈΡŽ
237 var statesMap = stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
188 var nextState = 0;
189 foreach (var item in optimalStates) {
190 var id = nextState++;
191 foreach (var s in item)
192 stateMap[s] = id;
193 }
238 194
239 195 // ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Π°Π»Ρ„Π°Π²ΠΈΡ‚
240 // Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ символы Π½Π΅ Ρ€Π°Π·Π»ΠΈΡ‡ΠΈΠΌΡ‹, Ссли Move(s,a1) == Move(s,a2)
241 var optimalAlphabet = m_transitions
242 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
196 // Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ символы Π½Π΅ Ρ€Π°Π·Π»ΠΈΡ‡ΠΈΠΌΡ‹, Ссли Move(s,a1) == Move(s,a2), для любого s
197 // для этого ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅ΠΌ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ кластСризации, сначала
198 // считаСм, Ρ‡Ρ‚ΠΎ всС символы Π½Π΅ Ρ€Π°Π·Π»ΠΈΡ‡ΠΈΠΌΡ‹
199
200 var minClasses = new HashSet<HashSet<int>>(setComparer);
201 var alphaQueue = new Queue<HashSet<int>>();
202 alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
203
204 // для всСх состояний, Π±ΡƒΠ΄Π΅ΠΌ ΠΏΡ€ΠΎΠ²Π΅Ρ€ΡΡ‚ΡŒ ΠΊΠ°ΠΆΠ΄Ρ‹ΠΉ класс Π½Π° Ρ€Π°Π·Π»ΠΈΡ‡ΠΈΠΌΠΎΡΡ‚ΡŒ,
205 // Ρ‚.Π΅. символы Ρ€Π°Π·Π»ΠΈΡ‡ΠΈΠΌΡ‹, Ссли ΠΎΠ½ΠΈ приводят ΠΊ Ρ€Π°Π·Π½Ρ‹ΠΌ состояниям
206 for (int s = 0 ; s < optimalStates.Count; s++) {
207 var newQueue = new Queue<HashSet<int>>();
208
209 foreach (var A in alphaQueue) {
210 // классы ΠΈΠ· ΠΎΠ΄Π½ΠΎΠ³ΠΎ символа Π΄Π΅Π»ΠΈΡ‚ΡŒ бСсполСзно, ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄ΠΈΠΌ ΠΈΡ… сразу Π²
211 // Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚ΠΈΡ€ΡƒΡŽΡ‰ΠΈΠΉ Π°Π»Ρ„Π°Π²ΠΈΡ‚
212 if (A.Count == 1) {
213 minClasses.Add(A);
214 continue;
215 }
216
217 // Ρ€Π°Π·Π»ΠΈΡ‡Π°Π΅ΠΌ классы символов, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ пСрСводят Π² Ρ€Π°Π·Π»ΠΈΡ‡Π½Ρ‹Π΅ ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ состояния
218 // optimalState -> alphaClass
219 var classes = new Dictionary<int, HashSet<int>>();
220
221 foreach (var term in A) {
222 // ΠΈΡ‰Π΅ΠΌ всС ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄Ρ‹ класса ΠΏΠΎ символу term
223 var res = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).ToArray();
224
225 var s2 = res.Length > 0 ? res[0] : -1;
243 226
244 var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
227 HashSet<int> a2;
228 if (!classes.TryGetValue(s2, out a2)) {
229 a2 = new HashSet<int>();
230 newQueue.Enqueue(a2);
231 classes[s2] = a2;
232 }
233 a2.Add(term);
234 }
235 }
236
237 if (newQueue.Count == 0)
238 break;
239 alphaQueue = newQueue;
240 }
241
242 // послС окончания Ρ€Π°Π±ΠΎΡ‚Ρ‹ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠ° Π² ΠΎΡ‡Π΅Ρ€Π΅Π΄ΠΈ останутся ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹Π΅ Ρ€Π°Π·Π»ΠΈΡ‡ΠΈΠΌΡ‹Π΅ классы
243 // Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… символов
244 foreach (var A in alphaQueue)
245 minClasses.Add(A);
246
247 // построСниС отобраТСния Π°Π»Ρ„Π°Π²ΠΈΡ‚ΠΎΠ² Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… символов.
248 // ΠΏΠΎΡΠΊΠΎΠ»ΡŒΠΊΡƒ символ DFAConst.UNCLASSIFIED_INPUT ΠΌΠΎΠΆΠ΅Ρ‚ ΠΈΠΌΠ΅Ρ‚ΡŒ
249 // ΡΠΏΠ΅Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΎΠ΅ Π·Π½Π°Ρ‡Π΅Π½ΠΈΠ΅, Ρ‚ΠΎΠ³Π΄Π° сохраним ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ класс,
250 // содСрТащий этот символ Π½Π° Ρ‚ΠΎΠΌΠΆΠ΅ мСстС.
251
252 var nextCls = 0;
253 foreach (var item in minClasses) {
254 if (nextCls == DFAConst.UNCLASSIFIED_INPUT)
255 nextCls++;
256
257 // сохраняСм DFAConst.UNCLASSIFIED_INPUT
258 var cls = item.Contains(DFAConst.UNCLASSIFIED_INPUT) ? DFAConst.UNCLASSIFIED_INPUT : nextCls;
259
260 foreach (var a in item)
261 alphabetMap[a] = cls;
262
263 nextCls++;
264 }
245 265
246 266 // построСниС Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°
247 optimalDFA.SetInitialState(statesMap[m_initialState]);
267 optimalDFA.SetInitialState(stateMap[m_initialState]);
248 268
249 foreach (var sf in m_finalStates.GroupBy(s => statesMap[s]))
250 optimalDFA.MarkFinalState(sf.Key);
269 foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct())
270 optimalDFA.MarkFinalState(sf);
251 271
252 foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
272 foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
253 273 optimalDFA.Add(t);
254
255 274 }
256 275
257 276 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
258 277 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
259 278 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
260 279
261 var inputMap = inputAlphabet.CreateReverseMap();
262 var stateMap = stateAlphabet.CreateReverseMap();
263
264 for (int i = 0; i < inputMap.Length; i++)
265 Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
266
267
268 280 foreach(var t in m_transitions)
269 281 Console.WriteLine(
270 282 "[{0}] -{{{1}}}-> [{2}]{3}",
271 stateMap[t.s1],
272 String.Join(",", inputMap[t.edge]),
273 stateMap[t.s2],
283 String.Join(",", stateAlphabet.GetSymbols(t.s1)),
284 String.Join("", inputAlphabet.GetSymbols(t.edge)),
285 String.Join(",", stateAlphabet.GetSymbols(t.s2)),
274 286 m_finalStates.Contains(t.s2) ? "$" : ""
275 287 );
276
277 288 }
278 289
279 290 }
280 291 }
Show file before | Show file after | Hide comments
@@ -1,56 +1,46
1 1 using System;
2 2 using System.Collections.Generic;
3 3 using System.Linq;
4 4
5 5 namespace Implab.Automaton {
6 6 /// <summary>
7 7 /// Dummy alphabet consists of integer numbers which are identical to their classes.
8 8 /// </summary>
9 9 public class DummyAlphabet : IAlphabet<int> {
10 10 readonly int m_size;
11 11
12 12 /// <summary>
13 13 /// Creates a new dummy alphabet with given size.
14 14 /// </summary>
15 15 /// <param name="size">The size of the alphabet, must be greater then zero.</param>
16 16 public DummyAlphabet(int size) {
17 17 Safe.ArgumentAssert(size > 0);
18 18 m_size = 0;
19 19 }
20 20
21 21 #region IAlphabet implementation
22 22
23 23 public List<int>[] CreateReverseMap() {
24 24 Enumerable.Range(0, m_size).ToArray();
25 25 }
26 26
27 public int[] Reclassify(IAlphabetBuilder<int> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
28 Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
29 Safe.ArgumentNotNull(classes, "classes");
30 var map = new int[m_size];
31 foreach (var cls in classes) {
32 if (cls.Contains(DFAConst.UNCLASSIFIED_INPUT))
33 continue;
34 var newid = newAlphabet.DefineClass(cls);
35 foreach (var id in cls)
36 map[id] = newid;
27 public int Translate(int symbol) {
28 Safe.ArgumentInRange(symbol, 0, m_size, "symbol");
29 return symbol;
37 30 }
38 31
39 return map;
40 }
41
42 public int Translate(int symobl) {
43 Safe.ArgumentInRange(symobl, 0, m_size, "symbol");
44 return symobl;
32 public bool Contains(int symbol) {
33 Safe.ArgumentInRange(symbol, 0, m_size, "symbol");
34 return true;
45 35 }
46 36
47 37 public int Count {
48 38 get {
49 39 return m_size;
50 40 }
51 41 }
52 42
53 43 #endregion
54 44 }
55 45 }
56 46
Show file before | Show file after | Hide comments
@@ -1,48 +1,34
1 1 using System;
2 2 using System.Collections.Generic;
3 3 using System.Linq;
4 4 using System.Text;
5 5 using System.Threading.Tasks;
6 6
7 7 namespace Implab.Automaton {
8 8 /// <summary>
9 9 /// Алфавит. ΠœΠ½ΠΎΠΆΠ΅ΡΡ‚Π²ΠΎ символов, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ Ρ€Π°Π·Π±ΠΈΡ‚Ρ‹ Π½Π° классы, ΠΏΡ€ΠΈ этом классы ΠΈΠΌΠ΅ΡŽΡ‚ Π½Π΅ΠΏΡ€Π΅Ρ€Ρ‹Π²Π½ΡƒΡŽ Π½ΡƒΠΌΠ΅Ρ€Π°Ρ†ΠΈΡŽ,
10 10 /// Ρ‡Ρ‚ΠΎ позволяСт ΠΈΡΠΏΠΎΠ»ΡŒΠ·ΠΎΠ²Π°Ρ‚ΡŒ ΠΈΡ… Π² качСствС индСксов массивов.
11 11 /// </summary>
12 12 /// <remarks>
13 13 /// <para>Алфавит являСтся ΡΡŽΡ€ΡŒΠ΅ΠΊΡ‚ΠΈΠ²Π½Ρ‹ΠΌ ΠΎΡ‚ΠΎΠ±Ρ€Π°ΠΆΠ΅Π½ΠΈΠ΅ΠΌ мноТСства символов Π² мноТСство индСксов, это позволяСт ΡΠΎΠΊΡ€Π°Ρ‚ΠΈΡ‚ΡŒ Ρ€Π°Π·ΠΌΠ΅Ρ€ Ρ‚Π°Π±Π»ΠΈΡ†Ρ‹ ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ΠΎΠ² Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°
14 14 /// для Π²Ρ…ΠΎΠ΄Π½Ρ‹Ρ… символов, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹Π΅ для Π½Π΅Π³ΠΎ Π½Π΅ Ρ€Π°Π·Π»ΠΈΡ‡ΠΈΠΌΡ‹.</para>
15 15 /// </remarks>
16 16 /// <typeparam name="TSymbol">Вип символов.</typeparam>
17 17 public interface IAlphabet<TSymbol> {
18 18 /// <summary>
19 19 /// ΠšΠΎΠ»ΠΈΡ‡Π΅ΡΡ‚Π²ΠΎ классов символов Π² Π°Π»Ρ„Π°Π²ΠΈΡ‚Π΅.
20 20 /// </summary>
21 21 int Count { get; }
22 22
23 23 /// <summary>
24 /// Π‘ΠΎΠ·Π΄Π°Π΅Ρ‚ ΠΊΠ°Ρ€Ρ‚Ρƒ ΠΎΠ±Ρ€Π°Ρ‚Π½ΠΎΠ³ΠΎ сопоставлСния класса символов Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° ΠΈ сопоставлСнным
25 /// Π΅ΠΌΡƒ исходным символам.
26 /// </summary>
27 /// <returns></returns>
28 List<TSymbol>[] CreateReverseMap();
29
30 /// <summary>
31 /// Π‘ΠΎΠ·Π΄Π°Π΅Ρ‚ Π½ΠΎΠ²Ρ‹ΠΉ Π°Π»Ρ„Π°Π²ΠΈΡ‚ Π½Π° основС Ρ‚Π΅ΠΊΡƒΡ‰Π΅Π³ΠΎ, горппируя Π΅Π³ΠΎ сиволы Π² Π±ΠΎΠ»Π΅Π΅
32 /// ΠΊΡ€ΡƒΠΏΠ½Ρ‹Π΅ Π½Π΅ΠΏΠ΅Ρ€Π΅ΡΠ΅ΠΊΠ°ΡŽΡ‰ΠΈΠ΅ΡΡ классы символов.
33 /// </summary>
34 /// <param name="newAlphabet">Новый, пустой Π°Π»Ρ„Π°Π²ΠΈΡ‚, Π² ΠΊΠΎΡ‚ΠΎΡ€ΠΎΠΌ Π±Ρ‹Π΄ΡƒΡ‚ ΠΎΠΏΡ€Π΅Π΄Π΅Π»Π΅Π½Ρ‹ классы.</param>
35 /// <param name="classes">ΠœΠ½ΠΎΠΆΠ΅ΡΡ‚Π²ΠΎ классов символов Ρ‚Π΅ΠΊΡƒΡ‰Π΅Π³ΠΎ Π°Π»Ρ„Π°Π²ΠΈΡ‚Π°.</param>
36 /// <returns>ΠšΠ°Ρ€Ρ‚Π° для ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄Π° классов Ρ‚Π΅ΠΊΡƒΡ‰Π΅Π³ΠΎ
37 /// Π°Π»Ρ„Π°Π²ΠΈΡ‚Π° ΠΊ классам Π½ΠΎΠ²ΠΎΠ³ΠΎ.</returns>
38 /// <remarks>ΠŸΠΎΠ»Π·Π²ΠΎΠ»ΡΠ΅Ρ‚ ΡƒΠΊΡ€ΡƒΠΏΠ½ΠΈΡ‚ΡŒ Π°Π»Ρ„Π°Π²ΠΈΡ‚, объСдинив классы Π² Ρ‚Π΅ΠΊΡƒΡ‰Π΅ΠΌ Π°Π»Ρ„Π°Π²ΠΈΡ‚Π΅. Π˜ΡΠΏΠΎΠ»ΡŒΠ·ΡƒΠ΅Ρ‚ΡΡ ΠΏΡ€ΠΈ ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°.</remarks>
39 int[] Reclassify(IAlphabetBuilder<TSymbol> newAlphabet, IEnumerable<IEnumerable<int>> classes);
40
41 /// <summary>
42 24 /// ΠŸΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΡƒΠ΅Ρ‚ Π²Ρ…ΠΎΠ΄Π½ΠΎΠΉ символ Π² индСкс символа ΠΈΠ· Π°Π»Ρ„Π°Π²ΠΈΡ‚Π°.
43 25 /// </summary>
44 26 /// <param name="symobl">Π˜ΡΡ…ΠΎΠ΄Π½Ρ‹ΠΉ символ</param>
45 27 /// <returns>ИндСкс Π² Π°Π»Ρ„Π°Π²ΠΈΡ‚Π΅</returns>
46 28 int Translate(TSymbol symobl);
29
30 bool Contains(TSymbol symbol);
31
32 IEnumerable<TSymbol> GetSymbols(int cls);
47 33 }
48 34 }
Show file before | Show file after | Hide comments
@@ -1,22 +1,26
1 1
2 2 using System.Collections.Generic;
3 3
4 4 namespace Implab.Automaton {
5 5 public interface IAlphabetBuilder<TSymbol> : IAlphabet<TSymbol> {
6 6 /// <summary>
7 7 /// ДобавляСт Π½ΠΎΠ²Ρ‹ΠΉ символ Π² Π°Π»Ρ„Π°Π²ΠΈΡ‚, Ссли символ ΡƒΠΆΠ΅ Π±Ρ‹Π» Π΄ΠΎΠ±Π°Π²Π»Π΅Π½, Ρ‚ΠΎ
8 8 /// возвращаСтся Ρ€Π°Π½Π΅Π΅ сопоставлСнный с символом класс.
9 9 /// </summary>
10 10 /// <param name="symbol">Бимвол для добавлСния.</param>
11 11 /// <returns>ИндСкс класса, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ попоставлСн с символом.</returns>
12 12 int DefineSymbol(TSymbol symbol);
13
14 int DefineSymbol(TSymbol symbol, int cls);
13 15 /// <summary>
14 16 /// ДоабвляСм класс символов. ΠœΠ½ΠΎΠΆΠ΅ΡΡ‚Π²Ρƒ ΡƒΠΊΠ°Π·Π°Π½Π½Ρ‹Ρ… исходных символов
15 17 /// Π±ΡƒΠ΄Π΅Ρ‚ сопоставлСн символ Π² Π°Π»Ρ„Π°Π²ΠΈΡ‚Π΅.
16 18 /// </summary>
17 19 /// <param name="symbols">ΠœΠ½ΠΎΠΆΠ΅ΡΡ‚ΠΎΠ² исходных символов</param>
18 20 /// <returns>Π˜Π΄Π΅Π½Ρ‚ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€ символа Π°Π»Ρ„Π°Π²ΠΈΡ‚Π°.</returns>
19 21 int DefineClass(IEnumerable<TSymbol> symbols);
22
23 int DefineClass(IEnumerable<TSymbol> symbols, int cls);
20 24 }
21 25 }
22 26
Show file before | Show file after | Hide comments
@@ -1,59 +1,53
1 1 using System.Collections.Generic;
2 2
3 3
4 4 namespace Implab.Automaton {
5 5 /// <summary>
6 6 /// ΠŸΠΎΠ»Π½ΠΎΡΡ‚ΡŒΡŽ описываСт DFA Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚, Π΅Π³ΠΎ ΠΏΠΎΠ²Π΅Π΄Π΅Π½ΠΈΠ΅, состояниС ΠΈ Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ символы.
7 7 /// </summary>
8 8 /// <example>
9 9 /// class MyAutomaton {
10 10 /// int m_current;
11 11 /// readonly DFAStateDescriptor<string>[] m_automaton;
12 12 /// readonly IAlphabet<MyCommands> m_commands;
13 13 ///
14 14 /// public MyAutomaton(IDFADefinition&lt;MyCommands,MyStates,string&gt; definition) {
15 15 /// m_current = definition.StateAlphabet.Translate(MyStates.Initial);
16 16 /// m_automaton = definition.GetTransitionTable();
17 17 /// m_commands = definition.InputAlphabet;
18 18 /// }
19 19 ///
20 20 /// // defined a method which will move the automaton to the next state
21 21 /// public void Move(MyCommands cmd) {
22 22 /// // use transition map to determine the next state
23 23 /// var next = m_automaton[m_current].transitions[m_commands.Translate(cmd)];
24 24 ///
25 25 /// // validate that we aren't in the unreachable state
26 26 /// if (next == DFAConst.UNREACHABLE_STATE)
27 27 /// throw new InvalidOperationException("The specified command is invalid");
28 28 ///
29 29 /// // if everything is ok
30 30 /// m_current = next;
31 31 /// }
32 32 /// }
33 33 /// </example>
34 34 public interface IDFATable : IEnumerable<AutomatonTransition> {
35 /// <summary>
36 /// Π’Π°Π±Π»ΠΈΡ†Π° ΠΏΠ΅Ρ€Π΅Ρ…ΠΎΠ΄ΠΎΠ² состояний Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°
37 /// </summary>
38 /// <returns>The transition table.</returns>
39 DFAStateDescriptior[] GetTransitionTable();
40
41 35 int StateCount {
42 36 get;
43 37 }
44 38
45 39 int AlphabetSize {
46 40 get;
47 41 }
48 42
49 43 int InitialState {
50 44 get;
51 45 }
52 46
53 47 bool IsFinalState(int s);
54 48
55 49 IEnumerable<int> FinalStates {
56 50 get;
57 51 }
58 52 }
59 53 }
Show file before | Show file after | Hide comments
@@ -1,108 +1,86
1 1 using Implab;
2 2 using System;
3 3 using System.Collections.Generic;
4 4 using System.Diagnostics;
5 5 using System.Linq;
6 6
7 7 namespace Implab.Automaton {
8 8 /// <summary>
9 9 /// Indexed alphabet is the finite set of symbols where each symbol has a zero-based unique index.
10 10 /// </summary>
11 11 /// <remarks>
12 12 /// Indexed alphabets are usefull in bulting efficient translations from source alphabet
13 13 /// to the input alphabet of the automaton. It's assumed that the index to the symbol match
14 14 /// is well known and documented.
15 15 /// </remarks>
16 16 public abstract class IndexedAlphabetBase<T> : IAlphabetBuilder<T> {
17 17 int m_nextId = 1;
18 18 readonly int[] m_map;
19 19
20 public int Count {
21 get { return m_nextId; }
22 }
23
24 20 protected IndexedAlphabetBase(int mapSize) {
25 21 m_map = new int[mapSize];
26 22 }
27 23
28 24 protected IndexedAlphabetBase(int[] map) {
29 Debug.Assert(map != null);
25 Debug.Assert(map != null && map.Length > 0);
26 Debug.Assert(map.All(x => x >= 0));
30 27
31 28 m_map = map;
32 29 m_nextId = map.Max() + 1;
33 30 }
34 31
35 32 public int DefineSymbol(T symbol) {
36 33 var index = GetSymbolIndex(symbol);
37 34 if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT)
38 35 m_map[index] = m_nextId++;
39 36 return m_map[index];
40 37 }
41 38
39 public int DefineSymbol(T symbol, int cls) {
40 var index = GetSymbolIndex(symbol);
41 m_map[index] = cls;
42 m_nextId = Math.Max(cls + 1, m_nextId);
43 return cls;
44 }
45
42 46 public int DefineClass(IEnumerable<T> symbols) {
47 return DefineClass(symbols, m_nextId);
48 }
49
50 public int DefineClass(IEnumerable<T> symbols, int cls) {
43 51 Safe.ArgumentNotNull(symbols, "symbols");
44 52 symbols = symbols.Distinct();
45 53
46 foreach (var symbol in symbols) {
47 var index = GetSymbolIndex(symbol);
48 if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT)
49 m_map[GetSymbolIndex(symbol)] = m_nextId;
50 else
51 throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
52 }
53 return m_nextId++;
54 }
55
56 public List<T>[] CreateReverseMap() {
57 return
58 Enumerable.Range(0, Count)
59 .Select(
60 i => InputSymbols
61 .Where(x => i != DFAConst.UNCLASSIFIED_INPUT && m_map[GetSymbolIndex(x)] == i)
62 .ToList()
63 )
64 .ToArray();
65 }
54 foreach (var symbol in symbols)
55 m_map[GetSymbolIndex(symbol)] = cls;
66 56
67 public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
68 Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
69 Safe.ArgumentNotNull(classes, "classes");
70 var reverseMap = CreateReverseMap();
71
72 var translationMap = new int[Count];
57 m_nextId = Math.Max(cls + 1, m_nextId);
73 58
74 foreach (var scl in classes) {
75 // skip if the supper class contains the unclassified element
76 if (scl.Contains(DFAConst.UNCLASSIFIED_INPUT))
77 continue;
78 var range = new List<T>();
79 foreach (var cl in scl) {
80 if (cl < 0 || cl >= reverseMap.Length)
81 throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", cl));
82 range.AddRange(reverseMap[cl]);
83 }
84 var newClass = newAlphabet.DefineClass(range);
85 foreach (var cl in scl)
86 translationMap[cl] = newClass;
87 }
88
89 return translationMap;
59 return cls;
90 60 }
91 61
92 62 public virtual int Translate(T symbol) {
93 63 return m_map[GetSymbolIndex(symbol)];
94 64 }
95 65
66 public int Count {
67 get { return m_nextId; }
68 }
69
70 public bool Contains(T symbol) {
71 return true;
72 }
73
96 74 public abstract int GetSymbolIndex(T symbol);
97 75
98 76 public abstract IEnumerable<T> InputSymbols { get; }
99 77
100 78 /// <summary>
101 79 /// Gets the translation map from the index of the symbol to it's class this is usefull for the optimized input symbols transtaion.
102 80 /// </summary>
103 81 /// <returns>The translation map.</returns>
104 82 public int[] GetTranslationMap() {
105 83 return m_map;
106 84 }
107 85 }
108 86 }
Show file before | Show file after | Hide comments
@@ -1,109 +1,74
1 1 using System;
2 2 using System.Collections.Generic;
3 3 using System.Linq;
4 4
5 5 namespace Implab.Automaton {
6 6 public class MapAlphabet<T> : IAlphabetBuilder<T> {
7 7 readonly Dictionary<T,int> m_map;
8 int m_nextCls = 1;
8 int m_nextCls;
9 readonly bool m_supportUnclassified;
9 10
10 public MapAlphabet() {
11 m_map = new Dictionary<T, int>();
12 }
13
14 public MapAlphabet(IEqualityComparer<T> comparer) {
15 m_map = new Dictionary<T, int>(comparer);
11 public MapAlphabet(bool supportUnclassified, IEqualityComparer<T> comparer) {
12 m_map = comparer != null ? new Dictionary<T, int>(comparer) : new Dictionary<T,int>();
13 m_supportUnclassified = supportUnclassified;
14 m_nextCls = supportUnclassified ? 1 : 0;
16 15 }
17 16
18 17 #region IAlphabetBuilder implementation
19 18
20 19 public int DefineSymbol(T symbol) {
21 20 int cls;
22 if (m_map.TryGetValue(symbol, out cls))
23 return cls;
21 return m_map.TryGetValue(symbol, out cls) ? cls : DefineSymbol(symbol, m_nextCls);
22 }
24 23
25 cls = m_nextCls++;
24 public int DefineSymbol(T symbol, int cls) {
25 Safe.ArgumentAssert(cls >= 0, "cls");
26 26
27 m_nextCls = Math.Max(cls + 1, m_nextCls);
27 28 m_map.Add(symbol, cls);
28
29 29 return cls;
30 30 }
31 31
32 32 public int DefineClass(IEnumerable<T> symbols) {
33 return DefineClass(symbols, m_nextCls);
34 }
35
36 public int DefineClass(IEnumerable<T> symbols, int cls) {
37 Safe.ArgumentAssert(cls >= 0, "cls");
33 38 Safe.ArgumentNotNull(symbols, "symbols");
39
40 m_nextCls = Math.Max(cls + 1, m_nextCls);
34 41 symbols = symbols.Distinct();
35 42
36 foreach (var symbol in symbols) {
37 if (!m_map.Contains(symbol))
38 m_map.Add(symbol, m_nextCls);
39 else
40 throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
41 }
42 return m_nextCls++;
43 foreach (var symbol in symbols)
44 m_map[symbol] = cls;
45 return cls;
43 46 }
44 47
45 48 #endregion
46 49
47 50 #region IAlphabet implementation
48 51
49 public List<T>[] CreateReverseMap() {
50 var empty = new List<T>();
51 var rmap = new List<T>[m_nextCls];
52
53 for (int i = 0; i < rmap.Length; i++)
54 rmap[i] = empty;
55
56 foreach (var pair in m_map) {
57 var symbols = rmap[pair.Value];
58 if (symbols == null) {
59 symbols = new List<T>();
60 rmap[pair.Value] = symbols;
61 }
62
63 symbols.Add(pair.Key);
64 }
65
66 return rmap;
67 }
68
69 public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
70 Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
71 Safe.ArgumentNotNull(classes, "classes");
72
73 var rmap = CreateReverseMap();
74 var map = new int[rmap.Length];
75
76 foreach (var cls in classes) {
77 if (cls.Contains(DFAConst.UNCLASSIFIED_INPUT))
78 continue;
79
80 var symbols = new List<T>();
81 foreach (var id in cls) {
82 if (id < 0 || id >= rmap.Length)
83 throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", id));
84 if (rmap[id] != null)
85 symbols.AddRange(rmap[id]);
86 }
87
88 var newId = newAlphabet.DefineClass(symbols);
89
90 foreach (var id in cls)
91 map[id] = newId;
92 }
93 }
94
95 public int Translate(T symobl) {
52 public int Translate(T symbol) {
96 53 int cls;
97 return m_map.TryGetValue(symobl, out cls) ? cls : DFAConst.UNCLASSIFIED_INPUT;
54 if (m_map.TryGetValue(symbol, out cls))
55 return cls;
56 if (!m_supportUnclassified)
57 throw new ArgumentOutOfRangeException("symbol", "The specified symbol isn't in the alphabet");
58 return DFAConst.UNCLASSIFIED_INPUT;
98 59 }
99 60
100 61 public int Count {
101 62 get {
102 63 return m_nextCls;
103 64 }
104 65 }
105 66
67 public bool Contains(T symbol) {
68 return m_supportUnclassified || m_map.ContainsKey(symbol);
69 }
70
106 71 #endregion
107 72 }
108 73 }
109 74
Show file before | Show file after | Hide comments
@@ -1,69 +1,69
1 1 using System;
2 2 using System.Collections.Generic;
3 3 using System.Linq;
4 4
5 5 namespace Implab.Automaton.RegularExpressions {
6 6 public class RegularDFADefinition<TInput, TTag> : DFATable {
7 7
8 8 readonly Dictionary<int,TTag[]> m_tags = new Dictionary<int, TTag[]>();
9 9 readonly IAlphabet<TInput> m_alphabet;
10 10
11 11 public RegularDFADefinition(IAlphabet<TInput> alphabet) {
12 12 Safe.ArgumentNotNull(alphabet, "aplhabet");
13 13
14 14 m_alphabet = alphabet;
15 15 }
16 16
17 17
18 18 public IAlphabet<TInput> InputAlphabet {
19 19 get {
20 20 return m_alphabet;
21 21 }
22 22 }
23 23
24 protected override DFAStateDescriptior[] ConstructTransitionTable() {
25 if (InputAlphabet.Count != m_alphabet.Count)
26 throw new InvalidOperationException("The alphabet doesn't match the transition table");
27
28 return base.ConstructTransitionTable();
29 }
30
31 24 public void MarkFinalState(int s, TTag[] tags) {
32 25 MarkFinalState(s);
33 26 SetStateTag(s, tags);
34 27 }
35 28
36 29 public void SetStateTag(int s, TTag[] tags) {
37 30 Safe.ArgumentNotNull(tags, "tags");
38 31 m_tags[s] = tags;
39 32 }
40 33
41 34 public TTag[] GetStateTag(int s) {
42 35 TTag[] tags;
43 36 return m_tags.TryGetValue(s, out tags) ? tags : new TTag[0];
44 37 }
45 38
46 39 /// <summary>
47 40 /// Optimize the specified alphabet.
48 41 /// </summary>
49 42 /// <param name="alphabet">ΠŸΡƒΡΡ‚ΠΎΠΉ Π°Π»Ρ„Π°Π²ΠΈΡ‚, ΠΊΠΎΡ‚ΠΎΡ€Ρ‹ΠΉ Π±ΡƒΠ΄Π΅Ρ‚ Π·ΠΏΠΎΠ»Π½Π΅Π½ Π² процСссС ΠΎΠΏΡ‚ΠΈΠΌΠΈΠ·Π°Ρ†ΠΈΠΈ.</param>
50 43 public RegularDFADefinition<TInput,TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {
51 44 Safe.ArgumentNotNull(alphabet, "alphabet");
52 45
53 46 var dfaTable = new RegularDFADefinition<TInput, TTag>(alphabet);
54 47
55 48 var states = new DummyAlphabet(StateCount);
56 var map = new MapAlphabet<int>();
49 var alphaMap = new Dictionary<int,int>();
50 var stateMap = new Dictionary<int,int>();
51 Optimize(dfaTable, alphaMap, stateMap);
57 52
58 Optimize(dfaTable, InputAlphabet, alphabet, states, map);
59
60 foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => map.Translate(x.Key), x => x.Value ))
53 foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => stateMap[x.Key], x => x.Value ))
61 54 dfaTable.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
62 55
63 56 return dfaTable;
64 57 }
65 58
59 protected override IEnumerable<HashSet<int>> GroupFinalStates() {
60 var arrayComparer = new CustomEqualityComparer<TTag[]>(
61 (x,y) => x.Length == y.Length && x.All(it => y.Contains(it)),
62 x => x.Sum(it => x.GetHashCode())
63 );
64 return FinalStates.GroupBy(x => m_tags[x], arrayComparer).Select(g => new HashSet<int>(g));
65 }
66 66
67 67 }
68 68 }
69 69
Show file before | Show file after | Hide comments
@@ -1,271 +1,272
1 1 ο»Ώ<?xml version="1.0" encoding="utf-8"?>
2 2 <Project DefaultTargets="Build" ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
3 3 <PropertyGroup>
4 4 <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
5 5 <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
6 6 <ProjectGuid>{F550F1F8-8746-4AD0-9614-855F4C4B7F05}</ProjectGuid>
7 7 <OutputType>Library</OutputType>
8 8 <RootNamespace>Implab</RootNamespace>
9 9 <AssemblyName>Implab</AssemblyName>
10 10 <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
11 11 <ReleaseVersion>0.2</ReleaseVersion>
12 12 <ProductVersion>8.0.30703</ProductVersion>
13 13 <SchemaVersion>2.0</SchemaVersion>
14 14 </PropertyGroup>
15 15 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
16 16 <DebugSymbols>true</DebugSymbols>
17 17 <DebugType>full</DebugType>
18 18 <Optimize>false</Optimize>
19 19 <OutputPath>bin\Debug</OutputPath>
20 20 <DefineConstants>TRACE;DEBUG;</DefineConstants>
21 21 <ErrorReport>prompt</ErrorReport>
22 22 <WarningLevel>4</WarningLevel>
23 23 <ConsolePause>false</ConsolePause>
24 24 <RunCodeAnalysis>true</RunCodeAnalysis>
25 25 </PropertyGroup>
26 26 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
27 27 <DebugType>full</DebugType>
28 28 <Optimize>true</Optimize>
29 29 <OutputPath>bin\Release</OutputPath>
30 30 <ErrorReport>prompt</ErrorReport>
31 31 <WarningLevel>4</WarningLevel>
32 32 <ConsolePause>false</ConsolePause>
33 33 </PropertyGroup>
34 34 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug 4.5|AnyCPU' ">
35 35 <DebugSymbols>true</DebugSymbols>
36 36 <DebugType>full</DebugType>
37 37 <Optimize>false</Optimize>
38 38 <OutputPath>bin\Debug</OutputPath>
39 39 <DefineConstants>TRACE;DEBUG;NET_4_5</DefineConstants>
40 40 <ErrorReport>prompt</ErrorReport>
41 41 <WarningLevel>4</WarningLevel>
42 42 <RunCodeAnalysis>true</RunCodeAnalysis>
43 43 <ConsolePause>false</ConsolePause>
44 44 </PropertyGroup>
45 45 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release 4.5|AnyCPU' ">
46 46 <Optimize>true</Optimize>
47 47 <OutputPath>bin\Release</OutputPath>
48 48 <ErrorReport>prompt</ErrorReport>
49 49 <WarningLevel>4</WarningLevel>
50 50 <ConsolePause>false</ConsolePause>
51 51 <DefineConstants>NET_4_5</DefineConstants>
52 52 </PropertyGroup>
53 53 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'DebugMono|AnyCPU' ">
54 54 <DebugSymbols>true</DebugSymbols>
55 55 <DebugType>full</DebugType>
56 56 <Optimize>false</Optimize>
57 57 <OutputPath>bin\Debug</OutputPath>
58 58 <DefineConstants>TRACE;DEBUG;NET_4_5;MONO</DefineConstants>
59 59 <ErrorReport>prompt</ErrorReport>
60 60 <WarningLevel>4</WarningLevel>
61 61 <RunCodeAnalysis>true</RunCodeAnalysis>
62 62 <ConsolePause>false</ConsolePause>
63 63 </PropertyGroup>
64 64 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'ReleaseMono|AnyCPU' ">
65 65 <Optimize>true</Optimize>
66 66 <OutputPath>bin\Release</OutputPath>
67 67 <DefineConstants>NET_4_5;MONO;</DefineConstants>
68 68 <ErrorReport>prompt</ErrorReport>
69 69 <WarningLevel>4</WarningLevel>
70 70 <ConsolePause>false</ConsolePause>
71 71 </PropertyGroup>
72 72 <ItemGroup>
73 73 <Reference Include="System" />
74 74 <Reference Include="System.Xml" />
75 75 <Reference Include="mscorlib" />
76 76 </ItemGroup>
77 77 <ItemGroup>
78 78 <Compile Include="CustomEqualityComparer.cs" />
79 79 <Compile Include="Diagnostics\ConsoleTraceListener.cs" />
80 80 <Compile Include="Diagnostics\EventText.cs" />
81 81 <Compile Include="Diagnostics\LogChannel.cs" />
82 82 <Compile Include="Diagnostics\LogicalOperation.cs" />
83 83 <Compile Include="Diagnostics\TextFileListener.cs" />
84 84 <Compile Include="Diagnostics\TraceLog.cs" />
85 85 <Compile Include="Diagnostics\TraceEvent.cs" />
86 86 <Compile Include="Diagnostics\TraceEventType.cs" />
87 87 <Compile Include="ICancellable.cs" />
88 88 <Compile Include="IProgressHandler.cs" />
89 89 <Compile Include="IProgressNotifier.cs" />
90 90 <Compile Include="IPromiseT.cs" />
91 91 <Compile Include="IPromise.cs" />
92 92 <Compile Include="IServiceLocator.cs" />
93 93 <Compile Include="ITaskController.cs" />
94 94 <Compile Include="Parallels\DispatchPool.cs" />
95 95 <Compile Include="Parallels\ArrayTraits.cs" />
96 96 <Compile Include="Parallels\MTQueue.cs" />
97 97 <Compile Include="Parallels\WorkerPool.cs" />
98 98 <Compile Include="ProgressInitEventArgs.cs" />
99 99 <Compile Include="Properties\AssemblyInfo.cs" />
100 100 <Compile Include="Parallels\AsyncPool.cs" />
101 101 <Compile Include="Safe.cs" />
102 102 <Compile Include="ValueEventArgs.cs" />
103 103 <Compile Include="PromiseExtensions.cs" />
104 104 <Compile Include="SyncContextPromise.cs" />
105 105 <Compile Include="Diagnostics\OperationContext.cs" />
106 106 <Compile Include="Diagnostics\TraceContext.cs" />
107 107 <Compile Include="Diagnostics\LogEventArgs.cs" />
108 108 <Compile Include="Diagnostics\LogEventArgsT.cs" />
109 109 <Compile Include="Diagnostics\Extensions.cs" />
110 110 <Compile Include="PromiseEventType.cs" />
111 111 <Compile Include="Parallels\AsyncQueue.cs" />
112 112 <Compile Include="PromiseT.cs" />
113 113 <Compile Include="IDeferred.cs" />
114 114 <Compile Include="IDeferredT.cs" />
115 115 <Compile Include="Promise.cs" />
116 116 <Compile Include="PromiseTransientException.cs" />
117 117 <Compile Include="Parallels\Signal.cs" />
118 118 <Compile Include="Parallels\SharedLock.cs" />
119 119 <Compile Include="Diagnostics\ILogWriter.cs" />
120 120 <Compile Include="Diagnostics\ListenerBase.cs" />
121 121 <Compile Include="Parallels\BlockingQueue.cs" />
122 122 <Compile Include="AbstractEvent.cs" />
123 123 <Compile Include="AbstractPromise.cs" />
124 124 <Compile Include="AbstractPromiseT.cs" />
125 125 <Compile Include="FuncTask.cs" />
126 126 <Compile Include="FuncTaskBase.cs" />
127 127 <Compile Include="FuncTaskT.cs" />
128 128 <Compile Include="ActionChainTaskBase.cs" />
129 129 <Compile Include="ActionChainTask.cs" />
130 130 <Compile Include="ActionChainTaskT.cs" />
131 131 <Compile Include="FuncChainTaskBase.cs" />
132 132 <Compile Include="FuncChainTask.cs" />
133 133 <Compile Include="FuncChainTaskT.cs" />
134 134 <Compile Include="ActionTaskBase.cs" />
135 135 <Compile Include="ActionTask.cs" />
136 136 <Compile Include="ActionTaskT.cs" />
137 137 <Compile Include="ICancellationToken.cs" />
138 138 <Compile Include="SuccessPromise.cs" />
139 139 <Compile Include="SuccessPromiseT.cs" />
140 140 <Compile Include="PromiseAwaiterT.cs" />
141 141 <Compile Include="PromiseAwaiter.cs" />
142 142 <Compile Include="Components\ComponentContainer.cs" />
143 143 <Compile Include="Components\Disposable.cs" />
144 144 <Compile Include="Components\DisposablePool.cs" />
145 145 <Compile Include="Components\ObjectPool.cs" />
146 146 <Compile Include="Components\ServiceLocator.cs" />
147 147 <Compile Include="Components\IInitializable.cs" />
148 148 <Compile Include="TaskController.cs" />
149 149 <Compile Include="Components\App.cs" />
150 150 <Compile Include="Components\IRunnable.cs" />
151 151 <Compile Include="Components\ExecutionState.cs" />
152 152 <Compile Include="Components\RunnableComponent.cs" />
153 153 <Compile Include="Components\IFactory.cs" />
154 154 <Compile Include="Automaton\DFAStateDescriptor.cs" />
155 155 <Compile Include="Automaton\EnumAlphabet.cs" />
156 156 <Compile Include="Automaton\IAlphabet.cs" />
157 157 <Compile Include="Automaton\ParserException.cs" />
158 158 <Compile Include="Automaton\Scanner.cs" />
159 159 <Compile Include="Automaton\IndexedAlphabetBase.cs" />
160 160 <Compile Include="Automaton\IAlphabetBuilder.cs" />
161 161 <Compile Include="Automaton\RegularExpressions\AltToken.cs" />
162 162 <Compile Include="Automaton\RegularExpressions\BinaryToken.cs" />
163 163 <Compile Include="Automaton\RegularExpressions\CatToken.cs" />
164 164 <Compile Include="Automaton\DFAConst.cs" />
165 165 <Compile Include="Automaton\RegularExpressions\Grammar.cs" />
166 166 <Compile Include="Automaton\RegularExpressions\StarToken.cs" />
167 167 <Compile Include="Automaton\RegularExpressions\SymbolToken.cs" />
168 168 <Compile Include="Automaton\RegularExpressions\EmptyToken.cs" />
169 169 <Compile Include="Automaton\RegularExpressions\EndToken.cs" />
170 170 <Compile Include="Automaton\RegularExpressions\Token.cs" />
171 171 <Compile Include="Automaton\RegularExpressions\IVisitor.cs" />
172 172 <Compile Include="Automaton\AutomatonTransition.cs" />
173 173 <Compile Include="Automaton\RegularExpressions\RegularDFABuilder.cs" />
174 174 <Compile Include="Formats\JSON\JSONElementContext.cs" />
175 175 <Compile Include="Formats\JSON\JSONElementType.cs" />
176 176 <Compile Include="Formats\JSON\JSONGrammar.cs" />
177 177 <Compile Include="Formats\JSON\JSONParser.cs" />
178 178 <Compile Include="Formats\JSON\JSONScanner.cs" />
179 179 <Compile Include="Formats\JSON\JsonTokenType.cs" />
180 180 <Compile Include="Formats\JSON\JSONWriter.cs" />
181 181 <Compile Include="Formats\JSON\JSONXmlReader.cs" />
182 182 <Compile Include="Formats\JSON\JSONXmlReaderOptions.cs" />
183 183 <Compile Include="Formats\JSON\StringTranslator.cs" />
184 184 <Compile Include="Automaton\MapAlphabet.cs" />
185 185 <Compile Include="Automaton\DummyAlphabet.cs" />
186 186 <Compile Include="Automaton\RegularExpressions\RegularDFADefinition.cs" />
187 187 <Compile Include="Formats\CharAlphabet.cs" />
188 188 <Compile Include="Formats\ByteAlphabet.cs" />
189 189 <Compile Include="Formats\RegularCharDFADefinition.cs" />
190 190 <Compile Include="Automaton\IDFATable.cs" />
191 191 <Compile Include="Automaton\IDFATableBuilder.cs" />
192 192 <Compile Include="Automaton\DFATable.cs" />
193 <Compile Include="Automaton\RegularExpressions\DFAStateDescriptorT.cs" />
193 194 </ItemGroup>
194 195 <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
195 196 <ItemGroup />
196 197 <ProjectExtensions>
197 198 <MonoDevelop>
198 199 <Properties>
199 200 <Policies>
200 201 <CSharpFormattingPolicy IndentSwitchBody="True" NamespaceBraceStyle="EndOfLine" ClassBraceStyle="EndOfLine" InterfaceBraceStyle="EndOfLine" StructBraceStyle="EndOfLine" EnumBraceStyle="EndOfLine" MethodBraceStyle="EndOfLine" ConstructorBraceStyle="EndOfLine" DestructorBraceStyle="EndOfLine" BeforeMethodDeclarationParentheses="False" BeforeMethodCallParentheses="False" BeforeConstructorDeclarationParentheses="False" NewLineBeforeConstructorInitializerColon="NewLine" NewLineAfterConstructorInitializerColon="SameLine" BeforeIndexerDeclarationBracket="False" BeforeDelegateDeclarationParentheses="False" NewParentheses="False" SpacesBeforeBrackets="False" inheritsSet="Mono" inheritsScope="text/x-csharp" scope="text/x-csharp" />
201 202 <TextStylePolicy FileWidth="120" EolMarker="Unix" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="text/x-csharp" />
202 203 <DotNetNamingPolicy DirectoryNamespaceAssociation="PrefixedHierarchical" ResourceNamePolicy="MSBuild" />
203 204 <TextStylePolicy FileWidth="120" TabsToSpaces="False" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="application/xml" />
204 205 <XmlFormattingPolicy inheritsSet="Mono" inheritsScope="application/xml" scope="application/xml" />
205 206 <TextStylePolicy FileWidth="120" TabsToSpaces="False" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="text/plain" />
206 207 <NameConventionPolicy>
207 208 <Rules>
208 209 <NamingRule Name="Namespaces" AffectedEntity="Namespace" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
209 210 <NamingRule Name="Types" AffectedEntity="Class, Struct, Enum, Delegate" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
210 211 <NamingRule Name="Interfaces" AffectedEntity="Interface" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
211 212 <RequiredPrefixes>
212 213 <String>I</String>
213 214 </RequiredPrefixes>
214 215 </NamingRule>
215 216 <NamingRule Name="Attributes" AffectedEntity="CustomAttributes" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
216 217 <RequiredSuffixes>
217 218 <String>Attribute</String>
218 219 </RequiredSuffixes>
219 220 </NamingRule>
220 221 <NamingRule Name="Event Arguments" AffectedEntity="CustomEventArgs" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
221 222 <RequiredSuffixes>
222 223 <String>EventArgs</String>
223 224 </RequiredSuffixes>
224 225 </NamingRule>
225 226 <NamingRule Name="Exceptions" AffectedEntity="CustomExceptions" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
226 227 <RequiredSuffixes>
227 228 <String>Exception</String>
228 229 </RequiredSuffixes>
229 230 </NamingRule>
230 231 <NamingRule Name="Methods" AffectedEntity="Methods" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
231 232 <NamingRule Name="Static Readonly Fields" AffectedEntity="ReadonlyField" VisibilityMask="Internal, Protected, Public" NamingStyle="CamelCase" IncludeInstanceMembers="False" IncludeStaticEntities="True" />
232 233 <NamingRule Name="Fields (Non Private)" AffectedEntity="Field" VisibilityMask="Internal, Public" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
233 234 <NamingRule Name="ReadOnly Fields (Non Private)" AffectedEntity="ReadonlyField" VisibilityMask="Internal, Public" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False" />
234 235 <NamingRule Name="Fields (Private)" AffectedEntity="Field, ReadonlyField" VisibilityMask="Private, Protected" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False">
235 236 <RequiredPrefixes>
236 237 <String>m_</String>
237 238 </RequiredPrefixes>
238 239 </NamingRule>
239 240 <NamingRule Name="Static Fields (Private)" AffectedEntity="Field" VisibilityMask="Private" NamingStyle="CamelCase" IncludeInstanceMembers="False" IncludeStaticEntities="True">
240 241 <RequiredPrefixes>
241 242 <String>_</String>
242 243 </RequiredPrefixes>
243 244 </NamingRule>
244 245 <NamingRule Name="ReadOnly Fields (Private)" AffectedEntity="ReadonlyField" VisibilityMask="Private, Protected" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False">
245 246 <RequiredPrefixes>
246 247 <String>m_</String>
247 248 </RequiredPrefixes>
248 249 </NamingRule>
249 250 <NamingRule Name="Constant Fields" AffectedEntity="ConstantField" VisibilityMask="VisibilityMask" NamingStyle="AllUpper" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
250 251 <NamingRule Name="Properties" AffectedEntity="Property" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
251 252 <NamingRule Name="Events" AffectedEntity="Event" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
252 253 <NamingRule Name="Enum Members" AffectedEntity="EnumMember" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
253 254 <NamingRule Name="Parameters" AffectedEntity="Parameter, LocalVariable" VisibilityMask="VisibilityMask" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
254 255 <NamingRule Name="Type Parameters" AffectedEntity="TypeParameter" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
255 256 <RequiredPrefixes>
256 257 <String>T</String>
257 258 </RequiredPrefixes>
258 259 </NamingRule>
259 260 </Rules>
260 261 </NameConventionPolicy>
261 262 </Policies>
262 263 </Properties>
263 264 </MonoDevelop>
264 265 </ProjectExtensions>
265 266 <ItemGroup>
266 267 <Folder Include="Components\" />
267 268 <Folder Include="Automaton\RegularExpressions\" />
268 269 <Folder Include="Formats\" />
269 270 <Folder Include="Formats\JSON\" />
270 271 </ItemGroup>
271 272 </Project> No newline at end of file
General Comments 0
You need to be logged in to leave comments. Login now