//哈夫曼编码的实现，还未经过测试，只写了实现思路，后续还会改进优化
// Package huffman 构造哈夫曼树和哈夫曼编码
package huffman

// HuffmanTreeNode 哈夫曼树结点
type HuffmanTreeNode struct {
	Data rune  //结点数据域
	Weight int //结点权重
	Parent int //父结点索引
	LeftChild int //左子树根节点索引
	RightChild int //右子树根结点索引
}

// HuffmanCodes 用来存储哈夫曼编码表

var HuffmanCodes map[rune]int

// HuffmanTreeCoding 进行哈夫曼编码
func HuffmanTreeCoding(
	huffmanTree []HuffmanTreeNode, //哈夫曼树
	huffmanCodes map[rune][]byte, //用于存放哈夫曼编码表
	//用于存储n个结点的权重
	weight []int){
	if len(weight)<=1{
		return
	}

	huffmanTreeLength:=2*(len(weight))-1
	huffmanTree=make([]HuffmanTreeNode,huffmanTreeLength)

	for i := 0; i < len(weight); i++ {
		huffmanTree[i].Weight=weight[i]
	}

	for i := len(weight); i < huffmanTreeLength; i++ {
		huffmanTree[i].Weight=weight[i]
	}

	//构建哈夫曼树
	for i := len(weight); i < huffmanTreeLength; i++ {
		min,secondaryMin:=Select(huffmanTree,i-1)
		huffmanTree[min].Parent=i
		huffmanTree[secondaryMin].Parent=i
		huffmanTree[i].LeftChild=min
		huffmanTree[i].RightChild=secondaryMin
		huffmanTree[i].Weight=huffmanTree[min].Weight+huffmanTree[secondaryMin].Weight
	}


	for i := 0; i < len(weight); i++ {

		j:=i
		parent:=huffmanTree[j].Parent
		for {

			//这里每个字符串对应的哈夫曼编码存储在一个切片中，且为倒序存储，取用编码的时候需要倒着取
			if parent==0{
				break
			}
			if huffmanTree[parent].LeftChild==i {
				huffmanCodes[huffmanTree[i].Data] = append(huffmanCodes[huffmanTree[i].Data], '0')
			}else {
				huffmanCodes[huffmanTree[i].Data] = append(huffmanCodes[huffmanTree[i].Data], '1')
			}
			j=parent
			parent=huffmanTree[parent].Parent
		}
	}

}

// Select 从切片组成的哈夫曼树中，从huffmanTree[0...bound]中选出权重最小的两个结点，返回对应的结点
func Select(huffmanTree []HuffmanTreeNode,bound int) (min int,secondaryMin int) {
	min=0
	for i := 0; i < bound; i++ {
		if huffmanTree[i].Weight<huffmanTree[min].Weight{
			min=i
		}
	}
	secondaryMin=1
	for i := 0; i < bound; i++ {
		if huffmanTree[i].Weight<huffmanTree[secondaryMin].Weight &&i!=min{
			secondaryMin=i
		}
	}

	return min,secondaryMin

}

``