Mercurial > pub > ImplabNet

comparison Implab/Automaton/MapAlphabet.cs @ 171:0f70905b4652 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Working on regular DFA
author cin
date Thu, 10 Mar 2016 01:19:33 +0300
parents ec35731ae299
children 92d5278d1b10
comparison
equal deleted inserted replaced
170:181119ef3b39 171:0f70905b4652
3 using System.Linq; 3 using System.Linq;
4 4
5 namespace Implab.Automaton { 5 namespace Implab.Automaton {
6 public class MapAlphabet<T> : IAlphabetBuilder<T> { 6 public class MapAlphabet<T> : IAlphabetBuilder<T> {
7 readonly Dictionary<T,int> m_map; 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 public MapAlphabet(bool supportUnclassified, IEqualityComparer<T> comparer) {
11 m_map = new Dictionary<T, int>(); 12 m_map = comparer != null ? new Dictionary<T, int>(comparer) : new Dictionary<T,int>();
12 } 13 m_supportUnclassified = supportUnclassified;
13 14 m_nextCls = supportUnclassified ? 1 : 0;
14 public MapAlphabet(IEqualityComparer<T> comparer) {
15 m_map = new Dictionary<T, int>(comparer);
16 } 15 }
17 16
18 #region IAlphabetBuilder implementation 17 #region IAlphabetBuilder implementation
19 18
20 public int DefineSymbol(T symbol) { 19 public int DefineSymbol(T symbol) {
21 int cls; 20 int cls;
22 if (m_map.TryGetValue(symbol, out cls)) 21 return m_map.TryGetValue(symbol, out cls) ? cls : DefineSymbol(symbol, m_nextCls);
23 return cls; 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 m_map.Add(symbol, cls); 28 m_map.Add(symbol, cls);
28
29 return cls; 29 return cls;
30 } 30 }
31 31
32 public int DefineClass(IEnumerable<T> symbols) { 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 Safe.ArgumentNotNull(symbols, "symbols"); 38 Safe.ArgumentNotNull(symbols, "symbols");
39
40 m_nextCls = Math.Max(cls + 1, m_nextCls);
34 symbols = symbols.Distinct(); 41 symbols = symbols.Distinct();
35 42
36 foreach (var symbol in symbols) { 43 foreach (var symbol in symbols)
37 if (!m_map.Contains(symbol)) 44 m_map[symbol] = cls;
38 m_map.Add(symbol, m_nextCls); 45 return cls;
39 else
40 throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
41 }
42 return m_nextCls++;
43 } 46 }
44 47
45 #endregion 48 #endregion
46 49
47 #region IAlphabet implementation 50 #region IAlphabet implementation
48 51
49 public List<T>[] CreateReverseMap() { 52 public int Translate(T symbol) {
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) {
96 int cls; 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 public int Count { 61 public int Count {
101 get { 62 get {
102 return m_nextCls; 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 #endregion 71 #endregion
107 } 72 }
108 } 73 }
109 74