#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include"huffman.h"
void Select(HuffmanTree HT,int n,int &s1,int &s2)
{
	int i,t;
	for(i=1;i<=n&&HT[i].parent;i++);
		s1=i;
	for(i=i+1;i<=n&&HT[i].parent;i++);
		s2=i;
	for(i=i+1;i<=n;i++)
	{
		if(HT[s1].weight>HT[s2].weight)t=s1;
		else t=s2;
		if(HT[i].parent==0&&HT[i].weight<HT[t].weight)
		{
			t=i;
            if(HT[s1].weight>HT[s2].weight)s1=t;
			else s2=t;
		}
	}
	if(HT[s1].lchild!=0&&HT[s2].lchild==0||s1>s2)
	{//若s1為非葉子結點而s2是葉子結點或者s1>s2則調換s1和s2的次序
		t=s1;
		s1=s2;
		s2=t;
	}
}
Status HfmCoding(Huffman &Hfm)
{
      int i,s1,s2,n,start,c,f;
	  char *cd;
	  n=Hfm.length;
	  for(i=n+1;i<=2*n-1;++i)
	  {//s1為左孩子而s2為右孩子
		  s1=s2=0;
		  Select(Hfm.HT,i-1,s1,s2);
		  Hfm.HT[s1].parent=i;
		  Hfm.HT[s2].parent=i;
		  Hfm.HT[i].lchild=s1;
          Hfm.HT[i].rchild=s2;
		  Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;
	  }
	  Hfm.HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
	  cd=(char *)malloc(n*sizeof(char));
	  cd[n-1]='\0';
	  for(i=1;i<=n;++i)
	  {
		  start=n-1;
		  for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)
			  if(Hfm.HT[f].lchild==c)cd[--start]='0';
			  else cd[--start]='1';
			  Hfm.HC[i]=(char *)malloc((n-start)*sizeof(char));
			  strcpy(Hfm.HC[i],&cd[start]);
			  //TEXT:printf("%s\n",Hfm.HC[i]);
	  }
	  free(cd);
	  return OK;
}
Huffman InputHuffman(Huffman Hfm)
{
	int i,n,m;
	printf("\n請輸入字符長度\n");
	fflush(stdin);
	scanf("%d",&n);
	while(n<1)
	{
		printf("\n請輸入字符長度\n");
		fflush(stdin);
		scanf("%d",&n);
	}
	getchar();
	m=2*n-1;
	Hfm.HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號單元未用
	Hfm.CH=(char *)malloc((n+1)*sizeof(char));//0號單元不用
    for(i=1;i<=n;++i)
	{
		fflush(stdin);
		printf("\n請輸入第%d個字符\n",i);
		scanf("%c",&Hfm.CH[i]);
		printf("\n請輸入第%d個字符對應的權值\n",i);
		scanf("%d",&Hfm.HT[i].weight);
		Hfm.HT[i].parent=0;
		Hfm.HT[i].lchild=0;
		Hfm.HT[i].rchild=0;
	}
	for(;i<=m;++i)
	{
		Hfm.HT[i].parent=0;
		Hfm.HT[i].lchild=0;
		Hfm.HT[i].rchild=0;
		Hfm.HT[i].weight=0;
	}
	Hfm.length=n;
	return Hfm;


}
Status InitHuffman(Huffman &Hfm)
{
	int i,n;
	FILE *fp;
	fp=fopen("hfmTree.txt","r+");
	if(fp==NULL)
	{
		Hfm=InputHuffman(Hfm);
		fp=fopen("hfmTree.txt","w+");
		fprintf(fp,"%d\n",Hfm.length);//將葉子結點的長度存入文件
		for(i=1;i<=Hfm.length;i++)
		{
			//fputc(Hfm.CH[i],fp);//將字符寫入文件
			//putw(Hfm.HT[i].weight,fp);//將對應的權值寫入文件
			fprintf(fp,"%c%d",Hfm.CH[i],Hfm.HT[i].weight);//將字符和對應的權值寫入文件
		}
		rewind(fp);
	}
	else
	{
		printf("\n赫夫曼樹已存在\n");
		fscanf(fp,"%d",&n);//接收葉子結點的長度
		Hfm.CH=(char *)malloc((n+1)*sizeof(char));//0號單元不用，存儲字符
		Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));//0號單元未用，建樹
		fgetc(fp);
		for(i=1;i<=n;i++)
		{
			//Hfm.CH[i]=fgetc(fp);
            //Hfm.HT[i].weight=getw(fp);
			fscanf(fp,"%c%d",&Hfm.CH[i],&Hfm.HT[i].weight);
		}
		for(i=1;i<=n;++i)
		{
			Hfm.HT[i].parent=0;
			Hfm.HT[i].lchild=0;
			Hfm.HT[i].rchild=0;
		}
		for(;i<=2*n-1;++i)
		{
			Hfm.HT[i].parent=0;
			Hfm.HT[i].lchild=0;
			Hfm.HT[i].rchild=0;
			Hfm.HT[i].weight=0;
		}
		Hfm.length=n;
	}
	fclose(fp);
	HfmCoding(Hfm);//進行編碼
	return OK;
}

