huffman.c

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

/***********************************************************/
/*			Synartiseis Huffman		   */
/***********************************************************/

struct tree
{
    char ch;
    int treeleaft;
    tree lchild,rchild;
};

struct huffman
{
   char characters[256];
   char *binarycode[256];
   tree treeptr;
};





void visit_treenode(tree treeptr);





huffman dimiourgia (void)
{
	huffman newhuff;
        int i=0;
	newhuff=malloc(sizeof(struct huffman));
        if  (newhuff == NULL)
	{
		fprintf(stderr, "sorry cannot allocate memory\n");
		exit(-1);
        }
        while (i<256)
	{
		newhuff->characters[i] = '\0';
	        i++;
        }
	newhuff->treeptr=treenode_creation();
        return newhuff;
}



void katastrofi (huffman huff)
{
	treenode_destroy(huff->treeptr);
	free (huff);
	return;
}




int eisagogi (huffman huff, char ch, char* code)
{
	int error;
	error = enter_char_tree(huff->treeptr, ch, code);
	if(error)
		return error;
        huff->characters[(int)ch] = ch;
	huff->binarycode[(int)ch]=malloc(strlen(code)+1);
        if (huff->binarycode[(int)ch] ==NULL)
	{
		fprintf(stderr, "sorry cannot allocate memory\n");
		exit(-1);
	}
	strcpy(huff->binarycode[(int)ch], code);

	return 0;
}



void kodikopoiisi (huffman newhuff, FILE *outfp, FILE* fp)
{
	char character;
	while( fscanf(fp, "%c", &character) == 1 )
		print_code(newhuff, character, outfp);
	return;
}



void apokodikopoiisi (huffman newhuff, FILE *outfp, FILE* fp)
{
	while(!print_char(newhuff, outfp, fp));
	return;
}



/************* sinartiseis printarismaton**************/


void print_code(huffman newhuff, char ch, FILE *fp)
{
	if(newhuff->characters[(int)ch] == '\0')
		return;
	fprintf(fp, "%s", newhuff->binarycode[(int)ch]);
	return;
}




int print_char(huffman newhuff, FILE *outfp, FILE *fp)
{
	char character;
	character = get_char_tree (newhuff->treeptr, fp);
	if (character == '\0')
		return 1;
	fprintf(outfp, "%c", character);
	return 0;
}



/***********************************************************/
/*		Synartiseis Dentrou Huffman		   */
/***********************************************************/

tree treenode_creation(void)
{
	tree treenodeptr;
	treenodeptr=malloc(sizeof(struct tree));
        if  (treenodeptr == NULL )
	{
		fprintf(stderr, "sorry cannot allocate memory\n");
		exit(-1);
	}
	treenodeptr->treeleaft = 0;
	treenodeptr->rchild = NULL;
	treenodeptr->lchild = NULL;
	return treenodeptr;
}



void treenode_destroy (tree treenodeptr)
{
	if ( treenodeptr == NULL )
		return;
	
	if ( treenodeptr->lchild != NULL )
		treenode_destroy(treenodeptr->lchild);
	if ( treenodeptr->rchild != NULL )
		treenode_destroy(treenodeptr->rchild);

	visit_node(treenodeptr);

	return;
}

void visit_treenode(tree treenodeptr)
{
      free(treenodeptr);
      return;
}

int enter_char_tree (tree treenodeptr, char ch, char *binarycode)
{
	int error;
	if (treenodeptr == NULL)
		return -1;

	if ( !strlen(binarycode) )			// an ftasame ston proorismo
	{
		if(treenodeptr->treeleaft)		// idi katilimeno
			return -1;
		if(treenodeptr->lchild != NULL || treenodeptr->rchild != NULL)	// komvos
			return -1;

		treenodeptr->ch = ch;
		treenodeptr->treeleaft = 1;
		return 0;
	}

	if(binarycode[0] == '0')			// go right
	{
		if ( treenodeptr->lchild == NULL )	// dimiourgw an den iparxei komvos
			treenodeptr->lchild = treenode_creation();
		error = enter_char_tree(treenodeptr->lchild, ch, binarycode+1);
	}
	else					// go left
	{
		if ( treenodeptr->rchild == NULL )	// dimiourgw an den iparxei komvos
			treenodeptr->rchild = treenode_creation();
		error = enter_char_tree(treenodeptr->rchild, ch, binarycode+1);
	}
	return error;
}

char get_char_tree (tree treenodeptr, FILE* fp)
{
	tree tmp = treenodeptr;
	char bincode;
        
       if(tmp->treeleaft) return (tmp->ch);
       else
         do
           {
		if ( fscanf(fp, "%c", &bincode) == EOF )
			return '\0';

		if (bincode == '0')
		{
			if(tmp->lchild == NULL) 	exit(-3);
			tmp = tmp->lchild;
		}
		else if (bincode == '1')
		{
			if(tmp->rchild == NULL)         exit(-3);
			tmp = tmp->rchild;
		}
		else
			return '\0';
	     }while(tmp->treeleaft);        //mexri na vreis fyllo

	return (tmp->ch);
}