Huffman Coding

Implement Huffman Encoding and Decoding and the classes shown on the following slides. You will also need to use the Stack class and the PriorityQueue class.

HuffmanEncode expects 2 command line arguments: the name of the source file (the file to be compressed) and the name of the destination file (the file to which the compressed file must be written) HuffmanDecode expects 2 command line arguments: the name of the source file (a file that contains a compressed file created by your encoder) and the name of the destination file (the file to which the uncompressed file must be written)

If your programs work the contents of decoders destination file should be exactly the same as the original source file used by encoder

I will post some large files for you to test with but you should first test with small files you create

The source file to encode will only include characters with character codes between 0 and 127 inclusive

You will demonstrate your implementation to me. Skeleton Code

import java.io.DataOutputStream;

import java.io.FileOutputStream;

import java.io.IOException;

public class BitOutputStream {

// add additional protected variables as needed

// do not modify the public methods signatures or add public methods

protected DataOutputStream d;

public BitOutputStream(String filename) {

try {

d = new DataOutputStream(new FileOutputStream(filename));

} catch (IOException e) {

} }

public void writeBit(char bit) {

// PRE: bit is a '0' or a '1' }

public void close() {

} } New Class import java.io.IOException;

public class HuffmanOutputStream extends BitOutputStream {

public HuffmanOutputStream(String filename, String tree, int totalChars) {

super(filename);

try {

d.writeUTF(tree);

d.writeInt(totalChars);

} catch (IOException e) {

}

} } New Class

import java.io.DataInputStream;

import java.io.FileInputStream;

import java.io.IOException;

public class BitInputStream {

// add additional protected variables as needed

// do not modify the public methods signatures or add public methods

protected DataInputStream d;

public BitInputStream(String filename) {

try {

d = new DataInputStream(new FileInputStream(filename));

} catch (IOException e) {

}

}

public int readBit() {

// return the next bit in the file

} public void close() {

} } New Class import java.io.IOException;

public class HuffmanInputStream extends BitInputStream {

// add additional private variables as needed

// do not modify the public method signatures or add public methods

private String tree;

private int totalChars;

public HuffmanInputStream(String filename) {

super(filename);

try {

tree = d.readUTF();

totalChars = d.readInt();

} catch (IOException e) {

}

}

public String getTree() {

}

public int getTotalChars() {

}

}

New Class import javax.xml.soap.Node;

public class HuffmanTree {

// add additional private variables as needed

// do not modify the public method signatures or add public methods private

// class Node {

private Node left;

private char data;

private Node right;

private Node parent;

private Node(Node L, char d, Node R, Node P) { left = L;

data = d; right = R; parent = P;

}

private Node root;

private Node current; // this value is changed by the move methods

public HuffmanTree() {

root = null;

current = null;

}

public HuffmanTree(char d) { // makes a single node tree

}

public HuffmanTree(String t, char nonLeaf) {

// Assumes t represents a post order representation of the tree as

// discussed //in class

// nonLeaf is the char value of the data in the non-leaf nodes //in

// classs we used (char) 128 for the non-leaf value

}

public HuffmanTree(HuffmanTree b1, HuffmanTree b2, char d) {

// makes a new tree where b1 is the left subtree and b2 is the right

// subtree //d is the data in the root

}

// use the move methods to traverse the tree //the move methods change the

// value of current

public void moveToRoot() {

}

public void moveToLeft() {

}

public void moveToRight() {

}

public void moveToParent() {

}

public boolean atLeaf() {

// returns true if current references a leave other wise returns false

}

public char current() {

// returns the data value in the node referenced by current

}

// the iterator returns the path (a series of 0s and 1s) to each leaf public

// class PathIterator implements Iterator {

public PathIterator() {

}

public boolean hasNext() {

}

public String next() {

}

public void remove() {

// optional method not implemented }

}

public Iterator iterator() { // return a PathIterator object

}

public String toString() {

// return a post order representation of the tree //using the format we

// discussed in class

}

} New Class

import java.io.*;

import java.util.*;

public class HuffmanEncode {

public HuffmanEncode(String in, String out) { // Implements the huffman

// encoding algorithm //Add

// private methods as needed

}

public static void main(String args[]) {

new HuffmanEncode(args[0], args[1]);

}

}

New Class

import java.io.*;

import java.util.*;

public class HuffmanDecode {

public HuffmanDecode(String in, String out) { // Implements the huffman

// decoding algorithm //Add

// private methods as needed

}

public static void main(String args[]) {

new HuffmanDecode(args[0], args[1]);

}

}