implab/ImplabNet Commit - r168:8fb9c9507a26

sync

cin -

r168:8fb9c9507a26 ref20160224

parent child

Context file:

r168:8fb9c9507a26

Collapse all files

Implab/Automaton/DFATransitionTable.cs +70 -28

                          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
                      #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,
                              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);
                          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()
                              );
                          // построение автомата
                              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) {

Implab/Automaton/IDFATableBuilder.cs 0 -1

                      void MarkFinalState(int state);
                      void SetInitialState(int s);
                  }
              }

General Comments 0

Write
Preview

You need to be logged in to leave comments. Login now

No TODOs yet

	Site-wide shortcuts
/	Use quick search box
g h	Goto home page
g g	Goto my private gists page
g G	Goto my public gists page
g 0-9	Goto bookmarked items from 0-9
n r	New repository page
n g	New gist page

	Repositories
g s	Goto summary page
g c	Goto changelog page
g f	Goto files page
g F	Goto files page with file search activated
g p	Goto pull requests page
g o	Goto repository settings
g O	Goto repository access permissions settings
t s	Toggle sidebar on some pages