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
|
import java.util.ArrayList;
public class HuffmanTree
{
private String str;
private BinaryNodeInterface<Character> root;
private ArrayList<Character> charList;
private ArrayList<Integer> freqList;
public HuffmanTree(String aString)
{
str = aString;
root = null;
generateFrequencyList();
generateHuffmanTree();
}
public BinaryNodeInterface<Character> getRootNode()
{
return root;
}
private void generateHuffmanTree()
{
if(str == null || str.equals(""))
{
root = null;
return;
}
MinHeapInterface<BinaryNodeFrequency<Character>> heap = new MinHeap<BinaryNodeFrequency<Character>>();
while(!charList.isEmpty())
{
char c = charList.remove(0);
int freq = freqList.remove(0);
BinaryNodeInterface<Character> newNode = new BinaryNode<Character>(c);
BinaryNodeFrequency<Character> newBNode = new BinaryNodeFrequency<Character>(newNode, freq);
heap.add(newBNode);
}
while(!heap.isEmpty())
{
BinaryNodeFrequency<Character> left = heap.removeMin();
if(heap.isEmpty())
{
root = left.node;
break;
}
BinaryNodeFrequency<Character> right = heap.removeMin();
int newFrequency = left.frequency + right.frequency;
BinaryNodeInterface<Character> newNode = new BinaryNode<Character>(null, (BinaryNode<Character>) left.node, (BinaryNode<Character>) right.node);
BinaryNodeFrequency<Character> newBNode = new BinaryNodeFrequency<Character>(newNode, newFrequency);
heap.add(newBNode);
}
if(root.isLeaf())
{
BinaryNodeInterface<Character> newNode = new BinaryNode<Character>(null, (BinaryNode<Character>) root, null);
root = newNode;
}
}
private void generateFrequencyList()
{
charList = new ArrayList<Character>();
freqList = new ArrayList<Integer>();
int strLength = str.length();
for(int i = 0; i < strLength; i++)
{
char c = str.charAt(i);
int charIndex = charList.indexOf(c);
if(charIndex != -1)
{
freqList.set(charIndex, freqList.get(charIndex) + 1);
}
else
{
charList.add(c);
freqList.add(1);
}
}
}
/* The min heap requires the object to implement comparable. According
* to the algorithm, we need to add BinaryNode into the min heap. However,
* BinaryNodes are not comparable, so we need a new type of object that
* can be used to represent a BinaryNode that implements Comparable.
* In this situation, our BinaryNode will be used to store a character.
* To compare, we compare the frequency of the character.
*/
private class BinaryNodeFrequency<T> implements Comparable<BinaryNodeFrequency<T>>
{
private BinaryNodeInterface<T> node;
private int frequency;
private BinaryNodeFrequency(BinaryNodeInterface<T> aNode, int aFrequency)
{
node = aNode;
frequency = aFrequency;
}
public int compareTo(BinaryNodeFrequency<T> otherBNF)
{
if(frequency < otherBNF.frequency)
{
return -1;
}
else if(frequency > otherBNF.frequency)
{
return 1;
}
else
{
return 0;
}
}
}
}
|
