Mercurial > pub > ImplabNet
annotate Implab/Automaton/RegularExpressions/RegularDFA.cs @ 242:cbe10ac0731e v3
Working on promises
| author | cin |
|---|---|
| date | Wed, 24 Jan 2018 03:03:21 +0300 |
| parents | fa6cbf4d8841 |
| children |
| rev | line source |
|---|---|
| 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 | |
|
240
fa6cbf4d8841
refactoring, moving to dotnercore, simplifying promises
cin
parents:
183
diff
changeset
|
80 /*public override string ToString() { |
| 182 | 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); | |
|
240
fa6cbf4d8841
refactoring, moving to dotnercore, simplifying promises
cin
parents:
183
diff
changeset
|
87 }*/ |
| 182 | 88 |
| 172 | 89 } |
| 90 } | |
| 91 |