#pragma once

#include <iostream>
#include <queue>
#include <unordered_map>

//unordered_map 与 map 的区别
//unordered_map：
//
//	底层是哈希表，键值对是无序的。
//	平均情况下，查找、插入、删除的时间复杂度为 O(1)。
//	需要依赖一个好的哈希函数，否则在发生大量冲突时性能会变差。
//map：
//
//	底层是红黑树（自平衡二叉搜索树），键值对是有序的（根据键进行排序）。
//	查找、插入、删除的时间复杂度为 O(log n)。

using namespace std;

namespace huffman_tree
{
	template <class TKey, class TWeight>
	struct HuffmanTreeNode
	{
		TKey key;						// 关键字
		TWeight weight;					// 权值
		HuffmanTreeNode* left_child;	// 左孩子
		HuffmanTreeNode* right_child;	// 右孩子
		HuffmanTreeNode* parent;		// 父节点

		HuffmanTreeNode()
			:key(TKey()), weight(TWeight()), left_child(NULL), right_child(NULL), parent(NULL) {}

		HuffmanTreeNode(TKey key, TWeight weight, HuffmanTreeNode* left = NULL, HuffmanTreeNode* right = NULL, HuffmanTreeNode* parent = NULL)
			:key(key), weight(weight), left_child(left), right_child(right), parent(parent) {}
	};

	template <class TKey, class TWeight>
	struct Compare
	{
		// 重载运算符“()”
		bool operator()(HuffmanTreeNode<TKey, TWeight>* node1, HuffmanTreeNode<TKey, TWeight>* node2)
		{
			return node1->weight > node2->weight;
		}
	};
}

template <class TKey,class TWeight>
class HuffmanTree
{
private:
	// 根结点
	huffman_tree::HuffmanTreeNode<TKey, TWeight>* root_;

	// 子树清空（递归）
	void clearSubTreeRecursive_(huffman_tree::HuffmanTreeNode<TKey,TWeight>* subtree_root);

	// 合并子树
	// 注意，如果只需要修改指针指向那片内存的内容，那么传入指针变量即可（当然也可以直接传入指针的指针或者指针的引用，但是没必要）；但是如何要修改指针的指向（修改指针变量的内容），那么此时就应该传入指针的指针（c语言）或者指针的引用（c++）
	void mergeSubTree_(huffman_tree::HuffmanTreeNode<TKey, TWeight>* subtree_root1,
						huffman_tree::HuffmanTreeNode<TKey, TWeight>* subtree_root2,
						huffman_tree::HuffmanTreeNode<TKey, TWeight>*& new_subtree_root);

	//打印子树（递归）
	void printSubTreeRecursive_(huffman_tree::HuffmanTreeNode<TKey,TWeight>* subtree_root);

	// 子树生成哈夫曼编码
	void generateHuffmanCodeOfSubTreeRecursive_(huffman_tree::HuffmanTreeNode<TKey,TWeight>* node,
												const string& current_prefix_code,
												unordered_map<TKey,string>& huffman_codes);
public:

	// 构造函数
	// 这里要注意的是：1、数组名在定义的时候，指代的就是这个完整的数组，2、而当数组名作为参数传入函数的时候，只是一个指针变量，用来记录数组的首地址。所以这里需要显式的传入数组长度而不可以在数组内使用sizeof计算出数组长度
	HuffmanTree(const TKey keys[], const TWeight weights[], int count);

	// 析构函数
	~HuffmanTree()
	{
		this->clearSubTreeRecursive_(this->root_);
		this->root_ = NULL;
	}

	// 生成哈夫曼编码
	unordered_map<TKey, string> generateHuffmanCodes();

	// 打印
	void printTree() { this->printSubTreeRecursive_(this->root_); cout << endl; }

};

template<class TKey, class TWeight>
inline void HuffmanTree<TKey, TWeight>::clearSubTreeRecursive_(huffman_tree::HuffmanTreeNode<TKey, TWeight>* subtree_root)
{
	// 空树处理
	if (!subtree_root)
		return;

	// 递归
	this->clearSubTreeRecursive_(subtree_root->left_child);
	this->clearSubTreeRecursive_(subtree_root->right_child);

	// 释放根结点
	delete subtree_root;
	subtree_root = NULL;
}

