//程序名：main.cpp
//程序功能：用二叉樹實現哈弗曼的編碼和譯碼
//作者：黃秋旋
//日期：2008.12.4
//版本：1.0
//對應類頭文件：hafuman.h
//對應類實現文件：HaffmanTree.h

#include"hafuman.h"
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//主函數
//參數返回值：無

int main()
{
	HaffmanTree HTree;    //聲明哈弗曼樹對象
	
	int finish=1,choice;
	            
	while(finish)
	{
		cout<<"\n ******MENU********\n";
		cout<<"\n 1:初始化哈弗曼樹\n";
		cout<<"\n 2:對文件進行編碼\n";
		cout<<"\n 3:對已編碼文件進行譯碼\n";
		cout<<"\n 4:印代碼文件\n";
		cout<<"\n 5:印哈弗曼樹\n";
		cout<<"\n 6:exit\n";
		cout<<"\n 請輸入你的選擇（1~6）： ";
		cin>>choice;
		cout<<endl;
		switch(choice)
		{
		case 1:
	       HTree.Haffman();            //調用初始化函數，生成哈弗曼樹      
		   break;
		case 2:
           HTree.Encode();             //調用編碼函數，對指定文件進行編碼
           break;
		case 3:
	        HTree.Decode();            //調用譯碼函數，對代碼文件進行翻譯
		    break;
		case 4:
			HTree.Print();             //調用輸出函數，輸出代碼文件中的代碼
	        break;
		case 5:
			HTree.PrintTree();         //調用輸出函數，輸出哈弗曼樹
			break;
		case 6:
			finish=0;                  //結束
			cout<<"歡迎使用! 再見!\n";
			break;
		}
	} 
	return 0;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//程序名：HaffmanTree.cpp
//程序功能：實現哈弗曼樹的編碼和譯碼功能
//作者：黃秋旋
//日期：2008.12.4
//版本：1.0
//對應類頭文件：hafuman.h
//對應主程序：main.cpp

#include"hafuman.h"

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函數名：初始化函數
//函數功能：初始化數據，并生成哈弗曼樹
//函數參數：無
//參數返回值：
//      如果重新初始化哈弗曼樹，則返回葉子節點的個數
//      如果從文件中讀取哈弗曼樹，則返回0表示讀取成功

int HaffmanTree::Haffman()          
{
	int num;
	int choice;
	cout<<"\n1:重新構造哈弗曼樹！";
	cout<<"\n2:從文件中讀取哈弗曼樹！";
	cout<<"請選擇： 1 或 2 ！";             //選擇重新構造哈弗曼樹，還是從文件中讀取哈弗曼樹
	cin>>choice;
	
	if(choice==1)       //選擇重新構造哈弗曼樹
	{
		int n;
	    cout<<"請輸入葉子的個數：";
		cin>>n;
		num=n;

	    ofstream fop;
	    fop.open("hfmTreey.txt", ios::out|ios::binary);    //打開文件，存儲哈弗曼樹的初始化字符
	    
		HaffNode * ht= new HaffNode[2*num-1];            //申請存儲哈弗曼樹的節點的空間
	    char *yezi=new char[num];              //申請存儲初始化字符的空間
		
	    for(int i=0; i<num; i++)
		{
			cout<<"請出入第"<<i+1<<"個字符： ";
            cin>>yezi[i];				//從終端輸入初始化字符
		    fop<<yezi[i];               //并將字符存儲到文件 hfmTreey.txt 中
		    cout<<"請輸入該字符的權值: ";
		    cin>>ht[i].weight;         //從終端輸入初始化字符的權值
		    ht[i].parent=0;            
		    ht[i].lchild=-1;
		    ht[i].rchild=-1;
		    cout<<endl;		        
		}
	    cout<<endl; 
	    fop.close();       //關閉文件

	    for(i=num; i<2*num-1; i++)
		{
			ht[i].weight=0;
		    ht[i].parent=0;		
		    ht[i].lchild=-1;
		    ht[i].rchild=-1;		
		}

	    for(i=0; i<num-1; i++)            //構造哈弗曼樹 
		{
			int m1,m2,x1,x2;
		    m1=m2=1000;                  //存儲兩個最小的權值
		    x1=x2=0;                 //存儲兩個最小權值在結構體數組中的位置
			for(int j=0; j<num+i; j++)
			{
				if(ht[j].weight<m1 && ht[j].parent==0)
				{
					m2=m1;
				    x2=x1;
				    m1=ht[j].weight;
				    x1=j;
				}
			    else if(ht[j].weight<m2 && ht[j].parent==0)
				{
					m2=ht[j].weight;
				    x2=j;
				}
			}

			ht[x1].parent=num+i;
	        ht[x2].parent=num+i;
	        ht[num+i].lchild=x1;
	        ht[num+i].rchild=x2;
	        ht[num+i].weight=ht[x1].weight+ht[x2].weight;           //給新節點付權值
		}

		ofstream fop1;                  
	    fop1.open("hfmTree.txt",ios::out|ios::binary);    //打開文件，寫入初始化字符的信息
	    for(i=0;i<2*num-1;i++)                         //向文件hfmTree.txt寫入哈弗曼樹的信息
		{ 
			fop1<<ht[i].weight<<" ";         
			fop1<<ht[i].parent<<" ";
		    fop1<<ht[i].lchild<<" ";
		    fop1<<ht[i].rchild<<" ";
		    fop1<<endl;
		}
	    fop1.close();                         //關閉文件
	
    	cout<<"\n初始化完成，且已將哈弗曼樹存儲到hfmTree.dat文件中！\n";
	}
	
	else if(choice==2)         //選擇從文件中已有的哈弗曼樹
	{   
		int i=0;
		int in;
		ifstream fip0;
	    fip0.open("hfmTree.txt",ios::in|ios::binary);             //打開文件，讀取哈弗曼樹的信息
		if(fip0.fail())            //判斷打開是否失敗
		{
			cout<<"\n打開失敗! 該文件不存在!\n";
            return 0;
		}
		while(fip0>>in)              //計算文件hfmTree中的節點個數   
			i++;                                                   
		fip0.close();
		leafnum=i/8+1;
       
		
	    cout<<"\n該二叉樹有"<<leafnum<<"個葉子節點!"<<endl;      //測試段
        HaffNode *ht= new HaffNode[2*leafnum-1];           //申請存儲節點的空間

	    ifstream fip;
	    fip.open("hfmTree.txt",ios::in|ios::binary);   //打開文件hfmTree,讀取文件中的內容
	    i=0;
	
		while(fip>>in)           //讀取哈弗曼樹的節點信息
		{
			int j=i/4;
		    int k=i%4;
		    switch(k)
			{
			case 0:
				ht[j].weight=in;

			    break;
		    case 1:
				ht[j].parent=in;

			    break;
		    case 2:
				ht[j].lchild=in;
			    break;
			case 3:
			    ht[j].rchild=in;
			    break;
			}
		    i++;
		}
	    fip.close();    //關閉文件hfmTree
 
		cout<<"\n讀取完成！請進行下一步操作！";
	    return 0; 
	}
	return leafnum=num;
}


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//編碼函數
//函數功能：利用哈弗曼樹為文件中的內容編碼
//函數參數：無
//參數返回值：無

void HaffmanTree::Encode()
{
	char ch;
	ifstream fip2;
	fip2.open("hfmTreey.txt",ios::in|ios::binary);                  //打開存儲初始化字符的文件
	if(fip2.fail()) 
	{
		cout<<"\n打開失敗！\n";
		return;
	}
	
	HaffNode *ht= new HaffNode[2*leafnum-1];
    char *yezi=new char[leafnum];
   
	int i=0;
	while(fip2.get(ch))                          
	{  
		yezi[i]=ch;              //將文件中的字符讀取到yezi數組中
		i++;
	}
	yezi[i]='\0';                 //結束標志
	fip2.close();                 //關閉文件hfmTreey
     
	ifstream fip3;
	fip3.open("hfmTree.txt",ios::in|ios::binary);   //打開文件hfmTree,讀取文件中的內容
	if(fip3.fail())
	{
		cout<<"\n打開失敗! 該文件不存在!\n";
		return;
	}
	i=0;
	int in;
	while(fip3>>in)        //讀取文件中內容
	{
		int j=i/4;
		int k=i%4;
		switch(k)
		{
		case 0:
			ht[j].weight=in;
			break;
		case 1:
			ht[j].parent=in;
			break;
		case 2:
			ht[j].lchild=in;
			break;
		case 3:
			ht[j].rchild=in;
			break;
		}
		i++;
	}
	fip3.close();    //關閉文件hfmTree
 
	ifstream fip;
	fip.open("ToBeTran.txt",ios::in|ios::binary);     //打開文件ToBeTran
	int count=0;

	while(fip.get(ch))
		count++;     //計算ToBeTran.txt中字符的個數
	fip.close();    //關閉文件ToBeTran.txt
  
	char *Tran=new char[count++];    //存儲ToBeTran.txt中字符
    count=0;
	ifstream fipp;
	fipp.open("ToBeTran.txt",ios::in|ios::binary);
	if(fipp.fail())
	{
		cout<<"\n 打開文件失敗！\n";
		return;
	}
	                  
	cout<<"\n需要編碼的內容是:  ";                   
	while(fipp.get(ch))
	{   
		cout<<ch;
		Tran[count]=ch;       //讀取ToBeTran.txt中字符
		count++;
	}
	cout<<endl;
	Tran[count]='\0';
	fipp.close();         //關閉文件ToBeTran.txt
    
   	ofstream fop;
	fop.open("CodeFile.txt", ios::out|ios::binary);     //打開存儲代碼的文件