// ++++++++++++++++++++++++++++++++++++++++
// 《零基础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 (
	"fmt"
	"sort"
	"strconv"
)

// 存储在节点中的值的类型
type ValueType int32

// 哈夫曼树中的节点
type Node struct {
	Parent *Node // 可选的父节点，用于快速读出代码
	Left   *Node // 可选左节点
	Right  *Node // 可选右节点
	Count  int   // 相对频率
	Value  ValueType
}

// 代码返回节点的霍夫曼代码
// 左子树得到位 0，右子树得到位 1。
// 实现使用 Node.Parent 在树中“向上”移动。
func (n *Node) Code() (r uint64, bits byte) {
	for parent := n.Parent; parent != nil; n, parent = parent, parent.Parent {
		if parent.Right == n { // 位 1
			r |= 1 << bits
		} // 否则位 0 与 r 无关
		bits++
	}
	return
}

// SortNodes 实现了 sort.Interface，顺序由 Node.Count 定义
type SortNodes []*Node

func (sn SortNodes) Len() int           { return len(sn) }
func (sn SortNodes) Less(i, j int) bool { return sn[i].Count < sn[j].Count }
func (sn SortNodes) Swap(i, j int)      { sn[i], sn[j] = sn[j], sn[i] }

// 从指定的叶子构建霍夫曼树
func Build(leaves []*Node) *Node {
	//排序一次，稍后使用二进制插入
	sort.Stable(SortNodes(leaves)) // 注意：确定性输出的稳定排序

	return BuildSorted(leaves)
}

// 从必须按 Node.Count 排序的指定叶子构建霍夫曼树
func BuildSorted(leaves []*Node) *Node {
	if len(leaves) == 0 {
		return nil
	}

	for len(leaves) > 1 {
		left, right := leaves[0], leaves[1]
		parentCount := left.Count + right.Count
		parent := &Node{Left: left, Right: right, Count: parentCount}
		left.Parent = parent
		right.Parent = parent

		ls := leaves[2:]
		idx := sort.Search(len(ls), func(i int) bool { return ls[i].Count >= parentCount })
		idx += 2

		copy(leaves[1:], leaves[2:idx])
		leaves[idx-1] = parent
		leaves = leaves[1:]
	}

	return leaves[0]
}

// 遍历霍夫曼树并以二进制表示形式打印值及其代码
func Print(root *Node) {
	// traverse 从给定节点遍历子树，
	// 使用指向此节点的前缀代码，具有指定的位数
	var traverse func(n *Node, code uint64, bits byte)

	traverse = func(n *Node, code uint64, bits byte) {
		if n.Left == nil {
			fmt.Printf("'%c': %0"+strconv.Itoa(int(bits))+"b\n", n.Value, code)
			return
		}
		bits++
		traverse(n.Left, code<<1, bits)
		traverse(n.Right, code<<1+1, bits)
	}

	traverse(root, 0, 0)
}

func main() {
	leaves := []*Node{
		{Value: ' ', Count: 20},
		{Value: 'a', Count: 40},
		{Value: 'm', Count: 10},
		{Value: 'l', Count: 7},
		{Value: 'f', Count: 8},
		{Value: 't', Count: 15},
	}
	root := Build(leaves)
	Print(root)
}

//$ go run interview8-4.go
//'a': 0
//'m': 100
//'l': 1010
//'f': 1011
//'t': 110
//' ': 111