Can somone please help me implement the following 2 classes, HuffmanInputStream(
ID: 3728660 • Letter: C
Question
Can somone please help me implement the following 2 classes,
HuffmanInputStream() and HuffmanOutputStream()
Here are the following outlines for each class:
//IMPLEMENT HuffmanInputStream
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) throws IOException {
super(filename);
try {
tree = d.readUTF();
totalChars = d.readInt();
}
catch (IOException e) {
throw new IOException();
}
}
public String getTree() {
return tree;
}
public int getTotalChars() {
return totalChars;
}
}
//IMPLEMENT HuffmanOutputStream
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) {
}
}
}
Thank You!
Explanation / Answer
import java.io.*;
import java.util.*;
public class HuffmanEncode {
int totalCharacters;
public HuffmanEncode(String in, String out) {
//implements the huffman encoding algorithm
//add private methods as needed
PriorityQueue<Item> characterQueue = new PriorityQueue<>(128);
int[] characterArray = new int[128];
characterArray = readFile(in, characterArray);
//putting everything from array into priority queue
for (int i = 0; i < characterArray.length; ++i) {
if (characterArray[i] > 0) {
HuffmanTree temp = new HuffmanTree((char) i);
characterQueue.add(new Item(temp, characterArray[i]));
}
}
//popping two things from priority queue, merging them, then pushing that
//tree back onto the priority queue
while (characterQueue.size() > 1) {
char d = (char) 128;
Item item1 = characterQueue.poll();
Item item2 = characterQueue.poll();
HuffmanTree newTree = new HuffmanTree(item1.tree, item2.tree, d);
int newNum= item1.frequency + item2.frequency;
characterQueue.add(new Item(newTree, newNum));
}
HuffmanTree tree = characterQueue.poll().tree;
String[] encodingsArray = new String[128];
Iterator<String> iter = tree.iterator();
while (iter.hasNext()) {
String s = iter.next();
char c = s.charAt(0);
encodingsArray[(int) c] = s.substring(1, s.length());
}
HuffmanOutputStream outFile = new HuffmanOutputStream(out, tree.toString(), totalCharacters);
writeFile(in, outFile, encodingsArray);
}
public static void main(String args[]) {
new HuffmanEncode(args[0], args[1]);
}
private class Item implements Comparable {
HuffmanTree tree;
int frequency;
public Item(HuffmanTree t, int n) {
tree = t;
frequency = n;
}
public int compareTo(Object x) {
return frequency - (((Item) x).frequency);
}
}
private int[] readFile(String file, int[] array) {
//method to read in the characters from a file and find their frequencies
try {
FileReader fin = new FileReader(file);
BufferedReader reader = new BufferedReader(fin);
int character = reader.read();
//while not at end of file add one to that character in the array
while (character != -1) {
array[character]++;
totalCharacters++;
character = reader.read();
}
} catch (IOException e) {
System.out.println("IOException");
}
return array;
}
private void writeFile(String in, HuffmanOutputStream out, String[] array) {
try {
FileReader fin = new FileReader(in);
BufferedReader reader = new BufferedReader(fin);
int character = reader.read();
while (character != -1) {
//write the bits to file
for (int i = 0; i < array[character].length(); ++i) {
String s = array[character];
out.writeBit(s.charAt(i) - '0');
}
character = reader.read();
}
fin.close();
reader.close();
out.close();
}
catch (IOException e) {
System.out.print("IOException");
}
}
}
-----------------------------------------------------------------------------------------------------------------
import java.io.*;
import java.util.*;
public class HuffmanDecode {
public HuffmanDecode(String in, String out) {
HuffmanInputStream stream = new HuffmanInputStream(in);
int totalChars = stream.totalChars();
String huffmantree = stream.getTree();
//make a new huffman tree
HuffmanTree tree = new HuffmanTree(huffmantree, (char) 128);
try {
readFile(stream, tree, out);
} catch(FileNotFoundException e) {
System.out.println("FileNotFoundException");
}
}
private void readFile(HuffmanInputStream in, HuffmanTree tree, String out) throws FileNotFoundException { //have to read bits backwards
int charactercount = 0;
PrintWriter output = new PrintWriter(out);
while (charactercount < in.totalChars()) {
tree.moveRoot();
while (!tree.atLeaf()) {
int bit = in.readBit();
if (bit == 0) {
tree.moveLeft();
}
else { //bit == 0
tree.moveRight();
}
}
output.print(tree.current());
charactercount++;
tree.moveRoot();
}
output.close();
}
public static void main(String args[]) {
new HuffmanDecode(args[0], args[1]);
}
}
-----------------------------------------------------------------------------------------------------------------
import java.util.*;
public class HuffmanTree {
private class Node {
private Node left;
private char data;
private Node right;
private Node(Node L, char d, Node R) {
left = L;
data = d;
right = R;
}
}
private Node root;
private Node current;
public HuffmanTree() {
root = null;
current = null;
}
public HuffmanTree(char d) {
//make a one node tree
root = new Node(null, d, null);
}
public HuffmanTree(String t, char nonLeaf) {
//assumes t represents a post order representation of the tree
//where a node is either a leaf or has two children
//nonLeaf is the char value of the data in the non-leaf nodes
Stack<HuffmanTree> stack = new Stack();
for (int i = 0; i < t.length(); ++i) {
if (t.charAt(i) != nonLeaf) {
//push the one node tree onto the stack
stack.push(new HuffmanTree(t.charAt(i)));
}
else {
//pop two trees and merge them
HuffmanTree tree1 = stack.pop();
HuffmanTree tree2 = stack.pop();
HuffmanTree newtree = new HuffmanTree(tree2, tree1, nonLeaf);
stack.push(newtree);
}
}
root = stack.pop().root;
}
public HuffmanTree(HuffmanTree b1, HuffmanTree b2, char d) {
//merges b1 and b2
root = new Node(b1.root, d, b2.root);
}
public void moveRoot() {
current = root;
}
public void moveLeft() {
current = current.left;
}
public void moveRight() {
current = current.right;
}
public boolean atLeaf() {
if (current.left == null && current.right == null) {
return true;
}
else {
return false;
}
}
public char current() {
return current.data;
}
public class PathIterator implements Iterator<String> {
private LinkedList<String> list;
public PathIterator() {
list = new LinkedList<>();
encoding(root, "");
}
public boolean hasNext() {
if (list.size() != 0) {
return true;
}
return false;
}
public String next() {
return list.poll();
}
public void remove() {
//not implemented
}
private void encoding(Node r, String s) {
if (r.right == null && r.left == null) {
list.add(r.data + s);
return;
}
else {
encoding(r.left, s + "0");
encoding(r.right, s + "1");
}
return;
}
}
public Iterator<String> iterator() {
//return a PathIterator object
return new PathIterator();
}
public String toString() {
//return a post order representation of the tree
return toString(root);
}
private String toString(Node r) {
if (r == null) {
return "";
}
return toString(r.left) + toString(r.right) + r.data;
}
}
--------------------------------------------------------------------------------------------------------------
import java.io.*;
public class HuffmanOutputStream extends BitOutputStream {
int b;
int count;
public HuffmanOutputStream(String filename, String tree, int totalChars) {
super(filename);
try {
d.writeUTF(tree);
d.writeInt(totalChars);
b = 0;
count = 0;
}
catch(IOException e) {
System.out.print("IOException");
}
}
public void writeBit(int bit) {//bit math
b = b*2 + bit;
++count;
if (count == 8) {
//write byte
try {
d.write(b);
}
catch(IOException e) {
System.out.print("IOException");
}
b = 0;
count = 0;
}
}
public void close() {
if (count < 8) {
int value = count;
for (int i = value; i < 8; ++i) {
writeBit(0);
}
}
try {
d.close();
}
catch (IOException e) {
System.out.print("IOException");
}
}
}
------------------------------------------------------------------------------------------------------------------------
import java.io.*;
public class HuffmanInputStream extends BitInputStream{
private String tree;
private int totalChars;
private int bit;
private int count;
private int[] array;
int i;
public HuffmanInputStream(String filename) {
super(filename);
try {
tree = d.readUTF();
totalChars = d.readInt();
array = new int[8];
bit = d.readUnsignedByte();
for (int j = 7; j >= 0; --j) {
array[j] = bit%2;
bit = bit/2;
}
count = 0;
}
catch (IOException e) {
System.out.print("IOEXception");
}
}
public int readBit() {
if (count == 8) {
count = 0;
try {
bit = d.readUnsignedByte();
for (int j = 7; j >=0 ; --j) {
array[j] = bit%2;
bit = bit/2;
}
}
catch(IOException e) {
System.out.println("Input Stream IOException");
}
}
int retVal = array[count];
count++;
return retVal;
}
public String getTree() {
return tree;
}
public int totalChars() {
return totalChars;
}
public void close() {
try {
d.close();
}
catch (IOException e) {
System.out.print("IOException");
}
}
}
-------------------------------------------------------------------------------------------------------------
import java.io.*;
public abstract class BitOutputStream {
protected DataOutputStream d;
public BitOutputStream(String filename) {
try {
d = new DataOutputStream(new FileOutputStream(filename));
}
catch (IOException e) {
System.out.print("IOException");
}
}
public abstract void writeBit(int bit);
public abstract void close();
}
--------------------------------------------------------------------------------------------------------
import java.io.*;
public abstract class BitInputStream {
protected DataInputStream d;
public BitInputStream(String filename) {
try {
d = new DataInputStream(new FileInputStream(filename));
}
catch (IOException e) {
System.out.print("IOException");
}
}
public abstract int readBit();
public abstract void close();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.