using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Lab1
{
    class Program
    {
        static void Main(string[] args)
        {
            Coding();
            Console.ReadLine();
        }

        private static void Coding()
        {
            var setProbability = new Dictionary<string, double>
            {
                { "p(a1)", 0.213 },
                { "p(a2)", 0.196 },
                { "p(a3)", 0.147 },
                { "p(a4)", 0.142 },
                { "p(a5)", 0.095 },
                { "p(a6)", 0.065 },
                { "p(a7)", 0.031 },
                { "p(a8)", 0.111 }
            };

            for (var i = 0; i < setProbability.Count; i++)
                Console.WriteLine($"p(a{i + 1}) = {setProbability[$"p(a{i + 1})"]}");



            var initialSet = setProbability;


            setProbability = Sort(setProbability);
            var codeShennonPhano = new Dictionary<string, string>();
            ShannoPhano(setProbability, codeShennonPhano);


            var L1 = 0.0;
            var Kcc1 = 0.0;
            var Koe1 = 0.0;
            var H1 = 0.0;
            var Hmax1 = 0.0;
            Console.WriteLine();
            Console.WriteLine("Коды элементов по методу Шеннона-Фано: ");
            foreach (var codeShPh in codeShennonPhano)
            {
                Console.WriteLine(codeShPh.Key + " = " + codeShPh.Value);
                L1 += codeShPh.Value.Length * initialSet[codeShPh.Key];
                H1 += -1 * (initialSet[codeShPh.Key] * Math.Log(initialSet[codeShPh.Key], 2));
            }

            Hmax1 = Math.Log(8, 2);
            Kcc1 = Hmax1 / L1;
            Koe1 = H1 / L1;
            Console.WriteLine($"lср = {L1}");
            Console.WriteLine($"H = {H1}");
            Console.WriteLine($"Hmax = {Hmax1}");
            Console.WriteLine($"Kcc = {Kcc1}");
            Console.WriteLine($"Kоэ = {Koe1}");


            var code = new Dictionary<string, Point>();
            foreach (var point in setProbability)
                code[point.Key] = new Point();

            Haffman(setProbability, code);

            var L2 = 0.0;
            var H2 = 0.0;
            var Hmax2 = 0.0;
            var Kcc2 = 0.0;
            var Koe2 = 0.0;
            var answer = string.Empty;
            Console.WriteLine();
            Console.WriteLine("Коды элементов по методу Хаффмана: ");
            foreach (var codeHaggman in initialSet)
            {
                answer = string.Empty;
                Console.Write(codeHaggman.Key + " = ");
                PrintHaffman(code[codeHaggman.Key], ref answer);
                L2 += answer.Length * initialSet[codeHaggman.Key];
                H2 += -1 * (initialSet[codeHaggman.Key] * Math.Log(initialSet[codeHaggman.Key], 2));
                Console.WriteLine();
            }

            Hmax2 = Math.Log(8, 2);
            Kcc2 = Hmax2 / L2;
            Koe2 = H1 / L2;
            Console.WriteLine($"lср = {L2}");
            Console.WriteLine($"H = {H2}");
            Console.WriteLine($"Hmax = {Hmax2}");
            Console.WriteLine($"Kcc = {Kcc2}");
            Console.WriteLine($"Kоэ = {Koe2}");
            Console.ReadKey();
        }


        private static void PrintHaffman(Point point, ref string answer, bool print = true)
        {
            if (point.parent != null)
                PrintHaffman(point.parent, ref answer);

            answer += point.value;
            if (print)
                Console.Write(point.value);
        }

        private static void Haffman(Dictionary<string, double> set, Dictionary<string, Point> code)
        {
            set = Sort(set, false);
            var count = 0;
            var dir = new Dictionary<string, double>();
            var sum = 0.0;
            var keyBuf = string.Empty;

            foreach (var point in set)
            {
                count++;
                if (count < 3)
                {
                    sum += point.Value;
                    if (count == 1)
                    {
                        code[point.Key].value += "0";
                        keyBuf += point.Key;
                    }

                    else
                    {
                        code[point.Key].value += "1";
                        code[keyBuf].parent = new Point();
                        code[point.Key].parent = code[keyBuf].parent;
                        code[keyBuf + point.Key] = code[keyBuf].parent;
                        dir[keyBuf + point.Key] = sum;
                    }
                }

                else
                {
                    dir[point.Key] = point.Value;
                }
            }

            if (set.Count != 2)
                Haffman(dir, code);
        }

        private static Dictionary<string, double> Sort(Dictionary<string, double> setProbability, bool reverse = true)
        {
            var sortSetProbability = setProbability.OrderBy(value => value.Value).ToDictionary(
                        row => row.Key,
                        row => row.Value);

            if (reverse)
                return sortSetProbability.Reverse().ToDictionary(
                 row => row.Key,
                 row => row.Value);
            else
                return sortSetProbability;
        }

        private static void ShannoPhano(Dictionary<string, double> set, Dictionary<string, string> code)
        {
            var SumProbability = set.Sum(x => x.Value);
            var group1 = new Dictionary<string, double>();
            var fullnessGroup1 = 0.0;
            var group2 = new Dictionary<string, double>();

            foreach (var point in set)
            {
                var fullness = (fullnessGroup1 + point.Value) / SumProbability;

                if (Math.Abs(fullnessGroup1 / SumProbability - 0.5) > Math.Abs(fullness - 0.5))
                {
                    group1.Add(point.Key, point.Value);
                    fullnessGroup1 += point.Value;
                    if (code.ContainsKey(point.Key))
                        code[point.Key] += "0";

                    else code[point.Key] = "0";
                }
                else
                {
                    group2.Add(point.Key, point.Value);
                    fullnessGroup1 += 1;
                    if (code.ContainsKey(point.Key))
                        code[point.Key] += "1";

                    else code[point.Key] = "1";
                }
            }
            if (group1.Count > 1)
                ShannoPhano(group1, code);

            if (group2.Count > 1)
                ShannoPhano(group2, code);
        }
    }
}