* Created on Apr 24, 2004
*
* FullHuffmanApplet
* It takes textual commands in a TextArea and when the user
* clicks on the Execute button, it processes the commands,
* updating the display as it goes.
*
* The program demonstrates the creation and use of a Huffman Code.
* It illustrates the whole process, including construction of the
* Huffman trees using a priority queue implemented as a binary heap.
* The compression ratio is shown at the end of the history window.
*
* Here is a sample command sequence:
*/
/*
DELAY 100 ; pause 100 ms between updates.
BEGIN-TEXT
This is a message
that is about two lines long.
END-TEXT
FREQUENCY-TABLE
CREATE-CODE
ENCODE
DECODE
STATS
*/
/**
* @author Steve Tanimoto, Copyright, 2004.
*
*/
import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
public class FullHuffmanApplet extends JApplet implements ActionListener, Runnable {
ScrolledPanel visPanel; //Where to paint graphics
MyScrollPane msp;
Button executeButton;
Button historyButton;
TextArea userInputText;
TextArea history;
JFrame historyFrame;
JTextField statusLine;
HuffmanHeap theHeap; // The data structure being demonstrated
String sourceText; // text used to build code or to be encoded
String cipherText; // Huffman-coded text.
FreqTable theTable; // Used to initialize the Huffman heap.
CodingTable theCodingTable; // Represents the code in a form for encoding.
DecodingTable theDecodingTable; // Represents the code in a form for decoding.
double rawRatio = 0.0; // compression ratio, ignoring code table.
double fullRatio = 0.0; // compression ratio, including code table.
Font headingFont, keyFont, objectFont, indexFont, treeFont;
int cellHeight = 20; // For drawing the heap.
int cellWidth = 30; // How wide to plot pink rectangles
int cellGap = 4; // Horizonal space between successive cells
int topMargin = 25; // Space above top of heap.
int fontSize = 16; // Height of font for displaying heap elemens.
int leftMargin = 20; // x value for left side of array.
int rightMargin = leftMargin;
int yTreeTops = topMargin + 150; // y coord of top of trees.
int bottomMargin = 10; // Minimum space betw. bot. of visPanel and bot. of lowest cell.
int leftOffset = 5; // space between left side of cell and contents string.
int delay = 300; // default is to wait 300 ms between updates.
Thread displayThread = null;
// For HuffmanTree display:
int nodeHeight = 15; // For drawing the nodes.
int nodeWidth = 40; // How wide to plot pink rectangles
int nodeVGap = 5; // vertical space between successive nodes
int nodeHGap = 10; // horizontal space between successive nodes
int nodeHorizSpacing = nodeWidth + nodeHGap;
int nodeVertSpacing = nodeHeight + nodeVGap;
int interTreeGap = 20; // horizontal space between trees.
int ycentering = (nodeHeight - fontSize) / 2;
static int m; // variable used when computing columns for tree layouts.
public void init() {
setSize(700,400); // default size of applet.
visPanel = new ScrolledPanel();
visPanel.setPreferredSize(new Dimension(400,400));
msp = new MyScrollPane(visPanel);
msp.setPreferredSize(new Dimension(400,200));
Container c = getContentPane();
c.setLayout(new BorderLayout());
c.add(msp, BorderLayout.CENTER);
JPanel buttons = new JPanel();
buttons.setLayout(new FlowLayout());
JPanel controls = new JPanel();
controls.setLayout(new BorderLayout());
executeButton = new Button("Execute");
executeButton.addActionListener(this);
buttons.add(executeButton);
historyButton = new Button("History");
historyButton.addActionListener(this);
buttons.add(historyButton);
userInputText = new TextArea(";Enter commands here.\n" +
"DELAY 100 ; pause 100 ms between updates.\n" +
"BEGIN-TEXT\n" +
"This is a message\n" +
"that is about two lines long.\n" +
"END-TEXT\n" +
"FREQUENCY-TABLE ; Build a table giving the number of occurrences of each char.\n" +
"CREATE-CODE ; Create an internal hash table mapping characters to binary codewords.\n" +
" ; This also creates a hash table going the other way, for decoding.\n" +
"ENCODE ; translate the previously given text into its Huffman encoding.\n" +
"DECODE ; translate the Huffman coding back to the standard representation.\n" +
"STATS ; print out the compression ratio, etc.\n");
statusLine = new JTextField();
statusLine.setBackground(Color.lightGray);
controls.add(buttons, BorderLayout.WEST);
controls.add(userInputText, BorderLayout.CENTER);
controls.add(statusLine, BorderLayout.SOUTH);
controls.setPreferredSize(new Dimension(400,100));
c.add(controls, BorderLayout.SOUTH);
c.validate();
theHeap = new HuffmanHeap();
theHeap.init();
headingFont = new Font("Helvetica", Font.PLAIN, 20);
keyFont = new Font("Helvetica", Font.BOLD, 16);
objectFont = new Font("Helvetica", Font.PLAIN, 20);
indexFont = new Font("Helvetica", Font.PLAIN, 14);
treeFont = new Font("Courier", Font.PLAIN, 14);
history = new TextArea("FullHuffmanApplet history:\n", 20, 40);
}
class ScrolledPanel extends JPanel {
public void paintComponent(Graphics g) {
super.paintComponent(g);
//paintGrid(g);
paintHeap(g);
paintTrees(g);
}
}
class MyScrollPane extends JScrollPane {
MyScrollPane(JPanel p) {
super(p,
JScrollPane.VERTICAL_SCROLLBAR_ALWAYS,
JScrollPane.HORIZONTAL_SCROLLBAR_ALWAYS);
}
}
/**
* This inner class implements a priority queue ADT
* for data elements that are Huffman trees.
*/
class HuffmanHeap {
int n; // number of elements in the heap
int ninserts; // number of INSERT operations so far.
int ndeletemins; // number of DELETEMIN operations so far.
int nfindmins; // number of FINDMIN operations so far.
int npercups; // number of calls to percolateUp so far.
int npercdowns; // number of calls to percolateDown so far.
int A[]; // Holds the key (priority) values.
Object B[]; // Holds the Huffman trees (references to roots).
final static int MAXSIZE = 256;
HuffmanHeap(int finalSize) {
A = new int[finalSize+1];
B = new Object[finalSize+1];
n = finalSize;
}
HuffmanHeap() {};
void init() { // Not used in this program (was used in Program 2).
n = 0; ninserts = 0; ndeletemins = 0; nfindmins = 0;
npercups = 0; npercdowns = 0;
A = new int[MAXSIZE+1];
B = new Object[MAXSIZE+1];
}
int parent(int i) { return (int) Math.floor(i / 2); }
int leftChild(int i) { return i*2; }
int rightChild(int i) { return i*2 + 1; }
String insert(Object theObject, int key) {
if (n == MAXSIZE) {
return "Error: the heap is full.";
}
n++;
percolateUp(n, key, theObject);
ninserts++;
return "Inserting " + key + " and data " +
theObject + " at position " + n;
}
void deletemin() {
if (n == 0) { return; }
ndeletemins++;
A[1] = A[n];
B[1] = B[n];
n--;
percolateDown(1);
}
int findmin() {
nfindmins++;
if (n > 0) { return A[1]; }
else { return 9999999; }
}
Object findminObject() {
nfindmins++;
if (n > 0) { return B[1]; }
else { return null; }
}
void buildHeap() {
for (int i = n / 2; i>0; i--) {
percolateDown(i);
}
}
void percolateUp(int i, int x, Object b) {
npercups++;
if (x < A[parent(i)]) {
A[i] = A[parent(i)];
B[i] = B[parent(i)];
updateDisplay();
percolateUp(parent(i), x, b);
}
else {
A[i] = x;
B[i] = b;
}
}
void percolateDown(int i) {
npercdowns++;
if (2*i > n) return;
if (2*i == n) {
if (A[i] > A[2*i]) {
int tempA = A[2*i];
Object tempB = B[2*i];
A[2*i] = A[i];
B[2*i] = B[i];
A[i] = tempA;
B[i] = tempB;
}
}
else {
int c = 2*i;
if (A[c] > A[c+1]) { c = c+1; }
if (A[i] > A[c]) {
int tempA = A[c];
Object tempB = B[c];
A[c] = A[i];
B[c] = B[i];
A[i] = tempA;
B[i] = tempB;
}
percolateDown(c);
}
}
boolean isEmpty() { return n == 0; }
}
public void actionPerformed(ActionEvent e) {
if (e.getActionCommand().equals("Execute")) {
displayThread = new Thread(this);
displayThread.start();
return;
}
if (e.getActionCommand().equals("History")) {
if (historyFrame == null) {
historyFrame = new JFrame("History of the FullHuffmanApplet");
history.setFont(new Font("Courier", Font.PLAIN, 12));
historyFrame.getContentPane().add(history);
historyFrame.setSize(new Dimension(300,300));
}
historyFrame.show();
}
}
// The following is executed by a separate thread for the display.
public void run() {
String commands = userInputText.getText();
String line = "";
StringTokenizer lines;
for (lines = new StringTokenizer(commands, "\n\r\f");
lines.hasMoreTokens();) {
line = lines.nextToken();
process(line, lines);
}
userInputText.setText(""); // Erase all the processed input.
}
// Helper function called by the run method above:
void process(String command, StringTokenizer lines) {
String arg1 = ""; String arg2 = "";
StringTokenizer st = new StringTokenizer(command);
if (! st.hasMoreTokens()) { return; }
String firstToken = st.nextToken();
if (firstToken.startsWith(";")) { return; }
history.appendText(command + "\n");
statusLine.setText(command);
if (firstToken.equals("RESET")) {
theHeap = new HuffmanHeap();
theHeap.init();
updateDisplay(); return;
}
if (firstToken.equals("SIZE")) {
String stats = "Current number of elements: " + theHeap.n;
statusLine.setText(stats);
history.appendText("; " + stats + "\n");
return;
}
if (firstToken.equals("ISEMPTY")) {
String stats = "The heap is ";
if (! theHeap.isEmpty()) { stats += "not "; }
stats += "empty.";
statusLine.setText(stats);
history.appendText("; " + stats + "\n");
return;
}
if (firstToken.equals("STATS")) {
String stats;
if (theCodingTable == null) {
report("No code has been created or used.");
return;
}
stats = "Coding table size (8 bits/symbol + 2 bits/coding bit) = " +
theCodingTable.computeTableNBits() + " bits.";
report(stats);
stats = "Source text size = " + sourceText.length() +
" bytes (or " + (sourceText.length()*8) + " bits).";
report(stats);
stats = "Ciphertext size = " + cipherText.length() +
" bits.";
report(stats);
stats = "Size of ciphertext and table combined = " +
(cipherText.length() + theCodingTable.tableNBits);
report(stats);
stats = "Compression ratio ignoring table itself = " + rawRatio;
report(stats);
stats = "Full compression ratio, considering the table = " + fullRatio;
report(stats);
return;
}
if (firstToken.equals("DELAY")) {
if (st.hasMoreTokens()) {
arg1 = st.nextToken();
try { delay =(new Integer(arg1)).intValue(); }
catch(NumberFormatException e) {
delay = 0;
}
statusLine.setText("delay = " + delay);
}
history.appendText("; delay is now " + delay + "\n");
return;
}
if (firstToken.equals("CREATE-LEAF")) {
arg1 = "UNDEFINED ELEMENT";
if (st.hasMoreTokens()) { arg1 = st.nextToken(); }
if (st.hasMoreTokens()) { arg2 = st.nextToken(); }
int f = (new Integer(arg2)).intValue();
HuffmanTree ht = new HuffmanTree(arg1, f);
theHeap.insert(ht, f);
checkScrolledPanelSize();
updateDisplay(); return;
}
if (firstToken.equals("INSERT")) {
arg1 = "UNDEFINED ELEMENT";
if (st.hasMoreTokens()) { arg1 = st.nextToken(); }
arg2 = "UNDEFINED ELEMENT";
if (st.hasMoreTokens()) { arg2 = st.nextToken(); }
theHeap.insert(arg1, getInt(arg2));
checkScrolledPanelSize();
updateDisplay();
return;
}
if (firstToken.equals("DELETEMIN")) {
theHeap.deletemin();
updateDisplay(); return;
}
if (firstToken.equals("TEST")) {
theTable = new FreqTable(100);
theTable.fillTable("This is a test of the table stuff");
theTable.show();
frequenciesToForest(theTable);
updateDisplay();
theHeap.buildHeap();
mergeAll();
updateDisplay(); return;
}
if (firstToken.equals("MERGEALL")) {
mergeAll();
updateDisplay(); return;
}
if (firstToken.equals("FINDMIN") ||
firstToken.equals("MINHTREE")) {
theHeap.findmin();
String minReport = "";
if (theHeap.n == 0) {
minReport = "The priority queue is empty.";
}
else {minReport = "Minimum key = " + theHeap.A[1] +
"; Data element = " + theHeap.B[1];
}
statusLine.setText(minReport);
history.appendText("; " + minReport + "\n");
updateDisplay(); return;
}
if (firstToken.equals("BEGIN-TEXT")) {
sourceText = "";
command = lines.nextToken() + "\n";
history.appendText(command);
while (! command.startsWith("END-TEXT")) {
sourceText += command;
command = lines.nextToken() + "\n";
history.appendText(command);
}
updateDisplay(); return;
}
if (firstToken.equals("FREQUENCY-TABLE")) {
theTable = new FreqTable(100);
theTable.fillTable(sourceText);
theTable.show();
updateDisplay(); return;
}
if (firstToken.equals("CREATE-CODE")) {
frequenciesToForest(theTable);
updateDisplay();
theHeap.buildHeap();
mergeAll();
theCodingTable = new CodingTable((HuffmanTree)theHeap.B[1]);
theCodingTable.show();
theDecodingTable = new DecodingTable();
theDecodingTable.init(theCodingTable);
theDecodingTable.show();
return;
}
if (firstToken.equals("ENCODE")) {
cipherText = "";
for(int i = 0; i < sourceText.length(); i++) {
cipherText += (String)theCodingTable.get(sourceText.substring(i,i+1));
}
report("Ciphertext is:");
report(cipherText);
rawRatio = ((cipherText.length() + 0.0) / (sourceText.length() + 0.0))/8.0;
fullRatio = (cipherText.length() + theCodingTable.computeTableNBits()) / (sourceText.length() * 8.0);
updateDisplay(); return;
}
if (firstToken.equals("DECODE")) {
sourceText = "";
String codeWord = "";
for(int i = 0; i < cipherText.length(); i++) {
codeWord += cipherText.substring(i,i+1);
String symbol = (String)theDecodingTable.get(codeWord);
if (symbol != null) {
sourceText += symbol;
codeWord = "";
}
}
report("Sourcetext is:");
report(sourceText);
updateDisplay(); return;
}
history.appendText("[Unknown Heap command]\n");
statusLine.setText("Unknown Heap command: " + command);
}
// Here is a "middleman" method that updates the display waiting with
// the current time delay after each repaint request.
void updateDisplay() {
visPanel.repaint();
if (delay > 0) {
try {
Thread.sleep(delay);
}
catch(InterruptedException e) {}
}
}
int getInt(String s) {
int n = 1;
try {
Integer I = new Integer(s);
n = I.intValue();
}
catch(Exception e) { n = 1; }
return n;
}
/*
* Graphics method to actually draw the heap.
* It's called by the ScrolledPanel paintComponent method.
*/
void paintHeap(Graphics g) {
g.setFont(headingFont);
g.setColor(Color.BLACK);
g.drawString( "Priority Queue of Huffman Trees", leftMargin,20);
int ystart = topMargin;
int ycentering = (cellHeight - fontSize) / 2;
int ypos = ystart;
int xpos = leftMargin;
FontMetrics fm = null;
for (int i = 0; i <= theHeap.n; i++) {
g.setColor(Color.pink);
g.fillRect(xpos, ypos, cellWidth, 2*cellHeight);
g.setColor(Color.black);
g.setFont(keyFont);
String key = theHeap.A[i]+"";
fm = g.getFontMetrics();
int keyWidth = fm.stringWidth(key);
// Center the strings in the cells:
g.drawString(key, (2*xpos + cellWidth - keyWidth)/2, ypos+cellHeight - ycentering);
g.setFont(objectFont);
String contents = theHeap.B[i]+"";
fm = g.getFontMetrics();
int contentsWidth = fm.stringWidth(contents);
g.drawString(contents, (2*xpos + cellWidth - contentsWidth)/2, ypos+2*cellHeight - ycentering);
g.setFont(indexFont);
fm = g.getFontMetrics();
int indexWidth = fm.stringWidth(i+"");
g.drawString(i+"", (2*xpos + cellWidth - indexWidth)/2, ypos+3*cellHeight);
xpos += (cellWidth + cellGap);
}
}
/*
* The following computes the height of the display area needed by the current
* heap, and if it won't fit in the scrolled panel, it enlarges the scrolled panel.
*/
void checkScrolledPanelSize() {
// Compute space needed for heap array, then for trees.
int heapHeightNeeded = 150;
int heapWidthNeeded = (theHeap.n + 1) * cellWidth +
(theHeap.n * cellGap) + leftMargin + rightMargin;
Dimension d = visPanel.getPreferredSize();
int currentHeight = (int) d.getHeight();
int currentWidth = (int) d.getWidth();
// Compute width needed for trees:
int treesWidthNeeded = leftMargin + rightMargin;
int treesHeightNeeded = 0;
for (int i = 1; i <= theHeap.n; i++) {
HuffmanTree ht = (HuffmanTree)theHeap.B[i];
if (ht != null) {
treesWidthNeeded += ht.getDisplayWidth();
treesHeightNeeded = Math.max(treesHeightNeeded, ht.getDisplayHeight());
}
}
treesWidthNeeded += Math.max(0, (theHeap.n - 1)*interTreeGap);
treesHeightNeeded += topMargin + bottomMargin;
// Enlarge scrolled panel if necessary:
int widthNeeded = Math.max(heapWidthNeeded, treesWidthNeeded);
int heightNeeded = heapHeightNeeded + treesHeightNeeded;
if ((heightNeeded > currentHeight) ||
(widthNeeded > currentWidth)) {
visPanel.setPreferredSize(new Dimension(
Math.max(currentWidth,widthNeeded),
Math.max(currentHeight,heightNeeded)));
visPanel.revalidate(); // Adjust the vertical scroll bar.
}
}
/*
* In order to keep the code simple, this one class
* is used for both leaf nodes and internal nodes.
* It's also used for the trees as a whole.
* If storage space were a big consideration, then
* specific classes could be created for each of these.
* However, with Huffman trees, space is not usually
* much of a concern.
*/
class HuffmanTree {
// Here are the essential data members for Huffman trees:
int nSymbols; // number of symbols in the tree
int weight; // used in all nodes.
HuffmanTree leftSubtree, rightSubtree; // used only in internal nodes.
String symbol; // used only in leaf nodes.
// The following are used in display layout:
int depth; // relative y position of this node in the display
int column; // relative x position in display, in units of nodes
int maxdepth; // height of tree whose root is this node.
int xcenter; // position of center of root relative to left side of tree.
int ycenter;
// Leaf node constructor:
HuffmanTree(String sym, int weight) {
symbol = sym;
this.weight = weight;
nSymbols = 1;
}
// Internal node constructor:
HuffmanTree(HuffmanTree T0, HuffmanTree T1) {
leftSubtree = T0;
rightSubtree = T1;
weight = T0.weight + T1.weight;
nSymbols = T0.nSymbols + T1.nSymbols;
}
boolean isLeaf() { return (symbol != null); }
String leftmostSymbol() {
if (isLeaf()) { return symbol; }
else { return leftSubtree.leftmostSymbol();}
}
void getCodes(Hashtable ht, String prefix) {
if (isLeaf()) {
ht.put(symbol, prefix);
}
else {
leftSubtree.getCodes(ht, prefix + "0");
rightSubtree.getCodes(ht, prefix + "1");
}
}
public String toString() { return leftmostSymbol(); }
void paint(Graphics g, int xpos, int ypos) {
treeColumns();
paintHelper(g, xpos, ypos);
}
void paintHelper(Graphics g, int xpos, int ypos) {
if (! (isLeaf())) {
g.setColor(Color.black);
g.drawLine(xcenter + xpos, ycenter + ypos,
leftSubtree.xcenter + xpos,
leftSubtree.ycenter + ypos);
g.drawLine(xcenter + xpos, ycenter + ypos,
rightSubtree.xcenter + xpos,
rightSubtree.ycenter + ypos);
}
g.setColor(Color.pink);
g.fillRect(xpos + column*nodeHorizSpacing,
ypos + depth*nodeVertSpacing,
nodeWidth,
nodeHeight);
g.setColor(Color.black);
if (isLeaf()) {
String adjustedSymbol = symbol;
if (symbol.equals("\n")) {
adjustedSymbol = "\\n";
}
g.drawString(adjustedSymbol + "," + weight,
xpos + column*nodeHorizSpacing + leftOffset,
ypos + depth*nodeVertSpacing + nodeHeight - ycentering);
}
else {
g.drawString(weight + "", xpos + column*nodeHorizSpacing + leftOffset,
ypos + depth*nodeVertSpacing + nodeHeight - ycentering);
leftSubtree.paintHelper(g, xpos, ypos);
rightSubtree.paintHelper(g, xpos, ypos);
}
}
int traverse(int currentDepth) {
// Traverse the tree, filling in the depth and the column index
// of each node for display purposes.
// Returns the column index of the rightmost node.
depth = currentDepth;
if (isLeaf()) {
column = m;
m++;
maxdepth = depth;
}
else {
leftSubtree.traverse(depth + 1);
column = m; m++;
}
xcenter = column*nodeHorizSpacing + (nodeWidth / 2);
ycenter = depth*nodeVertSpacing + nodeHeight - ycentering;
if (! isLeaf()) {
int rm = rightSubtree.traverse(depth + 1);
maxdepth = Math.max(leftSubtree.maxdepth,
rightSubtree.maxdepth);
return rm;
}
else {
return column;
}
}
int treeColumns() {
m = 0;
return traverse(0) + 1;
}
int getDisplayWidth() {
int hGap = nodeHorizSpacing - nodeWidth;
int val = treeColumns() * (nodeHorizSpacing) - hGap;
return val;
}
int getDisplayHeight() {
int val = (maxdepth + 1) * nodeVertSpacing - nodeVGap;
return val;
}
}
void frequenciesToForest(FreqTable ft) {
theHeap = new HuffmanHeap(ft.n);
theHeap.A[0] = -1;
for (int i = 0; i < ft.n; i++) {
theHeap.A[i+1] = ft.f[i];
String s = (ft.c[i]+"");
theHeap.B[i+1] = new HuffmanTree(new String(s), ft.f[i]);
}
report("The forest of Huffman trees has been created.");
}
void mergeAll() {
while(theHeap.n > 1) {
HuffmanTree tMin = (HuffmanTree) theHeap.findminObject();
theHeap.deletemin();
HuffmanTree tMin2 = (HuffmanTree) theHeap.findminObject();
theHeap.deletemin();
HuffmanTree newTree = new HuffmanTree(tMin, tMin2);
theHeap.insert(newTree, newTree.weight);
checkScrolledPanelSize();
updateDisplay();
}
}
/*
* A FreqTable (frequence table) object consists primarly
* of two arrays: one to hold characters and one to hold
* int values that represent the numbers of occurrences of
* the corresponding characters.
*/
class FreqTable {
char c[];
int f[];
int n;
int maxSize;
FreqTable(int maxSize) {
c = new char[maxSize];
f = new int[maxSize];
n = 0;
this.maxSize = maxSize;
}
void insert(char c, int freq) {
if (n == maxSize - 1) {
report("Frequency table is full");
return;
}
this.c[n] = c;
f[n] = freq;
n++;
}
/*
* Takes a text string and analyzes it, finding for
* each character, the number of its occurrences.
* Puts the characters and counts into the FreqTable.
*/
void fillTable(String text) {
Hashtable ht = new Hashtable(40);
for(int i = 0; i < text.length(); i++) {
String keyStr = text.substring(i,i+1);
Integer ii = (Integer) ht.get(keyStr);
if (ii == null) {
ht.put(keyStr, new Integer(1));
}
else {
int oldfreq = ii.intValue();
ht.put(keyStr, new Integer(oldfreq + 1));
}
}
for(Enumeration e = ht.keys(); e.hasMoreElements();) {
String keyStr = (String)e.nextElement();
insert(keyStr.charAt(0), ((Integer)(ht.get(keyStr))).intValue());
}
}
/*
* Add a display of the frequency table to the history window.
*/
void show() {
report("The frequency table:");
for (int i = 0; i < n; i++) {
String adjustedSymbol = c[i] + "";
if (adjustedSymbol.equals("\n")) {
adjustedSymbol = "\\n";
}
if (adjustedSymbol.equals(" ")) {
adjustedSymbol = "(space)";
}
report(adjustedSymbol + ": " + f[i]);
}
}
}
/*
* A handy function that reports a message to both the
* status line of the applet and the history window.
* Multiline messages are not fully visible in the status line.
*/
void report(String message) {
statusLine.setText(message);
history.appendText("; " + message + "\n");
}
/*
* Goes through the heap from left to right, and each
* Huffman tree is painted underneath the heap, in a
* left-to-right sequence of trees.
*/
void paintTrees(Graphics g) {
g.setFont(treeFont);
int ystart = yTreeTops;
int ypos = ystart;
int xpos = leftMargin;
g.setFont(headingFont);
g.setColor(Color.BLACK);
g.drawString("The Huffman Trees:", xpos, yTreeTops - 50);
for (int i = 1; i <= theHeap.n; i++) {
HuffmanTree ht = (HuffmanTree)theHeap.B[i];
if (ht != null) {
g.setColor(Color.BLUE);
g.setFont(headingFont);
g.drawString( "T" + i + ":", xpos, yTreeTops - fontSize - 4);
g.setColor(Color.BLACK);
g.setFont(treeFont);
ht.paint(g,xpos,ypos);
xpos += interTreeGap;
xpos += ht.getDisplayWidth();
}
}
}
/*
* Displays a white grid, useful in debugging the tree layout
* part of the problem.
* The size of the grid is somewhat arbitrary.
*/
void paintGrid(Graphics g) {
g.setColor(Color.white);
for (int i = 0; i < 60; i ++) {
g.drawLine(0, i*20, 1500, i*20);
g.drawLine(i*20, 0, i*20, 1500);
}
}
/*
* Represents a mapping from characters (represented as
* strings of length 1) to codewords (strings of 0s and 1s
* of possibly different lengths).
*/
class CodingTable extends Hashtable {
int tableNBits; // number of bits to store table, in principle,
// assuming 1-byte per char, two bits per code bit.
// This is only useful in estimating compression ratios.
CodingTable(HuffmanTree ht) {
ht.getCodes(this, "");
}
int computeTableNBits() {
tableNBits = 0;
for (Enumeration e = this.keys();
e.hasMoreElements();) {
String key = (String)e.nextElement();
String code = (String)get(key);
tableNBits += 1 + 3*code.length();
}
return tableNBits;
}
void show() {
report("The coding table:");
for (Enumeration e = this.keys();
e.hasMoreElements();) {
String key = (String)e.nextElement();
String code = (String)get(key);
String adjustedKey = key;
if (key.equals("\n")) {
adjustedKey = "\\n";
}
if (key.equals(" ")) {
adjustedKey = "(space)";
}
report(adjustedKey + ": " + code);
}
}
}
/*
* Similar to CodingTable, but mapping the other way.
*/
class DecodingTable extends Hashtable {
void init(CodingTable ct) {
for (Enumeration e = ct.keys();
e.hasMoreElements();) {
String key = (String)e.nextElement();
String code = (String)ct.get(key);
put(code, key);
}
}
void show() {
report("The decoding table:");
for (Enumeration e = this.keys();
e.hasMoreElements();) {
String key = (String)e.nextElement();
String sym = (String)get(key);
String adjustedSym = sym;
if (sym.equals("\n")) {
adjustedSym = "\\n";
}
if (sym.equals(" ")) {
adjustedSym = "(space)";
}
report(key + ": " + adjustedSym);
}
}
}
}