-
Notifications
You must be signed in to change notification settings - Fork 90
/
huffman.go
136 lines (108 loc) · 2.45 KB
/
huffman.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
package sendtables2
import (
"container/heap"
)
// Interface for the tree, only implements Weight
type huffmanTree interface {
Weight() int
IsLeaf() bool
Value() int
Left() huffmanTree
Right() huffmanTree
}
// A leaf, contains encoded value
type huffmanLeaf struct {
weight int
value int
}
// A node with potential left / right nodes or leafs
type huffmanNode struct {
weight int
value int
left huffmanTree
right huffmanTree
}
// Return weight for leaf
func (self huffmanLeaf) Weight() int {
return self.weight
}
// Return leaf state
func (self huffmanLeaf) IsLeaf() bool {
return true
}
// Return value for leaf
func (self huffmanLeaf) Value() int {
return self.value
}
func (self huffmanLeaf) Right() huffmanTree {
_panicf("huffmanLeaf doesn't have right node")
return nil
}
func (self huffmanLeaf) Left() huffmanTree {
_panicf("huffmanLeaf doesn't have left node")
return nil
}
// Return weight for node
func (self huffmanNode) Weight() int {
return self.weight
}
// Return leaf state
func (self huffmanNode) IsLeaf() bool {
return false
}
// Return value for node
func (self huffmanNode) Value() int {
return self.value
}
func (self huffmanNode) Left() huffmanTree {
return huffmanTree(self.left)
}
func (self huffmanNode) Right() huffmanTree {
return huffmanTree(self.right)
}
type treeHeap []huffmanTree
// Returns the amount of nodes in the tree
func (th treeHeap) Len() int {
return len(th)
}
// Weight compare function
func (th treeHeap) Less(i int, j int) bool {
if th[i].Weight() == th[j].Weight() {
return th[i].Value() >= th[j].Value()
} else {
return th[i].Weight() < th[j].Weight()
}
}
// Append item, required for heap
func (th *treeHeap) Push(ele interface{}) {
*th = append(*th, ele.(huffmanTree))
}
// Remove item, required for heap
func (th *treeHeap) Pop() (popped interface{}) {
popped = (*th)[len(*th)-1]
*th = (*th)[:len(*th)-1]
return
}
// Swap two items, required for heap
func (th treeHeap) Swap(i, j int) {
th[i], th[j] = th[j], th[i]
}
// Construct a tree from a map of weight -> item
func buildHuffmanTree(symFreqs []int) huffmanTree {
var trees treeHeap
for v, w := range symFreqs {
if w == 0 {
w = 1
}
trees = append(trees, &huffmanLeaf{w, v})
}
n := 40
heap.Init(&trees)
for trees.Len() > 1 {
a := heap.Pop(&trees).(huffmanTree)
b := heap.Pop(&trees).(huffmanTree)
heap.Push(&trees, &huffmanNode{a.Weight() + b.Weight(), n, a, b})
n++
}
return heap.Pop(&trees).(huffmanTree)
}