Huffman application

The assigment is overdue now. I will up the price I am willing to pay to have it done. It must be completed by the latest on the 8th. However I would greatly preffer for it to be finished on the 7th. I will add $20 to the price if you can complete it by then.

I need the files to run in Eclipse. Please upload them as such. See my file as an example.

They must be coded in java.

This is for a 200 level data structures class so please match that level accordingly.

I need java Test cases and comments please. (see my example file)

I have included part of the previous assigment so you can see what mine looks like and it also may have things you may need like map etc. Though I cannot guarantee all of it is working properly. (named example)

—

The Task

Okay, we are finally going to finish off the Huffman application. Last week, we got to the point where we could build the tree and do some simple encoding and decoding. The problem with our technique is that we were converting text into Strings of 0s and 1s. Hopefully, the vast majority realized that this is the opposite of actual compression. Our goal was to reduce the number of bits required to encode a character. Instead, we blew it up, replacing one character with a whole String of them! Ouch.

So, we are going to do some bit level work, and learn how to write binary data out to files and read it back in again. The second issue that we have is that once we have an encoded file, we don’t have a good way to decode it without first having the original source file, which rather defeats the purpose of compressing the file in the first place. Thus, we need to store a copy of the tree in the coded file. Of course, we want to store the tree in a format we can read back out again, and also doesn’t take up too much room…

Background: Canonical form

We would like our Huffman codes to be canonical. I gave you an algorithm for picking which character to add next to your Huffman tree that comes close to producing canonical codes, but, sadly, I have to admit it has a flaw. There is an edge case that it can never compensate for. So, we are going to have to do some more work to get it into the canonical form.

The canonical form adds two rules to the way Huffman codes work. First, all codes of a given bit length have lexicographically consecutive values (i.e., not just in order, but immediately consecutive), in the same order as the symbols they represent, and second, shorter codes lexicographically precede longer ones. An example will make this a little clearer…

Suppose we have some piece of text in which the characters A,B,C,and D appear, with the following frequencies [A:1, B:5, C:6, D:2]. We could put these into a Huffman tree and come out with the following codes:

B01

001

000

This is not in canonical form. The first rule is broken because A comes before D, but 000 should precede 001. The second rule is broken because C had a shorter code than B, but 01 precedes 1 lexicographically. Here is an alternate assignment of codes that does satisfy the rule:

B10

110

111

0 precedes 10, which precedes 11x, and 110 and 111 are lexicographically consecutive.

The algorithm for deriving canonical codes is fairly straightforward, provided we start by knowing the lengths of the codes. The trick is to think of the codes as binary numbers. The first code, which is given to the lexicographically smallest symbol with the shortest code, is 0, padded out with 0s to be as long as the symbol’s code. In our example, C has the shortest code (length 1), so its code is 0 (if C’s code has been length three, the code would have been 000). We then increment the code (counting in binary), which will produce the lexicographically consecutive code. If the next symbol has a longer code, we pad the code with 0s to the right to match the code length (in other words, we perform a left shift or a multiply by 2). Thus, the next code would be 1, but B has a longer code length, so it gets the code 10. To move to A, we increment (11), and shift again to get 110. D has the same code length as A, so it gets 111.

Why is this interesting? Well, it means that we can recover the entire tree starting only from knowledge about the length of the codes. So, when we want to store our tree in a file with our data, we just have to record the character followed by the length of its code. Cool, huh?

Part one: Generate canonical codes [25 pts]

We can keep all of the work that we did in the last assignment, but the tree that we produce is no longer the tree that we want to keep. Its sole purpose is to provide us with the initial code lengths for generating the canonical codes. Instead of traversing the tree and loading the reverse lookup into a map, you are going to traverse the tree and collect symbols and their code lengths, dumping them into a new priority queue as we go. I suggest tweaking your old wrapper class that held symbols and frequencies to be a more generic pairing of counts and symbols, so you can reuse it for symbols and code lengths (this is probably just some renaming to make it more general purpose). You will want to write a new Comparator that will return these items to you in order first by code length (shortest first) and then in lexicographic order (a to z).

You should then write a new private method called buildTreeFromMap which takes in a PriorityQueue of your wrapper objects as an argument. In this method you will use the PriorityQueue to implement the above algorithm to build the Huffman tree (which the algorithm I provided just specifies the codes, you will want to build up into a tree that represents the given code words). The tree that results from this process is the one to save as an instance variable (for decode). Now is when you will build the Map that you need for encode (you should be able to reuse the code you had for building it before). The old buildTreeFromFileshould obviously call buildTreeFromMap once it has built the code length map.

Part two: File handling [40 pts]

We can finally get to the actual application! The first step will be to encode the file. Start by making one additional tweak to buildFromFile that saves the File object in an instance variable. Write a new function called saveCompressedFile, which will take a single File object as an argument. This file will be the destination for the compressed file. This function will first write the tree representation to the destination file. Start by writing an integer that says how many character, code lengths pairs to expect (this tells the reader how many bytes of the file are consumed by the tree). Then write out each character followed by the length of its code. Following the tree, you can start writing the compressed data from the file. This works just like encode, walking character by character, except that you will want to write bits, rather than Strings holding 0s and 1s (we’ll talk about this in class).

You will then want to write the compliment to this. The difference here, however, is that we don’t have the original source data to build the tree again. So I want you to write a second static factory method called newTreeFromCompressedFile. Like newTreeFromFile, this will create a new HuffmanTree object and then call a private instance method called buildFromCompressedFile, to which it passes the compressed file. This should read the tree description out of the file, dumping the symbols and code lengths into a priority queue as it reads. It should then call buildTreeFromMap to initialize the tree and the reverse lookup map.

Finally, write a method called saveExpandedFile, which takes in a destination File and processes the original file, using the tree to decode the data.

If you encounter errors in either compressing or decompressing with respect to unknown codes, throw a CharConversionException.

A little help

To help you get started, here is a skeleton of the HuffmanTree that includes som of the old functionality from the last homework: — huffmanTree — see attatched

—

Java Tests needed

The assignment info from the previous assignment is attatched. It explains how other things such as map are supposed to be built.

Huffman tree skeleton is also attatched.

1/1/13 10:08 PM

Page 1 of 3http://web.cs.mtholyoke.edu/~candrews/cs211/examples/HuffmanTree.html

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Comparator;
import java.util.Scanner;
import java.util.Set;

