Mercurial > pub > ImplabNet

comparison Implab/Automaton/IndexedAlphabetBase.cs @ 162:0526412bbb26 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }