#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "huffman.h"

void main(int argc, char *argv[])
{
	if(argc==4 && (argv[1][0]=='c' || argv[1][0]=='x'))
	{
		if(argv[1][0]=='c') {
			printf("Compressing...\n");
			compress(argv[2],argv[3]);
		} else {
			printf("Decompressing...\n");
			decompress(argv[2],argv[3]);
		}
	} else {
		printf("Usage: huffman [c|x] infile outfile\n\n");
		exit(1);
	}
}

void compress(char *infile, char *outfile)
{
	FILE *fin, *fout;
	int c, i=0, insize=0, outsize=0;
    char *huffman_table[MAXCHAR];
    
	build_huffman_table(huffman_table);
	if ((fin = fopen(infile,"r")) == NULL) {
		fprintf (stderr, "ERROR : couldn't open file");
		exit(1);
	}
	if ((fout = fopen(outfile,"w")) == NULL) {
		fprintf (stderr, "ERROR : couldn't open file");
		exit(1);
	}
	while((c=fgetc(fin))!=EOF) {
		fprintf(fout, "%s",huffman_table[c]);
		insize+=8;
		outsize+=strlen(huffman_table[c]);
		if((i%3)==0)
			fprintf(fout,"\n");
		i++;
	}
	fclose(fin);
	fclose(fout);
	printf("File compressed.");
	printf("Input size: %d\nOutput size: %d\nCompression: %f\n",insize, outsize, ((float)outsize/(float)insize)*100.0);
}

void decompress(char *infile, char *outfile)
{
	FILE *fin, *fout;
	int c;
	BT_NODE *tree, *cur;
	
	cur=tree=build_huffman_tree();
	if ((fin = fopen(infile,"r")) == NULL) {
		fprintf (stderr, "ERROR : couldn't open file");
		exit(1);
	}
	if ((fout = fopen(outfile,"w")) == NULL) {
		fprintf (stderr, "ERROR : couldn't open file");
		exit(1);
	}
	while((c=fgetc(fin))!=EOF) {
		if(c!=10) {
			if(c=='0') {
				cur=cur->left;
			} else if(c=='1') {
				cur=cur->right;
			}
		    if(cur->c) {
				fprintf(fout,"%c",cur->c);
				cur=tree;
			}
		}
	}
	fclose(fin);
	fclose(fout);
}

void build_huffman_table(char **table)
{
	BT_NODE *tree;
	char *code=(char *)malloc(15);
	
	code[0]=0;
	
	tree=build_huffman_tree();
	traverse_tree(tree, code, table);
}

void traverse_tree(BT_NODE *node, char *code, char **table)
{
	if(node) {
		traverse_tree(node->left, strcat(code,"0\0"),table);
		traverse_tree(node->right, strcat(code,"1\0"),table);
		if(node->c)
			table[node->c]=str_dup(code);
		free(node);
	}
	if(strlen(code))
		code[strlen(code)-1]=0;
}

char *str_dup(char *string)
{
    char *p = (char *)malloc(strlen(string)+1);

    strcpy(p,string);
    return p;
}

BT_NODE *build_huffman_tree()
{
	BT_NODE tempnode, *nodearray[MAXARR], *nodea, *nodeb;
	char string[100];
	FILE *fin;
	int idex, i, a, b;
	for(idex=0;idex<MAXARR;idex++)
		nodearray[idex]=NULL;
	idex=0;
	if ((fin = fopen("huffman.dat","r")) == NULL) {
		fprintf (stderr, "ERROR : couldn't open file");
		exit(1);
	}
	while (fgets(string,100,fin)) {
		sscanf(string, "%d%f", &tempnode.c, &tempnode.w);
		nodearray[idex]=make_node(tempnode.c, tempnode.w, NULL, NULL);
		idex++;
	}
	fclose(fin);
	while(nodearray[find_lowest_node(nodearray, idex)]->w <1) {
		a=find_lowest_node(nodearray, idex);
		nodea=nodearray[a];
		nodearray[a]=NULL;
		b=find_lowest_node(nodearray, idex);
		nodeb=nodearray[b];
		nodearray[b]=NULL;
		if(b<a)
			a=b;
		nodearray[a]=make_node(0, nodea->w+nodeb->w, nodea, nodeb);
	}
	return nodearray[0];
}

int find_lowest_node(BT_NODE **nodearray, int idex)
{
	int i, n=idex;
	for(i=idex;i>=0;i--)
		if(nodearray[i])
			if(nodearray[n]==NULL || (nodearray[i]->w < nodearray[n]->w))
				n=i;
	return n;
}

BT_NODE *make_node(char c, float w, BT_NODE *left, BT_NODE *right)
{
	BT_NODE *node=(BT_NODE *)malloc(sizeof(BT_NODE));
	node->c=c;
	node->w=w;
	node->left=left;
	node->right=right;
	return node;
}
		
/*	Read data into an array of BT_NODEs.
	Traverse array, looking for two lowest.
	Turn those into dynamic nodes, replace one with new tree node, clear other.
	when only one node left, node is huffman tree. QED. */