##// END OF EJS Templates
implab » ImplabNet
RSS
Added 'Fail' method to RunnableComponent which allows component to move from...
Added 'Fail' method to RunnableComponent which allows component to move from Running to Failed state. Added PollingComponent a timer based runnable component More tests Added FailPromise a thin class to wrap exceptions Fixed error handling in SuccessPromise classes.
cin - - Load All Authors

File last commit:

r183:4f82e0f161c3 ref20160224
r203:4d9830a9bbb8 v2
Show More
DFATable.cs
348 lines | 13.6 KiB | text/x-csharp | CSharpLexer
/ Implab / Automaton / DFATable.cs
History | Source | Raw |Copy content |Copy permalink
cin
rewritten the text scanner
 r176 using Implab;
using System;
using System.Collections.Generic;
using System.Linq;
cin
minor fixes and debug
 r181 using System.Diagnostics;
cin
pretty print DFA, the minimization is still buggy
 r182 using System.IO;
using System.CodeDom.Compiler;
using System.CodeDom;
cin
rewritten the text scanner
 r176
namespace Implab.Automaton {
public class DFATable : IDFATableBuilder {
int m_stateCount;
int m_symbolCount;
int m_initialState;
readonly HashSet<int> m_finalStates = new HashSet<int>();
readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
#region IDFADefinition implementation
public bool IsFinalState(int s) {
Safe.ArgumentInRange(s, 0, m_stateCount, "s");
return m_finalStates.Contains(s);
}
public IEnumerable<int> FinalStates {
get {
return m_finalStates;
}
}
public int StateCount {
get { return m_stateCount; }
}
public int AlphabetSize {
get { return m_symbolCount; }
}
public int InitialState {
get { return m_initialState; }
}
#endregion
public void SetInitialState(int s) {
Safe.ArgumentAssert(s >= 0, "s");
cin
minor fixes and debug
 r181 m_stateCount = Math.Max(m_stateCount, s + 1);
cin
rewritten the text scanner
 r176 m_initialState = s;
}
public void MarkFinalState(int state) {
cin
minor fixes and debug
 r181 m_stateCount = Math.Max(m_stateCount, state + 1);
cin
rewritten the text scanner
 r176 m_finalStates.Add(state);
}
public void Add(AutomatonTransition item) {
Safe.ArgumentAssert(item.s1 >= 0, "item");
Safe.ArgumentAssert(item.s2 >= 0, "item");
Safe.ArgumentAssert(item.edge >= 0, "item");
m_stateCount = Math.Max(m_stateCount, Math.Max(item.s1, item.s2) + 1);
cin
minor fixes and debug
 r181 m_symbolCount = Math.Max(m_symbolCount, item.edge + 1);
cin
rewritten the text scanner
 r176
m_transitions.Add(item);
}
public void Clear() {
m_stateCount = 0;
m_symbolCount = 0;
m_finalStates.Clear();
m_transitions.Clear();
}
public bool Contains(AutomatonTransition item) {
return m_transitions.Contains(item);
}
public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
m_transitions.CopyTo(array, arrayIndex);
}
public bool Remove(AutomatonTransition item) {
cin
refactoring complete, JSONParser rewritten
 r180 return m_transitions.Remove(item);
cin
rewritten the text scanner
 r176 }
public int Count {
get {
return m_transitions.Count;
}
}
public bool IsReadOnly {
get {
return false;
}
}
public IEnumerator<AutomatonTransition> GetEnumerator() {
return m_transitions.GetEnumerator();
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
return GetEnumerator();
}
cin
pretty print DFA, the minimization is still buggy
 r182 public void AddSymbol(int symbol) {
Safe.ArgumentAssert(symbol >= 0, "symbol");
m_symbolCount = Math.Max(symbol + 1, m_symbolCount);
}
cin
rewritten the text scanner
 r176 public int[,] CreateTransitionTable() {
var table = new int[StateCount,AlphabetSize];
for (int i = 0; i < StateCount; i++)
cin
minor fixes and debug
 r181 for (int j = 0; j < AlphabetSize; j++)
cin
working on JSON parser
 r178 table[i, j] = AutomatonConst.UNREACHABLE_STATE;
cin
rewritten the text scanner
 r176
foreach (var t in this)
table[t.s1,t.edge] = t.s2;
return table;
}
public bool[] CreateFinalStateTable() {
var table = new bool[StateCount];
foreach (var s in FinalStates)
table[s] = true;
return table;
}
/// <summary>Формирует множества конечных состояний перед началом работы алгоритма минимизации.</summary>
/// <remarks>
/// В процессе построения минимального автомата требуется разделить множество состояний,
/// на два подмножества - конечные состояния и все остальные, после чего эти подмножества
/// будут резделены на более мелкие. Иногда требуется гарантировать различия конечных сосотяний,
/// для этого необходимо переопределить даннцю фукнцию, для получения множеств конечных состояний.
/// </remarks>
/// <returns>The final states.</returns>
cin
fixed DFA optimization, JSON is fully functional
 r183 protected virtual IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
return new [] { new HashSet<int>(states) };
cin
rewritten the text scanner
 r176 }
