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

using namespace std; 

#define MAX_SIZE 256

struct huffman_node 
{ 
     char id; 
     int freq; 
	 string code;
	 int mark;
     huffman_node *left, *right, *parent;
	 huffman_node():id('a'), freq(0),left(0), right(0), parent(0),mark(0){};
}; 

typedef huffman_node* node_ptr; 

class huffman { 
protected: 
	huffman_node dictionary[MAX_SIZE];
   	huffman_node* node_array [MAX_SIZE]; 
   	fstream in_file,out_file; 
   	node_ptr child, parent ,root; 
   	char id; 
	int count;
   	string in_file_name2; 

   class compare 
   { 
      public: 
			bool operator() ( const node_ptr& c1,const node_ptr& c2 ) const 
			{ return (*c1).freq > (*c2).freq; } 
    }; 

    priority_queue< node_ptr, vector<node_ptr>, compare > pq; 

    // Postcondition: The node_array, including the frequency of each character, has been created from the input file. 
    void create_node_array(); 

public: 
	 huffman() :id('a'), child(0),parent(0),root(0){};
	 // Postcondition: this huffman object has been initialized from in_file_name and out_file_name. 
	 huffman (string in_file_name, string out_file_name); 

     // Postcondition: the priority queue has been created. 
	 void create_pq(); 

     // Postcondition: the Huffman tree has been created. 
	 void create_huffman_tree(); 

     // Postcondition: the Huffman codes have been calculated. 
     void calculate_huffman_codes(); 

     // Postcondition: the Huffman codes and encoded message have been saved to a file.  
     void save_to_file(); 
}; 


void huffman::create_node_array()
{
	int pos = (int)id&0x0ff;     //是下表未整數
	if(!node_array[pos]){
			node_ptr tmp = new huffman_node;
			tmp->id=id;
			node_array[pos] = tmp; 
			(node_array[pos]->freq)++;
			count++;
		}
		else
			(node_array[pos]->freq)++;
}

huffman::huffman(string in_file_name, string out_file_name)
{ 
	in_file_name2 = in_file_name;

	in_file.open(in_file_name.c_str(), fstream::in | ios::binary);  //只讀方式打開一個文件

	if(!in_file)  
	{ 
		cout<<"\nCan not open file0！\n"<<endl; 
		getch(); 
		return; 
	} 

	out_file.open(out_file_name.c_str(), ios::out | ios::binary); 
	if(!out_file)  
	{ 
		cout<<"\nCan not open file！\n"<<endl; 
		getch(); 
		return; 
	} 
	
	count=0;
	for(int i=0; i<256; i++) node_array[i] = NULL;
	while(in_file.get(id))                       //循環將文件內的字符輸入到od中 
	{
		create_node_array();
	}
	in_file.close(); 
}

void huffman::create_pq()
{
	int j=0;
	for(int i=0 ;i<256 ; i++)
	{
		while(!node_array[i]) i++;
		if(j < count){
		pq.push(node_array[i]);
		j++;}
	}
}

void huffman::create_huffman_tree()
{
	node_ptr p,q; 

	//p、q初值為頭結點后的兩個結點，即最小權結點  
	while(pq.size() > 1)
	{
		p=pq.top();         //取出將最小的兩個結點 
		pq.pop();

		q=pq.top();
		pq.pop();

		node_ptr newnode = new huffman_node;
		root = newnode; 
		newnode->mark=0; //標記

		newnode->left=p; //取最小的兩個結點作為新結點的左、右孩子 
		newnode->right=q; 
		p->parent=newnode; 
		q->parent=newnode; 
		newnode->freq = p->freq + q->freq; //權值等于孩子權值相加 
		  
		pq.push(root);	 //將新結點插入原隊列的相應位置 		
	} 
	return; 
}


void huffman::calculate_huffman_codes()
{             
	node_ptr ptr = root;              //從樹的根結點開始
	if(root==NULL) 
	{ 
		cout<<"要壓縮的文件是空的!"<<endl; 
		exit(0); 
	} 
	else 
	{	
		int i=0,j=0;
		string s[256];     //用于統計每個字符的哈夫曼編碼 
		while(ptr->left && ptr->right && ptr->mark==0) 
		{ 
			while(ptr->left && ptr->left->mark==0) 
			{  
				ptr = ptr->left; 		
				s[j] =s[j]+'0';

				if(!ptr->left && !ptr->right) //判斷是否為葉子 
				{   
					dictionary[i].id=ptr->id;//給字典賦字符值  
					dictionary[i].code = s[j];
					i++;j++;
					ptr->mark=1; 
					ptr=root;
				} 
			} 
			if(ptr->right && ptr->right->mark==0) 
			{ 
				ptr=ptr->right;  
				s[j] = s[j] +'1';
			} 
			if(!ptr->left && !ptr->right) 
			{  
				dictionary[i].id=ptr->id; 
				dictionary[i].code = s[j];
				i++; j++;
				ptr->mark=1;
				ptr=root;   
			}
			
			if(ptr->left->mark==1 && ptr->right->mark==1)//如果左右孩子都已標志
				{ 
					j++;
					ptr->mark=1; 
					ptr=root; 
				} 		
		}
	} 
}

void deleteTree(node_ptr ptr) 
{ 
	node_ptr tmp=ptr;
	if(tmp) 
	{ 
		deleteTree(tmp->left); //第歸處理左子樹 
		deleteTree(tmp->right); //第歸處理右子樹 
		delete tmp; //釋放結點 
	} 
}


void huffman::save_to_file()
{
	fstream in_file2;
	in_file2.open(in_file_name2.c_str(), ios::in | ios::binary);  //只讀方式打開一個文件
	if(!in_file2)  
	{ 
		cout<<"\nCan not open file1！\n"<<endl; 
		getch(); 
		return; 
	} 
	for(int i=0; i<count ;i++)   //寫入字典
	{
		out_file.put(dictionary[i].id);
		for(int j=0;dictionary[i].code[j]!='\0' ; j++)
		out_file.put(dictionary[i].code[j]);
		out_file.put('\0');
	}

	char buf='0';
	int  jud=0;
	while(in_file2.get(id))                     //循環將文件內的字符輸入到od中 
	{
		for(int i=0;i<count;i++)
		{
			if(dictionary[i].id==id)
			{
				for(int j=1;dictionary[i].code[j-1];j++,jud++) 
				{ 
					if(dictionary[i].code[j-1]=='1') 
					{ 
						buf<<=1; 
						buf++; 
					} 
					if(dictionary[i].code[j-1]=='0') 
					{ 
						buf<<=1;  
					} 
					if(jud%8==0) 
					out_file.put(buf);
				}
			}
		}
	}
	deleteTree(root);
	in_file2.close(); 
	out_file.close();
}

int main(int argc, char *argv[]) 
{ 
    if(argc!=3) 
	{ 
		cout <<"Usage:\n\t huffmancoding inputfile outputfile"<<endl; 
		//exit(1);
		char path[50]="1.txt"; //文件的讀路徑 
		cout<<"請輸入要壓縮的文件地址：（需擴展名）"<<endl; 
		//gets(path); 
		argv[1] = path;
		
		char path2[50]="5.txt"; //文件的讀路徑
		cout<<"請輸入要存放的文件地址：（需擴展名）"<<endl; 
		//gets(path2); 
		argv[2] = path2;
	} 

    huffman h(argv[1], argv[2]); 

    h.create_pq(); 

    h.create_huffman_tree(); 

   h.calculate_huffman_codes(); 

    h.save_to_file(); 

    cout << endl; 

    return 0; 
}