Huffman

using System;
using System.Text;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Diagnostics;

namespace ForDZ
{
    class HuffmanTree<T> where T : IComparable<T>
    {
        #region INNER_CLASSES
        public enum NodeType
        {
            Void = 0,
            Value = 1
        }

        public interface INode
        {
            NodeType Type { get; }
            INode Left { get; set; }
            INode Right { get; set; }
            int Height { get; }
        }

        public class Node : INode
        {
            public T Value { get; set; }
            public INode Left { get; set; }
            public INode Right { get; set; }
            public NodeType Type { get => NodeType.Value; }
            public int Height { get; set; }
        }

        public class VoidNode : INode
        {
            public INode Left { get; set; }
            public INode Right { get; set; }
            public NodeType Type { get => NodeType.Void; }
            public int Height { get; set; }
        }

        private struct NodeWithCount : IComparable<NodeWithCount>
        {
            public INode Node;
            public int Count;

            public int CompareTo(NodeWithCount other)
            {
                int count_cmp = Count.CompareTo(other.Count);

                if(count_cmp != 0)
                {
                    return count_cmp;
                }

                return Node.Height.CompareTo(other.Node.Height);
            }
        }
        #endregion

        private INode root;
        public Dictionary<T, int> ElementsCounts { get; private set; }
        public Dictionary<T, bool[]> Table { get; private set; }

        public HuffmanTree(Dictionary<T, int> elements_counts)
        {
            ElementsCounts = new Dictionary<T, int>(elements_counts.Count);
            foreach(var t in elements_counts.OrderBy(x => x.Value))
            {
                ElementsCounts.Add(t.Key, t.Value);
            }

            InitTree();
            Table = new Dictionary<T, bool[]>();
            AddLeavesToTable(root, (new bool[0]));
        }

        public HuffmanTree(T[] input) : this(CountsOfElements(input))
        {
            //
        }

        private static Dictionary<T, int> CountsOfElements(T[] input)
        {
            Dictionary<T, int> res = new Dictionary<T, int>();

            foreach (T element in input)
            {
                if (res.ContainsKey(element))
                {
                    res[element]++;
                }
                else
                {
                    res.Add(element, 1);
                }
            }

            return res;
        }

        private void InitTree()
        {
            List<NodeWithCount> nodes = new List<NodeWithCount>(ElementsCounts.Count);
            nodes.AddRange(ElementsCounts
                .Select(x =>
                new NodeWithCount
                {
                    Node = new Node
                    {
                        Value = x.Key,
                        Left = null,
                        Right = null,
                        Height = 0
                    },
                    Count = x.Value
                }));
            nodes = nodes.OrderBy(x => x).ToList();

            while (nodes.Count > 1)
            {
                NodeWithCount tuple = new NodeWithCount
                {
                    Node = new VoidNode
                    {
                        Left = nodes[0].Node,
                        Right = nodes[1].Node,
                        Height =
                            (nodes[0].Node.Height < nodes[1].Node.Height ?
                                nodes[0].Node.Height :
                                nodes[1].Node.Height) + 1
                    },
                    Count = nodes[0].Count + nodes[1].Count
                };
                nodes.RemoveAt(0);
                nodes[0] = tuple;

                nodes = nodes.OrderBy(x => x).ToList();
            }

            root = nodes[0].Node;
        }

        private void AddLeavesToTable(INode node, IEnumerable<bool> code)
        {
            if (node.Type == NodeType.Value)
            {
                Table.Add((node as Node).Value, code.ToArray());
                return;
            }

            AddLeavesToTable(node.Left, code.Append(false).ToArray());
            AddLeavesToTable(node.Right, code.Append(true).ToArray());
        }
    }

    static class HuffmanCoder<T> where T : IComparable<T>
    {
        public static bool[] Code(HuffmanTree<T> Tree, T[] input)
        {
            foreach (var t in Tree.ElementsCounts)
            {
                Console.Write($"{t.Key} -> {t.Value} -> ");
                foreach (var i in Tree.Table[t.Key])
                {
                    Console.Write(i ? 1 : 0);
                }
                Console.Write($" ({Tree.Table[t.Key].Length})");
                Console.WriteLine();
            }

            List<bool> res = new List<bool>();

            foreach (T elem in input)
            {
                res.AddRange(Tree.Table[elem]);
            }

            return res.ToArray();
        }
    }

    static class HuffmanDecoder<T> where T : IComparable<T>
    {
        private static bool CheckEqual(bool[] a, bool[] b)
        {
            if (a.Length != b.Length)
            {
                return false;
            }

            for (int i = 0, len = a.Length; i < len; i++)
            {
                if (a[i] != b[i])
                {
                    return false;
                }
            }

            return true;
        }

