diff Implab/Automaton/DFATransitionTable.cs @ 168:8fb9c9507a26 ref20160224

sync
author cin
date Wed, 02 Mar 2016 19:59:16 +0300
parents 96681e9d0cea
children
line wrap: on
line diff
--- a/Implab/Automaton/DFATransitionTable.cs	Wed Mar 02 00:20:48 2016 +0300
+++ b/Implab/Automaton/DFATransitionTable.cs	Wed Mar 02 19:59:16 2016 +0300
@@ -53,27 +53,31 @@
             get { return m_initialState; }
         }
 
+        int[] NewTransitionArray() {
+            var t = new int[m_symbolCount];
+
+            for (var i = 0; i < m_symbolCount; i++)
+                t[i] = DFAConst.UNREACHABLE_STATE;
+            return t;
+        }
+
         #endregion
 
         protected virtual DFAStateDescriptior[] ConstructTransitionTable() {
             var dfaTable = new DFAStateDescriptior[m_stateCount];
 
-            foreach (var pair in m_finalStates) {
-                var idx = pair.Key;
-
-                dfaTable[idx].final = true;
-                dfaTable[idx].tag = pair.Value;
-            }
 
             foreach (var t in m_transitions) {
-                if (dfaTable[t.s1].transitions == null) {
-                    dfaTable[t.s1].transitions = new int[m_symbolCount];
-                    for (int i = 0; i < dfaTable[t.s1].transitions.Length; i++)
-                        dfaTable[t.s1].transitions[i] = DFAConst.UNREACHABLE_STATE;
-                }
-
+                if (dfaTable[t.s1].transitions == null)
+                    dfaTable[t.s1] = new DFAStateDescriptior(NewTransitionArray(), m_finalStates.Contains(t.s1));
+                
                 dfaTable[t.s1].transitions[t.edge] = t.s2;
             }
+
+            foreach (var s in m_finalStates)
+                if (!dfaTable[s].final) 
+                    m_dfaTable[s] = new DFAStateDescriptior(NewTransitionArray, true);
+                
         }
 
         #region IDFADefinitionBuilder
@@ -107,8 +111,12 @@
 
         #endregion
 
+        protected virtual IEnumerable<HashSet<int>> GroupFinalStates() {
+            return new HashSet<int>[] { m_finalStates };
+        }
+
         protected void Optimize<TInput, TState>(
-            IDFATableBuilder<TTag> optimalDFA,
+            IDFATableBuilder optimalDFA,
             IAlphabet<TInput> inputAlphabet,
             IAlphabetBuilder<TInput> optimalInputAlphabet,
             IAlphabet<TState> stateAlphabet,
@@ -130,30 +138,20 @@
                 s => s.Sum(x => x.GetHashCode())
             );
 
-            var arrayComparer = new CustomEqualityComparer<TTag[]>(
-                (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
-                a => a.Sum(x => x.GetHashCode())
-            );
-
             var optimalStates = new HashSet<HashSet<int>>(setComparer);
             var queue = new HashSet<HashSet<int>>(setComparer);
 
             // получаем конечные состояния, сгруппированные по маркерам
             optimalStates.UnionWith(
-                m_finalStates
-                .GroupBy(pair => pair.Value, arrayComparer)
-                .Select(
-                    g => new HashSet<int>(
-                        g.Select( pair => pair.Key)
-                    )
-                )
+                GroupFinalStates()
             );
 
             var state = new HashSet<int>(
                 Enumerable
                 .Range(0, m_stateCount - 1)
-                .Where(i => !m_finalStates.ContainsKey(i))
+                .Where(i => !m_finalStates.Contains(i))
             );
+
             optimalStates.Add(state);
             queue.Add(state);
 
@@ -208,10 +206,10 @@
             var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
 
             var optimalTags = m_finalStates
-                .GroupBy(pair => statesMap[pair.Key])
+                .GroupBy(s => statesMap[s])
                 .ToDictionary(
                     g => g.Key,
-                    g => g.SelectMany(pair => pair.Value).ToArray()
+                    g => g.ToArray()
                 );
 
             // построение автомата
@@ -221,10 +219,54 @@
                 optimalDFA.MarkFinalState(pair.Key, pair.Value);
 
             foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
-                optimalDFA.DefineTransition(t.s1, t.s2, t.edge);
+                optimalDFA.Add(new AutomatonTransition(t.s1, t.s2, t.edge));
             
         }
 
+        public void MarkFinalState(int state) {
+            throw new NotImplementedException();
+        }
+
+        public void Add(AutomatonTransition item) {
+            throw new NotImplementedException();
+        }
+
+        public void Clear() {
+            throw new NotImplementedException();
+        }
+
+        public bool Contains(AutomatonTransition item) {
+            throw new NotImplementedException();
+        }
+
+        public void CopyTo(AutomatonTransition[] array, int arrayIndex) {
+            throw new NotImplementedException();
+        }
+
+        public bool Remove(AutomatonTransition item) {
+            throw new NotImplementedException();
+        }
+
+        public int Count {
+            get {
+                throw new NotImplementedException();
+            }
+        }
+
+        public bool IsReadOnly {
+            get {
+                throw new NotImplementedException();
+            }
+        }
+
+        public IEnumerator<AutomatonTransition> GetEnumerator() {
+            throw new NotImplementedException();
+        }
+
+        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
+            throw new NotImplementedException();
+        }
+
         protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
             Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
             Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");