protected void Optimize(
IDFATableBuilder optimalDFA,
IDictionary<int,int> alphabetMap,
IDictionary<int,int> stateMap
) {
Safe.ArgumentNotNull(optimalDFA, "dfa");
Safe.ArgumentNotNull(alphabetMap, "alphabetMap");
Safe.ArgumentNotNull(stateMap, "stateMap");
var setComparer = new CustomEqualityComparer<HashSet<int>>(
(x, y) => x.SetEquals(y),
s => s.Sum(x => x.GetHashCode())
);
var optimalStates = new HashSet<HashSet<int>>(setComparer);
var queue = new HashSet<HashSet<int>>(setComparer);
cin
fixed DFA optimization, JSON is fully functional
 r183 optimalStates.Add(new HashSet<int>(FinalStates));
cin
rewritten the text scanner
 r176
var state = new HashSet<int>(
Enumerable
cin
pretty print DFA, the minimization is still buggy
 r182 .Range(0, m_stateCount)
cin
rewritten the text scanner
 r176 .Where(i => !m_finalStates.Contains(i))
);
optimalStates.Add(state);
queue.Add(state);
var rmap = m_transitions
.GroupBy(t => t.s2)
cin
refactoring complete, JSONParser rewritten
 r180 .ToDictionary(
cin
rewritten the text scanner
 r176 g => g.Key, // s2
cin
minor fixes and debug
 r181 g => g.ToLookup(t => t.edge, t => t.s1)//.ToDictionary(p => p.Key)
cin
rewritten the text scanner
 r176 );
while (queue.Count > 0) {
var stateA = queue.First();
queue.Remove(stateA);
for (int c = 0; c < m_symbolCount; c++) {
var stateX = new HashSet<int>();
cin
fixed DFA optimization, JSON is fully functional
 r183 foreach(var a in stateA.Where(rmap.ContainsKey))
stateX.UnionWith(rmap[a][c]); // all states from wich the symbol 'c' leads to the state 'a'
cin
pretty print DFA, the minimization is still buggy
 r182
var tmp = optimalStates.ToArray();
foreach (var stateY in tmp) {
cin
fixed DFA optimization, JSON is fully functional
 r183 var stateR1 = new HashSet<int>(stateY);
var stateR2 = new HashSet<int>(stateY);
cin
rewritten the text scanner
 r176
cin
fixed DFA optimization, JSON is fully functional
 r183 stateR1.IntersectWith(stateX);
stateR2.ExceptWith(stateX);
if (stateR1.Count > 0 && stateR2.Count > 0) {
cin
rewritten the text scanner
 r176
optimalStates.Remove(stateY);
optimalStates.Add(stateR1);
optimalStates.Add(stateR2);
if (queue.Contains(stateY)) {
queue.Remove(stateY);
queue.Add(stateR1);
queue.Add(stateR2);
} else {
queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
}
}
}
}
}
cin
fixed DFA optimization, JSON is fully functional
 r183 // дополнительно разбиваем конечные состояния
foreach (var final in optimalStates.Where(s => s.Overlaps(m_finalStates)).ToArray()) {
optimalStates.Remove(final);
foreach (var split in SplitFinalStates(final))
optimalStates.Add(split);
}
cin
rewritten the text scanner
 r176 // карта получения оптимального состояния по соотвествующему ему простому состоянию
var nextState = 0;
foreach (var item in optimalStates) {
var id = nextState++;
foreach (var s in item)
stateMap[s] = id;
}
// получаем минимальный алфавит
// входные символы не различимы, если Move(s,a1) == Move(s,a2), для любого s
// для этого используем алгоритм кластеризации, сначала
// считаем, что все символы не различимы
var minClasses = new HashSet<HashSet<int>>(setComparer);
var alphaQueue = new Queue<HashSet<int>>();
alphaQueue.Enqueue(new HashSet<int>(Enumerable.Range(0,AlphabetSize)));
// для всех состояний, будем проверять каждый класс на различимость,
// т.е. символы различимы, если они приводят к разным состояниям
for (int s = 0 ; s < optimalStates.Count; s++) {
var newQueue = new Queue<HashSet<int>>();
foreach (var A in alphaQueue) {
// классы из одного символа делить бесполезно, переводим их сразу в
// результирующий алфавит
if (A.Count == 1) {
minClasses.Add(A);
continue;
}
// различаем классы символов, которые переводят в различные оптимальные состояния
// optimalState -> alphaClass
var classes = new Dictionary<int, HashSet<int>>();
foreach (var term in A) {
// ищем все переходы класса по символу term
cin
pretty print DFA, the minimization is still buggy
 r182 var s2 = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).DefaultIfEmpty(-1).First();
cin
rewritten the text scanner
 r176
HashSet<int> a2;
if (!classes.TryGetValue(s2, out a2)) {
a2 = new HashSet<int>();
newQueue.Enqueue(a2);
classes[s2] = a2;
}
a2.Add(term);
}
}
if (newQueue.Count == 0)
break;
alphaQueue = newQueue;
}
// после окончания работы алгоритма в очереди останутся минимальные различимые классы
// входных символов
foreach (var A in alphaQueue)
minClasses.Add(A);
// построение отображения алфавитов входных символов.
// поскольку символ DFAConst.UNCLASSIFIED_INPUT может иметь
// специальное значение, тогда сохраним минимальный класс,
// содержащий этот символ на томже месте.
var nextCls = 0;
foreach (var item in minClasses) {
cin
working on JSON parser
 r178 if (nextCls == AutomatonConst.UNCLASSIFIED_INPUT)
cin
rewritten the text scanner
 r176 nextCls++;
// сохраняем DFAConst.UNCLASSIFIED_INPUT
cin
minor fixes and debug
 r181 var cls = item.Contains(AutomatonConst.UNCLASSIFIED_INPUT) ? AutomatonConst.UNCLASSIFIED_INPUT : nextCls++;
cin
pretty print DFA, the minimization is still buggy
 r182 optimalDFA.AddSymbol(cls);
cin
rewritten the text scanner
 r176
foreach (var a in item)
alphabetMap[a] = cls;
}
// построение автомата
optimalDFA.SetInitialState(stateMap[m_initialState]);
foreach (var sf in m_finalStates.Select(s => stateMap[s]).Distinct())
optimalDFA.MarkFinalState(sf);
foreach (var t in m_transitions.Select(t => new AutomatonTransition(stateMap[t.s1],stateMap[t.s2],alphabetMap[t.edge])).Distinct())
optimalDFA.Add(t);
}
cin
pretty print DFA, the minimization is still buggy
 r182 protected string PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
