177
+ − 1 using System.Collections.Generic;
172
+ − 2 using System.Linq;
+ − 3
+ − 4 namespace Implab.Automaton.RegularExpressions {
179
+ − 5 public class RegularDFA<TInput, TTag> : DFATable, ITaggedDFABuilder<TTag> {
172
+ − 6
+ − 7 readonly Dictionary<int,TTag[]> m_tags = new Dictionary<int, TTag[]>();
+ − 8 readonly IAlphabet<TInput> m_alphabet;
+ − 9
179
+ − 10 public RegularDFA(IAlphabet<TInput> alphabet) {
172
+ − 11 Safe.ArgumentNotNull(alphabet, "aplhabet");
+ − 12
+ − 13 m_alphabet = alphabet;
+ − 14 }
+ − 15
+ − 16
+ − 17 public IAlphabet<TInput> InputAlphabet {
+ − 18 get {
+ − 19 return m_alphabet;
+ − 20 }
+ − 21 }
+ − 22
+ − 23 public void MarkFinalState(int s, TTag[] tags) {
+ − 24 MarkFinalState(s);
+ − 25 SetStateTag(s, tags);
+ − 26 }
+ − 27
+ − 28 public void SetStateTag(int s, TTag[] tags) {
+ − 29 Safe.ArgumentNotNull(tags, "tags");
+ − 30 m_tags[s] = tags;
+ − 31 }
+ − 32
+ − 33 public TTag[] GetStateTag(int s) {
+ − 34 TTag[] tags;
+ − 35 return m_tags.TryGetValue(s, out tags) ? tags : new TTag[0];
+ − 36 }
+ − 37
176
+ − 38 public TTag[][] CreateTagTable() {
+ − 39 var table = new TTag[StateCount][];
172
+ − 40
176
+ − 41 foreach (var pair in m_tags)
+ − 42 table[pair.Key] = pair.Value;
172
+ − 43
+ − 44 return table;
+ − 45 }
+ − 46
+ − 47 /// <summary>
+ − 48 /// Optimize the specified alphabet.
+ − 49 /// </summary>
+ − 50 /// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>
179
+ − 51 public RegularDFA<TInput,TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {
172
+ − 52 Safe.ArgumentNotNull(alphabet, "alphabet");
+ − 53
179
+ − 54 var dfa = new RegularDFA<TInput, TTag>(alphabet);
172
+ − 55
+ − 56 var alphaMap = new Dictionary<int,int>();
+ − 57 var stateMap = new Dictionary<int,int>();
+ − 58
+ − 59 Optimize(dfa, alphaMap, stateMap);
+ − 60
+ − 61 // mark tags in the new DFA
+ − 62 foreach (var g in m_tags.Where(x => x.Key < StateCount).GroupBy(x => stateMap[x.Key], x => x.Value ))
+ − 63 dfa.SetStateTag(g.Key, g.SelectMany(x => x).ToArray());
+ − 64
+ − 65 // make the alphabet for the new DFA
181
+ − 66 // skip all unclassified symbols
+ − 67 foreach (var pair in alphaMap.Where(x => x.Value != 0))
172
+ − 68 alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value);
+ − 69 return dfa;
+ − 70 }
+ − 71
183
+ − 72 protected override IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
172
+ − 73 var arrayComparer = new CustomEqualityComparer<TTag[]>(
+ − 74 (x,y) => x.Length == y.Length && x.All(it => y.Contains(it)),
+ − 75 x => x.Sum(it => x.GetHashCode())
+ − 76 );
183
+ − 77 return states.GroupBy(x => m_tags[x] ?? new TTag[0], arrayComparer).Select(g => new HashSet<int>(g));
172
+ − 78 }
+ − 79
182
+ − 80 public override string ToString() {
+ − 81 var states = new MapAlphabet<string>(false, null);
+ − 82
+ − 83 for (int i = 0; i < StateCount; i++)
+ − 84 states.DefineSymbol(string.Format("s{0}", i), i);
+ − 85
+ − 86 return string.Format("//[RegularDFA {1} x {2}]\n{0}", PrintDFA(InputAlphabet, states),StateCount, AlphabetSize);
+ − 87 }
+ − 88
172
+ − 89 }
+ − 90 }
+ − 91
