/*
	Author: Az1r 
	Date: 2022/10/14
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <limits>
#include <queue>
#include <map>
#include <fstream>
#include <iomanip>


#define MAX_LENTH 100

using namespace std;

// 哈夫曼樹
struct TreeNode{
	int weight;
	char ch;

	TreeNode* left;
	TreeNode* right;
};
typedef TreeNode* Huff;

// 小根堆
struct HeapNode{
	Huff* data;
	int size;// 堆的大小 
	int cap; //容量 
};
typedef HeapNode* Heap;
Huff T = NULL;

//編碼表 
const int N = 128;
int cnt[N];
map<int, string> mp;

Huff CreateNode(char ch, int weight);	//建立一個哈夫曼樹的節點 
Heap CreateHeap();						//建立一個小根堆 
void InitHeap(Heap H);					//初始化堆 
void SetHeap(Heap H, int p);			//向下調整堆 
bool IsFull(Heap H);					//判滿 
bool IsEmpty(Heap H);					//判空 
bool InsertHeap(Heap H,Huff tree);		//向堆中插入插入 
Huff Pop(Heap H);						//彈出堆中根節點 
void LoadTreeByInput();					//通過輸入初始化哈夫曼樹 
Huff BuildHuffmanTree(Heap H);			//建立哈夫曼樹 
void PrintTree(Huff tree);				//列印哈夫曼樹 
void Menu();							//列印選單 
void CreateDict(Huff tree, string temp);//建立哈夫曼編碼表 
void PrintCode();						//列印編碼表 
void LoadTreeByFile();					//檔案輸入哈夫曼樹 
void CodeFile();						//編碼文字檔案 
void Caulcute();						//計算壓縮率 
void DecodeFile(Huff tree);				//解碼文字檔案 

/* 
	test.txt 		英文文字測試檔案 
	test_Copy.txt 	英文文字解碼檔案
	code.txt		哈夫曼編碼檔案
	huffman.txt		哈夫曼樹的結構檔案 	
*/ 
int main()
{
	int select = -1;
	while(select)
	{
		system("pause");
		system("cls");
		Menu();
		printf("input your choose: ");
		scanf("%d", &select);
		
		switch(select)
		{
			case 1:
			{
				PrintTree(T);
				break;
			}
			case 2:
			{
				DecodeFile(T);
				break;
			}	
			case 3:
			{
				CodeFile();
				break;
			}
			case 4:
			{
				PrintCode();
			}
			case 5:
			{
				Caulcute();
				break;
			}
			case 0:
			{
				break;
			}
			default:
			{
				break;
			}		 
		}
	}
	return 0;
}

