using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace PinyinModel
{
    internal class SLMGraph : Graph
    {
        private class Distance
        {
            public double distance = Double.NegativeInfinity;
            public Edge previous = null;

            public Distance()
            {
            }

            public Distance(double distance, Edge previous)
            {
                this.distance = distance;
                this.previous = previous;
            }
        }

        private class DistanceSet : IEnumerable<Distance>
        {
            private LinkedList<Distance> dlist = new LinkedList<Distance>();
            private int limit;

            public DistanceSet(int limit)
            {
                this.limit = limit;
            }

            public Distance First
            {
                get { return dlist.First.Value; }
            }

            public bool Add(Distance new_dist)
            {
                LinkedListNode<Distance> current = dlist.First;
                bool added = false;
                while (current != null)
                {
                    if (new_dist.distance > current.Value.distance)
                    {
                        dlist.AddBefore(current, new_dist);
                        if (dlist.Count > limit)
                            dlist.RemoveLast();
                        added = true;
                        break;
                    }
                    current = current.Next;
                }
                if (!added)
                {
                    if (dlist.Count == limit)
                        return false;
                    dlist.AddLast(new_dist);
                }
                return true;
            }

            #region IEnumerable<Distance> 成员

            IEnumerator<Distance> IEnumerable<Distance>.GetEnumerator()
            {
                return dlist.GetEnumerator();
            }

            #endregion

            #region IEnumerable 成员

            IEnumerator IEnumerable.GetEnumerator()
            {
                return dlist.GetEnumerator();
            }

            #endregion
        }

        private class VertexData
        {
            public string phrase = null;
			public PinyinSequence pinyin_sequence = null;
            public bool calculated = false;
            public DistanceSet dist;

            public VertexData(int solution_set_size)
            {
                dist = new DistanceSet(solution_set_size);
            }
        }

        private class EdgeData
        {
            public double weight = 0;
        }

        int solution_set_size;

        public SLMGraph(LexiconGraph lexicon_graph, LanguageMode slm, int solution_set_size)
        {
            Console.Write("Making statistical language model graph... ");
            this.solution_set_size = solution_set_size;
            this.vertex_count = lexicon_graph.EdgeCount + 2;
            InitializeVertex();
            for (int i = 0; i < vertex_count; i++)
            {
                vertex[i].data = new VertexData(solution_set_size);
            }

            foreach (Edge e in lexicon_graph.Edges)
            {
                int id = (e.data as LexiconGraph.EdgeData).id;
                (vertex[id].data as VertexData).phrase = (e.data as LexiconGraph.EdgeData).phrase;
				(vertex[id].data as VertexData).pinyin_sequence = (e.data as LexiconGraph.EdgeData).pinyin_sequence;
            }

            foreach (Edge e in lexicon_graph.Vertexes[0].to)
            {
                int id = (e.data as LexiconGraph.EdgeData).id;
                AddEdge(0, id, slm.GetUnigram((e.data as LexiconGraph.EdgeData).phrase));
            }

            foreach (Edge e in lexicon_graph.Vertexes[lexicon_graph.VertexCount - 1].from)
            {
                int id = (e.data as LexiconGraph.EdgeData).id;
                AddEdge(id, vertex_count - 1, 1);
            }

            (vertex[0].data as VertexData).phrase = "(S)";
            (vertex[vertex_count - 1].data as VertexData).phrase = "(T)";

            for (int i = 0; i < lexicon_graph.VertexCount; i++)
            {
                foreach (Edge eprev in lexicon_graph.Vertexes[i].from)
                {
                    int prev_id = (eprev.data as LexiconGraph.EdgeData).id;
                    string prev_phrase = (eprev.data as LexiconGraph.EdgeData).phrase;

                    foreach (Edge esucc in lexicon_graph.Vertexes[i].to)
                    {
                        int succ_id = (esucc.data as LexiconGraph.EdgeData).id;
                        string succ_phrase = (esucc.data as LexiconGraph.EdgeData).phrase;
                        AddEdge(prev_id, succ_id, slm.GetBigram(prev_phrase, succ_phrase));
                    }
                }
            }

            Console.WriteLine("Done.");
        }

        private double CalculateWeight(double weight)
        {
            return Math.Log(weight);
        }

        protected Edge AddEdge(int from, int to, double weight)
        {
            Edge e = base.AddEdge(vertex[from], vertex[to]);
            e.data = new EdgeData();
            (e.data as EdgeData).weight = CalculateWeight(weight);
            return e;
        }

        protected void CalculatePath(Vertex vcur)
        {
            VertexData vcur_data = vcur.data as VertexData;
            vcur_data.calculated = true;
            foreach (Edge e in vcur.from)
            {
                double weight = (e.data as EdgeData).weight;
                Vertex vprev = e.from;
                VertexData vprev_data = vprev.data as VertexData;

                if (!vprev_data.calculated)
                    CalculatePath(vprev);

                foreach (Distance vprev_dist in vprev_data.dist)
                {
                    bool retval = vcur_data.dist.Add(new Distance(vprev_dist.distance + weight, e));
                    if (!retval)
                        break; //解集單調性優化
                }
            }
        }

        int SolutionCompare(PinyinModel.Solution a, PinyinModel.Solution b)
        {
            if (a.probability > b.probability)
                return -1;
            return 1;
        }
		
        private LinkedList<VertexData> phrase_seq = new LinkedList<VertexData>();
        private List<PinyinModel.Solution> sentences = new List<PinyinModel.Solution>();

        private void MakeSentence(Vertex vcur, double new_probability)
        {
            phrase_seq.AddFirst(vcur.data as VertexData);

            foreach (Distance vdist in (vcur.data as VertexData).dist)
            {
                Edge prev = vdist.previous;
                if (prev != null)
                {
                    MakeSentence(prev.from, new_probability + (prev.data as EdgeData).weight);
                }
                else
                {
                    StringBuilder sentence = new StringBuilder();
					List<string> pinyin = new List<string>();
					
                    for (LinkedListNode<VertexData> i = phrase_seq.First; i != null; i = i.Next)
                    {
						if (i.Value.phrase == null || i.Value.pinyin_sequence == null)
							continue;
                        sentence.Append(i.Value.phrase);
						foreach (string pinyin_segment in i.Value.pinyin_sequence.Pinyins)
						{
							pinyin.Add(pinyin_segment);
						}
                    }
                    string new_sentence = sentence.ToString();
                    PinyinModel.Solution new_solution = new PinyinModel.Solution();
                    new_solution.sentence = new_sentence;
                    new_solution.probability = new_probability;
					new_solution.pinyin = pinyin.ToArray();
                    sentences.Add(new_solution);
                }
            }

            phrase_seq.RemoveFirst();
        }

        public PinyinModel.Solution[] MakeSentence()
        {
            VertexData vs_data = vertex[0].data as VertexData;
            vs_data.calculated = true;
            vs_data.dist.Add(new Distance(0, null));

            CalculatePath(vertex[vertex_count - 1]);
            MakeSentence(vertex[vertex_count - 1], 0);

            sentences.Sort(this.SolutionCompare);
            List<PinyinModel.Solution> final_sentences = new List<PinyinModel.Solution>();

            for (int i = 0; i < sentences.Count; i++)
            {
                bool duplicated = false;
                foreach (PinyinModel.Solution solution_i in final_sentences)
                {
                    if (sentences[i].sentence == solution_i.sentence)
                    {
                        duplicated = true;
                        break;
                    }
                }
                if (duplicated)
                    continue;

                Console.WriteLine("{0} {1}", sentences[i].sentence, Math.Exp(sentences[i].probability));
                final_sentences.Add(sentences[i]);
                if (final_sentences.Count >= this.solution_set_size)
                    break;
            }
            return final_sentences.ToArray();
        }

        public override string ToString()
        {
            StringBuilder buffer = new StringBuilder();
            foreach (Edge e in this.edges)
            {
                Vertex vs = e.from;
                Vertex vt = e.to;

                buffer.AppendFormat("{0}(\"{1}\") {2}(\"{3}\") {4}",
                    vs.id,
                    (vs.data as VertexData).phrase,
                    vt.id,
                    (vt.data as VertexData).phrase,
                    (e.data as EdgeData).weight);
                buffer.AppendLine();

            }
            return buffer.ToString();
        }
    }
}
