// according to slides: http://cs.nyu.edu/~melamed/courses/102/lectures/huffman.ppt

using System;
using System.Collections.Generic;
using System.Linq;
using System.Net;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;

namespace HuffmanCoding
{
    public partial class MainPage : UserControl
    {
        struct Coding
        {
            public int code;
            public int depth;
        };

        class TreeNode
        {
            
            public int frequency;
            public int index;      // ASCII table code
            public TreeNode left;
            public TreeNode right;

            public TreeNode(int frequency, int index, TreeNode left, TreeNode right)
            {
                this.frequency = frequency;
                this.index = index;
                this.left = left;
                this.right = right;
            }
        };

        TreeNode buildTree(TreeNode [] nodes, int L)
        {	
	        int i, pos;

	        while (L > 0)
	        {
                TreeNode temp;

                temp = new TreeNode(nodes[0].frequency + nodes[1].frequency, 0, nodes[0], nodes[1]);

                //temp.frequency = nodes[0].frequency + nodes[1].frequency;
                //temp.left = nodes[0];
                //temp.right = nodes[1];

		        i = 0; pos = 0;
		        while (i < L)
		        {
			        if (temp.frequency >= nodes[i].frequency) pos += 1;
			        else break;
			        i += 1;
		        }

		        L -=1;

		        int j = 2;
		        for (i = 0; i < L; i++)
		        {
			        if(i == pos - 2)
			        {
				        nodes[i] = temp;
				        j = 1;
			        }
			        else
			        {
				        nodes[i] = nodes[i + j];
			        }
		        }
	        }

	        return nodes[0];
        }

        void createCodeBook(TreeNode node, int code, int depth, Coding [] letterCodes)
        {
	        if ( node.left == null && node.right == null)
	        {
		        letterCodes[node.index].code = code;
		        letterCodes[node.index].depth = depth;
	        }
	        else
	        {
		        createCodeBook(node.left, code << 1, depth + 1, letterCodes);
		        createCodeBook(node.right, (code << 1) | 1, depth + 1, letterCodes);
	        }
        }

        void printIntAsBinary(int code, int depth, char [] charCode)
        {
	        int i, j;

	        for (i = 0; i < depth; i++)
	        {
		        j = code & (1 << (depth - i - 1));
                if (j == 0)
                    charCode[i] = '0';
                else
                    charCode[i] = '1';
	        }
	        //charCode[depth] = '\0';
        } 

        public MainPage()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, RoutedEventArgs e)
        {
            int i, j;

	        string input = string1.Text;
	        int inputLength = input.Length;

            int[] frequencies = new int[256];		// frequencies[32] corresponds to space and so on.

	        for (i = 0; i < 256; i++)		
		        frequencies[i] = 0;

	        for (i = 0; i < inputLength; i++)				// scanning the text, calculating frequencies
		        frequencies[(byte)input[i]]++;

	        TreeNode[] myQueue = new TreeNode[2*256];	
	        int myQueueItems = 0;

	        for (i = 0; i < 256; i++)		// creating the queue
	        {
		        if ( frequencies[i] > 0 )
		        {
                    myQueue[myQueueItems] = new TreeNode(frequencies[i], i, null, null);
			        myQueueItems++;
		        }
	        }

	        TreeNode temp;
	        for (i = 0; i < myQueueItems - 1; i++)		// sorting the queue
	        {
		        for (j = i; j < myQueueItems - 1; j++)
		        {
			        if ( myQueue[j].frequency > myQueue[j + 1].frequency )
			        {
				        temp = myQueue[j];
				        myQueue[j] = myQueue[j + 1];
				        myQueue[j + 1] = temp;
			        }
		        }
	        }

	        TreeNode root = buildTree(myQueue, myQueueItems);

	        Coding[] letterCodes = new Coding[256];
	        createCodeBook(root, 0, 0, letterCodes);

            string result = "";
            char[] charCode = new char[32];
            for (i = 0; i < 256; i++)
                if (frequencies[i] > 0)
                {
                    printIntAsBinary(letterCodes[i].code, letterCodes[i].depth, charCode);
                    string s = new string(charCode);
                    s = s.Remove(letterCodes[i].depth, 32 - letterCodes[i].depth); 
                    result += ((char)i) + " :" + s + "     ";
                }
            
            resultstring.Text = result;
        }
    }
}