view Implab/Automaton/DFATable.cs @ 187:dd4a3590f9c6 ref20160224

Reworked cancelation handling, if the cancel handler isn't specified the OperationCanceledException will be handled by the error handler Any unhandled OperationCanceledException will cause the promise cancelation
author cin
date Tue, 19 Apr 2016 17:35:20 +0300
parents 4f82e0f161c3
children 5f7a3e1d32b9
line wrap: on
line source

using Implab;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
using System.IO;
using System.CodeDom.Compiler;
using System.CodeDom;

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");
            m_stateCount = Math.Max(m_stateCount, s + 1);
            m_initialState = s;
        }

        public void MarkFinalState(int state) {
            m_stateCount = Math.Max(m_stateCount, state + 1);
            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);
            m_symbolCount = Math.Max(m_symbolCount, item.edge + 1);

            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) {
            return m_transitions.Remove(item);
        }

        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();
        }

        public void AddSymbol(int symbol) {
            Safe.ArgumentAssert(symbol >= 0, "symbol");
            m_symbolCount = Math.Max(symbol + 1, m_symbolCount);
        }

        public int[,] CreateTransitionTable() {
            var table = new int[StateCount,AlphabetSize];

            for (int i = 0; i < StateCount; i++)
                for (int j = 0; j < AlphabetSize; j++)
                    table[i, j] = AutomatonConst.UNREACHABLE_STATE;

            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>
        protected virtual IEnumerable<HashSet<int>> SplitFinalStates(IEnumerable<int> states) {
            return new [] { new HashSet<int>(states) };
        }

        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);

            optimalStates.Add(new HashSet<int>(FinalStates));

            var state = new HashSet<int>(
                Enumerable
                .Range(0, m_stateCount)
                .Where(i => !m_finalStates.Contains(i))
            );

            optimalStates.Add(state);
            queue.Add(state);

            var rmap = m_transitions
                .GroupBy(t => t.s2)
                .ToDictionary(
                    g => g.Key, // s2
                    g => g.ToLookup(t => t.edge, t => t.s1)//.ToDictionary(p => p.Key)
                );

            while (queue.Count > 0) {
                var stateA = queue.First();
                queue.Remove(stateA);

                for (int c = 0; c < m_symbolCount; c++) {
                    var stateX = new HashSet<int>();
                    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'

                    var tmp = optimalStates.ToArray();
                    foreach (var stateY in tmp) {
                        var stateR1 = new HashSet<int>(stateY);
                        var stateR2 = new HashSet<int>(stateY);

                        stateR1.IntersectWith(stateX);
                        stateR2.ExceptWith(stateX);

                        if (stateR1.Count > 0 && stateR2.Count > 0) {
                            

                            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);
                            }
                        }
                    }
                }
            }

            // дополнительно разбиваем конечные состояния
            foreach (var final in optimalStates.Where(s => s.Overlaps(m_finalStates)).ToArray()) {
                optimalStates.Remove(final);
                foreach (var split in SplitFinalStates(final))
                    optimalStates.Add(split);
            }
                

            // карта получения оптимального состояния по соотвествующему ему простому состоянию
            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
                        var s2 = m_transitions.Where(t => stateMap[t.s1] == s && t.edge == term).Select(t => stateMap[t.s2]).DefaultIfEmpty(-1).First();

                        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) {
                if (nextCls == AutomatonConst.UNCLASSIFIED_INPUT)
                    nextCls++;

                // сохраняем DFAConst.UNCLASSIFIED_INPUT
                var cls = item.Contains(AutomatonConst.UNCLASSIFIED_INPUT) ? AutomatonConst.UNCLASSIFIED_INPUT : nextCls++;
                optimalDFA.AddSymbol(cls);

                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);
        }

        protected string PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
            Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
            Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");

            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);
        }

        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();
                }
            }
        }
    }
}