// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import (
	"container/heap"
	"fmt"
)

// 霍夫曼树接口
type HuffmanTree interface {
	Freq() int
}

// 霍夫曼树子节点
type HuffmanLeaf struct {
	freq  int
	value rune
}

func (huffman HuffmanLeaf) Freq() int {
	return huffman.freq
}

// 霍夫曼节点
type HuffmanNode struct {
	freq        int
	left, right HuffmanTree
}

func (huffman HuffmanNode) Freq() int {
	return huffman.freq
}

// 最小堆
// 这是霍夫曼树最小堆的自定义实现。它是霍夫曼树切片的类型定义。
type minHeap []HuffmanTree

// 下面三个函数实现了Go中 heap 包所需要的接口
// 这使得minHeap类型可以与Go提供的内置堆函数一起使用。Len函数返回堆中元素的数量
func (th minHeap) Len() int { return len(th) }

// Less 函数用于比较堆中的两个元素并确定哪个更小。 在这里，它比较了两个 HuffmanTrees 的频率
// 如果第1棵树的频率小于第2棵树的频率，则返回真，表示第1棵树“小于”第2棵树
func (th minHeap) Less(i, j int) bool {
	return th[i].Freq() < th[j].Freq()
}

// Push 函数用于向堆中添加新元素。它采用 interface{} 类型
// 然后将其类型断言为 HuffmanTree 类型并附加到切片
func (th *minHeap) Push(ele interface{}) {
	*th = append(*th, ele.(HuffmanTree))
}

// Pop 函数用于从堆中移除最小的元素。它返回最小的元素（弹出）并将其从切片中移除
func (th *minHeap) Pop() (popped interface{}) {
	popped = (*th)[len(*th)-1]
	*th = (*th)[:len(*th)-1]
	return
}

// Swap 函数用于交换两个元素在堆中的位置。它获取两个元素的索引并在切片中交换它们
func (th minHeap) Swap(i, j int) { th[i], th[j] = th[j], th[i] }

// 构建哈夫曼树并遍历打印代码的main()函数，构建的霍夫曼树
func buildTree(symFreqs map[rune]int) HuffmanTree {
	var trees minHeap
	for c, f := range symFreqs {
		trees = append(trees, HuffmanLeaf{f, c})
	}
	heap.Init(&trees)
	for trees.Len() > 1 {
		// 频率最低的两棵树
		a := heap.Pop(&trees).(HuffmanTree)
		b := heap.Pop(&trees).(HuffmanTree)

		// 放入新节点并重新插入队列
		heap.Push(&trees, HuffmanNode{a.Freq() + b.Freq(), a, b})
	}
	return heap.Pop(&trees).(HuffmanTree)
}

// 从霍夫曼树的根部打印霍夫曼代码。 它使用 byte[] 来存储代码
func printCodes(tree HuffmanTree, prefix []byte) {
	switch i := tree.(type) {
	case HuffmanLeaf:
		// 如果这是一个叶节点，那么它包含一个输入字符，从 byte[] 打印字符及其代码
		fmt.Printf("%c\t%d\t%s\n", i.value, i.freq, string(prefix))
	case HuffmanNode:
		// 将 0 分配给左边缘并重复出现
		prefix = append(prefix, '0')
		printCodes(i.left, prefix)
		prefix = prefix[:len(prefix)-1]

		// 将 1 赋值给右边缘并重复出现
		prefix = append(prefix, '1')
		printCodes(i.right, prefix)
		prefix = prefix[:len(prefix)-1]
	}
}

func main() {
	test := "abcdefghijklmnopqrstuvwxyz"

	symFreqs := make(map[rune]int)
	// 读取每个符号并记录频率
	for _, c := range test {
		symFreqs[c]++
	}

	// 示例树
	exampleTree := buildTree(symFreqs)

	// 打印结果
	fmt.Println("符号霍夫曼码\t权重\t霍夫曼编码")
	printCodes(exampleTree, []byte{})
}

//$ go run huffmanCode.go
//符号霍夫曼码    权重    霍夫曼编码
//d       1       0000
//v       1       0001
//w       1       0010
//s       1       0011
//p       1       0100
//x       1       0101
//n       1       01100
//y       1       01101
//u       1       01110
//f       1       01111
//b       1       10000
//q       1       10001
//z       1       10010
//l       1       10011
//a       1       10100
//r       1       10101
//k       1       10110
//i       1       10111
//j       1       11000
//t       1       11001
//m       1       11010
//c       1       11011
//g       1       11100
//h       1       11101
//e       1       11110
//o       1       11111