cin
rewritten the text scanner
 r176 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
cin
pretty print DFA, the minimization is still buggy
 r182 var data = new List<string>();
data.Add("digraph dfa {");
foreach (var final in m_finalStates)
data.Add(String.Format("{0} [shape=box];",String.Join("", stateAlphabet.GetSymbols(final))));
foreach (var t in m_transitions)
data.Add(String.Format(
"{0} -> {2} [label={1}];",
String.Join("", stateAlphabet.GetSymbols(t.s1)),
ToLiteral(ToLiteral(String.Join("", t.edge == AutomatonConst.UNCLASSIFIED_INPUT ? new [] { "@" } : inputAlphabet.GetSymbols(t.edge).Select(x => x.ToString())))),
String.Join("", stateAlphabet.GetSymbols(t.s2))
));
data.Add("}");
return String.Join("\n", data);
cin
rewritten the text scanner
 r176 }
cin
pretty print DFA, the minimization is still buggy
 r182 static string ToLiteral(string input)
{
using (var writer = new StringWriter())
{
using (var provider = CodeDomProvider.CreateProvider("CSharp"))
{
provider.GenerateCodeFromExpression(new CodePrimitiveExpression(input), writer, null);
return writer.ToString();
}
}
}
cin
rewritten the text scanner
 r176 }
}