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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
/**
* It is okay to use ArrayList class but you are not allowed to use any other
* predefined class supplied by Java.
*/
import java.util.ArrayList;
public class CompressDecompress
{
/**
* Get a string representing a Huffman tree where its root node is root
* @param root the root node of a Huffman tree
* @return a string representing a Huffman tree
*/
public static String getTreeString(final BinaryNodeInterface<Character> root)
{
String output = getTreeStringHelper(root);
return output; // Do not forget to change this line!!!
}
private static String getTreeStringHelper(final BinaryNodeInterface<Character> root)
{
//System.out.println("\n finding ");
String output = "";
if(root != null)
{
if(root.hasLeftChild() || root.hasRightChild())
{
//System.out.println("Found non-leaf node Right:" + root.hasRightChild() + " left: " + root.hasLeftChild());
output += "I";
output += getTreeStringHelper(root.getLeftChild());
output += getTreeStringHelper(root.getRightChild());
return output;
}
else
{
//System.out.println("Found a leaf node!");
output += "L"+root.getData();
return output;
}
}
else
{
return output;
}
// if(root.hasLeftChild())
// {
// //System.out.println("Finding left child");
// output += getTreeStringHelper(root.getLeftChild());
// }
// if(root.hasRightChild())
// {
// //System.out.println("Finding right child");
// output += getTreeStringHelper(root.getRightChild());
// }
// return output;
}
/**
* Compress the message using Huffman tree represented by treeString
* @param root the root node of a Huffman tree
* @param message the message to be compressed
* @return a string representing compressed message.
*/
public static String compress(final BinaryNodeInterface<Character> root, final String message)
{
// TO DO
//System.out.println("Got tree: " + getTreeString(root));
return compressHelper(root,message);
//return ""; // Do not forget to change this line!!!
}
private static String compressHelper(final BinaryNodeInterface<Character> root, final String message)
{
String output = "";
if(message.isEmpty())
{
return output;
}
else
{
output += getStringForChar(root,message.charAt(0));
output += compressHelper(root,message.substring(1));
return output;
}
}
private static String getStringForChar(BinaryNodeInterface<Character> root, char c)
{
return getStringForCharHelper(root,c,"");
}
private static String getStringForCharHelper(BinaryNodeInterface<Character> root,char c, String p)
{
if(root == null)
return "";
if(root.getData() != null && root.getData().equals(new Character(c)))
{
return p;
}
String output = "";
if(root.hasLeftChild())
{
output = getStringForCharHelper(root.getLeftChild(),c,p+"0");
}
if(root.hasRightChild() && output == "")
{
output = getStringForCharHelper(root.getRightChild(),c,p+"1");
}
return output;
}
/**
* Decompress the message using Huffman tree represented by treeString
* @param treeString the string represents the Huffman tree of the
* compressed message
* @param message the compressed message to be decompressed
* @return a string representing decompressed message
*/
public static String decompress(final String treeString, final String message)
{
//First, create a tree out of treeString
BinaryNode<Character> node = getTreeFor(treeString);
//Then find the output from this string
String output = "";
for(int i = 0; i < message.length();)
{
BinaryNodeInterface tmp = node;
while(!tmp.isLeaf())
{
if(message.charAt(i) == '0')
{
tmp = tmp.getLeftChild();
}
else if(message.charAt(i) == '1')
{
tmp = tmp.getRightChild();
}
i++;
}
output += tmp.getData();
}
return output; // Do not forget to change this line!!!
}
private static BinaryNode<Character> getTreeFor(String pre)
{
if(pre.isEmpty())
{
return null;
}
char type = pre.charAt(0);
BinaryNode<Character> root = new BinaryNode<Character>(null,null,null);
if(type == 'I')
{
int length = 0;
if(!root.hasLeftChild())
{
length = treeLength(pre.substring(1));
String lefttree = pre.substring(1,length+1);
root.setLeftChild(getTreeFor(lefttree));
}
if(!root.hasRightChild())
{
String righttree = pre.substring(length+1);
root.setRightChild(getTreeFor(righttree));
}
return root;
}
else if(type == 'L')
{
root.setData(pre.charAt(1));
return root;
}
return root;
}
private static int treeLength(String s) //Figure out how long the string should be
{
int output = 1;
for(int i = 0; i < output; i++)
{
if(s.charAt(i) == 'I')
{
output += 2;
}
if(s.charAt(i) == 'L')
{
output += 1;
i++;
}
}
return output;
}
}
|