        public static T[] Decode(HuffmanTree<T> Tree, IEnumerable<bool> coded_sequence)
        {
            Dictionary<bool[], T> BackTable = new Dictionary<bool[], T>();
            foreach (T elem in Tree.Table.Keys)
            {
                BackTable.Add(Tree.Table[elem], elem);
            }

            List<T> res = new List<T>();

            List<bool> current_code = new List<bool>();
            bool[][] keys = BackTable.Keys.ToArray();

            foreach (bool t in coded_sequence)
            {
                current_code.Add(t);

                for (int i = 0; i < keys.Length; i++)
                {
                    if (CheckEqual(keys[i], current_code.ToArray()))
                    {
                        res.Add(BackTable[keys[i]]);
                        current_code.Clear();
                        break;
                    }
                }
            }

            return res.ToArray();
        }
    }

    static class FileHuffmanTree
    {
        public static void CodeToFileWithHuffman(string content, string file_name)
        {
            char[] input = content.ToArray();

            HuffmanTree<char> tree = new HuffmanTree<char>(input);

            bool[] coded_sequence = HuffmanCoder<char>.Code(tree, input);

            List<byte> bytes = new List<byte>();

            bytes.AddRange(BitConverter.GetBytes(tree.ElementsCounts.Count));
            foreach (var t in tree.ElementsCounts)
            {
                bytes.AddRange(BitConverter.GetBytes(t.Key));
                bytes.AddRange(BitConverter.GetBytes(t.Value));
            }

            int byte_length = coded_sequence.Length;
            bytes.AddRange(BitConverter.GetBytes(byte_length));
            byte t_byte = 0;
            for (int i = 0; i < coded_sequence.Length; i++)
            {
                int bit_index = i % 8;

                if (coded_sequence[i])
                {
                    byte adder = (byte)(1 << bit_index);
                    t_byte = (byte)(t_byte | adder);
                }

                if (bit_index == 7)
                {
                    bytes.Add(t_byte);
                    t_byte = 0;
                }
            }
            bytes.Add(t_byte);

            File.WriteAllBytes(file_name, bytes.ToArray());
        }

        public static char[] DecodeToFileWithHuffman(string file_name)
        {
            byte[] file_bytes = File.ReadAllBytes(file_name);
            MemoryStream stream = new MemoryStream(file_bytes);

            byte[] buffer = new byte[4];
            stream.Read(buffer, 0, 4);
            int table_count = BitConverter.ToInt32(buffer, 0);
            Dictionary<char, int> char_table = new Dictionary<char, int>();
            for (int i = 0; i < table_count; i++)
            {
                stream.Read(buffer, 0, 2);
                char letter = BitConverter.ToChar(buffer, 0);
                stream.Read(buffer, 0, 4);
                int count = BitConverter.ToInt32(buffer, 0);
                char_table.Add(letter, count);
            }

            stream.Read(buffer, 0, 4);
            int bit_buffer_len = BitConverter.ToInt32(buffer, 0);
            List<bool> coded_sequence = new List<bool>();

            while (stream.Read(buffer, 0, 1) > 0)
            {
                byte t = buffer[0];
                for (int i = 0; i < 8; i++)
                {
                    coded_sequence.Add((t & (1 << i)) != 0);
                }
            }

            coded_sequence = coded_sequence.Take(bit_buffer_len).ToList();

            HuffmanTree<char> tree = new HuffmanTree<char>(char_table);

            return HuffmanDecoder<char>.Decode(tree, coded_sequence);
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch stopwatch = new Stopwatch();

            string input = File.ReadAllText("input.txt");

            stopwatch.Start();
            FileHuffmanTree.CodeToFileWithHuffman(input, "coded_input.dla");
            stopwatch.Stop();

            Console.Write($"Coding complete ");
            Console.Write($"from {stopwatch.ElapsedMilliseconds} ms ");
            Console.WriteLine($"({stopwatch.ElapsedMilliseconds / 1000.0} s)");

            stopwatch.Reset();

            stopwatch.Start();
            char[] file = FileHuffmanTree.DecodeToFileWithHuffman("coded_input.dla");
            stopwatch.Stop();

            StringBuilder char_list = new StringBuilder();
            char_list.Append(file);
            File.WriteAllText("decoded_input.txt", char_list.ToString());

            Console.Write($"DeCoding complete ");
            Console.Write($"from {stopwatch.ElapsedMilliseconds} ms ");
            Console.WriteLine($"({stopwatch.ElapsedMilliseconds / 1000.0} s)");

            Console.WriteLine("\n\nend.");
            Console.ReadKey();
        }
    }
}