using Implab;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

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 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>> GroupFinalStates() {
            return new HashSet<int>[] { m_finalStates };
        }

        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.UnionWith(
                GroupFinalStates()
            );

            var state = new HashSet<int>(
                Enumerable
                .Range(0, m_stateCount - 1)
                .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'

                    foreach (var stateY in optimalStates.ToArray()) {
                        if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
                            var stateR1 = new HashSet<int>(stateY);
                            var stateR2 = new HashSet<int>(stateY);

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

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

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

                        Debug.Assert(res.Length <= 1);

                        var s2 = res.Length > 0 ? res[0] : -1;
                            
                        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++;

                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 void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
            Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
            Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");

            foreach(var t in m_transitions)
                Console.WriteLine(
                    "[{0}] -{{{1}}}-> [{2}]{3}",
                    String.Join(",", stateAlphabet.GetSymbols(t.s1)),
                    String.Join("", inputAlphabet.GetSymbols(t.edge)),
                    String.Join(",", stateAlphabet.GetSymbols(t.s2)),
                    m_finalStates.Contains(t.s2) ? "$" : ""
                );
        }

    }
}