/***************************************************/
/*    項目名稱:霍夫曼編碼算法     */
                                  
/***************************************************/
#include <iostream.h>
#include <vector>
#include <string>
#include <stdlib.h>

using namespace std;


//存儲霍夫曼樹節點的數據結構
typedef struct treenode
{
    char data;                    //存儲要編碼的字符
    int weight;                   //存儲要編碼的字符的權重
    struct treenode* parent;    //父節點
    struct treenode* lchild;    //左子樹
    struct treenode* rchild;    //右子樹
}TreeNode;

//存儲霍夫曼碼表單元的數據結構
typedef struct nodecode
{
	char node;     //存儲要編碼的字符
	string huffmancode;//存儲相應字符的霍夫曼碼
}Nodecode;

//定義全局變量
 static int N;  //記錄文件中出現的字符總數
 static nodecode s[30];//計算出的霍夫曼碼表
 static int index=0; 
/*******************************************************************/
/*函數功能:獲得字符cc在文件中出現的次重,以此作為權重
/******************************************************************/
int GetCount(FILE* fp,char cc)
{
    int i=1;
    while(!feof(fp))
    {
        if(cc==fgetc(fp))
            i++;
    }
    rewind(fp);
    return i;
}
/******************************************************************************/
//函數功能:判斷vector中是否已存在指定字符為cc的treenode
/******************************************************************************/
int IsExit(vector<TreeNode*> vec,char cc)
{
    for(int i=0;i<vec.size();i++)
    {
        if(cc==vec[i]->data)
            return 1;
    }
    return 0;
}
/******************************************************************************/
//函數功能:從vector中選擇權重最小的兩個節點lnode,
//         rnode,并將其從vector中移除
/******************************************************************************/
vector<TreeNode*> Select(vector<TreeNode*> vec,TreeNode** lnode,TreeNode** rnode)
{
    int temp=vec[0]->weight;
    vector<TreeNode*>::iterator iter=vec.begin();
    vector<TreeNode*>::iterator it=vec.begin();
    if(vec.size()==1)
        return vec;
    while(iter!=vec.end())
    {
        if(temp>=iter[0]->weight)
        {
            *lnode=iter[0];
            it=iter;
            temp=iter[0]->weight;
        }
        iter++;
    }
    vec.erase(it);//將取出的第一個節點從vector中刪掉
    temp=vec[0]->weight;
    it=iter=vec.begin();
    while(iter!=vec.end())
    {
        if(temp>=iter[0]->weight)
        {
            *rnode=iter[0];
            it=iter;
            temp=iter[0]->weight;
        }
        iter++;
    }

    vec.erase(it);//將取出的第二個節點從vector中刪掉

    return vec;
}
/******************************************************************************/
//函數功能:判斷vector中是否只含有一個父節點為NULL的節點
//         則將此節點作為霍夫曼樹的根節點返回
/******************************************************************************/
TreeNode* Top(vector<TreeNode*> vec)
{
    int flag=0;
    TreeNode* node;
    for(int i=0;i<vec.size();i++)
    {
        if(vec[i]->parent==NULL)
        {
            flag++;
            node=vec[i];
        }
    }
    if(flag>1)
        return NULL;
    return node;
}
/******************************************************************************/
//函數功能：輸出文件的霍夫曼編碼結果
/******************************************************************************/
string output(FILE *fp)
{
	char cc;
	int i,j;
	string ss;
	ss="";
	cout<<"the encode result is :";
	while(!feof(fp))
	{
		cc=fgetc(fp);
	
		if(cc==EOF)
			break;
	
		for(i=0;i<N;i++)
		{
			if(cc==s[i].node)
			{   
				for(j=0;j<s[i].huffmancode.size();j++)
					cout<<s[i].huffmancode[j];
				ss=ss+s[i].huffmancode;
			
			}
			
		}
	}
	cout<<endl;
	return ss;
}
/******************************************************************************/
//函數功能:對霍夫曼編碼后數據解碼，恢復源文件
/******************************************************************************/
void decode(string encode)
{
	int i=0;
	string ss;
	ss="";
	cout<<"the decode result is :";
	while(i<encode.size())
	{
	
		ss=ss+encode[i];
		for(int j=0;j<N;j++)
		{
			if(ss==s[j].huffmancode)
			{
				cout<<s[j].node;
				ss="";
				continue;
			}
		}
		i=i+1;

	}

}
/******************************************************************************/
//函數功能:初始化vector,將文件中的字符及其權重
//                  不重復的寫入treenode,并將其壓入vector
/******************************************************************************/
vector<TreeNode*> InitList(FILE *fp)
{
    
    int i=0,k=0,flag=0,len=0;
    char cc;
    TreeNode* node;
    vector<TreeNode*> vec;

    while(!feof(fp))
    {
	
        cc=fgetc(fp);
		if (cc==EOF)
			break;
        //若數據重復則跳過此次循環
        if(IsExit(vec,cc))
        {
            continue;
        }
		else
		{
        //將本次循環取出的字符作為TreeNode的data,并計算其權重,將TreeNode
        //的左子樹和右字樹以及父節點初始化為NULL,其壓入vector
        node=(TreeNode*)malloc(sizeof(TreeNode));
        node->data=cc;
        node->weight=GetCount(fp,node->data);
		cout<<"the data is : "<<node->data;
		cout<<" the frequency is : "<<node->weight<<endl;
        node->lchild=node->rchild=node->parent=NULL;
        vec.push_back(node);
  
		}
		
	}
   rewind(fp);//將文件指針重定向到文件頭

    return vec;

}
/******************************************************************************/
//函數功能:構造霍夫曼樹
/******************************************************************************/
TreeNode* CreateTree(vector<TreeNode*> vec)
{
    TreeNode* root;        //霍夫曼樹的根節點
    TreeNode* lchild;    //霍夫曼樹的左子樹
    TreeNode* rchild;    //霍夫曼樹的右子樹
    TreeNode* tree;
    tree=(TreeNode*)malloc(sizeof(TreeNode));
    int i=0;
    while(1)
    {
        lchild=rchild=(TreeNode*)malloc(sizeof(TreeNode));
        //從vector中選擇權重最小的兩個節點
        vec=Select(vec,&lchild,&rchild);
        //新建一個TreeNode節點
        TreeNode* node=(TreeNode*)malloc(sizeof(TreeNode));
        //將取出的節點作為TreeNode節點的的左子樹和右子樹
        node->parent=NULL;
        node->lchild=lchild;
        node->rchild=rchild;
        //新節點的權重為其左子樹和右子樹的權重之和
        node->weight=lchild->weight+rchild->weight;
        lchild->parent=rchild->parent=node;    
        //將新建的節點壓入vector
        vec.push_back(node);

        
        if((root=Top(vec))!=NULL)
            break;
    }
    return root;

}
/******************************************************************************/
//函數功能:遞歸遍歷某一支樹,對某一字符進行編碼
/******************************************************************************/
string Trace(TreeNode* Node,string& cc)
{
    if(Node->parent)
    {
        if(Node->parent->lchild==Node)
        {
            cc="1"+cc;
		//	strcpy("1",cc);
        }
        if(Node->parent->rchild==Node)
        {
		//	strcpy("0",cc);
            cc="0"+cc;
        }
        cc=Trace(Node->parent,cc);
    }
    return cc;
}
/******************************************************************************/
//函數功能:對霍夫曼樹的節點進行訪問
/******************************************************************************/
void Visit(TreeNode* Node)
{
   string cc;
   char ss;
   int i;
   int len;
	cc="";
	Trace(Node,cc);	
    if(Node->lchild==NULL&&Node->rchild==NULL)
    {
	   s[index].node=Node->data;
	   s[index].huffmancode=s[index].huffmancode + cc;	   
	  cout<<"the character is: "<<Node->data;
		len=cc.size();
		cout<<"; the encoding is "; 
		for(i=0;i<len;i++)
		{
			ss=cc[i];
			cout<<ss;
		}
		index=index+1;
		cout<<endl;
    }

	
}
/******************************************************************************/
//函數功能:對霍夫曼樹進行中序遍歷
/******************************************************************************/
/*void Inorder(TreeNode* top, void (*Visit)(TreeNode* Node))
{
    if(top)
    {
        Inorder(top->lchild,Visit);
        Visit(top);
        Inorder(top->rchild,Visit);
    }
}*/
void Inorder(TreeNode* top)
{
    if(top)
    {
        Inorder(top->lchild);
        Visit(top);
        Inorder(top->rchild);
    }
}
/******************************************************************************/
//主函數
/******************************************************************************/

int main(int argc,char* argv[])
{
   
    vector<TreeNode*> vec;	
	string encode;
    FILE* fp;
    TreeNode* top=(TreeNode*)malloc(sizeof(TreeNode));

    fp=fopen("D:\\test.txt","r");
	if(fp==NULL) 
	{ 
		printf("\nerror on open test.dat!");
		exit(1);
	} 
    vec=InitList(fp);
    N=vec.size();//確定文件中出現的字符數	

    vector<TreeNode*>::iterator iter=vec.begin();
    top=CreateTree(vec);
    
    Inorder(top); 
	encode=output(fp);//霍夫曼編碼輸出結果

    decode(encode);//對霍夫曼碼解碼后源文件輸出
	
    
    return 0;
}