using System;

using System.Collections.Generic;

​

//1. Порахувати частоти символів рядок -> символи, частоти

//1a. Порахувати ймовірності і ентропію джерела

//2. Побудувати дерево по Алгоритму Хафмана

//3. Порахувати коди символів

//4. Закодувати

//5. Декодувати

​

//символ, частота, лівий і правий підвузел

//Лист - символ, частота

//Внутрішній - частота, лівий і правий підвузел

​

//Лист чи внутрішній вузел

public abstract class HuffmanNode : IComparable<HuffmanNode>

{

    //частота

    private int frequency;

    public int Frequency { get {return frequency;} }

    public HuffmanNode(int frequency)

    {

        this.frequency = frequency;

    }

    public int CompareTo(HuffmanNode other)

    {

        return frequency.CompareTo(other.Frequency);

    }

    public abstract void Print(int indent = 0, string code = "");

}

​

public class LeafHuffmanNode : HuffmanNode

{

    //символ

    private char symbol;

    public char Symbol { get {return symbol;} }

    public LeafHuffmanNode(char symbol, int frequency) : base(frequency)

    {

        this.symbol = symbol;

    }

    public override void Print(int indent, string code)

    {

        for (int i = 0; i < indent; i++) Console.Write("   ");

        Console.WriteLine("{0} ({1}) code = {2}", Symbol, Frequency, code);

    }

}

​

public class InternalHuffmanNode : HuffmanNode

{

    //лівий і правий підвузел

    private HuffmanNode left;

    private HuffmanNode right;

    public HuffmanNode Left { get {return left;} }

    public HuffmanNode Right { get {return right;} }

    public InternalHuffmanNode (HuffmanNode left, HuffmanNode right) : base (left.Frequency + right.Frequency)

    {

        this.left = left;

        this.right = right;

    }

    public override void Print(int indent, string code)

    {

        left.Print(indent + 1, code + "0");

        for (int i = 0; i < indent; i++) Console.Write("   "); 

        Console.WriteLine('|');

        right.Print(indent + 1, code + "1");

    }

}

​

public class HuffmanCoding 

{

    private HuffmanNode root;

    public HuffmanCoding()

    {

        root = null;

    }

    public static Dictionary<char, int> CalculateFrequency (string str)

    {

        Dictionary<char, int> result = new Dictionary<char, int>();

        foreach (char c in str)

        {

            if (result.ContainsKey(c)) 

            {

                result[c]++;

            }

            else 

            {

                result.Add(c, 1);

            }

        }

        return result;

    }

    public void BuildTree(Dictionary<char, int> freq)

    {

        PriorityQueue<HuffmanNode, int> queue = new PriorityQueue<HuffmanNode, int>();

        foreach( KeyValuePair<char, int> kvp in freq )

        {

            LeafHuffmanNode node = new LeafHuffmanNode(kvp.Key, kvp.Value);

            queue.Enqueue(node, node.Frequency);

        }

        while (queue.Count > 1)

        {

            HuffmanNode node1 = queue.Dequeue();

            HuffmanNode node2 = queue.Dequeue();

            InternalHuffmanNode newnode = new InternalHuffmanNode(node1, node2);

            queue.Enqueue(newnode, newnode.Frequency);

        }

        root = queue.Dequeue();

    }

    public void PrintTree()

    {

        if (root == null) 

        {

            Console.WriteLine("no tree");

        }

        else

        {

            root.Print();

        }

    }

}

public class Program

{

    public static void Main()

    {

        Dictionary<char, int> dict = HuffmanCoding.CalculateFrequency("aaaabbccd");//("But, look, the morn, in russet mantle clad,");

        foreach( KeyValuePair<char, int> kvp in dict )

        {

            Console.WriteLine("Key = {0}, Value = {1}",

                kvp.Key, kvp.Value);

        }

        HuffmanCoding coder = new HuffmanCoding();

        coder.BuildTree(dict);

        coder.PrintTree();

    }

}