#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <fstream.h>
#include <iomanip.h>

typedef struct
{
	int weight,parent,lchild,rchild;
	char ch;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

void Select(HuffmanTree HT,int i,int &s1,int &s2);
void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n);
void ReadCode(HuffmanTree &HT,int n);
int  intchar();
void FinHuffmanTree(fstream &fin,HuffmanTree HT,int n);
void TextCoding(fstream &intxt,fstream &outxt,HuffmanTree HT,HuffmanCode HC);
int  getnum(HuffmanTree HT,char ch);
void Decoding(fstream &intxt,fstream &outcode,HuffmanTree HT);
void PrintCode();
void PrintTree(HuffmanTree HT,int n,int &space);

void main()
{
	int n,p,markI,markD,markC;
	markI=markD=markC=0;
	char select[5];
	HuffmanTree HT;
	HuffmanCode HC;
	HT=NULL;
	fstream FinHT,FoutHT,Ftxt,FCode,FDeCode;
//	textmode(3)
//	clrscr();
	cout<<"\t\t ______________________________ "<<endl;
	cout<<"\t\t             1初始化            "<<endl;            
	cout<<"\t\t             2建哈夫曼樹(shù)        "<<endl;
	cout<<"\t\t             3譯碼              "<<endl;
	cout<<"\t\t             4查看編碼          "<<endl;
    cout<<"\t\t             5導(dǎo)入文件          "<<endl;
	cout<<"\t\t             6退出              "<<endl;
	cout<<"\t\t ______________________________ "<<endl;
	cout<<"\t\t請(qǐng)選擇:";
    cin>>select;
	while((strlen(select)>1)&&(select[0]!='C'&&select[0]!='I'&&select[0]!='D'&&select[0]!='P'&&select[0]!='T'&&select[0]!='E'))
	{
		cout<<"Incorrect input!";
		cout<<"Input again:";
		cin>>select;
	}
	while (select[0]!='6')
	{
		switch(select[0])
		{
		case '1':
			markI=1;
			cout<<"\t常用字符個(gè)數(shù):";
			cout<<"\tn=:";
			n=intchar();
			ReadCode(HT,n);
			HuffmanCoding(HT,HC,n);
			FinHuffmanTree(FinHT,HT,n);
			break;
		case '2':
			markC=1;
			if(!markI)
			{
				HTNode one;
				FoutHT.open("hfmtree.txt",ios::in);
				FoutHT.read((char*)&one,sizeof(HTNode));
				n=one.weight;
				HT=(HuffmanTree)malloc(2*n*sizeof(HTNode));
				for(int i=1;i<=2*n-1;i++)
					FoutHT.read((char*)&HT[i],sizeof(HTNode));
				FoutHT.close();
				HuffmanCoding(HT,HC,n);
			}
			TextCoding(Ftxt,FCode,HT,HC);
			break;
		case '3':
			markD=1;
			if((!markI)&&(!markC))
			{
				HTNode one;
				FoutHT.open("hfmtree.txt",ios::in);
				FoutHT.read((char*)&one,sizeof(HTNode));
				n=one.weight;
				HT=(HuffmanTree)malloc(2*n*sizeof(HTNode));
				for(int i=1;i<=2*n-1;i++)
					FoutHT.read((char*)&HT[i],sizeof(HTNode));
				FoutHT.close();
				HuffmanCoding(HT,HC,n);
			}
			Decoding(FCode,FDeCode,HT);
			break;
		case '4':
			PrintCode();
			break;
		case '5':
			if((!markI)&&(!markC)&&(!markD))
			{
				HTNode one;
				FoutHT.open("hfmtree.txt",ios::in);
				FoutHT.read((char*)&one,sizeof(HTNode));
				n=one.weight;
				HT=(HuffmanTree)malloc(2*n*sizeof(HTNode));
				for(int i=1;i<=2*n-1;i++)
					FoutHT.read((char*)&HT[i],sizeof(HTNode));
				FoutHT.close();
				HuffmanCoding(HT,HC,n);
				while(HT[p].parent!=0)
					p=HT[p].parent;
//			cout<<"\nHUM:"<<p;
			}
			int m=30;
			PrintTree(HT,p,m);
		}
		cout<<"\nItem:";
		    cin>>select;
		while((strlen(select)>1)&&(select[0]!='C'&&select[0]!='I'
			&&select[0]!='D'&&select[0]!='P'&&select[0]!='T'&&select[0]!='E'))
		{
			cout<<"Incorrect input!";
			cout<<"Input again:";
			cin>>select;
		}
	}
}

int intchar()
{
	char tcin[5];
	int i,mark=1;
	cin>>tcin;
	while(mark)
	{
		mark=0;
		for (i=0;i<strlen(tcin);i++)
			if(tcin[i]<'0'||tcin[i]>'9')
				mark=1;
		if(mark)
		{
			cout<<"Incorrect input!"<<endl;
			cout<<"Input again:";
			cin>>tcin;
		}
	}
	return(atoi(tcin));
}


