View difference between Paste ID: vpDcf99Q and rAZRUsyB
SHOW: | | - or go back to the newest paste.
1
import java.util.*;
2
import java.io.*;
3
4
class HuffmanNode implements Comparable<HuffmanNode>{
5
HuffmanNode right;
6
HuffmanNode left;
7
HuffmanNode parent;
8
int count;          
9
String letter;
10
11
public HuffmanNode(){}
12
13
public HuffmanNode (String letter, int count){
14
this.letter = letter;
15
this.count = count;
16
}
17
public HuffmanNode (String letter, int count, HuffmanNode parent, HuffmanNode left, HuffmanNode right){
18
    this.letter = letter;
19
    this.count = count;
20
    this.left = left;
21
    this.right = right;
22
    this.parent = parent;
23
}
24
25
public void setCount(int count){
26
this.count = count;
27
}
28
29
public int getCount(){
30
return count;
31
}
32
33
public void setRight(HuffmanNode right){
34
this.right = right;
35
}
36
37
public HuffmanNode getRight(HuffmanNode right){
38
return right;
39
}
40
41
public void setLeft(HuffmanNode left){
42
this.left = left;
43
}
44
45
public HuffmanNode getLeft(HuffmanNode left){
46
return left;
47
}       
48
public void setParent(HuffmanNode right){
49
this.left = left;
50
}   
51
public HuffmanNode getParent(HuffmanNode parent){
52
return parent;
53
}
54
55
public void buildTree(HuffmanNode node){
56
    if (node.compareTo(this) <= 0 && left != null){
57
    System.out.println(node.getCount() + ":" + this.count);
58
    left.buildTree(node);
59
    }
60
    else if (node.compareTo(this) <= 0 && left == null){
61
    this.left = node;
62
    node.parent = this;
63
    }
64
    else if (node.compareTo(this) > 0 && right != null){
65
    System.out.println(node.getCount() + ":" +this.count);
66
    right.buildTree(node);
67
    }
68
    else if (node.compareTo(this) > 0 && right == null){
69
    this.right = node;
70
    node.parent = this;
71
    }
72
}
73
74
75
public int compareTo(HuffmanNode x){
76
return this.count - x.count;
77
}
78
public void genCode(String s){
79
    if(left != null){
80
    left.genCode(s + "0");
81
    }
82
    if(right != null){
83
    right.genCode(s + "1"); 
84
    }
85
    if (left == null && right == null){
86
    System.out.println(s);
87
    }
88
}
89
}
90
91
public class hw4{
92
public static void main (String []args)throws IOException{
93
94
//ask user to enter file name
95
System.out.printf("Enter a file location and name to encode [press Enter]: ");
96
Scanner input = new Scanner(System.in);
97-
z
97+
98
99
//Gets file name from Scanner and checks to see if valid
100-
Code:
100+
101
//if (!file.isFile()){
102
//System.out.printf("Enter a file location and name to encode [press Enter]: ");
103
//}
104
Scanner text = new Scanner(file);
105
106
String[] letters = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
107
int[] freq = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
108
109
String letter;
110
String tempStr;
111
int tempInt;
112
113
    while(text.hasNext()){
114
        letter = text.next();
115
        //System.out.printf("%s\n", letter);
116
117
                    char c = letter.charAt(0);
118
        int index = c - 97;
119
        freq[index]++;     
120
    }
121
122
    for(int i=0; i <25; i++){
123
    System.out.printf("%s:%d\n", letters[i], freq[i]);
124
    }
125
    System.out.printf("\n");
126
127
    for (int n=0; n <25; n++) {
128
        for (int i=0; i <25; i++) {
129
            if (freq[i] > freq[i+1]) {
130
                // exchange elements
131
                tempInt = freq[i];  
132
                tempStr = letters[i]; 
133
                freq[i] = freq[i+1];
134
                letters[i] = letters[i+1];  
135
                freq[i+1] = tempInt;
136
                letters[i+1] = tempStr;
137
            }
138
        }   
139
       } 
140
141
    PriorityQueue<HuffmanNode> huffmanList = new PriorityQueue<HuffmanNode>();
142
143
    for(int i=0; i <26; i++){
144
    System.out.printf("%s:%d\n", letters[i], freq[i]);
145
        if(freq[i] > 0){
146
        huffmanList.add(new HuffmanNode(letters[i],freq[i]));
147
        }
148
    }
149
150
    HuffmanNode root = new HuffmanNode();
151
152
    while(huffmanList.size() > 1){
153
    HuffmanNode x = huffmanList.poll();
154
    HuffmanNode y = huffmanList.poll();
155
    HuffmanNode result = new HuffmanNode("-", x.getCount() + y.getCount(), null, x, y);
156
        if(root == null){
157
        root = result;
158
        }
159
        else{
160
        root.buildTree(result); 
161
        }
162
    huffmanList.add(result);                    
163
    }
164
     root.genCode(" ");
165
}
166
}
167
168
input file data:
169
a
170
a
171
a
172
a
173
d
174
d
175
d
176
d
177
d
178
d
179
d
180
d
181
k
182
k
183
k
184
k
185
k
186
k
187
f
188
f
189
f
190
f
191
f
192
f
193
h
194
h
195
h
196
h
197
h
198
h
199
b
200
b
201
b
202
b
203
b
204
b
205
b
206
b
207
n
208
n
209
n
210
n
211
n
212
n
213
n
214
e
215
e
216
e
217
e
218
e
219
i
220
i
221
i
222
i
223
i
224
i
225
i
226
i
227
l
228
k
229
j
230
a
231
n
232
s
233
g
234
l
235
k
236
j
237
a
238
s
239
v
240
o
241
i
242
j
243
a
244
s
245
d
246
l
247
k
248
g
249
k
250
n
251
m
252
a
253
s
254
d
255
k
256
l
257
o
258
v
259
h
260
a
261
s
262
d
263
g
264
z