/***********************************
 * Functions for use in            *
 * construction of Huffman trees,  *
 * encoding, and decoding          *
 *                                 *
 * Code Copyright 2000             *
 * Jonathan Sapan '03              *
 * (unless noted otherwise)        *
 ***********************************/
 
#include "tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

/*  
    Linked list / pointer manipulation code
    adapted from, inspired by, or just plain
    lifted from COS 126 TSP Assignment,
    Spring '00 semester.
*/


extern FILE *inputFile;
extern FILE *outputFile;

static link list = NULL;
int bitBuffer[BIT_BUFF_SIZE];
unsigned char byteBuffer[BYTE_BUFF_SIZE];
int bit_num  = 0;
int byte_num = 0;

link CodeArray[CHARS];


/* Used by call to quicksort in huff.c */
int compare(const void *x, const void *y)
{
	const letter *a, *b;
	a = x;
	b = y;

	if ( a->freq > b->freq)
		return 1;
	if ( a->freq < b->freq )
		return -1;
		
	return 0;
}


link NewNode(letter a) 
{
	link c = malloc(sizeof *c);                  
	assert(c != NULL);
                 
	c->character	= a.ascii;  
	c->weight		= a.freq;
	c->bit			= NULL;
	
	c->parent		= NULL;
	c->left			= NULL;
	c->right			= NULL;
	c->next			= NULL;  
	
	return c;                       
}

void InsertNode(link new)
{
	
	if ( list == NULL)
	{
		list = new;
		new->next = NULL;
	}
	
	else if ( new->weight <= list->weight )
	{
		new->next = list;
		list = new;
	}
	
	else
	{
		link x = list->next;
		link y = list;
                
		while ( (x != NULL) && ( new->weight > x->weight) )
		{
			x = x->next;
			y = y->next;
		}
			
		
		new->next = x;
		y->next = new;
	}
}
	
void RemoveNode(link old)
{
	
	link x;
	
	if ( old == list )
	{
		list = old->next;
	
	}
		
	else
	{
		x = list;
		
		while ( x->next != old )
			x = x->next;
		
		x->next = old->next;
	}
}



link maketree(link a, link b)
{ 
	link c = malloc(sizeof *c);
	
	c->character = -1;
	c->weight = a->weight + b->weight;
	c->left  = a;
	c->right = b;
	c->next  = NULL;
	
	a->parent = b->parent = c;
	
	/* 	
	Left branches are assigned 0
	and right branches 1 for 
	traversal of Huffman tree
	*/
  
	
	a->bit = 0;
	b->bit = 1;
	
	return c;	
}



void Display(void) 
{	
	link x = list;
	
	while ( x != NULL )
  	{ 
  		printf("%3d\t%10d\n", x->character, x->weight);
  		x = x->next;
	}
	
}



void merge(void)
{
	link a, b;
	
	if ( list->next == NULL )
	{
		link c = malloc(sizeof *c);
		
		c->character	= -1;  
		c->weight		= list->weight;
		c->bit			= NULL;
	
		c->parent		= NULL;
		c->left			= list;
		c->right			= NULL;
		c->next			= NULL;
		
		list->bit = 0;
		list->parent = c;
		
		list = c;
	}
	
	else
	{  
		while ( list->next != NULL ) 
		{
			a = list;
			b = list->next;
		
			RemoveNode( list->next );
			RemoveNode( list );
		
			list = b->next;
		
			InsertNode( maketree(a, b) );
		}
	}
	
}



void traverse(void)
{
	int i;
	
	
	for (i=0; i<CHARS; i++)
		CodeArray[i] = NULL;
		
	makeCode( list, height(list), CodeArray );

}




int printCode(link x)
{
	int i, j, codeLength;
	link a = x;
	int bits[CHARS];
	
		
	for ( i = 0; i < CHARS; i++ )
		bits[i] = 0;
	

	for ( i = 0; a != list; a = a->parent, i++ )
		bits[i] = a->bit;
		
	codeLength = i;
	
	for( i = i - 1; i >= 0; i-- )
	{
		if ( byte_num == BYTE_BUFF_SIZE ) /*Flush buffer to file if full*/
		{
			fwrite(byteBuffer, 1, BYTE_BUFF_SIZE, outputFile);
			byte_num = 0;
			
			for (j=0; j<BYTE_BUFF_SIZE; j++)
				byteBuffer[j] = 0;
		}
			
		if ( bit_num == BIT_BUFF_SIZE ) /*If buffer full, flush byte to byteBuffer[]*/
		{
			int sum;
			
			for ( j = 0, sum = 0; j < BIT_BUFF_SIZE; j++ ) {
				sum += bitBuffer[j] * pow(2.0, 1.0*( BIT_BUFF_SIZE - 1 - j )  );
				// printf("%d", bitBuffer[j]);
                        }
			byteBuffer[byte_num] = sum;
			byte_num++;
			
			for (j=0; j<BIT_BUFF_SIZE; j++)
				bitBuffer[j] = 0;
				
			bit_num = 0;
		}  
			
		bitBuffer[bit_num] = bits[i];
		bit_num++;
	}
	
	return codeLength;
}


void decode(void)
{
	int i;
	link x = list;
	unsigned char a;	
	unsigned int number;
	
	fread( byteBuffer, 1, BYTE_BUFF_SIZE, inputFile );
	
	byte_num = 0;
	bit_num = BIT_BUFF_SIZE;
	
	while(1) /*Loop until fread() fails*/
	{
		if ( byte_num == BYTE_BUFF_SIZE )
		{
			if (( fread( byteBuffer, 1, BYTE_BUFF_SIZE, inputFile ) ) == 0 )
				break;
			byte_num = 0;
		}
			
		if ( bit_num == BIT_BUFF_SIZE )
		{	
			number = byteBuffer[byte_num];
			
			for (i = 0; i<BIT_BUFF_SIZE; i++)
			{
				bitBuffer[BIT_BUFF_SIZE - 1 - i] = ( number % 2 );
				number = ( number / 2 );
			}
			
			bit_num = 0;
			byte_num++;
		}
		
		
		while ( (x->character < 0) && (bit_num < BIT_BUFF_SIZE) )
		{
			if ( bitBuffer[bit_num] == 0 )
				x = x->left;
			else if	( bitBuffer[bit_num] == 1 )
				x = x->right;
				
			bit_num++;
		}	
		
		if ( x->character >= 0 )
		{
			fprintf( outputFile, "%c", (char)x->character );
			x = list;
		}
	}
	
	
}







void CodeIO(int a)
{
	if (CodeArray[a] != NULL)
		printCode( CodeArray[a] );
	else
	 	return;
}







/*------------------------------
	Functions adapted/taken from 
	Prof. Robert Sedgewick's 
	Algorithms in C, Sec. 5.7
 ------------------------------*/

int height(link h)
{
	int u, v;
	if ( h == NULL ) return -1;
	u = height(h->left); v = height(h->right);
	if (u<v) return u+1; else return v+1;
}


void makeCode(link x, int h, link CodeArray[]) 
{

	if ( x == NULL ) return;
	
	if (x->character == -1)
		;
		
	else 
		CodeArray[x->character] = x;
	
	makeCode(x->left,  h+1, CodeArray);
	makeCode(x->right, h+1, CodeArray);
}