red black tree

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)

—–

Implementing a red-black tree

The main goal of this assignment is for you to implement a red-black tree. As we did with the previous binary search tree, we are going to implement this as a Map, so it should have exactly the same interface as the last time. In keeping with the naming convention established last time, you should name your new class RBMap. To help you test your code, add three extra public methods:

public boolean redViolationExists()This method will traverse the tree and return true if any red node has a red child.public int blackHeight()This method will return the black height of the tree. If the black height of the two children of the tree do not agree, it will return -1, indicating a black height violationpublic String toString()This overrides the default toString method to print out a traversal of the tree. This should be in the form of a preorder traversal of the tree in which each node is printed out in the form of the key, followed by a colon and then a B or an R, all in square brackets. So a tree with root 5 and children 3 and 9 would look like [5:B][3:R][9:R].

We would not, of course, include these in any production code (just like the Node class, the use of red and black are meaningless to actual uses of your class). These will a) assure me that you know what those are, and b) be useful in testing your code (provided you write them correctly…). Note that while these are useful for testing, they are not replacements for testing the functionality of the tree (they only tell us that there are no red or black violations), and they cannot themselves be tested in the usual way (there shouldn’t be a way to create a tree with violations). Also, DO NOT USE THESE ANYWHERE IN YOUR CODE — THEY ARE FOR TESTING ONLY!

As I said in class, the actual mechanics of most of the functionality of the BSTMap class will remain the same. The biggest difference is that you need to rebalance the tree after insertions and deletions. To help you out, I have created some

starter code

for you. This is basically an implementation of the BSTMap class that you had to build for the last homework, with some features to help with the red-black tree added in. You are not required to use this code, but I encourage you to read through it.

This is an assignment about details. There are a lot of different cases that you need to worry about, and you need to be careful how you handle them. As I said in class, I didn’t show you a number of cases because they were the mirror of the cases we did discuss. You, of course, need to cover them. Think about ways to write your code so that you can cover these right and left differences at the same time (the less code you write, the easier it will be to debug).

Testing

I would like you to be particularly careful in writing your tests. It is not enough to just reuse your tests from the last map and dump some values in and read them back out. You can keep them around to make sure that the Map still behaves properly as a map, but we also want to make sure that all of your correction code is functioning correctly. This time, I want to see tests that exercise each of the conditions that we discussed in class (you can have tests that hit more than one condition; for example, you can test case 2 and case 3 insertion at the same time). In your comments, be explicit about which case you are testing and how your test makes sure that it worked.

please note I need a javaTests for all of the methods.

The example of the methods used in the previous binary tree are attatched as well as the sample code

1/1/13 9:26 PM

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

import java.util.Set;
import java.util.TreeSet;