void Menu()
{
	printf("----         Menu         ----");	printf("\n");
	printf("----    1.PrintTree  	  ----");	printf("\n");
	printf("----    2.Decode          ----");	printf("\n");
	printf("----    3.Code            ----");	printf("\n");
	printf("----    4.PrintDictCode   ----");	printf("\n");
	printf("----    5.Caulcute        ----");	printf("\n");
	printf("----    0.Exit            ----");	printf("\n");

}
void Caulcute()
{
	int chTotal = 0;
	int hfmTotal = 0;
	for(int i = 0; i < N; i ++ )
	{
		chTotal += cnt[i];
		hfmTotal += cnt[i] * mp[i].length();
	}
	
	double rate = hfmTotal * 1.0 / ( 8 * chTotal ) * 100; //1個字元佔8位元 
	cout << "Code rate: " << rate << "%" << "\n"; 
}
void DecodeFile(Huff tree)
{
	ifstream infile;
	infile.open("code.txt");
	
	ofstream outfile;
	outfile.open("test_Copy.txt");
	
	if(infile == NULL || outfile == NULL)
	{
		printf("File open error!\n");
		return;
	}
	
	char temp;
	Huff x = tree;
	
	while(!infile.eof())
	{
		infile >> temp;
		if(infile.fail())//防止讀到最後一個字元 
		{
			break;
		}
		if(temp == '0') // 左為 0，右為 1 
		{
			x = x->left;
		}else
		{
			x = x->right;
		}
			
		if(x->left == NULL && x->right == NULL) // 左右兒子都無，那就是葉子節點，即儲存字元的節點 
		{
			outfile << x->ch;
			x = tree;
		}
	}
	
	infile.close();
	outfile.close();
	printf("Succeeful decode file!");
}
void CodeFile()
{
	for(int i = 0; i < N; i ++ )
	{
		cnt[i] = 0;
	}
	ifstream infile;
	infile.open("test.txt");
	
	infile >> noskipws; //  控制符，可以讀取空格回車 
	
	char ch;
	while(!infile.eof())
	{
		infile >> ch;
		
		if(infile.fail())//防止讀到最後一個字元 
		{
			break;
		}
		cnt[(int)ch] ++;
	}
	infile.close();
	
	ofstream outfile;
	outfile.open("huffman.txt");
	
	for(int i = 0; i < N; i ++ )
	{
		if(cnt[i])
		{
			ch = i;
			outfile << ch << cnt[i] << "\n"; //輸出到哈夫曼樹結構檔案中 
		}
	}
	outfile.close();
	
	LoadTreeByFile();
	CreateDict(T, "");
	
	infile.open("test.txt");
	infile >> noskipws;
	outfile.open("code.txt");
	while(!infile.eof())
	{
		infile >> ch;
		if(infile.fail())//防止讀到最後一個字元 
		{
			break;
		}
		outfile << mp[(int)ch];
	}
	
	infile.close();
	outfile.close();
	
	printf("Succeeful code file!");
}
void PrintCode()
{
	int total = 0;
	for(int i = 0; i < N; i ++ )
	{
		total += cnt[i];
	}
	for(int i = 0; i < N; i ++ )  // 輸出字元,頻率,編碼 
	{
	
		if(cnt[i])
		{
			float f = cnt[i] * 1.0 / total;
			if(i == 10)
			{
				cout << setw(3) << i << "---- " << "\\n" << "      ---- " << fixed << setprecision(3) << f << "  " << mp[i] << "\n" ; 
			}else if (i == 32)
			{
				cout << setw(3) << i << "---- " << "<space>" << " ---- " << fixed << setprecision(3) << f << "  " << mp[i] << "\n" ; 
			}else
			{
				cout << setw(3)  << i << "---- " << (char)i << "       ---- " << fixed << setprecision(3) << f << "  " << mp[i] << "\n" ; 
			}
		}
	}
}
void CreateDict(Huff tree, string temp)
{
	if(tree)
	{
		if(tree->left == NULL && tree->right == NULL)
		{
			int idx = tree->ch;
			mp[idx] = temp;
		}else
		{
			CreateDict(tree->left, temp + "0");//左 0 
			CreateDict(tree->right, temp + "1");//右 1 
		}
	}
}


Huff CreateNode(char ch, int weight)
{
	Huff Node = (Huff)malloc(sizeof (TreeNode));

	Node->ch = ch;
	Node->weight = weight;
	Node->left = Node->right = NULL;
	return Node;
}
// 堆的構建
Heap CreateHeap()
{
	Heap Node = (Heap)malloc(sizeof (HeapNode));
	
	Node->data = (Huff *)malloc((MAX_LENTH + 1) * sizeof (Huff));
	Node->size = 0;
	Node->cap = MAX_LENTH;
	Node->data[0] = CreateNode('\0',INT_MIN);

	return Node;
}

// 堆的向下調整
void SetHeap(Heap H, int p)
{
	int parent, child;
	int lenth = H->size;

	Huff root = H->data[p];

	for(parent = p; parent * 2 <= lenth; parent = child)
	{
		// 將Child指向Parent的左右子節點中最小者 
		child = parent * 2;
		if((child < lenth) && H->data[child]->weight > H->data[child + 1]->weight){
			child++;
		}
		// 如果child的權重不再小於parent,調整完畢,否則繼續進行調整
		if(root->weight <= H->data[child]->weight)
		{
			break;
		}else
		{
			H->data[parent] = H->data[child];
		}
	}
	H->data[parent] = root;

}
// 初始化最小堆
void InitHeap(Heap H)
{
	// 從最後一個節點的父節點開始,一直到根節點1 (0是哨兵節點) 
	for(int i = H->size / 2; i > 0; i --)
	{	
		SetHeap(H,i);
	}
}
// 判空，判滿
bool IsFull(Heap H)
{
	return (H->size == H->cap);
}
bool IsEmpty(Heap H)
{
	return (H->size == 0);
}