template<class TKey, class TWeight>
inline void HuffmanTree<TKey, TWeight>::mergeSubTree_(huffman_tree::HuffmanTreeNode<TKey, TWeight>* subtree_root1, huffman_tree::HuffmanTreeNode<TKey, TWeight>* subtree_root2, huffman_tree::HuffmanTreeNode<TKey, TWeight>* & new_subtree_root)
{
	// 构造新子树根结点
	TKey key = (TKey)'*';
	new_subtree_root = new huffman_tree::HuffmanTreeNode<TKey, TWeight>(key,subtree_root1->weight + subtree_root2->weight,subtree_root1,subtree_root2,NULL);

	// 两个子树根结点的parent指向新子树根结点
	subtree_root1->parent = new_subtree_root;
	subtree_root2->parent = new_subtree_root;
}

template<class TKey, class TWeight>
inline void HuffmanTree<TKey, TWeight>::printSubTreeRecursive_(huffman_tree::HuffmanTreeNode<TKey, TWeight>* subtree_root)
{
	// 空树处理
	if (!subtree_root)
		return;

	// 递归
	cout << subtree_root->key; // 打印根结点
	cout << "(";
	this->printSubTreeRecursive_(subtree_root->left_child); // 递归调用打印左子树
	cout << ",";
	this->printSubTreeRecursive_(subtree_root->right_child); // 递归调用打印右子树
	cout << ")";
}

template<class TKey, class TWeight>
inline void HuffmanTree<TKey, TWeight>::generateHuffmanCodeOfSubTreeRecursive_(huffman_tree::HuffmanTreeNode<TKey, TWeight>* node, const string& current_prefix_code, unordered_map<TKey, string>& huffman_codes)
{
	// 空结点处理
	if (!node)
		return;

	// 叶子节点处理，哈夫曼树需要编码的结点一定是叶子节点
	if (node->left_child == NULL && node->right_child == NULL)
	{
		huffman_codes[node->key] = current_prefix_code;
		return;
	}

	// 非叶子结点处理
	// 左侧树枝为“0”
	//string str_zero("0");
	//this->generateHuffmanCodeOfSubTreeRecursive_(node->left_child, current_prefix_code + str_zero,huffman_codes);
	this->generateHuffmanCodeOfSubTreeRecursive_(node->left_child, current_prefix_code + "0", huffman_codes);

	// 右侧树枝为“1”
	string str_one("1");
	this->generateHuffmanCodeOfSubTreeRecursive_(node->right_child, current_prefix_code + str_one, huffman_codes);
}

template<class TKey, class TWeight>
inline HuffmanTree<TKey, TWeight>::HuffmanTree(const TKey keys[], const TWeight weights[], int count)
{
	// 初始化最小优先队列

	// 使用最小堆，小根堆的第一个元素是权值最小的结点
	priority_queue<huffman_tree::HuffmanTreeNode<TKey, TWeight>*, vector<huffman_tree::HuffmanTreeNode<TKey, TWeight>*>, huffman_tree::Compare<TKey, TWeight>> min_priority_queue;

	for (int i = 0; i < count; i++)
	{
		huffman_tree::HuffmanTreeNode<TKey, TWeight>* node = new huffman_tree::HuffmanTreeNode<TKey, TWeight>(keys[i],weights[i],NULL,NULL,NULL);
		min_priority_queue.push(node);
	}

	// 使用最小优先队列构造哈夫曼树

	// 合并后形成的新子树的树根
	huffman_tree::HuffmanTreeNode<TKey, TWeight>* cur_parent = NULL;
	for (int i = 0; i < count - 1; i++)
	{
		// 取出小根堆（最小优先队列）的第一个元素
		huffman_tree::HuffmanTreeNode<TKey, TWeight>* first = min_priority_queue.top();
		min_priority_queue.pop();

		// 取出小根堆（最小优先队列）的第一个元素
		huffman_tree::HuffmanTreeNode<TKey, TWeight>* second = min_priority_queue.top();
		min_priority_queue.pop();

		this->mergeSubTree_(first,second,cur_parent);
		min_priority_queue.push(cur_parent);
	}

	this->root_ = cur_parent;
}

template<class TKey, class TWeight>
inline unordered_map<TKey, string> HuffmanTree<TKey, TWeight>::generateHuffmanCodes()
{
	unordered_map<TKey, string> huffman_codes;

	string current_prefix_code;

	// 调用generateHuffmanCodeOfSubTreeRecursive_，生成哈夫曼编码
	this->generateHuffmanCodeOfSubTreeRecursive_(this->root_,current_prefix_code,huffman_codes);

	return huffman_codes;
}