/**
* This class implements the basic functionality of Huffman compression and expansion.

*
* @author C. Andrews
*
*/
public class HuffmanTree {
Map _lookupTable = new BSTMap();
BinaryTree _huffmanTree;

/**
* This is a factory method for reading in a fresh text file to initialize the Huffman tree.
*
* @param file the document to use for the code frequencies
* @return a HuffmanTree containing the Huffman codes based on the frequencies observed in the document
* @throws FileNotFoundException
*/
public static HuffmanTree newTreeFromFile(File file) throws FileNotFoundException{
HuffmanTree tree = new HuffmanTree();
tree.buildFromFile(file);
return tree;

}

/**
* This is a factory method that builds a new HuffmanTree from a compressed file.
*
* @param file a file that has been compressed with a Huffman tool
* @return a new HuffmanTree containing the codes for decoding the file
* @throws FileNotFoundException
*/
public static HuffmanTree newTreeFromCompressedFile(File file) throws FileNotFoundException{
// TODO implement this
}

/**
* This method builds the Huffman tree from the input file.
*
* @param file the file to use to construct the Huffman tree
* @throws FileNotFoundException
*/
private void buildFromFile(File file) throws FileNotFoundException {

// read file and build the map of the character frequencies
Map freqMap = new BSTMap();
Scanner scanner = new Scanner(file);
scanner.useDelimiter(“”);
String character;

while (scanner.hasNext()){
character = scanner.next();

Integer count = freqMap.get(character);
if (count == null){
count = Integer.valueOf(0);
}

freqMap.put(character, count+1);

}

// for each key, make a tree and load it into the priority queue
PriorityQueue> treeQueue = new PriorityQueue>(freqMap.keySet().size(), new CountPairTreeComparator
BinaryTree tmpTree;

for (String key: freqMap.keySet()){
int frequency = freqMap.get(key);
tmpTree = new BinaryTree(null, new CountPair(key, frequency), null);
treeQueue.add(tmpTree);
}

// while the size of the priority queue is greater than 1, combine the top items into a tree and put them back in the priority queue
BinaryTree tree1, tree2;
int newFrequency;

1/1/13 10:08 PM

Page 2 of 3http://web.cs.mtholyoke.edu/~candrews/cs211/examples/HuffmanTree.html

String newText;
while (treeQueue.size() > 1){
tree1 = treeQueue.remove();
tree2 = treeQueue.remove();
// If the height of the second tree is less than the height of the first,
// or the heights are the same and tree2 precedes tree1 alphabetically, swap them so
// the smaller/earlier tree is put on the left
if (tree1.getValue()._text.length() > tree2.getValue()._text.length()
||( tree1.getValue()._text.length() == tree2.getValue()._text.length()
&& tree1.getValue()._text.compareTo(tree2.getValue()._text) > 0)){
tmpTree = tree1;
tree1 = tree2;
tree2 = tmpTree;
}

// create a new tree combining the two smaller trees, computing a new frequency that is the sum of the
// children frequencies and a new text that is the appended combination of the children’s text
newFrequency = tree1.getValue()._count + tree2.getValue()._count;
newText = tree1.getValue()._text + tree2.getValue()._text;
tmpTree = new BinaryTree(tree1, new CountPair(newText, newFrequency), tree2);
treeQueue.add(tmpTree);
}

// pull the completed tree from the priority queue
BinaryTree tree = treeQueue.remove();

// create map of symbols to code lengths using the tree
Map codeLengthMap = new Map();
// TODO implement this part

buildTreeFromMap(codeLengthMap);

}

/**
* Builds the tree using information found in a compressed file.
*
* The table is the first thing we find in the file. The first piece of data is the length
* of the table (L). This is followed by L pairs of character and code length pairs.
*
* @param file the file to read the Huffman code from.
*/
private void buildFromCompressedFile(File file) throws FileNotFoundException{
// TODO implement this
}

/**
* Read the original file and compress it using the Huffman codes, writing the result
* into the output file.
*
* @param outputFile the output file
*/
public void saveCompressedFile(File outputFile){
// TODO implement this
}

/**
* Read the compressed file that initialized this object and write the decoded version out
* into the output file.
*
* @param outputFile the destination file for the uncompressed file.
*/
public void saveExpandedFile(File outputFile){
// TODO implement this
}

/**
* This method reads in a String of text and returns a String of 0s and 1s corresponding to the Huffman code stored in this tree.
* @param text the text to be encoded
* @return a String representation of the Huffman code
*/
public String encode(String text){
StringBuilder builder = new StringBuilder();
String tmp;
for (int i =0; i < text.length(); i++){ tmp = _lookupTable.get(String.valueOf(text.charAt(i))); builder.append(tmp); }

1/1/13 10:08 PM

Page 3 of 3http://web.cs.mtholyoke.edu/~candrews/cs211/examples/HuffmanTree.html

return builder.toString();
}

/**
* This method reads in a String representation of a Huffman code corresponding to this Huffman tree and decodes it.
* @param text a String representation of the a Huffman coded message
* @return the original text
*/
public String decode(String text){
StringBuilder builder = new StringBuilder();

BinaryTree current = _huffmanTree;
for (int i =0; i < text.length(); i++){ char c = text.charAt(i);

if (c == ‘0’){
current = current.getLeft();
}else if (c == ‘1’){
current = current.getRight();
}else{
throw new RuntimeException(“Encountered unexpected character in coded String”);
}

if (current.isLeaf()){
builder.append(current.getValue()._text);
current = _huffmanTree;
}

}
return builder.toString();
}

private class CountPair{
int _count;
String _text;

private CountPair(String text, int count){
_text = text;
_count = count;
}
}

private class CountPairTreeComparator implements Comparator>{

@Override
public int compare(BinaryTree t1, BinaryTree t2) {
CountPair p1 = t1.getValue();
CountPair p2 = t2.getValue();

if (p1._count != p2._count){
return p2._count – p1._count;
}else if (p1._text.length() != p2._text.length()){
return -p1._text.length() – p2._text.length();
} else{
return p1._text.compareTo(p2._text);
}
}

}

1/1/13 10:10 PMCS 211 Homework Seven — Fall 2012

Page 1 of 3http://web.cs.mtholyoke.edu/~candrews/cs211/homework/hw7.html

CS 212 — Homework Seven
Huffman Codes

Due: 13 November 2012, 11:59p

Worth: 90 points

The Task

This week you are going to implement a new data structure and the main Huffman tree. Next week we
will finish this off with a full application for compressing and decompressing text files.

Part one: PriorityQueue [20 pts]

As I said in class, I redesigned final product of this project, so we need to redo the PriorityQueue and the
Heap. This is actually good practice for you because refactoring code to meet changing specifications is a
common occurrence in software development. We basically want to have a different level of control, so
we are going to change our classes to be closer to the PriorityQueue provided in the Java API. The new
interface for PriorityQueue looks like this:

public PriorityQueue(int initialCapacity,Comparator comparator)
This is the constructor. It should initialize the heap using the initialCapacity. The comparator is the tool that will
allow us to change how priority is calculated for various inputs.

public E peek()
This returns the next item without removing it. This returns null if the queue is empty.

E remove()
This removes the first item from the queue.

void add(E item)
This adds item to the queue

boolean isEmpty()
Obviously, this says if the queue is empty or not.

int size()
This should return the size of the queue.

The main difference is the addition of the Comparator. Comparators are classes that provide the same
functionality as compareTo(). You will use this instead of the compareTo method for comparing items in the
queue. We can write different comparators to give us high value priority, low value priority, or more
complex variations (which is why we need to do this).

Doing this will mean that the wrapper class you wrote for the last assignment is no longer needed, the
priority will be supplied in a different way. You may be wondering about the Comparator. We
are specifying that our Comparator is capable of comparing two objects of type E. The ? says that it can
compare two Es, or E is a subclass of the class that the Comparator can handle.

You will, of course, need to adjust the Heap as well to work with this new PriorityQueue. Add the
Comparator to the constructor and update siftup and siftdown to use it. Also, write two static, public
inner classes on the Heap called MaxHeapComparator and MinHeapComparator. These comparators will provide
the normal functionality of min and max by calling the compareTo methods on the stored items (i.e., they
will only work for objects that implement Comparable.

Part two: Map [30 pts]

Next, we need a new data structure. We are going to build this in two pieces so that we can reuse the

http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html

1/1/13 10:10 PMCS 211 Homework Seven — Fall 2012

Page 2 of 3http://web.cs.mtholyoke.edu/~candrews/cs211/homework/hw7.html

interface later. So, the first this you should build is an interface called Map,V>.
The interface should look like this:

void put(K key, V value)
This should load the value value into the map at the location associated with the key, replacing any preexisting value
already associated with the key.

V get(K key)
This should fetch the value V associated with the key key, or null, if no match can be found.

boolean containsKey(K key)
This will report if there is a value associated with the value key in the map.

V remove(K key)
This method should remove the entry associated with key and return the associated value. Return null if the key is
not found.

Set keySet()
This method should return a Set of all available keys in the map. You may use the java.util.TreeSet class to return
these. You can build these on the fly using a traversal, or collect them as new keys are added to the map.

Of course, since this is just the interface, you will need to implement an actual instance so that you can
use it. This instance should be called BSTMap. Obviously, this will use a binary search tree to actually
implement the methods described above. While one perfectly valid implementation choice would be to
create a separate binary search tree class and just use it to implement the described methods, it can
force you to jump through some hoops to make methods like get and containsKey to work properly. So
instead, you can build the binary search tree structure directly into your implementation of BSTMap.

When constructing the underlying BST, you will need to create some form of node structure that will hold
both the key and the value. You will, of course, need to adjust the pseudocode that we walked through in
class to work directly with the key values. It is important that these nodes are not visible outside of the
class. The other major aspect of this design is whether you use an array or links in the nodes to
implement the actual tree. I encourage you to use the linked version as we will be building on this class
later and will want it to be easy to move nodes around.

Part three: The Huffman tree [40 pts]

Once you have built your map, you will have enough tools to actually build the Huffman tree. The tree
should be in a class called HuffmanTree. The interface should look like this:

static HuffmanTree newTreeFromFile(File file)
This is a static factory method that creates a new Huffman tree. In essence, this just creates the new object and
calls buildFromFile on it. This should throw a FileNotFoundException when appropriate.

private void buildFromFile(File file)
This reads in an unencoded file and builds the Huffman tree based on the character frequencies. This should throw a
FileNotFoundException when appropriate.

String encode(String text)
This method takes in some plain text and returns the encoded version as a String of 1’s and 0’s.

String decode(String text)
This method takes in a String of 1’s and 0’s and returns a decoded raw text version.

For this assignment I am introducing you to a new Java design pattern called the “factory method”.
Factory methods are methods (usually static) that return new instances of a class. We typically use them
when there is some complex initialization that needs to be performed or we have more than one way in
which we want an object to be created. In this case, we are paving the way for future development. The
factory method should just create a new HuffmanTree and then call buildFromFile on it.

To actually build the tree, you should start by reading the seed file one character at a time, using the Map
to keep track of the frequencies of each character. Once the file has been consumed, you will use your
PriorityQueue to to build the Huffman tree.

You will want to create a private inner node class that holds a frequency and a String. Since we want to
assemble everything into a binary tree structure (it will be a heap, but we won’t use the Heap class for it),
also include left and right children. Call this class HTree. Write a constructor that sets all of the fields at

1/1/13 10:10 PMCS 211 Homework Seven — Fall 2012

Page 3 of 3http://web.cs.mtholyoke.edu/~candrews/cs211/homework/hw7.html

once.

For each character you read in, create an HTree wrapper for it and its frequency and put it in the
PriorityQueue. The general algorithm for building the Huffman tree goes like this:

Remove the two trees with the lowest frequency from the queue
Use these two trees as the left and right children of a new tree with a root node that has the
frequency of the two children combined.
Return this tree to the queue
Repeat until there is only one tree — this is the Huffman tree

To make this work, you will want to write a Comparator that uses the lowest frequency as the highest
priority. Unfortunately, this algorithm does not create unique trees. We would like to build a canonical
Huffman tree. In order to do that, we will add some more rules. When we have two trees that have the
same frequency, we will take the shorter one first. When we have two trees of the same complexity and
the same length, we will use alphabetical order to determine priority (e.g., ‘a’ comes before ‘b’). In
addition, when we build our subtrees, the shorter tree goes on the left. If the trees are the same length,
the first alphabetically goes of the left (note that this is true regardless of frequency).

Once the tree is fully constructed, you should create a second map that stores the final codes for each
character. The tree and this map should be the two data structures that you keep around after the
construction process. For encoding, you will use the map to lookup each character, and for decoding, you
will use the tree to find the decoded characters.

I want you to notice that the two methods, encode and decode are really only for testing. They transform
the data into Strings of 1s and 0s, which is certainly not a compressed form for the data.

Turning the assignment in…

Commented source files and tests should be put into a single directory, zipped, tarred or jarred, and
submitted online into your course dropbox on ella (I only want source files, I do not want any class files).
Please name your files cs211_pid_hw7.suffix, where pid is your Mount Holyoke email account name and
suffix is the appropriate suffix for your archive format.

Last modified: Mon Dec 17 17:11:21 EST 2012

META-INF/MANIFEST.MF
Manifest-Version: 1.0

.classpath

PriorityQueue.class
public synchronized class PriorityQueue {
Heap q;
public void PriorityQueue(int, java.util.Comparator);
public Object peek();
public Object remove();
void add(Object);
boolean isEmpty();
public int size();
}

PriorityQueue.java
PriorityQueue.java
import
java
.
util
.
Comparator
;

public

class

PriorityQueue
< E >

{

Heap
q
;

/**

*PriorityQueue initializes the queue.

*
@param
initialCapacity an int that is the heaps initial size.

*
@param
comparator the priority of various imputs.

public

PriorityQueue
(
int
initialCapacity
,
Comparator

comparator
){

q
=

new

Heap
(
initialCapacity
,
comparator
);

}

/**

* Peek, returns the next item in the queue without removing it.

* If it is empty then null is returned.

*
@return
the next item in the queue.

public
E peek
(){

if
(
q
.
size
()
==
0
){

return

null
;

}

return

(
E
)
q
.
findMax
();

}

/**

* This removes the first item from the queue.

* It returns null if the queue is empty.

*
@return
the first item in the queue.

public
E remove
(){

if
(
q
.
size
()
==
0
){

return

null
;

}

return

(
E
)
q
.
removeMax
();

}

/**

* This adds item to the queue

*
@param
item that is added to the queue.

void
add
(
E item
){

q
.
insert
(
item
);

}

/**

* isEmpty returns if the queue is empty or not.

*
@return
boolean if the queue is empty or not.

boolean
isEmpty
(){

if
(
q
.
size
()
!=

0
){

return

false
;

}

return

true
;

}

/**

* size returns the size of the queue.

*
@return
int the size of the queue.

public

int
size
(){

return
q
.
size
();

}

ArithmeticExpression.class
public synchronized class ArithmeticExpression {
BinaryTree t;
java.util.ArrayList list;
String equation;
void ArithmeticExpression(String) throws java.text.ParseException;
public String toString(BinaryTree);
public String toPostfixString(BinaryTree);
void setVariable(String, int) throws java.rmi.NotBoundException;
public int evaluate(BinaryTree);
}

ArithmeticExpression.java
ArithmeticExpression.java
import
java
.
rmi
.
NotBoundException
;

import
java
.
text
.
ParseException
;

import
java
.
util
.
ArrayList
;

import
java
.
util
.
Stack
;

/**

* ArithmeticExpression takes equations in the form of strings creates a binary

* tree, and can return either the regular or postfix equation. It also allows

* them to be calculated.

* Extra Credit:

* ** it can handle spaces or no spaces in the string inputted. ** it can return

* regular or postfix notation

*
@author
tai-lanhirabayashi

public

class

ArithmeticExpression

{

BinaryTree
t
;

ArrayList
list
;

String
equation
;

/**

* ArithmeticExpression is the construction which takes in a space

* delimitated equation containing “*,/,+,-” symbols and converts it into a

* binary tree.

* If the expression is not valid it will throw a ParseException. This is

* the constructor. It will take a String containing the expression.

* ** The equation can take in stings delimitated by spaces, or withot any

* spaces. If it contains a mix, then the non spaced part(s) will be

* considered to be a variable.

*
@param
expression

*
@throws
ParseException

* if the string is not a valid equation

@
SuppressWarnings
({

“unchecked”
,

“rawtypes”

})

ArithmeticExpression
(
String
expression
)

throws

ParseException

{

//hold the string globally

equation
=
expression
;

//create a new arrayList to be used globally that holds the variables

list
=

new

ArrayList
();

//split the string

String
[]
s
=
expression
.
split
(
” ”
);

// create a stack of tree’s and operators

Stack
tree
=

new

Stack
();

Stack
operator
=

new

Stack
();

//create the string Next

String
next
=

“”
;

// if the string expression doesnt contain spaces

if

(
!
expression
.
contains
(
” ”
))

{

int
i
=

0
;

//if it starts with an operator throw an error this cannot be.

if

(
expression
.
charAt
(
0
)

==

‘+’

||
expression
.
charAt
(
0
)

==

‘*’

||
expression
.
charAt
(
0
)

==

‘-‘

||
expression
.
charAt
(
0
)

==

‘/’
)

{

System
.
out
.
println
(
“this equation starts with a operator.”
);

throw

new

ParseException
(
expression
,

0
);

}

// if the expression ends with an operator throw an error this cannot be.

if

(
expression
.
charAt
(
expression
.
length
()

–

1
)

==

‘+’

||
expression
.
charAt
(
expression
.
length
()

–

1
)

==

‘*’

||
expression
.
charAt
(
expression
.
length
()

–

1
)

==

‘-‘

||
expression
.
charAt
(
expression
.
length
()

–

1
)

==

‘/’
)

{

System
.
out
.
println
(
“this equation ends with a operator.”
);

throw

new

ParseException
(
expression
,
expression
.
length
());

}

//go through each characer in the expression and see if its a number/variable, or operator.

while

(
i
< expression . length ()) { if ( expression . charAt ( i ) == '+' || expression . charAt ( i ) == '*' || expression . charAt ( i ) == '-' || expression . charAt ( i ) == '/' ) { // if the character is a operator add a space to the begining and front and add it to the "next" string String str = String . valueOf ( expression . charAt ( i )); next = next + " " + str + " " ; } else { // if its an operator add it to the end of the "next" string. next = next + expression . charAt ( i ); } // increase i to move to the next character. i ++ ; } // split the new string with added spaces. s = next . split ( " " ); } // if the string still doesnt exist throw the error. if ( s . length == 0 ) { System . out . println ( "there has been an error. You have not entered a string with any characters" ); throw new ParseException ( expression , 0 ); } // make sure there arent two operators in a row. for ( int i = 0 ; i < s . length ; i ++ ) { if ( i >=

1

&&

(
s
[
i
].
equals
(
“+”
)

||
s
[
i
].
equals
(
“-”
)

||
s
[
i
].
equals
(
“*”
)

||
s
[
i
].
equals
(
“/”
)))

{

if

(
s
[
i
–

1
].
equals
(
“+”
)

||
s
[
i
–

1
].
equals
(
“-”
)

||
s
[
i
–

1
].
equals
(
“*”
)

||
s
[
i
–

1
].
equals
(
“/”
))

{

System
.
out

.
println
(
“there were two operators in a row. The equation is not valid.”
);

throw

new

ParseException
(
expression
,
i
);

}

// check to make sure there arent two operands in a row in the String[]

if

(
i
>=

1

&&

(
s
[
i
].
equals
(
“+”
)

==

false

&&
s
[
i
].
equals
(
“-”
)

==

false

&&
s
[
i
].
equals
(
“*”
)

==

false

&&
s
[
i
].
equals
(
“/”
)

==

false
))

{

if

(
s
[
i
–

1
].
equals
(
“+”
)

==

false

&&
s
[
i
–

1
].
equals
(
“-”
)

==

false

&&
s
[
i
–

1
].
equals
(
“*”
)

==

false

&&
s
[
i
–

1
].
equals
(
“/”
)

==

false
)

{

System
.
out

.
println
(
“there were two operands in a row. The equation is not valid.”
);

throw

new

ParseException
(
expression
,
i
);

}

// if its a number create a new tree node, and add it to the tree stack

if

(
s
[
i
].
equals
(
“+”
)

==

false

&&
s
[
i
].
equals
(
“-”
)

==

false

&&
s
[
i
].
equals
(
“*”
)

==

false

&&
s
[
i
].
equals
(
“/”
)

==

false
)

{

BinaryTree
o
=

new

BinaryTree
(
null
,
s
[
i
],

null
);

tree
.
add
(
o
);

}

else

if

(
operator
.
empty
()

||
s
[
i
].
equals
(
“*”
)

||
s
[
i
].
equals
(
“/”
))

{

//if its a * or / symbol hold it to ensure order of operation

operator
.
push
(
s
[
i
]);

}

else

{

//group the tree’s together.

while

(
operator
.
empty
()

==

false
)

{

String
operatorHeld
=

(
String
)
operator
.
pop
();

BinaryTree
one
=

(
BinaryTree
)
tree
.
pop
();

BinaryTree
two
=

(
BinaryTree
)
tree
.
pop
();

BinaryTree
n
=

new

BinaryTree
(
one
,
operatorHeld
,
two
);

tree
.
push
(
n
);

}

operator
.
push
(
s
[
i
]);

}

// at the end ensure that the operator is empty.

while

(
operator
.
empty
()

==

false
)

{

String
operatorHeld
=

(
String
)
operator
.
pop
();

BinaryTree
one
=

(
BinaryTree
)
tree
.
pop
();

BinaryTree
two
=

(
BinaryTree
)
tree
.
pop
();

BinaryTree
n
=

new

BinaryTree
(
one
,
operatorHeld
,
two
);

tree
.
push
(
n
);

}

//if there is more than 1 tree at the end something went wrong

// this should not occur as it should have been caught earlier

// this is just to ensure completeness.

if

(
tree
.
size
()

>=

2
)

{

System
.
out

.
println
(
“this expression is invalid. There were more operands than operators.”
);

System
.
out

.
println
(
“this should not occur it should have been caught earlier”
);

while

(
tree
.
empty
()

==

false
)

{

return
;

}

//if there are still operators there is something wrong

// this should not occur as it should have been caught earlier

// this is just to ensure completeness.

if

(
operator
.
empty
()

==

false
)

{

System
.
out

.
println
(
“this should not occur it should have been caught earlier.”
);

System
.
out

.
println
(
“there were too many operators in the string the program cannot continue.”
);

{

return
;

}

// set the tree globally

t
=

(
BinaryTree
)
tree
.
pop
();

}

/**

* toString returns the String equation of that the passed in binary tree

* represents.

*
@param
tree

* that represents an equation

*
@return
the String that is represented by the passed in BinaryTree.

@
SuppressWarnings
(
“rawtypes”
)

public

String
toString
(
BinaryTree
tree
)

{

// if its a leaf return its value

if

(
tree
.
isLeaf
()

==

true
)

{

return

(
String
)
tree
.
getValue
();

}

else

{

//else combine each parent child combination

//call recursively, and contain each call in parenthesis.

String
s
=

(
“(”

+
toString
(
tree
.
getLeftChild
())

+
tree
.
getValue
()

+
toString
(
tree
.
getRightChild
())

+

“)”
);

return
s
;

}

/**

* toPostfixString returns the string containing the parsed expression in

* postFix notation with spaces between numbers and operators to ensure clarity.

*
@param
tree that represents an equation

*
@return
the String that is represented by the passed in BinaryTree in

* postfix form.

@
SuppressWarnings
(
“unchecked”
)

public

String
toPostfixString
(
BinaryTree
tree
)

{

//if its a leaf return its value

if

(
tree
.
isLeaf
()

==

true
)

{

return

(
String
)
tree
.
getValue
();

}

else

{

//otherwise call recursively down the tree

// and add the operator to the end of the two operands.

// also add spaces to allow numbers to be seen individually.

String
s
=
toPostfixString
(
tree
.
getRightChild
())

+

” ”

+
toPostfixString
(
tree
.
getLeftChild
())

+

” ”

+
tree
.
getValue
();

System
.
out
.
println
(
“this is what s is ”

+
s
);

return
s
;

}

/**

* This allows the user to set a value for a variable in the expression. If

* the variable does not exist in the function, throw a NotBoundException.

*
@param
name of the variable

*
@param
value that the variable has

*
@throws
NotBoundException if the variable is not used in the equation

void
setVariable
(
String
name
,

int
value
)

throws

NotBoundException

{

//Note var, is not a Var it is a seperate class that is an object.

//if the equation string doesnt contain the variable throw an error

if

(
!
equation
.
contains
(
name
))

{

throw

new

NotBoundException
();

}

// else continue and check if the var object is already in the list

for

(
int
i
=

0
;
i
< list . size (); i ++ ) { var v = ( var ) list . get ( i ); if ( v . getName (). equals ( name )) { //if so change the value of the var object v . setValue ( value ); return ; } } // otherwise add the var object to the list. list . add ( new var ( name , value )); } /** * Evaluate returns the integer result of the expression. * * Variables that are not declared are calculated at 0. * * @return the value of the equation */ @ SuppressWarnings ( "unused" ) public int evaluate ( BinaryTree tree ) { //if it is a leaf if ( tree . isLeaf () == true ) { String s = ( String ) tree . getValue (); //if all characters are numbers simply skip down to return the integer value. for ( int i = 0 ; i < s . length (); i ++ ) { if ( s . charAt ( i ) == '0' || s . charAt ( i ) == ( '1' ) || s . charAt ( i ) == '2' || s . charAt ( i ) == '3' || s . charAt ( i ) == '4' || s . charAt ( i ) == '5' || s . charAt ( i ) == '6' || s . charAt ( i ) == '7' || s . charAt ( i ) == '8' || s . charAt ( i ) == '9' ) { } else { //if there are non numeric characters check if the list has their values for ( int j = 0 ; j < list . size (); j ++ ) { var h = ( var ) list . get ( j ); if ( h . getName (). equals ( s )) { return h . getValue (); } } //otherwise tell the user that this variable cannot be found and that its value is calulated at 0 System . out . println ( "this variable " + s + " cannot be found! Its value will be 0." ); return 0 ; } return Integer . parseInt (( String ) tree . getValue ()); } } //find the left and right values of the tree int left = evaluate ( tree . getLeftChild ()); int right = evaluate ( tree . getRightChild ()); //calculate appropriately. if ( tree . getValue (). equals ( "*" )) { return left * right ; } else if ( tree . getValue (). equals ( "/" )) { return left / right ; } else if ( tree . getValue (). equals ( "+" )) { return left + right ; } return left - right ; } } Map.class public synchronized class Map { BSTMap root; BSTMap found; java.util.TreeSet set; public void Map(); public void put(Comparable, Object); public Object get(Comparable); public boolean containsKey(Comparable); private BSTMap getBSTMap(Comparable); public Object remove(Comparable); private BSTMap sucessor(BSTMap); public java.util.Set keySet(); } Map.java Map.java import java . util . Set ; import java . util . TreeSet ; public class Map < K extends Comparable < K >
,
V
>

{

BSTMap
root
;

BSTMap
found
;

TreeSet
< K >
set
;

/**

* Map initializes the map.

public

Map
(){

set
=

new

TreeSet
< K >
();

root
=
null
;

found
=
null
;

}

/**

* put loads the Key and value into a BSTMap object, and the key into the set.

* If the key already exists the value is changed to the new value.

*
@param
key the K key value

*
@param
value the V value value

public

void
put
(
K key
,
V value
){

//if the root is null this is the root

if
(
root
==
null
){

root
=

new

BSTMap
(
key
,
value
);

set
.
add
(
key
);

//if the key exists then change the value

}
else

if
(
get
(
key
)
!=
null
){

getBSTMap
(
key
).
obj
.
value
=
value
;

}
else
{

//otherwise create a new BSTMap

BSTMap
i
=

new

BSTMap
(
key
,
value
);

//add it to the set

set
.
add
(
key
);

//and find its place in the BSTmap tree.No key can be identical.

boolean
done
=

false
;

BSTMap
c
=
root
;

while
(
done
==
false
){

//if it is bigger go right

if
(
key
.
compareTo
((
K
)
c
.
obj
.
getKey
())
>=
0
){

if
(
c
.
getRight
()
==
null
){

c
.
setRight
(
i
);

done
=
true
;

}
else
{

c
=
c
.
getRight
();

}

//if it is smaller go left.

}
else

if
(
key
.
compareTo
((
K
)
c
.
obj
.
getKey
())
< 0 ){ if ( c . getLeft () == null ){ c . setLeft ( i ); done = true ; } else { c = c . getLeft (); } } } } } /** * This finds the value associated with they key. If this key cannot be found null is returned. * @param key the K key value * @return V the associated V value. */ public V get ( K key ){ BSTMap current = root ; if ( root == null ){ return null ; } while ( current != null && current . obj . getKey (). equals ( key ) == false ){ if ( key . compareTo (( K ) current . obj . getKey ()) < 0 ){ current = current . getLeft (); } else { current = current . getRight (); } } if ( current == null ){ return null ; } if ( current . obj . getKey (). equals ( key )){ return ( V ) current . obj . getValue (); } return null ; } /** *containsKey returns boolean if the key exists in the map. * @param key the K key value to look for * @return boolean if it exists */ public boolean containsKey ( K key ){ BSTMap current = root ; if ( root == null ){ return false ; } while ( current != null && current . obj . getKey (). equals ( key ) == false ){ if ( key . compareTo (( K ) current . obj . getKey ()) < 0 ){ current = current . getLeft (); } else { current = current . getRight (); } } if ( current == null ){ return false ; } return current . obj . getKey (). equals ( key ); } /** * getBSTMap returns the BSTMap associated with a key value * @param key the K key value * @return BSTMap contained the K key. */ private BSTMap getBSTMap ( K key ){ BSTMap current = root ; if ( root == null ){ return null ; } while ( current != null && current . obj . getKey (). equals ( key ) == false ){ if ( key . compareTo (( K ) current . obj . getKey ()) < 0 ){ current = current . getLeft (); } else { current = current . getRight (); } } if ( current . obj . getKey (). equals ( key )){ return current ; } return null ; } /** * remove removes the BSTMap associated with they key, and returns its associated value. * * If the key cannot be found null is returned * @param key the K key value to be found * @return V the value of associated with the BSTMap containing the K key value. */ public V remove ( K key ){ if ( root == null ){ return null ; } else if ( root . obj . getKey (). equals ( key )){ System . out . println ( "the node to remove is the root." ); V val = ( V ) root . obj . getValue (); if ( root . isLeaf ()){ root = null ; } else if ( root . getLeft () == null ){ root = root . getRight (); } else if ( root . getRight () == null ){ root = root . getLeft (); } else { root = sucessor ( root ); } return val ; } BSTMap n = getBSTMap ( key ); if ( n == null ){ return null ; } else { set . remove ( key ); V a = ( V ) n . obj . getValue (); BSTMap temp = null ; BSTMap child = null ; if ( n . isLeaf ()){ temp = n ; n = null ; } else if ( n . getLeft () != null && n . getLeft (). getRight () == null ){ temp = n ; n . getLeft (). setRight ( n . right ); n . setLeft ( null ); } else if ( n . getRight () != null && n . getRight (). getLeft () == null ){ temp = n ; n . getRight (). setLeft ( n . getLeft ()); n . setRight ( null ); } else { temp = sucessor ( n ); n . setRight ( null ); } System . out . println ( "this is the temp:" + temp . obj . key ); if ( temp . getLeft () != null ){ child = temp . getLeft (); } else { child = temp . getRight (); } if ( child != null ){ child . parent = temp . parent ; } if ( temp . parent . getLeft () == temp ){ temp . parent . setLeft ( child ); } else { temp . parent . setRight ( child ); } return a ; } } private BSTMap sucessor ( BSTMap n ){ boolean running = true ; BSTMap current = n . getRight (); while ( running ){ if ( current . getLeft () != null ){ current = current . getLeft (); } else { running = false ; } } return current ; } /** * keySet returns a Set of the K key values in the map. * @return */ public Set < K >
keySet
(){

return
set
;

}

BinaryTree.class
public synchronized class BinaryTree {
Object v;
BinaryTree treeLeft;
BinaryTree treeRight;
void BinaryTree(BinaryTree, Object, BinaryTree);
BinaryTree getLeftChild();
BinaryTree getRightChild();
void setLeftChild(BinaryTree);
void setRightChild(BinaryTree);
void setValue(Object);
Object getValue();
boolean isLeaf();
}

BinaryTree.java
BinaryTree.java

/**

* BinaryTree is a form of linked nodes that form a tree.

*
@author
tai-lan hirabayashi

*
@param
the object value that is within each node.

public

class

BinaryTree
< E >

{

E v
;

BinaryTree
< E >
treeLeft
;

BinaryTree
< E >
treeRight
;

/**

* BinaryTree creates a new node binaryTree which holds an object value.

* It takes in the value, left and right child and holds them within the node.

*
@param
left the left child of the node.

*
@param
value the object the node holds

*
@param
right the right child of the node

BinaryTree
(
BinaryTree
< E >
left
,
E value
,

BinaryTree
< E >
right
){

v
=
value
;

treeLeft
=
left
;

treeRight
=
right
;

}

/**

* getLeftChild returns the left child node.

*
@return
the left child, a binary tree node.

BinaryTree
< E >
getLeftChild
(){

return
treeLeft
;

}

/**

* getRightChild returns the right child node.

*
@return
the right child,a binaryTree node.

BinaryTree
< E >
getRightChild
(){

return
treeRight
;

}

/**

* setLeftChild, sets the left child of the current node.

*
@param
l is the left child, a binaryTree node.

void
setLeftChild
(
BinaryTree
< E >
l
){

treeLeft
=
l
;

}

/**

* setRightChild, sets the right child of the current node.

*
@param
r the right child, a binaryTree node.

void
setRightChild
(
BinaryTree
< E >
r
){

treeRight
=
r
;

}

/**

* setValue sets the value of a node.

*
@param
object value of the node.

void
setValue
(
E object
){

v
=
object
;

}

/**

* getValue returns the value held in the node.

*
@return
the object value of the node.

E getValue
(){

return
v
;

}

/**

* isLeaf checks if the node is a leaf node by checking if it has children.

*
@return
boolean if the node is a leaf node.

boolean
isLeaf
(){

if
(
getLeftChild
()
==
null

&&
getRightChild
()
==
null
){

return

true
;

}

return

false
;

}

HuffmanTreeTest.class
public synchronized class HuffmanTreeTest {
HuffmanTree h;
String t;
public void HuffmanTreeTest();
public void start() throws java.io.FileNotFoundException;
public void testEncode();
public void testDecode();
}

HuffmanTreeTest.java
HuffmanTreeTest.java

import

static
org
.
junit
.
Assert
.
*
;

import
java
.
io
.
File
;

import
java
.
io
.
FileNotFoundException
;

import
org
.
junit
.
Before
;

import
org
.
junit
.
Test
;

public

class

HuffmanTreeTest

{

HuffmanTree
h
;

String
t
;

/**

* start creates a test case

*
@throws
FileNotFoundException

@
Before

public

void
start
()

throws

FileNotFoundException
{

h
=

HuffmanTree
.
newTreeFromFile
(
new

File
(

“/Users/tai-lanhirabayashi/Desktop/test.txt”
));

}

/**

* testEncode tries to encode a string.

@
Test

public

void
testEncode
()

{

t
=
h
.
encode
(
“This program must work!”
);

}

/**

* testDecode tries to decode the string.

@
Test

public

void
testDecode
()

{

assertEquals
(
“This program must work!”
,
h
.
decode
(
t
));

}

HTreeTest.class
public synchronized class HTreeTest {
HTree t;
public void HTreeTest();
public void start();
public void testGetBelow();
public void testGetF();
public void testGetS();
public void testGetL();
public void testGetR();
public void testIsLeaf();
public void testSetL();
public void testSetR();
}

HTreeTest.java
HTreeTest.java
import

static
org
.
junit
.
Assert
.
*
;

import
org
.
junit
.
Before
;

import
org
.
junit
.
Test
;

public

class

HTreeTest

{

HTree
t
;

/**

* Start initializes a test case of HTree

@
Before

public

void
start
(){

t
=
new

HTree
(
1
,
“one”
);

HTree
a
=
new

HTree
(
2
,
“two”
);

HTree
b
=
new

HTree
(
3
,
“three”
);

t
.
setL
(
a
);

t
.
setR
(
b
);

}

/**

* testGetBelow tests GetBelow

@
Test

public

void
testGetBelow
()

{

assertEquals
(
1
,
t
.
getBelow
());

assertEquals
(
0
,
t
.
getL
().
getBelow
());

HTree
a
=
new

HTree
(
4
,
“a”
);

HTree
b
=
new

HTree
(
5
,
“b”
);

t
.
getL
().
setL
(
a
);

t
.
getL
().
setR
(
b
);

assertEquals
(
2
,
t
.
getBelow
());

}

/**

* testGetF tests getF

@
Test

public

void
testGetF
(){

assertEquals
(
1
,
t
.
getF
());

assertEquals
(
2
,
t
.
getL
().
getF
());

assertEquals
(
3
,
t
.
getR
().
getF
());

}

/**

* testGetS tests getS

@
Test

public

void
testGetS
(){

assertEquals
(
“one”
,
t
.
getS
());

assertEquals
(
“two”
,
t
.
getL
().
getS
());

assertEquals
(
“three”
,
t
.
getR
().
getS
());

}

/**

* testGetL tests getL

@
Test

public

void
testGetL
(){

assertEquals
(
2
,
t
.
getL
().
getF
());

assertEquals
(
null
,
t
.
getL
().
getL
());

}

/**

* testGetR tests getR

@
Test

public

void
testGetR
(){

assertEquals
(
3
,
t
.
getR
().
getF
());

assertEquals
(
null
,
t
.
getR
().
getR
());

}

/**

* testIsLeaf tests isLeaf

@
Test

public

void
testIsLeaf
(){

assertEquals
(
false
,
t
.
isLeaf
());

assertEquals
(
true
,
t
.
getR
().
isLeaf
());

assertEquals
(
true
,
t
.
getL
().
isLeaf
());

}

/**

* testSetL tests setL

@
Test

public

void
testSetL
(){

assertEquals
(
2
,
t
.
getL
().
getF
());

t
.
setL
(
null
);

assertEquals
(
null
,
t
.
getL
());

}

/**

* testSetR tests setR

@
Test

public

void
testSetR
(){

assertEquals
(
3
,
t
.
getR
().
getF
());

t
.
setR
(
null
);

assertEquals
(
null
,
t
.
getR
());

}

Heap$MaxHeapComparator.class
public synchronized class Heap$MaxHeapComparator implements java.util.Comparator {
public void Heap$MaxHeapComparator();
public int compare(Comparable, Comparable);
}

Heap$MinHeapComparator.class
public synchronized class Heap$MinHeapComparator implements java.util.Comparator {
public void Heap$MinHeapComparator();
public int compare(Comparable, Comparable);
}

Heap.class
public synchronized class Heap {
int s;
Object[] h;
int maxS;
java.util.Comparator c;
public void Heap(int, java.util.Comparator);
public Object findMax();
public Object removeMax();
public void insert(Object);
public int size();
private void siftUp(int);
private void siftDown(int);
}

Heap.java
Heap.java
import
java
.
lang
.
reflect
.
Array
;

import
java
.
util
.
Comparator
;

import
java
.
util
.
NoSuchElementException
;

public

class

Heap
< E >

{

int
s
;

Object
[]
h
;

int
maxS
;

Comparator
c
;

/**

* Heap takes in the initial size of the heap.

*
@param
i the integer value of the size of the heap.

public

Heap
(
int
i
,

Comparator

comparator
){

c
=
comparator
;

s
=
0
;

maxS
=
i
;

h
=

new

Object
[
i
];

}

/**

* findMax returns the largest item of the heap.

* If the heap is empty it will throw a noSuchElementException.

*
@return
E the max object

public
E findMax
(){

if
(
s
==
0
){

System
.
out
.
println
(
“an error has been thrown because the heap is empty”
);

throw

new

NoSuchElementException
();

}

return

(
E
)
h
[
0
];

}

/**

* removeMax removes the largest item. If the list is empty a NoSuchElementException is thrown.

*
@return
the max object

public
E removeMax
(){

if
(
s
==
0
){

System
.
out
.
println
(
“an error has been thrown because the heap is empty”
);

throw

new

NoSuchElementException
();

}

E last
=

(
E
)
h
[
s
–
1
];

E first
=

(
E
)
h
[
0
];

h
[
0
]
=
last
;

h
[
s
–
1
]
=

null
;

s
—
;

siftDown
(
0
);

return
first
;

}

/**

* insert inserts an item into the heap and bubbles it into the correct position.

*
@param
item that is inserted

public

void
insert
(
E item
){

if
(
s
==
maxS
–
1
){

maxS
=
maxS
*
2
;

Object
[]
grownArray
=

new

Object
[
maxS
];

System
.
arraycopy
(
h
,

0
,
grownArray
,

0
,
h
.
length
);

h
=
grownArray
;

}

h
[
s
]
=
item
;

siftUp
(
s
);

s
++
;

}

/**

* size returns the size of the heap.

*
@return
the integer size of the heap

public

int
size
(){

return
s
;

}

/**

* siftUp, sifts the node at index i up through the heap into the correct position.

*
@param
i the value to begin sifting

private

void
siftUp
(
int
i
)

{

int
n
=
i
;

boolean
inPlace
=

false
;

if
(
n
==
0
){

inPlace
=
true
;

}

while
(
inPlace
==
false
){

int
a
=
(
n
–
1
)
/
2
;

E below
=

(
E
)
h
[
n
];

E above
=

(
E
)
h
[
a
];

if
(
c
.
compare
(
below
,
above
)
>
0
){

h
[
n
]
=
above
;

h
[
a
]
=
below
;

n
=
a
;

}
else
{

inPlace
=
true
;

}

/**

* SiftDown sifts the node at index i down to the correct spot in the heap.

*
@param
i the value to begin sifting

private

void
siftDown
(
int
i
)

{

int
n
=
i
;

boolean
inPlace
=

false
;

while
(
inPlace
==
false
){

int
a
=
(
n
*
2
)
+
1
;

E above
=

(
E
)
h
[
n
];

E belowL
=

(
E
)
h
[
a
];

E belowR
=

(
E
)
h
[
a
+
1
];

if
(
belowL
==
null

&&
belowR
==
null
){

return
;

}

//if neither of the children are null

if
(
belowL
!=

null

&&
belowR
!=

null
){

//compare to the left child

if
(
c
.
compare
(
above
,
belowL
)

< 0 && c . compare ( belowL , belowR ) >=
0

){

System
.
out
.
println
(
“down and to the left!”
);

h
[
a
]
=
above
;

h
[
n
]
=
belowL
;

n
=
a
;

//compare to the right child

}
else

if
(
c
.
compare
(
above
,
belowR
)
< 0 ){ System . out . println ( "down and to the right!" ); h [ a + 1 ] = above ; h [ n ] = belowR ; n = a ; //otherwise its in place } else { System . out . println ( "its down in place" ); inPlace = true ; } //if the left child isnt null } else if ( belowL != null ){ if ( c . compare ( above , belowL ) < 0 ){ h [ n ] = above ; h [ a ] = belowL ; n = a ; } else { inPlace = true ; } } else { // if the right child isnt null compare it to the parent if ( c . compare ( above , belowR ) < 0 ){ h [ a + 1 ] = above ; h [ n ] = belowR ; n = a ; } else { inPlace = true ; } } } } /** * MaxHeapComparator compares two values and prioritizes the max value. * @author tai-lanhirabayashi * * @param the comparable object

public

static

class

MaxHeapComparator
< E extends Comparable < E >>

implements

Comparator
< E >

{

@
Override

public

int
compare
(
E o1
,
E o2
)

{

return
o1
.
compareTo
(
o2
);

}

/**

* MinHeapComparator compares two values and prioritizes the lower value

*
@author
tai-lanhirabayashi

*
@param
the comparable object

public

static

class

MinHeapComparator
< E extends Comparable < E >>

implements

Comparator
< E >
{

@
Override

public

int
compare
(
E o1
,
E o2
)

{

return

(
–
1

*
o1
.
compareTo
(
o2
));

}

PriorityQueueTest.class
public synchronized class PriorityQueueTest {
PriorityQueue p;
public void PriorityQueueTest();
public void start();
public void testPeek();
public void testRemove();
public void testSize();
public void testEmpty();
}

PriorityQueueTest.java
PriorityQueueTest.java
import

static
org
.
junit
.
Assert
.
*
;

import
java
.
util
.
Comparator
;

import
org
.
junit
.
Before
;

import
org
.
junit
.
Test
;

public

class

PriorityQueueTest

{

PriorityQueue
p
;

/**

* Start initialized the program, with a queue of 1,2,3,4 and a max priority.

@
Before

public

void
start
(){

Comparator
< Integer >
c
=

new

Heap
.
MaxHeapComparator
();

p
=
new

PriorityQueue
(
10
,
c
);

p
.
add
(
1
);

p
.
add
(
2
);

p
.
add
(
3
);

p
.
add
(
4
);

}

/**

* testPeek tests the peek function.

@
Test

public

void
testPeek
()

{

assertEquals
(
4
,
p
.
peek
());

p
.
remove
();

assertEquals
(
3
,
p
.
peek
());

p
.
remove
();

assertEquals
(
2
,
p
.
peek
());

p
.
remove
();

assertEquals
(
1
,
p
.
peek
());

p
.
remove
();

assertEquals
(
null
,
p
.
peek
());

}

/**

* restRemove tests the remove function.

@
Test

public

void
testRemove
()

{

assertEquals
(
4
,
p
.
remove
());

assertEquals
(
3
,
p
.
remove
());

assertEquals
(
2
,
p
.
remove
());

assertEquals
(
1
,
p
.
remove
());

assertEquals
(
null
,
p
.
remove
());

}

/**

* testSize tests the size function.

@
Test

public

void
testSize
()

{

assertEquals
(
4
,
p
.
size
());

p
.
remove
();

assertEquals
(
3
,
p
.
size
());

p
.
remove
();

assertEquals
(
2
,
p
.
size
());

p
.
remove
();

assertEquals
(
1
,
p
.
size
());

p
.
remove
();

assertEquals
(
0
,
p
.
size
());

p
.
add
(
9
);

assertEquals
(
1
,
p
.
size
());

}

/**

* testEmpty tests the isEmpty function of priorityQueue.

@
Test

public

void
testEmpty
(){