/**
* This is a skeleton of a red black tree. The basic functionality of a map backed by a binary search tree is provided, but
* the red black handling has been left as an exercise.
*
* @author C. Andrews
*
* @param the key type of the Map
* @param the value type associated with the key
*/
public class RBMap, V> implements Map {
private static enum NodeColor {RED, BLACK};
BinaryTree _root =null;
Set _keys;

public RBMap(){
_keys = new TreeSet();
}

/**
* Add an element to the map.
*
* If the key is already present in the map, the value is replaced with {@code value}.
*
* @param key the key to associate the value with
* @param value the value being added to the map
*/
@Override
public void put(K key, V value) {
BinaryTree tmp = new BinaryTree(null, new Pair(key, value), null);
BinaryTree current = _root;
BinaryTree parent = null;
_keys.add(key);

while (current != null){
parent = current;
if (key.compareTo(current.getValue()._key) == 0){ // they are the same, just update the value
current.getValue()._value = value;
return;
}else if (key.compareTo(current.getValue()._key) < 0){ // the key is smaller, go left current = current.getLeft(); }else{ // the key is larger, go right current = current.getRight(); } }

tmp.setParent(parent);

if (parent == null){
_root = tmp;
}else{
if (key.compareTo(parent.getValue()._key) < 0){ parent.setLeft(tmp); }else{ parent.setRight(tmp); }

}

// TODO rebalance the tree
}

/**
* Perform a lookup in the map based on the input key.

1/1/13 9:26 PM

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

*
* @param key the key associated with the value to be returned
*/
@Override
public V get(K key) {
BinaryTree tmp = find(key);

if(tmp == null)
return null;
else
return tmp.getValue()._value;
}

/**
* This private method finds nodes in the tree based on the key value.
*
* If the key exists in the map, this returns the node associated with it (not just the value). If the
* key is not present, this returns null. This is used to implement get and remove.
*
* @param key the key that we are looking for
* @return the node containing the key or null if the key is not present
*/
private BinaryTree find(K key){
BinaryTree current = _root;

while (current != null && key.compareTo(current.getValue()._key) != 0){
if (key.compareTo(current.getValue()._key) < 0){ current = current.getLeft(); }else{ current = current.getRight(); } }

if (current != null)
return current;
else
return null;
}

/**
* Does the map contain the given key?
*
* @param key the key value to look for in the map
* @return a boolean value indicating if the key is present
*/
@Override
public boolean containsKey(K key) {
return get(key) != null;
}

/**
* Remove the value associated with {@code key} from the map.
*
* Removes the key and value pair and returns the value.
*
* @param key the key for the value we are trying to remove
* @return the value associated with the key or null if the key is not present in the map
*/
@Override
public V remove(K key) {
_keys.remove(key);
BinaryTree toRemove = find(key);
BinaryTree child;
V value;
if (toRemove == null){
return null;
}
value = toRemove.getValue()._value;
if (toRemove.getLeft() != null && toRemove.getRight() != null){
BinaryTreetmp = toRemove;
NodeColor color = toRemove.getValue()._color;

1/1/13 9:26 PM

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

toRemove = successor(toRemove);
tmp.setValue( toRemove.getValue());
tmp.getValue()._color = color;
}

if (toRemove.getLeft() != null){
child = toRemove.getLeft();
}else{
child = toRemove.getRight();
}

if (child != null){
child.setParent(toRemove.getParent());
}
if (toRemove.getParent() == null){
_root = child;
}else if (toRemove.getParent().getLeft() == toRemove){
toRemove.getParent().setLeft(child);
}else{
toRemove.getParent().setRight(child);
}

// TODO rebalance tree if necessary

return value;
}

/**
* Return the set of all keys present in the map.
*
* @return the {@code Set} of all keys in the map
*/
@Override
public Set keySet() {
return _keys;
}

/**
* A private helper that finds the immediate successor of a node in the tree.
*
* @param t the node we are trying to find the successor of
* @return the immediate successor of the node or null if there isn’t one
*/
private BinaryTree successor(BinaryTree t){
if (t.getRight() != null){
return minimum(t.getRight());
}

BinaryTree parent = t.getParent();

while (parent != null && parent.getRight() == t){
t = parent;
parent = parent.getParent();
}
return parent;
}

/**
* A private helper that finds the minimum value in the tree rooted at t.
*
* This will fail if t is null since that would be an invalid operation.
*
* @param t the subtree we are exploring
* @return the minimum value in t
*/
private BinaryTree minimum(BinaryTree t){
while (t.getLeft() != null){
t = t.getLeft();
}
return t;
}

1/1/13 9:26 PM

Page 4 of 5http://web.cs.mtholyoke.edu/~candrews/cs211/examples/RBMap.html

/**
* A private helper that finds the maximum value in the tree rooted at t.
*
* This will fail if t is null since that would be an invalid operation.
*
* @param t the subtree we are exploring
* @return the maximum value in t
*/
@SuppressWarnings(“unused”)
private BinaryTree maximum(BinaryTree t){
while (t.getRight() != null){
t = t.getRight();
}
return t;
}

/**
* Returns a String representation of the tree.
*
* The representation is a preorder traversal of the tree in which each node is printed out in the
* form of the key, followed by a colon and then a B or an R, all in square brackets. So a tree
* with root 5 and children 3 and 9 would look like [5:B][3:R][9:R].
*
*/
public String toString(){
// TODO implement this method
}

/**
* Returns the black height of the tree.
*
* If there are any violations, this returns -1.
*
* @return the black height or -1 if there are any violations
*/
public int blackHeight(){
// TODO implement this method
}

/**
* Indicates if there is a red violation in the tree
*
* @return a boolean value that indicates if there is a red violation in the tree
*/
public boolean redViolation(){
// TODO implement this method
}

/**
* This is a simple wrapper class that provides the associations in the tree.
*
* @author C. Andrews
*
*/
private class Pair{
private K _key;
private V _value;
private NodeColor _color;

private Pair(K key, V value){
_key = key;
_value =value;
_color = NodeColor.RED; // all new nodes are RED
}

1/1/13 9:26 PM

Page 5 of 5http://web.cs.mtholyoke.edu/~candrews/cs211/examples/RBMap.html

}
}

1/1/13 9:26 PMCS 211 Homework Five — Fall 2012

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

CS 212 — Homework Five
Can’t see the forest…

Due: 30 October 2012, 11:59p

Worth: 75 points

Part One: Implement a Binary Tree

Worth: 15 points

The first step is to build a simple BinaryTree ADT (so it should support generics). Our needs for the tree
are pretty simple, so you will only need to implement the following

interface:

BinaryTree(BinaryTree left, E value, BinaryTree right)
BinaryTree getLeftChild()
BinaryTree getRightChild()
void setLeftChild(BinaryTree)
void setRightChild(BinaryTree)
void setValue(E)
E getValue()
boolean isLeaf()

For this tree, you will be implementing it in “linked-list” style, as described in class. For the second part of
the assignment you will be doing a lot of merging of the binary trees and that would be something of a
pain that outweighs the trouble of the extra null references.

I, of course, expect to see JUnit tests included with this class.

Part Two: Parsing Expressions

Worth: 60 points

One use of trees is to build expression trees. For this assignment, you will be building an arithmetic
expression tree that can represent arithmetic expressions. The idea behind expression trees is that inner
nodes are operators (in our case, +,-,*,/), and the leaves are operands (either constant values or
variables). The value of an expression tree is either the value stored in the node (if the node has no
children) or the result of applying the operator stored in the node to its left and right subtrees. So, for
example, the expression x + 5 – 6 would be represented as:

Your task will be to read in an expression, parse it into a tree, and then let the user perform some basic
operations on the expression. You will create a class called ArithmeticExpression with the following

1/1/13 9:26 PMCS 211 Homework Five — Fall 2012

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

interface:

ArithmeticExpression(String expression) [25 pts]
This is the constructor. It will take a String containing the expression. The expression will contain operators (+,-
,*,/), integer constants, and arbitrary strings that should be interpreted as variables.There is no guarantee that this
expression is valid. If the expression is not valid, this should throw a ParseException (be sure to indicate where you
had a problem with the parse). To make your lives a little easier, the expression will be space delimitated. Being the
constructor, this function should only perform the parse a build the resulting data structure (using a BinaryTree, of
course).

String toString() [10 pts]
This method should return a String containing the parsed expression. In this case, that means fully parenthesized
according to operator precedence (i.e., * and / have higher precedence than + and -). For example, “6 + 5 * 2”
should result in “(6+(5*2))”. The result should contain no spaces. Hint: this should sound like some kind of traversal
— what kind?

void setVariable(String name, int value) [10 pts]
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.

int evaluate() [15 pts]
Obviously, this should return the integer result of evaluating the expression. Unset variables should be considered to
have the value of 0.

Example usage

Code:

ArithmeticExpression expression = new ArithmeticExpression(“x + 5 * 6”);
System.out.println(expression);
expression.setVariable(“x”, 5);
System.out.println(expression.evaluate());
expression.setVariable(“x”, 10);
System.out.println(expression.evaluate());

Output:

(x+(5*6))
35
40

Implementation details

The hardest part of this is implementing the parser that builds the expression tree so that the correct
operator precedence is maintained. For example, given the expression x + y * 2, assuming that we
interpret the left and right sides of the operators as left and right children, there are two trees we could
build, but only one of them is correct.

1/1/13 9:26 PMCS 211 Homework Five — Fall 2012

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

So, we can’t just start chaining nodes together. Instead, we are going to use a pair of Stacks to help us
out (that’s right, you’ll need to pull out your Stack class from the first homework). One stack will be the
operator stack, and it will hold operators that we don’t know how to use yet. The other stack will be a
tree stack, and will hold the partial binary trees that we have not fit together yet. As we read tokens from
the input expression, the operation will then be:

If the token is an operand,
make it into a tree and push it on the tree stack
If the token is an operator, operator stack is empty OR the operator is either * or /,
push the operator on the operator stack
Otherwise:
While the operator stack is not empty
Pop an operator from the operator stack
Pop the top two trees from the tree stack
Create a new tree with the two trees and the operator
Push the new tree on the tree stack
Push the new operator onto the operator stack
When the String is consumed, repeat the above loop to clear out any unused operators

At the end, the expression tree should be sitting alone in the tree stack. Clearly, if any of the pops fail, or
if there are more trees in the tree stack at the end of the process, the expression was invalid.

Another issue you will have is storing the variable values. The obvious answer would be to replace any
variables in the tree with the value when they get set. Of course, then you won’t be able to change the
variable’s value and re-evaluate the expression (which would rather remove the value of having variables
there). So, we want to build a lookup table to hold the current values of all of the variables. Very soon,
we will start talking about a data structure tailor-made for this purpose, but for right now we will just use
an ArrayList. You will need to create some kind of inner class to hold name/value pairs. Stick these in the
ArrayList and just iterate through everything to find the right entry. This isn’t terribly efficient, but we
are unlikely to have very many variables. Very soon, we will start talking about a data structure that is
tailor-made to this, but for right now we will put up with this little bit of inefficiency.

Bonus round

I decided that I would give you the opportunity to earn a little extra credit on this one. If you chose to do
any of these, be very clear that you did it in your comments, and provide appropriate test cases
demonstrating them in action.

(4 points) Adjust your code so that it can handle input strings without spaces.
(4 points) Handle implicit multiplication on variables (i.e., 2x + 5).
(5 points) Rewrite the parser so that it can handle parentheses in the input string. You will have to
think a little bit about how to handle the logic of this case since the parentheses affect the
precedence of operations (i.e., they will not be represented in the tree, they will affect the
structure of the tree).
(5 points) Allow for unary operators. A unary operator would be an operator that takes only a single
operand (i.e., -5 or +34). Again, you will have to think about how to change the logic of the parse
to allow these
(5 points) Write a new method called toPostfixString() that will return the expression in postfix
form.

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_hw5.suffix, where pid is your Mount Holyoke email account name and
suffix is the appropriate suffix for your archive format.

Last modified: Tue Oct 23 18:03:05 EDT 2012

1/1/13 9:26 PMCS 211 Homework Five — Fall 2012

Page 4 of 4http://web.cs.mtholyoke.edu/~candrews/cs211/homework/hw5.html

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
(){