#include <fstream>
#include <string>
#include <iostream>
#include <iomanip>

using namespace std;

const int MAXLEN = 20;
const int MAXNUM = 10000;

class node
{
private:
	char cha;
	int weight;
	node *parent;
	node *lchild, *rchild;
	bool intree;
	node *pre, *next;
	bool cflag;
	char code[MAXLEN];
public:
	node(int w=0, char ch='\0')
	{
		weight = w;
		cha = ch;
		parent = lchild = rchild = NULL;
		intree = false;
		pre = next = NULL;
		cflag = false;
		code[0]='\0';
	}
	~node(){}
	friend class tree;
};


class tree
{
private:
	node *headleaf;
	node *headnoleaf;
public:
	tree();
	~tree();
	int code(char *filename);
	void show();
	int coding(char *filein, char *fileout);
	int encoding(char *filein, char *fileout);
};

tree::tree()
{
	headleaf = new node(MAXNUM);
	headleaf->pre = headleaf;
	headleaf->next =  headleaf;

	headnoleaf = new node(MAXNUM);
	headnoleaf->pre = headnoleaf;
	headnoleaf->next =  headnoleaf;
}

tree::~tree()
{
	node *i, *ndelete;

	for(i=headleaf->next;i!=headleaf;)
	{
		i->pre->next = i->next;
		i->next->pre = i->pre;
		ndelete = i;
		i = i->next;
		delete ndelete;
	}
	delete headleaf;

	for(i=headnoleaf->next;i!=headnoleaf;)
	{
		i->pre->next = i->next;
		i->next->pre = i->pre;
		ndelete = i;
		i = i->next;
		delete ndelete;
	}
	delete headnoleaf;
}

int tree::code(char *filename)
{
	ifstream fin(filename);
	if(!fin)
    {
        cout << "Cannot open input file "<<filename<<"." << endl;
        return 1;
    }

	node *newnode;
	node *i;
	char ch;

	while(!fin.eof())
	{
		fin>>ch;
		//search(ch)
		for(i=headleaf->next;i!=headleaf;i=i->next)
		{
			if(i->cha==ch)
			{
				i->weight++;
				break;
			}
		}

		if(i==headleaf)
		{
			newnode = new node(1,ch);
			headleaf->pre->next = newnode;
			newnode->pre = headleaf->pre;
			headleaf->pre = newnode;
			newnode->next = headleaf;
		}
		fin.get(ch);
		fin.seekg(-1,ios::cur);	
	}
	fin.close(); //構造葉子節點的雙向鏈表

	//1最小，2次之
	node *node1, *node2;

	while(1)
	{
		node1 = headleaf;
		node2 = headleaf;
		for(i=headleaf->next;i!=headleaf;i=i->next)
		{
			if(!(i->intree)&&i->weight<node2->weight)
			{
				if(i->weight<node1->weight)
				{
					node2 = node1;
					node1 = i;
				}
				else 
					node2 = i;
			}
		}
		for(i=headnoleaf->next;i!=headnoleaf;i=i->next)
		{
			if(!(i->intree)&&i->weight<node2->weight)
			{
				if(i->weight<node1->weight)
				{
					node2 = node1;
					node1 = i;
				}
				else
					node2 = i;
			}
		}//找到weight最小的兩個節點

		if(node2==headleaf)
			break;

		newnode = new node(node1->weight+node2->weight);
		newnode->lchild = node1;
		newnode->rchild = node2;
		node1->parent = newnode;
		node2->parent = newnode;
		node1->intree = true;
		node2->intree = true;//將兩個最小節點插到樹結構中

		newnode->next = headnoleaf;
		newnode->pre = headnoleaf->pre;
		headnoleaf->pre->next = newnode;
		headnoleaf->pre = newnode;//將非葉子節點插到非葉子節點的鏈表中去
	}//構造huffman樹

	if(headnoleaf->pre!=headnoleaf)
		i = headnoleaf->pre;
	else	//針對只有一個元素的特殊情況
	{
		i = headleaf->next;
		i->code[0] = '1';
		i->code[1] = '\0';
		i->cflag = true;
		return 0;
	}

	i->cflag = true;
	int i_code;

	while(1)
	{
		for(;i->lchild;i=i->lchild)
		{
			for(i_code=0;i->code[i_code]!='\0';i_code++)
				i->lchild->code[i_code] = i->code[i_code];
			i->lchild->code[i_code++] = '1';
			i->lchild->code[i_code] = '\0';
			i->lchild->cflag = true;
		}
		while(1)
		{
			i = i->parent;
			if(!i)
				return 0;
			if(i->rchild&&!(i->rchild->cflag))
			{
				for(i_code=0;i->code[i_code]!='\0';i_code++)
					i->rchild->code[i_code] = i->code[i_code];
				i->rchild->code[i_code++] = '0';
				i->rchild->code[i_code] = '\0';
				i->rchild->cflag = true;
				i = i->rchild;
				break;
			}
		}
	}//對已經構造好的huffman樹的各個位置進行編碼，左為1右為0

	return 0;
}


void tree::show()
{
	node *i;

	for(i=headleaf->next;i!=headleaf;i=i->next)
		cout<<i->cha<<"("<<i->weight<<"):"<<i->code<<endl;

	return;
}

int tree::coding(char *filein, char *fileout)
{
	ifstream fin(filein);
	if(!fin)
    {
        cout << "Cannot open input file "<<filein<<"." << endl;
        return 1;
    }
	ofstream fout(fileout);
	if(!fout)
    {
        cout << "Cannot open output file "<<fileout<<"." << endl;
        return 1;
    }

	node *i;
	char ch;
	while(!fin.eof())
	{
		fin>>ch;
		//search(ch)
		for(i=headleaf->next;i!=headleaf;i=i->next)
		{
			if(i->cha==ch)
			{
				fout<<i->code;
				break;
			}
		}
		fin>>ch;
		fin.seekg(-1,ios::cur);
	}
	fin.close();
	fout.close();

	return 0;
}

int tree::encoding(char *filein, char *fileout)
{
	ifstream fin(filein);
	if(!fin)
    {
        cout << "Cannot open input file "<<filein<<"." << endl;
        return 1;
    }
	ofstream fout(fileout);
	if(!fout)
    {
        cout << "Cannot open output file "<<fileout<<"." << endl;
        return 1;
    }

	node *i;
	char ch;
	char incode[MAXLEN]="";
	int i_incode;


	while(!fin.eof())
	{
		fin>>ch;
		
		for(i_incode=0;incode[i_incode]!='\0';i_incode++);
		incode[i_incode++] = ch;
		incode[i_incode] = '\0';

		//search(code)
		for(i=headleaf->next;i!=headleaf;i=i->next)
		{
			//issame(i->code,incode)
			for(i_incode=0;incode[i_incode]!='\0'&&i->code[i_incode]!='\0';i_incode++)
				if(incode[i_incode]!=i->code[i_incode])
					break;
			if(incode[i_incode]=='\0'&&i->code[i_incode]=='\0')
			{
				fout<<i->cha;
				incode[0]='\0';
				break;
			}
		}
		fin.get(ch);
		fin.seekg(-1,ios::cur);
	}
	fin.close();
	fout.close();

	return 0;

}

int main()
{
	tree file1;
	file1.code("file1.txt");
	file1.coding("file1.txt","file1_1.txt");
	file1.encoding("file1_1.txt","file1_2.txt");
	file1.show();
	return 0;
}