Mercurial > pub > ImplabNet

comparison Implab/Automaton/IndexedAlphabetBase.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 96681e9d0cea
children 92d5278d1b10
comparison
equal deleted inserted replaced
170:181119ef3b39 171:0f70905b4652
15 /// </remarks> 15 /// </remarks>
16 public abstract class IndexedAlphabetBase<T> : IAlphabetBuilder<T> { 16 public abstract class IndexedAlphabetBase<T> : IAlphabetBuilder<T> {
17 int m_nextId = 1; 17 int m_nextId = 1;
18 readonly int[] m_map; 18 readonly int[] m_map;
19 19
20 public int Count {
21 get { return m_nextId; }
22 }
23
24 protected IndexedAlphabetBase(int mapSize) { 20 protected IndexedAlphabetBase(int mapSize) {
25 m_map = new int[mapSize]; 21 m_map = new int[mapSize];
26 } 22 }
27 23
28 protected IndexedAlphabetBase(int[] map) { 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 m_map = map; 28 m_map = map;
32 m_nextId = map.Max() + 1; 29 m_nextId = map.Max() + 1;
33 } 30 }
34 31
37 if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT) 34 if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT)
38 m_map[index] = m_nextId++; 35 m_map[index] = m_nextId++;
39 return m_map[index]; 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 public int DefineClass(IEnumerable<T> symbols) { 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 Safe.ArgumentNotNull(symbols, "symbols"); 51 Safe.ArgumentNotNull(symbols, "symbols");
44 symbols = symbols.Distinct(); 52 symbols = symbols.Distinct();
45 53
46 foreach (var symbol in symbols) { 54 foreach (var symbol in symbols)
47 var index = GetSymbolIndex(symbol); 55 m_map[GetSymbolIndex(symbol)] = cls;
48 if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT) 56
49 m_map[GetSymbolIndex(symbol)] = m_nextId; 57 m_nextId = Math.Max(cls + 1, m_nextId);
50 else
51 throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
52 }
53 return m_nextId++;
54 }
55 58
56 public List<T>[] CreateReverseMap() { 59 return cls;
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 }
66
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];
73
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;
90 } 60 }
91 61
92 public virtual int Translate(T symbol) { 62 public virtual int Translate(T symbol) {
93 return m_map[GetSymbolIndex(symbol)]; 63 return m_map[GetSymbolIndex(symbol)];
64 }
65
66 public int Count {
67 get { return m_nextId; }
68 }
69
70 public bool Contains(T symbol) {
71 return true;
94 } 72 }
95 73
96 public abstract int GetSymbolIndex(T symbol); 74 public abstract int GetSymbolIndex(T symbol);
97 75
98 public abstract IEnumerable<T> InputSymbols { get; } 76 public abstract IEnumerable<T> InputSymbols { get; }