import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
class Huffman {
private int value;
private int s;
public int p;
public boolean use;
public Huffman parent;
public Huffman leftchild;
public Huffman rightchild;
public ArrayList path;
public Huffman() {
this.value = 0;
this.s = 10;
this.parent = null;
this.leftchild = null;
this.rightchild = null;
this.use = false;
this.path = new ArrayList();
}
public Huffman(int v, int p) {
this.value = v;
this.p = p;
this.s = 10;
this.parent = null;
this.leftchild = null;
this.rightchild = null;
this.use = false;
this.path = new ArrayList();
}
public void setValue(int v1, int v2) {
this.value = v1 + v2;
}
public int getValue() {
return this.value;
}
public int getS() {
return this.s;
}
public void setS(int s) {
this.s = s;
}
}
public class HuffmanCode {
static int place = 0;
public static Huffman merge(Huffman h1, Huffman h2) {
Huffman parent = new Huffman();
parent.setValue(h1.getValue(), h2.getValue());
if (h1.getValue() >= h2.getValue()) {
h1.setS(0);
h2.setS(1);
h1.parent = parent;
h2.parent = parent;
parent.leftchild = h1;
parent.rightchild = h2;
} else {
h1.setS(1);
h2.setS(0);
h1.parent = parent;
h2.parent = parent;
parent.rightchild = h1;
parent.leftchild = h2;
}
return parent;
}
public static void main(String[] args) throws IOException {
FileReader file = new FileReader("f:\\huffman.txt");
BufferedReader reader = new BufferedReader(file);
List<Huffman> list1 = new ArrayList<Huffman>();
List<Huffman> list2 = new ArrayList<Huffman>();
Huffman temp = null;
Huffman com = null;
Huffman it = null;
int time = 0;
String line = reader.readLine();
while (line != null) {
list1.clear();
list2.clear();
time++;
place = 0;
System.out.println("Case " + time);
String[] str;
str = line.split(",");
int[] in = new int[str.length];
for (int i = 0; i < str.length; i++)
in[i] = Integer.parseInt(str[i]);
for (int t : in) {
place++;
list1.add(new Huffman(t, place));
}
while (list1.size() > 1) {
for (int i = 0; i < list1.size(); i++)
for (int j = i + 1; j < list1.size(); j++) {
if (list1.get(i).getValue() < list1.get(j).getValue()) {
temp = list1.get(i);
list1.set(i, list1.get(j));
list1.set(j, temp);
}
}
int last = list1.size() - 1;
int second = list1.size() - 2;
com = merge(list1.get(second), list1.get(last));
list2.add(list1.remove(last));
list2.add(list1.remove(second));
list1.add(com);
}
for (int i = 0; i < list2.size(); i++)
for (int j = 0; j < in.length; j++) {
if (list2.get(i).getValue() == in[j] && list2.get(i).rightchild == null
&& list2.get(i).leftchild == null && !list2.get(i).use) {
it = list2.get(i);
while (it.parent != null) {
list2.get(i).path.add(it.getS());
it.use = true;
it = it.parent;
}
}
}
for (int i = 1; i <= place; i++) {
for (int j = 0; j < list2.size(); j++) {
if (list2.get(j).p == i) {
System.out.print(list2.get(j).getValue() + ":");
for (int k = list2.get(j).path.size() - 1; k >= 0; k--)
System.out.print(list2.get(j).path.get(k));
break;
}
}
System.out.println();
}
System.out.println();
line = reader.readLine();
}
}
}
