Mercurial > pub > ImplabNet
comparison Implab/Automaton/IndexedAlphabetBase.cs @ 162:0526412bbb26 ref20160224
DFA refactoring
author | cin |
---|---|
date | Wed, 24 Feb 2016 08:39:53 +0300 |
parents | |
children | ec35731ae299 |
comparison
equal
deleted
inserted
replaced
161:2a8466f0cb8a | 162:0526412bbb26 |
---|---|
1 using Implab; | |
2 using System; | |
3 using System.Collections.Generic; | |
4 using System.Diagnostics; | |
5 using System.Linq; | |
6 | |
7 namespace Implab.Automaton { | |
8 /// <summary> | |
9 /// Indexed alphabet is the finite set of symbols where each symbol has a zero-based unique index. | |
10 /// </summary> | |
11 public abstract class IndexedAlphabetBase<T> : IAlphabetBuilder<T> { | |
12 public const int UNCLASSIFIED = 0; | |
13 | |
14 int m_nextId = 1; | |
15 readonly int[] m_map; | |
16 | |
17 public int Count { | |
18 get { return m_nextId; } | |
19 } | |
20 | |
21 protected IndexedAlphabetBase(int mapSize) { | |
22 m_map = new int[mapSize]; | |
23 } | |
24 | |
25 protected IndexedAlphabetBase(int[] map) { | |
26 Debug.Assert(map != null); | |
27 | |
28 m_map = map; | |
29 m_nextId = map.Max() + 1; | |
30 } | |
31 | |
32 public int DefineSymbol(T symbol) { | |
33 var index = GetSymbolIndex(symbol); | |
34 if (m_map[index] == UNCLASSIFIED) | |
35 m_map[index] = m_nextId++; | |
36 return m_map[index]; | |
37 } | |
38 | |
39 public int DefineClass(IEnumerable<T> symbols) { | |
40 Safe.ArgumentNotNull(symbols, "symbols"); | |
41 symbols = symbols.Distinct(); | |
42 | |
43 foreach (var symbol in symbols) { | |
44 var index = GetSymbolIndex(symbol); | |
45 if (m_map[index] == UNCLASSIFIED) | |
46 m_map[GetSymbolIndex(symbol)] = m_nextId; | |
47 else | |
48 throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol)); | |
49 } | |
50 return m_nextId++; | |
51 } | |
52 | |
53 public List<T>[] CreateReverseMap() { | |
54 return | |
55 Enumerable.Range(UNCLASSIFIED, Count) | |
56 .Select( | |
57 i => InputSymbols | |
58 .Where(x => i != UNCLASSIFIED && m_map[GetSymbolIndex(x)] == i) | |
59 .ToList() | |
60 ) | |
61 .ToArray(); | |
62 } | |
63 | |
64 public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) { | |
65 Safe.ArgumentNotNull(newAlphabet, "newAlphabet"); | |
66 Safe.ArgumentNotNull(classes, "classes"); | |
67 var reverseMap = CreateReverseMap(); | |
68 | |
69 var translationMap = new int[Count]; | |
70 | |
71 foreach (var scl in classes) { | |
72 // skip if the supper class contains the unclassified element | |
73 if (scl.Contains(UNCLASSIFIED)) | |
74 continue; | |
75 var range = new List<T>(); | |
76 foreach (var cl in scl) { | |
77 if (cl < 0 || cl >= reverseMap.Length) | |
78 throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", cl)); | |
79 range.AddRange(reverseMap[cl]); | |
80 } | |
81 var newClass = newAlphabet.DefineClass(range); | |
82 foreach (var cl in scl) | |
83 translationMap[cl] = newClass; | |
84 } | |
85 | |
86 return translationMap; | |
87 } | |
88 | |
89 public virtual int Translate(T symbol) { | |
90 return m_map[GetSymbolIndex(symbol)]; | |
91 } | |
92 | |
93 public abstract int GetSymbolIndex(T symbol); | |
94 | |
95 public abstract IEnumerable<T> InputSymbols { get; } | |
96 | |
97 /// <summary> | |
98 /// Gets the translation map from the index of the symbol to it's class this is usefull for the optimized input symbols transtaion. | |
99 /// </summary> | |
100 /// <returns>The translation map.</returns> | |
101 public int[] GetTranslationMap() { | |
102 return m_map; | |
103 } | |
104 } | |
105 } |