/************************************************
* tree.c: This program creates a Huffman binary
* tree. It is used with compression.c
*************************************************/
#include "compress.h"
/*t_create: This function is passed a pointer to the 
first element in the priority queue. It usues this pointer
to create a binary tree. It returns a pointer to the root
of the tree.*/
qtptr t_create(qtptr qfirst) {
	qtptr lchild,rchild,root;	/*Pointers to left child(lchild) right child (rchild) and root*/

	while(TRUE) {
		/*Obtain two child nodes from queue*/
		qfirst = q_dequeue(qfirst,&lchild);
		qfirst = q_dequeue(qfirst,&rchild);
		/*disconnect child nodes from other elements in queue*/
		lchild->previous = NULL;
		lchild->next = NULL;
		rchild->previous = NULL;
		rchild->next = NULL;
		/*allocate root node*/
		root = malloc(sizeof(qtnode));
		/*define root node*/
		root->c = 0x00;
		/*give root node the combined priority of the two child nodes*/
		root->priority = (lchild->priority)+(rchild->priority);
		/*set pointers in the root node to the two child nodes*/
		root->left = lchild;
		root->right = rchild;
		/*If no more elements in queue, then tree has been made, therefore break*/
		if(qfirst == NULL) {
			break;
		}
		/*If more elements in queue, add newly created root node back into queue*/
		qfirst = q_enqueue(qfirst,root);
	}
	/*Return pointer to root node of newly created tree*/
	return root;
}

/*t_find: This function is given two arguments. The first argument
is a pointer to the root of the tree and the second is a character. This
function finds the node with the appropriate character and returns a string.
The string contains the path traversed through the tree to find this character.
This path also serves as the huffman encoding (in bits) for the character.*/
char *t_find(qtptr root, char c) {
	char *cval,*ctemp;				/*Two character pointers used to create strings*/
	
	/*Allocate space for each of the pointers*/
	cval = malloc(sizeof(char)*9);
	ctemp = malloc(sizeof(char)*9);
	/*Define each of ths strings as empty ('\0' is a null byte)*/
	*cval = '\0';
	*ctemp = '\0';
	/*Call recrusive find function*/
	cval = t_recurfind(root,c,ctemp,cval);
	/*Free memory pointed to by ctemp, since it is no longer used*/
	free(ctemp);
	/*Return string that designates path to character (which is also the Huffman Encoding)*/
	return cval;
}

/*t_recurfind: This function uses recursion to traverse through a tree and find
the path to a desired character. This function is only called by t_find.*/
char *t_recurfind(qtptr root, char c, char *ctemp,char *cval) {
	char *ccur;				/*Pointer to string (used for temporary storage)*/
	
	/*If not leaf of tree*/
	if(root != NULL) {
		/*Check to see if current node is a leaf*/
		if((root->left == NULL)&&(root->right == NULL)) {
			/*Check to see if leaf contains desired character*/
			if(root->c == c) {
				/*If so, save path*/
				strcpy(cval,ctemp);
			}
		}
		/*Allocate space for ccur*/
		ccur = malloc(sizeof(char)*9);
		/*Copy current path to ccur*/
		strcpy(ccur,ctemp);
		/*Add zero to current path , since going to left child*/
		strcat(ctemp,"0");
		/*Go to left child*/
		t_recurfind(root->left,c,ctemp,cval);
		/*Restore path*/
		strcpy(ctemp,ccur);
		/*Add a one to current path, since going to right child*/
		strcat(ctemp,"1");
		/*Goto right child*/
		t_recurfind(root->right,c,ctemp,cval);
		/*Free ccur, since it is no longer needed*/
		free(ccur);
	}
	/*Return the found path to the character*/
	return cval;
}

/*t_charencode: This function takes three arguments. The first is a pointer
to the root of the tree, the second is the a pointer to the input file, and 
the thrid is a pointer to the output file. This function obtains the path for
all of the characters to be encoded and stores it into the output file.*/
void t_charencode(qtptr root, FILE *input, FILE *output) {
	
	char ctemp = 0;							/*Temporary character*/
	char *cpath = NULL;						/*String that will store path to character in tree*/
	unsigned char cbyte = 0;				/*Character that will store path in byte (instead of string)*/
	unsigned char cmask = 0x80;				/*Mask that will help transform string into byte (for path)*/
	int bitcount = 0;						/*Counter of number of bits (help with transforming string into byte)*/

	while(TRUE)	{
		/*Obtain next character & path if current one stored*/
		if((cpath==NULL)||(*cpath == '\0')) {
			/*If end of file, break (note EOF character has been stored for help with decoding)*/
			if(ctemp ==	EOF) {
				break;
			}
			/*Obtain next character*/
			ctemp =	fgetc(input);
			/*Obtain path for next character*/
			cpath = t_find(root,ctemp);
		}
		/*Transform string into byte*/
		while(bitcount < 8) {
			/*If end of string, break*/
			if(*cpath == '\0') {
				break;
			}
			/*If 1 in string, then add one to byte in appropriate location*/
			if(*cpath == '1') {
				cbyte = cmask | cbyte;
			}
			/*Move to next character in string*/
			cpath++;
			/*Increment bit count*/
			bitcount++;
			/*Move mask to next location for storing*/
			cmask = cmask >> 1;
		}
		/*If all bits in a byte traversed...*/
		if(bitcount == 8) {
			/*Store byte in output file*/
			fputc(cbyte,output);
			/*Reset bitcount, mask, and byte*/
			bitcount = 0;
			cmask = 0x80;
			cbyte = 0;
		}
	}
	/*If more bytes left over, store them*/
	if(bitcount != 0) {
		fputc(cbyte,output);
	}
}