using System;

using System.Collections.Generic;

using System.Text;

​

public class Program

{

    public static void Main()

    {

        string strr="hi man i love youuuuuuuuuuuuuu";

        Dictionary<char,int> frequencies = HuffmanEncoding.BuildFrequencies(strr);//new Dictionary<char,int>();

        foreach(var item in frequencies)

        {

            Console.WriteLine("{0} has frequency of {1}",item.Key,item.Value);

            //list.Add(new Node(item.Key,item.Value));

            //pq.Enqueue(new Node(item.Key,item.Value));

        }

        /*

        PriorityQueue<Node> pq = new PriorityQueue<Node>();

        foreach(var item in frequencies)

        {

            Console.WriteLine("{0} has frequency of {1}",item.Key,item.Value);

            //list.Add(new Node(item.Key,item.Value));

            pq.Enqueue(new Node(item.Key,item.Value));

        }

        //list.Sort();

        Console.WriteLine("################after sorting###################");

        foreach(var item in list)

        {

            Console.WriteLine("{0} has frequency of {1}",item.Ch,item.Freq);

            //list.Add(new Node(item.Key,item.Value));

        }

        while(!pq.IsEmpty())

        {

            Node currentNode=pq.Dequeue();

            Console.WriteLine("{0} has frequency of {1}",currentNode.Ch,currentNode.Freq);

        }

        Console.WriteLine();

        Console.WriteLine();

​

        Node huffmanTree = HuffmanEncoding.BuildHuffmanTree(frequencies);

        while(!huffmanTree.left.IsLeaf())

        {

            huffmanTree=huffmanTree.left;

            Console.Write('0');

        }

        Console.WriteLine(huffmanTree.Ch);*/

        Dictionary<char,string> lookupTable= HuffmanEncoding.BuildLookUpTable(HuffmanEncoding.BuildHuffmanTree(frequencies));

        foreach(var item in lookupTable)

        {

            Console.WriteLine("{0} has string: {1}",item.Key,item.Value);

            //list.Add(new Node(item.Key,item.Value));

            //pq.Enqueue(new Node(item.Key,item.Value));

        }

        Console.WriteLine("str={0}, compressed={1}",strr,HuffmanEncoding.CompressString(strr,lookupTable));

    }

}

class HuffmanEncoding{

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

    {

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

        int freq;

        foreach (char ch in str)

        {

            if(frequencies.TryGetValue(ch,out freq))

            {

                frequencies.Remove(ch);

                frequencies.Add(ch,freq+1);

            }else

            {

                frequencies.Add(ch,1);

            }

        }

        return frequencies;

    }

    public static Node BuildHuffmanTree(Dictionary<char,int> freqs)

    {

        PriorityQueue<Node> pq = new PriorityQueue<Node>();

        foreach(var item in freqs)

        {

            pq.Enqueue(new Node(item.Key,item.Value));

        }

        if(pq.Size()==1)

        {

            pq.Enqueue(new Node('j',1));

        }

        while(pq.Size()>1)

        {

            Node left = pq.Dequeue();

            Node right = pq.Dequeue();

            Console.WriteLine("enqueuing left={0},right={1}",left.Ch,right.Ch);

            pq.Enqueue(new Node('\0',left.Freq+right.Freq,left,right));

        }

        return pq.Dequeue();

    }

    public static Dictionary<char,string> BuildLookUpTable(Node node)

    {

        Dictionary<char,string> lookupTable = new Dictionary<char,string>();

        BuildLookUpTableRec(node, "",lookupTable);

        return lookupTable;     

    }

    public static void BuildLookUpTableRec(Node node, string input, Dictionary<char,string> lookupTable)

    {

        if(!node.IsLeaf())

        {

            BuildLookUpTableRec(node.left,input+'0',lookupTable);

            BuildLookUpTableRec(node.right,input+'1',lookupTable);

        }

        else

        {

            lookupTable.Add(node.Ch,input);

        }

    }

    public static string CompressString(string str, Dictionary<char,string> lookupTable)

    {

        StringBuilder sb = new StringBuilder();

        string output;

        foreach(char ch in str)

        {

            if(lookupTable.TryGetValue(ch,out output))

                sb.Append(output);

        }

        return sb.ToString();

    }

}

class Node:IComparable<Node>{

    public int Freq{get;set;}

    public char Ch{get;set;}

    public Node left;

    public Node right;

    public Node(char ch,int freq)

    {

        this.Ch=ch;

        this.Freq=freq;

    }

    public Node(char ch,int freq,Node left,Node right)

    {

        this.Ch=ch;

        this.Freq=freq;

        this.left=left;

        this.right=right;

    }

    public bool IsLeaf()

    {

        return this.left==null && this.right==null;

    }

    public int CompareTo(Node other)

    {

        return this.Freq.CompareTo(other.Freq);

        /*if(this.freq==other.freq)

           return 0;

        if(this.freq>other.freq)

            return 1;

        else

            return -1;*/

    }

}

class PriorityQueue<T>

{

    List<T> list;

    int size;

    public PriorityQueue()

    {

        list=new List<T>();

        size=0;

    }

    public void Enqueue(T element)

    {

        list.Add(element);

        size++;

        list.Sort();

    }

    public T Dequeue()

    {

        if(size!=0)

        {

            T element = list[0];

            list.RemoveAt(0);

            size--;

            return element;

        }

        return default(T);

    }

    public T Peek()

    {

        if(size!=0)

        {

            T element = list[0];

            return element;

        }

        return default(T);

    }

    public bool IsEmpty()

    {

        return size==0;

    }

    public int Size()

    {

        return size;

    }

}