void Encoding(Huffman Hfm)
{
	FILE *fp1,*fp2;
	int j,i=0;
	char ch[MAX];
	fp1=fopen("ToBeRan.txt","r+");
	if(fp1==NULL)
	{//從鍵盤讀入字符串
		fflush(stdin);
		printf("請輸入要編碼的語句\n");
		gets(ch);
		printf("\n");
	}
	else
	{
		printf("\n要編碼的文件已存在\n");
		fgets(ch,MAX,fp1);
		fclose(fp1);
	}

	//TEXT printf("%s",ch);
	
	fp2=fopen("CodeFile.txt","w+");
	while(ch[i]!='\0')
	{
		for(j=1;j<=Hfm.length;j++)
			if(ch[i]==Hfm.CH[j])
			{
				printf("%s",Hfm.HC[j]);
				fprintf(fp2,"%s",Hfm.HC[j]);
				break;
			}
			i++;
	}
	rewind(fp2);
	fclose(fp2);
	
}

void Decoding(Huffman Hfm)
{
	FILE *fp1,*fp2;
	char cd[MAXNUM];
	int i,j=0;
	fp1=fopen("CodeFile.txt","r+");
	if(fp1==NULL)
	{
		printf("\n請輸入赫夫曼碼進行譯碼：");
		scanf("%s",cd);
	}
	else
	{
		printf("\n要譯碼的文件已存在\n");
		fgets(cd,MAXNUM,fp1);
		fclose(fp1);
	}
	fp2=fopen("TextFile.txt","w+");
	while(cd[j]!='\0')
	{
		i=2*Hfm.length-1;//i為根節點
		while(Hfm.HT[i].lchild||Hfm.HT[i].rchild)
		{
			//printf("%c",cd[j]);
			if(cd[j]=='0')i=Hfm.HT[i].lchild;
			else if(cd[j]=='1')i=Hfm.HT[i].rchild;
			j++;
			//printf("%c",cd[j]);
		}

		printf("%c",Hfm.CH[i]);
		fprintf(fp2,"%c",Hfm.CH[i]);
	}
	fclose(fp2);
}
void Print()
{
	FILE *fp1,*fp2;
	char cd;
	int n=0;
	if((fp1=fopen("CodeFile.txt","r+"))==NULL)
	{
		printf("\nThe file cannot open!\n");
		return;
	}
	fp2=fopen("CodePrin.txt","w+");
	cd=fgetc(fp1);
	while(cd!=EOF)
	{
		printf("%c",cd);
		fprintf(fp2,"%c",cd);
		n++;
		if(n%50==0)
		{
			printf("\n");
			fprintf(fp2,"\n",cd);
		}
		cd=fgetc(fp1);
	}
	fclose(fp1);
	fclose(fp2);

}
Status PreOrderTraverse(Huffman Hfm,int n)
{
	if(n)
	{
		if(Hfm.HT[n].lchild||Hfm.HT[n].rchild)printf("*");//不存在字符，用*代替
		else printf("%c",Hfm.CH[n]);
		if(PreOrderTraverse(Hfm,Hfm.HT[n].lchild))
			if(PreOrderTraverse(Hfm,Hfm.HT[n].rchild))
				return OK;
		return ERROR;
	}
	else return OK;
}
void TreePrint(Huffman Hfm)
{
	int i,n;
	n=Hfm.length;
	printf("\n該赫夫曼樹的編碼規則\n");
	//printf("%s",Hfm.HC[1]);
	for(i=1;i<=n;i++)
	{
		printf("\n");
		printf("字符：%c ",Hfm.CH[i]);
		printf("權值：%d ",Hfm.HT[i].weight);
		printf("對應的編碼：%s ",Hfm.HC[i]);
		//puts(Hfm.HC[i]);
	}
	printf("\n打印赫夫曼樹(先根)\n");
	PreOrderTraverse(Hfm,2*Hfm.length-1);//先根遍歷樹

	
}
void menu()
{
	printf("\n************************************************************\n");
	printf("\n歡迎使用赫夫曼編/譯碼器\n");
	printf("\nI.初始化  E.編碼  D.譯碼  P.印代碼文件  T.印赫夫曼樹  Q.退出\n");
	printf("\n************************************************************\n");
}