#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
const SIZE=256;
const SMALLSIZE=20;
struct  HTnode {
	int weight;
	int parent;
	int lchild;
	int rchild;
	char data;
	char code[SIZE];
};
HTnode *HT;
int m,n;
int hashf[SIZE];
char str[SIZE];
void computef()
{
	FILE *in;
	in=fopen("ToBeTran.txt","r");
	if(!in)
	{
		printf("不能打開輸入文件\n");
		return;
	}	
	memset(hashf,0,sizeof(hashf));
	char ch;
	while((ch=fgetc(in))!=EOF)		
		hashf[ch]++;
	n=0;
	int i,j=-1;
	for(i=0;i<SIZE;i++)
		if(hashf[i])
			n++;	
	for(i=0;i<SIZE;i++)
		if(hashf[i]!=0)		
			str[++j]=(char)i;
	fclose(in);
}

//s1<=s2
void select(HTnode *HT,int end,int &s1,int &s2)
{
	int min1,min2,i,j,t;
	min1=INT_MAX;
	for(i=1;i<=end;i++)
		if(HT[i].parent==0 && HT[i].weight<min1)
		{
			min1=HT[i].weight;
			s1=i;
		}	
	min2=INT_MAX;
	for(j=1;j<=end;j++)
		if(HT[j].parent==0 && HT[j].weight<min2 && j!=s1)
		{
			min2=HT[i].weight;
			s2=j;
		}
	if(s1>s2)
	{
		t=s1;
		s1=s2;
		s2=t;
	}
}
//初始化
void Init()
{	
	int i,j,*w;	
	computef();
	m=2*n-1;
	w=(int *)malloc(sizeof(int)*n);
	for(i=0,j=-1;i<SIZE;i++)
		if(hashf[i])
			w[++j]=hashf[i];
	HT=(HTnode *)malloc(sizeof(HTnode)*(m+1));
	if(!HT)
	{
		printf("內存不足\n");
		exit(0);
	}
	for(i=1;i<=n;i++)
	{
		HT[i].weight=w[i-1];
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
		HT[i].data=str[i-1];
	}	
	for(;i<=m;i++)
	{
		HT[i].weight=0;
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
		HT[i].data='\0';
		HT[i].code[0]='\0';
	}	
	int s1,s2;
	for(i=n+1;i<=m;i++)
	{
		select(HT,i-1,s1,s2);
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	char *cd;
	int c,f,start;
	cd=(char *)malloc(sizeof(char)*n);
	cd[n-1]='\0';
	for(i=1;i<=n;i++)
	{
		start=n-1;
		for(c=i,f=HT[i].parent;f;c=f,f=HT[f].parent)
			if(HT[f].lchild==c)
				cd[--start]='0';
			else
				cd[--start]='1';
		strcpy(HT[i].code,&cd[start]);		
	}
	free(cd);
	printf("初始化完畢\n");
}
//編碼
void Encoding()
{
	FILE *in,*out;
	in=fopen("ToBeTran.txt","r");
	if(!in)
	{
		printf("不能打開輸入文件\n");
		return;
	}
	out=fopen("CodeFile.txt","w");
	char ch;
	while((ch=fgetc(in))!=EOF)	
		for(int i=1;i<=n;i++)
			if(HT[i].data==ch)
				fprintf(out,"%s",HT[i].code);
	fprintf(out,"\n");
	printf("編碼完畢\n");
	fclose(in);
	fclose(out);
}

//譯碼
void Decording()
{
	int i,j=-1,find=0;
	char ch,str[SMALLSIZE];
	memset(str,0,sizeof(str));
	FILE *in,*out;
	in=fopen("CodeFile.txt","r");
	if(!in)
	{
		printf("不能打開輸入文件\n");
		return;
	}
	out=fopen("TextFile.txt","w");
	while((ch=fgetc(in))!=EOF)
	{		
		if(find)
		{
			memset(str,0,sizeof(str));
			j=-1;
		}
		str[++j]=ch;
		for(i=0;i<=n;i++)
			if(strcmp(HT[i].code,str)==0)
			{
				find=1;
				fprintf(out,"%c",HT[i].data);
				break;
			}
		if(i>n)
			find=0;
	}
	printf("譯碼完畢\n");
	fclose(in);
	fclose(out);
}

//打印輸出代碼文件
void Printing()
{
	FILE *in;
	in=fopen("CodeFile.txt","r");
	if(!in)
	{
		printf("不能打開輸入文件\n");
		return;
	}
	char ch;
	while((ch=fgetc(in))!=EOF)
		putchar(ch);
}
//打印哈夫曼樹（樹形）
void TreePrinting()
{
	int i,j;	
	for(i=n;i>=1;i--) 
	{		
		if(i==n)
		{
			printf("\t\t*\n\n");
			printf("\t%c\t\t*\n\n",HT[n-i+1].data);		
		}
		else if(i!=2&&i!=1)
		{
			for(j=0;j<=n-i;j++)
				printf("\t");
			printf("%c\t\t*\n\n",HT[n-i+1].data);		
		}
		else if(i==2)
		{
			for(j=0;j<=n-i;j++)
				printf("\t");
			printf("%c\t\t%c\n\n",HT[n-i+1].data,HT[n].data);		
		}
		else if(i==1)
			printf("\n\n");
	}
	printf("\n");
}
//打印哈夫曼樹（樹形）
void TreePrint()
{
	int i,j;	
	for(i=1;i<=n;i++)
	{		
		if(i==1)
		{
			printf("\t\t*\n\n");
			printf("\t%c\t\t*\n\n",HT[i].data);		
		}
		else if(i==2)
		{
			for(j=0;j<i;j++)
				printf("\t");
			printf("%c\t\t*\n\n",HT[i].data);		
		}
		else if(i!=2 && i!=1 && i!=n)
		{
			for(j=0;j<i;j++)
				printf("\t");
			printf("%c\t\t%c\n\n",HT[i].data,HT[n].data);		
		}		
		else if(i==n)
			printf("\n\n");
	}
	printf("\n");
}
int getd(int n)
{
	int h=0;
	return h;
}
void show()
{
	int i;
	printf("父節點\t左兒子\t右兒子\t字符\n");
	for(i=1;i<=m;i++)
		printf("%d\t%d\t%d\t%c\n",HT[i].parent,HT[i].lchild,HT[i].rchild,HT[i].data);
}
int main()
{
	FILE *out;
	out=fopen("ToBeTran.txt","w");
	for(int i=0;i<7;i++)
		fputc('a',out);
	for(i=0;i<5;i++)
		fputc('b',out);
	for(i=0;i<2;i++)
		fputc('c',out);
	for(i=0;i<4;i++)
		fputc('d',out);
/*	for(i=0;i<29;i++)
		fputc('e',out);
	for(i=0;i<14;i++)
		fputc('f',out);
	for(i=0;i<7;i++)
		fputc('g',out);
	for(i=0;i<8;i++)
		fputc('h',out);*/
	fclose(out);
	int InitDid,EnDid,DecDid;
 	InitDid=EnDid=DecDid=0;
	while(1)
	{		
		printf("===================================\n");
		printf("\t赫夫曼編/譯碼器設計\n");
		printf("===================================\n");
		printf("1.初始化\n");
		printf("2.編碼\n");
		printf("3.譯碼\n");
		printf("4.打印輸出代碼文件\n");
		printf("5.打印輸出赫夫曼樹\n");
		printf("0.退出\n");
		int choice=0;
		fcloseall();
		scanf("%d",&choice);
		while(choice<0 || choice >5)
		{
			printf("輸入錯誤，請重新輸入:");
			scanf("%d",&choice);
		}
		
		switch(choice)
		{
			case 1:				
				if(!InitDid)
				{
					Init();
					InitDid=1;
				}
				break;
			case 2:				
				if(InitDid)
				{
					Encoding();
					EnDid=1;
				}
				else
					printf("還沒初始化，請先初始化\n");
				break;
			case 3:				
				if(EnDid)
				{
					Decording();
					DecDid=1;
				}
				else
					printf("還未編碼，請先編碼\n");
				break;
			case 4:				
				if(EnDid)				
					Printing();
				else
					printf("還未譯碼，請先編碼\n");
				break;
			case 5:TreePrinting();				
				break;
			case 0:printf("謝謝使用，再見！\n");
				return 0;
		}		
	}

	return 0;
}