Mercurial > pub > ImplabNet

comparison Implab/Automaton/RegularExpressions/RegularDFA.cs @ 190:1c2a16d071a7 v2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Слияние с ref20160224
author cin
date Fri, 22 Apr 2016 13:08:08 +0300
parents 4f82e0f161c3
children fa6cbf4d8841
comparison
equal deleted inserted replaced
161:2a8466f0cb8a 190:1c2a16d071a7
1 using System.Collections.Generic;
2 using System.Linq;
3
4 namespace Implab.Automaton.RegularExpressions {
5 public class RegularDFA<TInput, TTag> : DFATable, ITaggedDFABuilder<TTag> {
6
7 readonly Dictionary<int,TTag[]> m_tags = new Dictionary<int, TTag[]>();
8 readonly IAlphabet<TInput> m_alphabet;
9
10 public RegularDFA(IAlphabet<TInput> alphabet) {
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
38 public TTag[][] CreateTagTable() {
39 var table = new TTag[StateCount][];
40
41 foreach (var pair in m_tags)
42 table[pair.Key] = pair.Value;
43
44 return table;
45 }
46
47 /// <summary>
48 /// Optimize the specified alphabet.
49 /// </summary>
50 /// <param name="alphabet">Пустой алфавит, который будет зполнен в процессе оптимизации.</param>
51 public RegularDFA<TInput,TTag> Optimize(IAlphabetBuilder<TInput> alphabet) {
52 Safe.ArgumentNotNull(alphabet, "alphabet");
53
54 var dfa = new RegularDFA<TInput, TTag>(alphabet);
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
66 // skip all unclassified symbols
67 foreach (var pair in alphaMap.Where(x => x.Value != 0))
68 alphabet.DefineClass(m_alphabet.GetSymbols(pair.Key), pair.Value);
69 return dfa;
70 }
71
72 protected override IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
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 );
77 return states.GroupBy(x => m_tags[x] ?? new TTag[0], arrayComparer).Select(g => new HashSet<int>(g));
78 }
79
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
89 }
90 }
91