#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

#define MaxValue 10000
#define MaxBit 10
#define MaxN 100

struct letter
{
	
	char a;
	int num;
	
}lett[26];
char text[100];
char code[100];
int code_save[100];

typedef struct  
{
	int weight;
	int flag;
	int parent;
	int leftchild;
	int rightchild;
}HaffNode;

typedef struct
{
	
	int bit[MaxN];
	int start;
	int weight;
}Code;





void Haffman(int weight[],int n,HaffNode haffTree[])
{
	
	int i,j,m1,m2,x1,x2;
	for(i=0;i<2*n-1;i++)//initial
	{
		
		if (i<n)haffTree[i].weight=weight[i];
		else haffTree[i].weight=0;
		haffTree[i].parent=-1;
		haffTree[i].flag=0;
		haffTree[i].leftchild=-1;
		haffTree[i].rightchild=-1;
	}
	
	for (i=0;i<n-1;i++)//search for the least weight dot
	{
		m1=m2=MaxValue;
		x1=x2=0;
		for(j=0;j<n+i;j++)
		{
			
			if (haffTree[j].weight<m1&&haffTree[j].flag==0)
			{
				m2=m1;
				x2=x1;
				m1=haffTree[j].weight;
				x1=j;
			}
			else if (haffTree[j].weight<m2&&haffTree[j].flag==0)
			{
				m2=haffTree[j].weight;
				x2=j;
			}
		}
		haffTree[x1].parent=n+i;
		haffTree[x2].parent=n+i;
		haffTree[x1].flag=1;
		haffTree[x2].flag=1;
		haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
		haffTree[n+i].leftchild=x1;
		haffTree[n+i].rightchild=x2;
	}
}

void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[])
{
	Code *cd=(Code *)malloc(sizeof(Code));
	int i,j,child,parent;
	
	for(i=0;i<n;i++)
	{
		
		cd->start=n-1;
		cd->weight=haffTree[i].weight;
		child=i;
		parent=haffTree[child].parent;
		
		while (parent!=-1)
		{
			if (haffTree[parent].leftchild==child)
				cd->bit[cd->start]=0;
			else
				cd->bit[cd->start]=1;
			
			cd->start--;
			child=parent;
			parent=haffTree[child].parent;
			
		}
		for(j=cd->start+1;j<n;j++)
			haffCode[i].bit[j]=cd->bit[j];
		haffCode[i].start=cd->start+1;
		haffCode[i].weight=cd->weight;
	}
}



void decode(HaffNode tree[])
{
	int i,j,m,k=0;
	char ch;
	FILE *fp;
	m=2*26-2;
	i=m;
//	load();
	printf("\nDecode:\n");
	k=0;
	while(code_save[k]!=10)   //遇到回車時，結束
	{
		
		if(code_save[k]==0)i=tree[i].leftchild;
		else i=tree[i].rightchild;
		if(tree[i].leftchild==-1)
		{
			printf("%c",lett[i].a);
			j=i,i=m;
			
		}k++;

	}
	if(tree[j].leftchild!=-1)
		printf("\nERROR\n");
	printf("\n\n");
}


void main()
{
	
	int k,temp,m=0;
	int i=0,j; 
	FILE *fp;
	char ch;
	fp=fopen("text.txt","r"); 
	ch=fgetc(fp);
	while(ch!=EOF)
	{
		text[i]=ch;
		i++;
		ch=fgetc(fp);
	}
	fclose(fp);
    i=0;
	for (k=0;k<26;k++)
	{
		lett[k].a=k+97;
		lett[k].num=0;
	}
	while(text[i]!=10)
	{
		for (int j=0;j<26;j++)
		{
			if(lett[j].a==text[i])
			{
				lett[j].num++;
				break;
			}
		}
		i++;
	}
	
	int weight[26];
	
	for(k=0;k<26;k++)
	{
		weight[k]=lett[k].num;
	}
	
	HaffNode *myHaffTree=(HaffNode*)malloc(sizeof(HaffNode)*(2*26+1));
	Code *myHaffCode=(Code *)malloc(sizeof(Code)*26);
	
	Haffman(weight,26,myHaffTree);
	HaffmanCode(myHaffTree,26,myHaffCode);
	//k=0;
	for(i=0;i<26;i++)
	{
		printf("letter=%c    weight=%d     code=",lett[i].a,myHaffCode[i].weight);
		for (j=myHaffCode[i].start;j<26;j++)
		{
			printf("%d",myHaffCode[i].bit[j]);
		//	code_save[k]=myHaffCode[i].bit[j];
		//	k++;
		}
		printf("\n");
	}
	i=0;k=0;
	while (text[i]!=10)
	{
		while(text[i]!=lett[k].a)k++;
		
		if (text[i]==lett[k].a)
		{
			for (j=myHaffCode[k].start;j<26;j++)
				
				//break;
			{
				temp=myHaffCode[k].bit[j];
               code_save[m]=temp;
			   m++;
				
				printf("%d",temp);
			}
			
		}
		k=0;
		i++;
	}
	code_save[m]=10;
//	save();
	decode(myHaffTree);
}



void load()
{
	char ch;
	FILE *fp;
	int i;
	if((fp=fopen("code.txt","r"))==NULL)
	{
		printf("\n無法打開文件code.txt!\n");
		return ;
	}
	for(i=0;!feof(fp);i++)
		fread(&code[i],1,1,fp);
	fclose(fp);
}

void save()
{
	
	FILE *fp;
	int i=0;
	if((fp=fopen("code.txt","w"))==NULL)
	{
		printf("\n無法打開文件code.txt!\n");
		return;
	}
	while(code_save[i]!=10)
	{
		if((fwrite(&code_save[i],2,1,fp))!=1)
			//	printf("文件code.txt寫入錯誤\n");
			i++;
	}
	
	fclose(fp);
	
}