void ReadCode(HuffmanTree &HT,int n)
{
	char inch;
	int m;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	for(int i=0;i<=m;i++)
		HT[i].ch=HT[i].lchild=HT[i].parent=HT[i].rchild=HT[i].weight=0;
	cout<<"\t請(qǐng)輸入字符和權(quán)值!"<<endl;
	for(i=1;i<=n;i++)
	{
		cout<<"\tNO."<<setw(2)<<i<<" Char:";
		cin>>inch;
		cout<<"\tNO."<<setw(2)<<i<<" weight:";
		HT[i].weight=intchar();
		 
	}
}

void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)
{
	int i,s1,s2,start;
	char *cd;
//	HuffmanTree p;
/*	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	for (p=HT,i=1;i<=n;++i,++p)
		p[i].parent=p[i].rchild=p[i].lchild=0;
	for (;i<=m;++i,++p)
		p[i].ch=p[i].weight=p[i].parent=p[i].rchild=p[i].lchild=0;    */
	HT[0].ch=HT[0].lchild=HT[0].parent=HT[0].rchild=0;
	HT[0].weight=n;
	if(HT[1].parent==0)
	{
		for(i=n+1;i<=2*n-1;++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;
		}
	}
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	char ooo[6]="Error";
	HC[0]=ooo;
	cd=(char*)malloc(n*sizeof(char));
	cd[n-1]='\0';
	for (i=1;i<=n;++i)
	{
		start=n-1;
		for (int c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
			if (HT[f].lchild==c)
				cd[--start]='0';
			else
				cd[--start]='1';
		HC[i]=(char*)malloc((n-start)*sizeof(char));
		strcpy(HC[i],&cd[start]);
	}
	free(cd);
}

void Select(HuffmanTree HT,int i,int &s1,int &s2)
{
	int m=1;
	s1=s2=0;
	while (!s1&&m<=i)
	{
		if (HT[m].parent==0)
			s1=m;
		m++;
	}
	while (!s2&&m<=i)
	{
		if (HT[m].parent==0)
			s2=m;
		m++;
	}
	while(m<=i)
	{
		if(HT[m].parent==0)
		{
			if(HT[m].weight<HT[s1].weight)
			{
				s2=s1;
				s1=m;
			}
			if(HT[m].weight<HT[s2].weight)
				s2=m;
		}
		m++;
	}
}

void FinHuffmanTree(fstream &fin,HuffmanTree HT,int n)
{
	fin.open("hfmtree.txt",ios::out|ios::trunc);
	for(int i=0;i<=2*n-1;i++)
		fin.write((char*)&HT[i],sizeof(HTNode));
	fin.close();
}

int getnum(HuffmanTree HT,char ch)
{
	int i=1;
	while(i<=HT[0].weight&&HT[i].ch!=ch)
		i++;
	if(i>HT[0].weight)
	{
		cout<<"\nError! '"<<ch<<"' is not involved!";
			return (0);
	}
	return(i);
}

void TextCoding(fstream &intxt,fstream &outxt,HuffmanTree HT,HuffmanCode HC)
{
	char txt;
	int i;
	intxt.open("tobetrans.txt",ios::in);
	outxt.open("codefile.hfm",ios::out|ios::trunc);
	while(!intxt.eof())
	{
		intxt.get(txt);
		i=getnum(HT,txt);
		if(i)
			outxt.write(&(*HC[i]),strlen(HC[i]));
	}
	outxt.close();
	intxt.close();		
}

void Decoding(fstream &intxt,fstream &outcode,HuffmanTree HT)
{
	char txt;
	int i,p=1;
	while(HT[p].parent)
		p=HT[p].parent;
	intxt.open("codefile.hfm",ios::in);
	outcode.open("txtfile.txt",ios::out|ios::trunc);
	intxt.get(txt);
	while(!intxt.eof())
	{
		i=p;
		while((HT[i].lchild)&&(!intxt.eof()))
		{
			if(txt=='0')
				i=HT[i].lchild;
			else
				if(txt=='1')
					i=HT[i].rchild;
			intxt.get(txt);
		}
		outcode.put(HT[i].ch);
	}
	intxt.close();
	outcode.close();
}

void PrintCode()
{
	char print;
	fstream intxt,outxt;
	intxt.open("codefile.hfm",ios::in);
	outxt.open("codeprint.txt",ios::out|ios::trunc);
	while(!intxt.eof())
	{
		intxt.get(print);
		outxt.put(print);
		cout<<print;
	}
	intxt.close();
	outxt.close();
}

void PrintTree(HuffmanTree HT,int n,int &space)
{
	int mark;
	for(int i=0;i<space;i++)
		cout<<" ";
	space=space+4;
	cout<<HT[n].ch;
	for(int a=space+1;a<60;a++)
		cout<<"*";
	cout<<endl;
	mark=space;
	if(HT[n].lchild)
		PrintTree(HT,HT[n].lchild,space);
	space=mark;
	if(HT[n].rchild)
		PrintTree(HT,HT[n].rchild,space);
}