// 插入堆的操作
bool InsertHeap(Heap H,Huff tree)
{
	if(IsFull(H))
	{
		printf("Full Heap!\n");
		return false; 
	}

	H->size ++;
	int i= H->size;
	// i為最後一個位置，然後一層一層向上過濾 
	for(; H->data[i / 2]->weight > tree->weight; i /= 2)
	{
		H->data[i] = H->data[i / 2];
	}
	H->data[i] = tree;

	return true;
}
// 從堆中取出最小元素的實現
Huff Pop(Heap H)
{
	if(IsEmpty(H))
	{
		printf("Empty Heap!\n");
		return NULL;
	}
	int parent,child;
	int lenth = H->size;
	// 取出根節點
	Huff rootTree = H->data[1];
	// xTree為最後一個元素，同時size-1（因為取出了根節點） 
	Huff xTree = H->data[H->size --];
	// 從根節點下面找出最小的替換上來
	for(parent = 1;parent * 2 <= lenth; parent = child)
	{
		child = parent * 2;
		if((child < lenth) && (H->data[child]->weight > H->data[child+1]->weight))
		{
			child ++;
		}
		if(xTree->weight <= H->data[child]->weight)
		{
			break;
		}else
		{
			H->data[parent] = H->data[child];
		}
	}
	H->data[parent] = xTree;

	return rootTree;
}

// 哈夫曼樹的構造
Huff BuildHuffmanTree(Heap H)
{
	// 假設已經無序的將節點儲存在堆的data中,
	// 首先要將堆調整為最小堆
	Huff tree;
	InitHeap(H);
	int size = H->size;
	for(int i = 1;i < size; i ++)
	{
		tree = (Huff)malloc(sizeof (TreeNode));
		// 取出兩個最小節點，作為這個節點的左右分支
		tree->ch = '\0';
		tree->left = Pop(H);
		tree->right = Pop(H);
		// 計算新的權值
		tree->weight = tree->left->weight + tree->right->weight;
		// 將這個節點再插入最小堆
		InsertHeap(H,tree); 
		
		/* test
		
		*/
	}
	// 取出哈夫曼樹根節點(也就是堆頂節點)
	tree = Pop(H);
	return tree; 
}
// 先序遍歷哈夫曼樹
void PrintTree(Huff tree)
{
	if(tree)
	{
		if((tree->left == NULL) && (tree->right == NULL))
		{
			char ch = tree->ch;
			if(ch == '\n')
			{
				cout << "Leaf  " << setw(3) << tree->weight << " ---- " << "\\n" << "\n" ; 
			}else if(ch == ' ')
			{
				cout << "Leaf  " << setw(3) << tree->weight << " ---- " << "<space>" << "\n" ; 
			}else
			{
				cout << "Leaf  " << setw(3) << tree->weight << " ---- " << ch << "\n" ; 
			}
		}else
		{
			cout << "Node  " << setw(3) << tree->weight << "\n" ; 
		}
		PrintTree(tree->left);
		PrintTree(tree->right); 
	}
}
void LoadTreeByFile()
{
	ifstream infile;
	infile.open("huffman.txt");
	if(infile == NULL)
	{
		printf("load file error!\n");
		return; 
	}
	int weight;
	char ch;
	char temp[20];
	
	Heap heap = CreateHeap();
	
	infile >> noskipws; //  控制符，可以讀取空格回車 
	while(!infile.eof())
	{
		infile >> ch;
		infile.getline(temp, 20);
		weight = atoi(temp);
		
		heap->data[++ heap->size] = CreateNode(ch, weight);
	}
	infile.close();
   	T = BuildHuffmanTree(heap);
}
// 哈夫曼樹從使用者輸入
void LoadTreeByInput()
{
	printf("please input your haffman:\n");
	int weight,count;
	char ch;
	char temp[10];

	Heap heap = CreateHeap();
	printf("input data num :");
	scanf("%d", &count); 
	cout << "( data+weight ):" <<endl; 
	for(int i = 1;i <= count; i ++)
	{
		scanf("%s", temp);
		ch = temp[0];
		weight = atoi(temp + 1);
		
		cnt[(int)ch] = weight;
		
		heap->data[i] = CreateNode(ch, weight);
		heap->size ++;
	}
	T = BuildHuffmanTree(heap);
}