81 lines
2.2 KiB
Java
81 lines
2.2 KiB
Java
import java.util.*;
|
|
import java.io.*;
|
|
|
|
public class HuffmanCode {
|
|
|
|
public HuffmanNode root;
|
|
|
|
public HuffmanCode(int[] frequencies) {
|
|
Queue<HuffmanNode> nodes = new PriorityQueue<>();
|
|
for (int i=0;i<frequencies.length;i++) {
|
|
nodes.add(new HuffmanNode((char) i, frequencies[i]));
|
|
}
|
|
while (nodes.size()>1) {
|
|
HuffmanNode left = nodes.remove();
|
|
HuffmanNode right = nodes.remove();
|
|
HuffmanNode branch = new HuffmanNode(null, left.freq + right.freq, left, right);
|
|
nodes.add(branch);
|
|
}
|
|
this.root = nodes.remove();
|
|
}
|
|
|
|
public HuffmanCode(Scanner input) {
|
|
assembleTree(input, new HuffmanNode(null, null));
|
|
}
|
|
|
|
private assembleTree(Scanner input, HuffmanNode head) {
|
|
if (input.hasNextLine()) {
|
|
char character = (char) input.nextLine();
|
|
}
|
|
if (input.hasNextLine()) {
|
|
String loc = input.nextLine();
|
|
}
|
|
if (head == null) {
|
|
head = new HuffmanNode(null, null);
|
|
}
|
|
}
|
|
|
|
public void save(PrintStream output) {
|
|
save(output, this.root)
|
|
}
|
|
|
|
private void save(PrintStream output, HuffmanNode head) {
|
|
output.println((int) head.data);
|
|
output.println() ;
|
|
save(head.left);
|
|
save(head.right);
|
|
}
|
|
|
|
public void translate(BitInputStream input, PrintStream output) {
|
|
}
|
|
|
|
private static class HuffmanNode implements Comparable<HuffmanNode> {
|
|
public final char data;
|
|
public final int freq;
|
|
public HuffmanNode left;
|
|
public HuffmanNode right;
|
|
|
|
public HuffmanNode(char data, int frequency) {
|
|
this(data, frequency, null, null);
|
|
}
|
|
|
|
public HuffmanNode(char data, int frequency, HuffmanNode left, HuffmanNode right) {
|
|
this.data = data;
|
|
this.freq = freq;
|
|
this.left = left;
|
|
this.right = right;
|
|
}
|
|
|
|
public int compareTo(HuffmanNode other) {
|
|
if (this.freq == other.freq) {
|
|
return 0;
|
|
}
|
|
else if (this.freq < other.freq) {
|
|
return -1;
|
|
}
|
|
return 1;
|
|
}
|
|
|
|
}
|
|
}
|