Huffman application
compSci
example.jarMETA-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
<?
super
E
>
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
<E> 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
<?
super
E
>
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
<E> 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
<E> 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
(){
assertFalse
(
p
.
isEmpty
());
p
.
remove
();
assertFalse
(
p
.
isEmpty
());
p
.
remove
();
assertFalse
(
p
.
isEmpty
());
p
.
remove
();
assertFalse
(
p
.
isEmpty
());
p
.
remove
();
assertTrue
(
p
.
isEmpty
());
p
.
add
(
5
);
assertFalse
(
p
.
isEmpty
());
}
}
BSTMap.class
public synchronized class BSTMap extends Map { nObject obj; BSTMap left; BSTMap right; int s; BSTMap parent; public void BSTMap(Object, Object); public void setParent(BSTMap); public BSTMap getParent(); public void setLeft(BSTMap); public void setRight(BSTMap); public BSTMap getLeft(); public BSTMap getRight(); boolean isLeaf(); }
BSTMap.java
BSTMap.java
public
class
BSTMap
<
K
,
V
>
extends
Map
{
nObject obj
;
BSTMap
<
K
,
V
>
left
;
BSTMap
<
K
,
V
>
right
;
int
s
;
BSTMap
<
K
,
V
>
parent
;
/**
* BSTMap creates a node with a K key and V value.
*
@param
ke the K value
*
@param
va the V value
*/
public
BSTMap
(
K ke
,
V va
){
obj
=
new
nObject
(
ke
,
va
);
left
=
null
;
right
=
null
;
parent
=
null
;
}
/**
* setParent sets the BSTMap which is this nodes parent.
*
@param
p the parent
*/
public
void
setParent
(
BSTMap
<
K
,
V
>
p
){
parent
=
p
;
}
/**
* getParent returns the parent of this node.
*
@return
BSTMap that is this nodes parent.
*/
public
BSTMap
<
K
,
V
>
getParent
(){
return
parent
;
}
/**
* setLeft sets the BSTMap left child.
*
*
@param
child BSTMap that is this nodes child.
*/
public
void
setLeft
(
BSTMap
<
K
,
V
>
child
){
left
=
child
;
if
(
child
!=
null
){
left
.
setParent
(
this
);
}
}
/**
* setRight sets the this nodes BSTMap child.
*
@param
child BSTMap that is this nodes child.
*/
public
void
setRight
(
BSTMap
<
K
,
V
>
child
){
right
=
child
;
if
(
child
!=
null
){
right
.
setParent
(
this
);
}
}
/**
* getLeft returns this nodes left BSTMap child.
*
@return
BSTMap this nodes left child
*/
public
BSTMap
<
K
,
V
>
getLeft
(){
return
left
;
}
/**
* getRight returns this nodes right BSTMap child.
*
@return
BSTMap this nodes right child
*/
public
BSTMap
<
K
,
V
>
getRight
(){
return
right
;
}
/**
* isLeaf checks if the node is a leaf node by checking if it has children.
*
* It returns true for leaf, false for if it has children.
*
@return
boolean if the node is a leaf node.
*/
boolean
isLeaf
(){
if
(
getLeft
()
==
null
&&
getRight
()
==
null
){
return
true
;
}
return
false
;
}
}
BinaryTreeTest.class
public synchronized class BinaryTreeTest { BinaryTree t; public void BinaryTreeTest(); public void before(); public void testSetup(); public void testGetLeft(); public void testGetRight(); public void isLeaf(); public void setLeft(); public void setRight(); public void setValue(); }
BinaryTreeTest.java
BinaryTreeTest.java
import
static
org
.
junit
.
Assert
.
*
;
import
org
.
junit
.
Before
;
import
org
.
junit
.
Test
;
/**
* BinaryTreeTest tests to see if Binary Tree functions as expected.
*
@author
tai-lanhirabayashi
*
*/
public
class
BinaryTreeTest
{
BinaryTree
t
;
/**
* before sets up a base case.
*/
@
Before
public
void
before
(){
t
=
new
BinaryTree
(
null
,
"head"
,
null
);
t
.
setLeftChild
(
new
BinaryTree
(
null
,
"second"
,
null
));
t
.
getLeftChild
().
setLeftChild
(
new
BinaryTree
(
null
,
"third"
,
null
));
}
/**
* testSetup makes sure the test has been initialized.
*/
@
Test
public
void
testSetup
()
{
assertEquals
(
t
.
getValue
(),
"head"
);
}
/**
* tests the getLeft function
*/
@
Test
public
void
testGetLeft
(){
assertEquals
(
t
.
getLeftChild
().
getValue
(),
"second"
);
}
/**
* Tests the get right function
*/
@
Test
public
void
testGetRight
(){
assertEquals
(
t
.
getRightChild
(),
null
);
}
/**
* Tests the isLeaf function.
*/
@
Test
public
void
isLeaf
(){
assertEquals
(
t
.
getLeftChild
().
getLeftChild
().
isLeaf
(),
true
);
}
/**
* Tests the setLeft function
*/
@
SuppressWarnings
(
"unchecked"
)
@
Test
public
void
setLeft
(){
t
.
setLeftChild
(
new
BinaryTree
(
null
,
"replace"
,
null
));
assertEquals
(
t
.
getLeftChild
().
getValue
(),
"replace"
);
}
/**
* tests the setRightChild function
*/
@
SuppressWarnings
(
"unchecked"
)
@
Test
public
void
setRight
(){
t
.
setRightChild
(
new
BinaryTree
(
null
,
"right"
,
null
));
assertEquals
(
t
.
getRightChild
().
getValue
(),
"right"
);
}
/**
* Tests the setValue function.
*/
@
Test
public
void
setValue
(){
t
.
getLeftChild
().
setValue
(
"reset"
);
assertEquals
(
t
.
getLeftChild
().
getValue
(),
"reset"
);
}
}
ArithmeticExpressionTest.class
public synchronized class ArithmeticExpressionTest { ArithmeticExpression a; public void ArithmeticExpressionTest(); public void startUp() throws java.text.ParseException; public void testExceptions(); public void testToString(); public void testEval(); public void testVar() throws java.rmi.NotBoundException, java.text.ParseException; public void testPostFix(); public void testWithoutSpaces() throws java.text.ParseException; }
ArithmeticExpressionTest.java
ArithmeticExpressionTest.java
import
static
org
.
junit
.
Assert
.
*
;
import
java
.
rmi
.
NotBoundException
;
import
java
.
text
.
ParseException
;
import
org
.
junit
.
Before
;
import
org
.
junit
.
Test
;
/**
* ArithmeticExpressionTest tests the functionality of ArithmeticExpression.
*** Note, the Program includes postFix() which returns a postfix String of the equation.
*** It can also handle strings with or without spaces.
*
*
*
@author
tai-lan hirabayashi
*
*/
public
class
ArithmeticExpressionTest
{
ArithmeticExpression
a
;
/**
* StartUp sets up the base case scenario.
*
@throws
ParseException if the equation is not valid.
*/
@
Before
public
void
startUp
()
throws
ParseException
{
a
=
new
ArithmeticExpression
(
"3 + 4 * 2"
);
}
/**
* testExceptions tests the programs thrown exceptions.
*/
@
Test
public
void
testExceptions
(){
boolean
errorThrown
=
false
;
try
{
a
=
new
ArithmeticExpression
(
"3 + * 2"
);
}
catch
(
ParseException
e
)
{
errorThrown
=
true
;
}
assert
(
errorThrown
);
errorThrown
=
false
;
try
{
a
.
setVariable
(
"y"
,
2
);
}
catch
(
NotBoundException
e
)
{
errorThrown
=
true
;
}
assert
(
errorThrown
);
}
/**
* testToString tests the toString method of the ArithmeticExpression
*/
@
Test
public
void
testToString
()
{
System
.
out
.
println
(
"this is toString: "
+
a
.
toString
(
a
.
t
));
assertEquals
(
a
.
toString
(
a
.
t
),
"((2*4)+3)"
);
}
/**
* testEval tests the evaluate method of ArithmeticExpression
*/
@
Test
public
void
testEval
(){
assertEquals
(
a
.
evaluate
(
a
.
t
),
11
);
}
/**
* testVar tests the setVariable function of ArithmeticExpression
* by checking how a variable is handled.
*
@throws
NotBoundException
*
@throws
ParseException if the equation is not valid.
*/
@
Test
public
void
testVar
()
throws
NotBoundException
,
ParseException
{
a
=
new
ArithmeticExpression
(
"2 + 3 * x"
);
assertEquals
(
a
.
evaluate
(
a
.
t
),
2
);
a
.
setVariable
(
"x"
,
2
);
assertEquals
(
a
.
evaluate
(
a
.
t
),
8
);
}
/**
* Tests the postFix() method.
*/
@
Test
public
void
testPostFix
(){
assertEquals
(
a
.
toPostfixString
(
a
.
t
),
"3 4 2 * +"
);
}
@
Test
public
void
testWithoutSpaces
()
throws
ParseException
{
a
=
new
ArithmeticExpression
(
"2+3*x"
);
assertEquals
(
a
.
evaluate
(
a
.
t
),
2
);
}
}
nObject.class
public synchronized class nObject { Object key; Object value; public void nObject(Object, Object); public Object getKey(); public Object getValue(); public void changeKey(Object); public void changeValue(Object); }
nObject.java
nObject.java
public
class
nObject
<
K
,
V
>
{
K key
;
V value
;
/**
* nObject creates a new nObject object with a K,V values held.
*
@param
ky the K key value
*
@param
val the V value value.
*/
public
nObject
(
K ky
,
V val
){
key
=
ky
;
value
=
val
;
}
/**
* getKey returns the K key.
*
@return
K, the key
*/
public
K getKey
(){
return
key
;
}
/**
* getValue returns the V value.
*
@return
V value
*/
public
V getValue
(){
return
value
;
}
/**
* changeK allows the user to pass in a new K key.
*
@param
ky K to be changed to.
*/
public
void
changeKey
(
K ky
){
key
=
ky
;
}
/**
* changeValue allows the value to be changed.
*
@param
val the new V value.
*/
public
void
changeValue
(
V val
){
value
=
val
;
}
}
BSTMapTest.class
public synchronized class BSTMapTest { BSTMap m; public void BSTMapTest(); public void startUp(); public void testGetLeft(); public void testGetRight(); public void testGetParent(); public void testIsLeaf(); public void testSetLeft(); public void testSetRight(); public void testSetParent(); }
BSTMapTest.java
BSTMapTest.java
import
static
org
.
junit
.
Assert
.
*
;
import
org
.
junit
.
Before
;
import
org
.
junit
.
Test
;
public
class
BSTMapTest
{
BSTMap
m
;
/**
* startUp creates a new instance of BSTMap.
*/
@
Before
public
void
startUp
(){
m
=
new
BSTMap
(
1
,
"one"
);
}
/**
* testGetLeft tests getLeft().
*
* It tests when it doesnt exist, when it does exist, when it has been changed, and when it has been removed.
*/
@
Test
public
void
testGetLeft
()
{
assertEquals
(
null
,
m
.
getLeft
());
m
.
setRight
(
new
BSTMap
(
3
,
"three"
));
assertEquals
(
null
,
m
.
getLeft
());
BSTMap
child
=
new
BSTMap
(
2
,
"two"
);
BSTMap
a
=
new
BSTMap
(
1
,
"a"
);
m
.
setLeft
(
child
);
assertEquals
(
child
,
m
.
getLeft
());
m
.
setLeft
(
a
);
assertEquals
(
a
,
m
.
getLeft
());
m
.
setLeft
(
null
);
assertEquals
(
null
,
m
.
getLeft
());
}
/**
* testGetRight tests getRight().
*
* It tests when it doesnt exist, when it does exist, and when it has been removed.
*/
@
Test
public
void
testGetRight
()
{
assertEquals
(
null
,
m
.
getRight
());
m
.
setLeft
(
new
BSTMap
(
2
,
"two"
));
assertEquals
(
null
,
m
.
getRight
());
BSTMap
child
=
new
BSTMap
(
3
,
"three"
);
BSTMap
a
=
new
BSTMap
(
1
,
"a"
);
m
.
setRight
(
child
);
assertEquals
(
child
,
m
.
getRight
());
m
.
setRight
(
a
);
assertEquals
(
a
,
m
.
getRight
());
m
.
setRight
(
null
);
assertEquals
(
null
,
m
.
getRight
());
}
/**
* testGetParent tests getParent()
*
* It tests when there is a parent, when there is not a parent.
*/
@
Test
public
void
testGetParent
()
{
assertEquals
(
null
,
m
.
getParent
());
m
.
setLeft
(
new
BSTMap
(
2
,
"two"
));
assertEquals
(
null
,
m
.
getParent
());
BSTMap
child
=
new
BSTMap
(
3
,
"three"
);
m
.
setRight
(
child
);
assertEquals
(
m
,
child
.
getParent
());
}
/**
* testIsLeaf tests to see if a node is a leaf.
*
* It tests when it has no children, when it has a left child, a right child, both, and when they have been removed.
*/
@
Test
public
void
testIsLeaf
()
{
assertTrue
(
m
.
isLeaf
());
m
.
setLeft
(
new
BSTMap
(
2
,
"two"
));
assertFalse
(
m
.
isLeaf
());
m
.
setRight
(
new
BSTMap
(
3
,
"three"
));
assertFalse
(
m
.
isLeaf
());
m
.
setLeft
(
null
);
assertFalse
(
m
.
isLeaf
());
m
.
setRight
(
null
);
assertTrue
(
m
.
isLeaf
());
}
/**
* testSetLeft tests setLeft()
*
*/
@
Test
public
void
testSetLeft
()
{
assertEquals
(
null
,
m
.
getLeft
());
BSTMap
child
=
new
BSTMap
(
2
,
"two"
);
m
.
setLeft
(
child
);
m
.
setRight
(
new
BSTMap
(
3
,
"three"
));
assertEquals
(
child
,
m
.
getLeft
());
m
.
setLeft
(
null
);
assertEquals
(
null
,
m
.
getLeft
());
}
/**
* testSetRight tests setRight
*/
@
Test
public
void
testSetRight
()
{
BSTMap
child
=
new
BSTMap
(
2
,
"two"
);
BSTMap
a
=
new
BSTMap
(
1
,
"a"
);
assertEquals
(
null
,
a
.
getRight
());
a
.
setRight
(
child
);
assertEquals
(
child
,
a
.
getRight
());
a
.
setRight
(
null
);
assertEquals
(
null
,
a
.
getRight
());
}
/**
* testSetParent tests setParent
*/
@
Test
public
void
testSetParent
()
{
BSTMap
child
=
new
BSTMap
(
2
,
"two"
);
BSTMap
a
=
new
BSTMap
(
1
,
"a"
);
assertEquals
(
null
,
a
.
getParent
());
a
.
setParent
(
child
);
assertEquals
(
child
,
a
.
getParent
());
a
.
setParent
(
null
);
assertEquals
(
null
,
a
.
getParent
());
}
}
HTree.class
public synchronized class HTree { private String s; private int f; HTree l; HTree r; public void HTree(int, String); public void setL(HTree); public void setR(HTree); public HTree getL(); public HTree getR(); public String getS(); public int getF(); public boolean isLeaf(); public int getBelow(); }
HTree.java
HTree.java
public
class
HTree
<
E
extends
Comparable
<
E
>>
{
private
String
s
;
private
int
f
;
HTree
l
;
HTree
r
;
/**
* HTree creates a HTree object containing a int frequency and a String str.
*
@param
frequency the integer frequency of the str
*
@param
str the str value of this HTree
*/
public
HTree
(
int
frequency
,
String
str
){
s
=
str
;
f
=
frequency
;
l
=
null
;
r
=
null
;
}
/**
* setL sets the left HTree value
*
@param
left the HTree that is the left child of this node
*/
public
void
setL
(
HTree
left
){
l
=
left
;
}
/**
* setR sets the right HTree child value
*
@param
right the HTree that is the right child of this node
*/
public
void
setR
(
HTree
right
){
r
=
right
;
}
/**
* getL returns the left child of this node.
*
@return
HTree the left child.
*/
public
HTree
getL
(){
return
l
;
}
/**
* getR returns the right child of this node.
*
@return
HTree the right child.
*/
public
HTree
getR
(){
return
r
;
}
/**
* getS returns the string value associated with this node
*
@return
String the value of this node
*/
public
String
getS
(){
return
s
;
}
/**
* getF returns the frequency value associated with this node.
*
@return
the int frequency value associated with this node.
*/
public
int
getF
(){
return
f
;
}
/**
* isLeaf returns boolean if this node is a leaf.
*
@return
boolean wether this node is a leaf.
*/
public
boolean
isLeaf
(){
if
(
l
==
null
&&
r
==
null
){
return
true
;
}
return
false
;
}
/**
* getBelow recursively finds how many children this node has.
*
* **this does not handle trees with only one child (as this does not occur in a huffmanTree)
*
@return
the int number height
*/
public
int
getBelow
(){
if
(
isLeaf
()){
return
0
;
}
else
{
int
a
=
1
+
l
.
getBelow
();
int
b
=
1
+
r
.
getBelow
();
if
(
a
>
b
){
System
.
out
.
println
(
"returning a: "
+
a
);
return
a
;
}
System
.
out
.
println
(
"returning b"
+
b
);
return
b
;
}
}
}
HeapTest.class
public synchronized class HeapTest { Heap h; Heap min; public void HeapTest(); public void start(); public void testFindMax(); public void testRemoveMax(); public void testSize(); public void testMin(); }
HeapTest.java
HeapTest.java
import
static
org
.
junit
.
Assert
.
*
;
import
java
.
util
.
Comparator
;
import
org
.
junit
.
Before
;
import
org
.
junit
.
Test
;
public
class
HeapTest
{
Heap
h
;
Heap
min
;
/**
* start creates a test case of heap both min and max comparator.
*/
@
Before
public
void
start
(){
Comparator
<
Integer
>
c
=
new
Heap
.
MaxHeapComparator
<
Integer
>
();
Comparator
<
Integer
>
m
=
new
Heap
.
MinHeapComparator
<
Integer
>
();
min
=
new
Heap
(
10
,
m
);
min
.
insert
(
1
);
min
.
insert
(
2
);
min
.
insert
(
3
);
min
.
insert
(
4
);
h
=
new
Heap
(
10
,
c
);
System
.
out
.
println
(
"this is 1"
);
h
.
insert
(
1
);
System
.
out
.
println
(
h
.
h
[
0
]);
System
.
out
.
println
(
"this is 2"
);
h
.
insert
(
2
);
System
.
out
.
println
(
h
.
h
[
0
]
+
","
+
h
.
h
[
1
]);
System
.
out
.
println
(
"this is 3"
);
h
.
insert
(
3
);
System
.
out
.
println
(
h
.
h
[
0
]
+
","
+
h
.
h
[
1
]
+
","
+
h
.
h
[
2
]);
System
.
out
.
println
(
"this is 4"
);
h
.
insert
(
4
);
System
.
out
.
println
(
h
.
h
[
0
]
+
","
+
h
.
h
[
1
]
+
","
+
h
.
h
[
2
]
+
","
+
h
.
h
[
3
]);
}
/**
* testFindMax tests the findMax function
*/
@
Test
public
void
testFindMax
()
{
assertEquals
(
4
,
h
.
findMax
());
assertEquals
(
4
,
h
.
removeMax
());
assertEquals
(
3
,
h
.
findMax
());
assertEquals
(
1
,
min
.
findMax
());
assertEquals
(
1
,
min
.
removeMax
());
assertEquals
(
2
,
min
.
findMax
());
}
/**
* testRemoveMax tests the remove max function
*/
@
Test
public
void
testRemoveMax
()
{
assertEquals
(
4
,
h
.
findMax
());
assertEquals
(
4
,
h
.
removeMax
());
assertEquals
(
3
,
h
.
findMax
());
assertEquals
(
3
,
h
.
removeMax
());
assertEquals
(
2
,
h
.
removeMax
());
assertEquals
(
1
,
h
.
removeMax
());
assertEquals
(
0
,
h
.
size
());
assertEquals
(
1
,
min
.
findMax
());
}
/**
* testSize tests the size function of heap.
*/
@
Test
public
void
testSize
(){
assertEquals
(
4
,
h
.
size
());
int
o
=
(
Integer
)
h
.
removeMax
();
assertEquals
(
3
,
h
.
size
());
h
.
insert
(
o
);
assertEquals
(
4
,
h
.
size
());
h
.
removeMax
();
h
.
removeMax
();
h
.
removeMax
();
h
.
removeMax
();
assertEquals
(
0
,
h
.
size
());
assertEquals
(
4
,
min
.
size
());
}
/**
* testMin tests the minSort comparator.
*/
@
Test
public
void
testMin
(){
assertEquals
(
4
,
min
.
size
());
assertEquals
(
1
,
min
.
removeMax
());
assertEquals
(
2
,
min
.
removeMax
());
assertEquals
(
3
,
min
.
removeMax
());
assertEquals
(
4
,
min
.
removeMax
());
}
}
HuffmanTree$CountPair.class
synchronized class HuffmanTree$CountPair { int _count; String _text; private void HuffmanTree$CountPair(HuffmanTree, String, int); }
HuffmanTree$CountPairTreeComparator.class
synchronized class HuffmanTree$CountPairTreeComparator implements java.util.Comparator { private void HuffmanTree$CountPairTreeComparator(HuffmanTree); public int compare(BinaryTree, BinaryTree); }
HuffmanTree.class
public synchronized class HuffmanTree { java.io.File current; BSTMap _lookupTable; BinaryTree _huffmanTree; public void HuffmanTree(); public static HuffmanTree newTreeFromFile(java.io.File) throws java.io.FileNotFoundException; public static HuffmanTree newTreeFromCompressedFile(java.io.File) throws java.io.FileNotFoundException; private void buildFromFile(java.io.File) throws java.io.FileNotFoundException; private void buildTreeFromMap(PriorityQueue); private void buildFromCompressedFile(java.io.File) throws java.io.FileNotFoundException; public void saveCompressedFile(java.io.File); public void saveExpandedFile(java.io.File); public String encode(String); public String decode(String); }
HuffmanTree.java
HuffmanTree.java
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
{
File
current
;
BSTMap
<
String
,
String
>
_lookupTable
=
new
BSTMap
<
String
,
String
>
(
null
,
null
);
BinaryTree
<
CountPair
>
_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
{
current
=
file
;
// read file and build the map of the character frequencies
Map
<
String
,
Integer
>
freqMap
=
new
BSTMap
<
String
,
Integer
>
();
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
<
BinaryTree
<
CountPair
>>
treeQueue
=
new
PriorityQueue
<
BinaryTree
<
CountPair
>>
(
freqMap
.
keySet
().
size
(),
new
CountPairTreeComparator
());
BinaryTree
<
CountPair
>
tmpTree
;
for
(
String
key
:
freqMap
.
keySet
()){
int
frequency
=
freqMap
.
get
(
key
);
tmpTree
=
new
BinaryTree
<
CountPair
>
(
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
<
CountPair
>
tree1
,
tree2
;
int
newFrequency
;
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
<
CountPair
>
(
tree1
,
new
CountPair
(
newText
,
newFrequency
),
tree2
);
treeQueue
.
add
(
tmpTree
);
}
// pull the completed tree from the priority queue
BinaryTree
<
CountPair
>
tree
=
treeQueue
.
remove
();
// create map of symbols to code lengths using the tree
Map
<
String
,
Integer
>
codeLengthMap
=
new
Map
<
String
,
Integer
>
();
// TODO implement this part
PriorityQueue
pq
=
new
PriorityQueue
(
setC
.
size
(),
new
treeComparator
());
buildTreeFromMap
(
pq
);
}
private
void
buildTreeFromMap
(
PriorityQueue
q
)
{
// TODO Auto-generated method stub
}
/**
* 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
);
}
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
<
CountPair
>
current
=
_huffmanTree
;
for
(
int
i
=
0
;
i
<
text
.
length
();
i
++
){
char
c
=
text
.
charAt
(
i
);
if
(
c
==
'0'
){
current
=
current
.
getLeftChild
();
}
else
if
(
c
==
'1'
){
current
=
current
.
getRightChild
();
}
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
<
BinaryTree
<
CountPair
>>
{
@
Override
public
int
compare
(
BinaryTree
<
CountPair
>
t1
,
BinaryTree
<
CountPair
>
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
);
}
}
}
}
nObjectTest.class
public synchronized class nObjectTest { nObject o; public void nObjectTest(); public void setUp(); public void testChangeKey(); public void testChangeValue(); public void testGetKey(); public void testGetValue(); }
nObjectTest.java
nObjectTest.java
import
static
org
.
junit
.
Assert
.
*
;
import
org
.
junit
.
Before
;
import
org
.
junit
.
BeforeClass
;
import
org
.
junit
.
Test
;
public
class
nObjectTest
{
nObject o
;
/**
* setUp sets up the test.
*/
@
Before
public
void
setUp
()
{
o
=
new
nObject
(
"one"
,
1
);
}
/**
* tests the change Key function
*/
@
Test
public
void
testChangeKey
()
{
assertEquals
(
"one"
,
o
.
getKey
());
o
.
changeKey
(
"two"
);
assertEquals
(
"two"
,
o
.
getKey
());
}
/**
* tests the change Value function
*/
@
Test
public
void
testChangeValue
()
{
assertEquals
(
1
,
o
.
getValue
());
o
.
changeValue
(
2
);
assertEquals
(
2
,
o
.
getValue
());
}
/**
* testGetKey tests the getKey method
*/
@
Test
public
void
testGetKey
()
{
assertEquals
(
"one"
,
o
.
getKey
());
o
.
changeKey
(
"two"
);
assertEquals
(
"two"
,
o
.
getKey
());
}
/**
* testGetValue tests get Value
*/
@
Test
public
void
testGetValue
()
{
assertEquals
(
1
,
o
.
getValue
());
o
.
changeValue
(
2
);
assertEquals
(
2
,
o
.
getValue
());
}
}
MapTest.class
public synchronized class MapTest { Map m; public void MapTest(); public void start(); public void testContainsKey(); public void testGet(); public void testKeySet(); public void testPut(); public void testRemove(); }
MapTest.java
MapTest.java
import
static
org
.
junit
.
Assert
.
*
;
import
org
.
junit
.
Before
;
import
org
.
junit
.
Test
;
public
class
MapTest
{
Map
m
;
/**
* start() creates an initial map to test.
*/
@
Before
public
void
start
(){
m
=
new
Map
();
}
/**
* testContainsKey tests the containsKey function.
* It tests when there are more than one object, one object,
* when the object is contained, and when the object is not contained.
*/
@
Test
public
void
testContainsKey
()
{
assertFalse
(
m
.
containsKey
(
5
));
m
.
put
(
5
,
"five"
);
m
.
put
(
4
,
"four"
);
assertTrue
(
m
.
containsKey
(
5
));
m
.
remove
(
5
);
assertFalse
(
m
.
containsKey
(
5
));
m
.
remove
(
4
);
assertFalse
(
m
.
containsKey
(
4
));
}
/**
* testGet tests the get function of map.
*
* It tests when there are no objects, when there is an object, and when there are more than one objects.
*/
@
Test
public
void
testGet
()
{
assertEquals
(
null
,
m
.
get
(
5
));
m
.
put
(
5
,
"five"
);
assertEquals
(
"five"
,
m
.
get
(
5
));
m
.
put
(
4
,
"four"
);
assertEquals
(
"five"
,
m
.
get
(
5
));
}
/**
* testKeySet tests keySet.
*/
@
Test
public
void
testKeySet
()
{
assertEquals
(
true
,
m
.
keySet
().
isEmpty
());
m
.
put
(
5
,
"five"
);
assertEquals
(
false
,
m
.
keySet
().
isEmpty
());
assertEquals
(
true
,
m
.
keySet
().
contains
(
5
));
}
/**
* testPut tests the put method of map.
*/
@
Test
public
void
testPut
()
{
assertEquals
(
null
,
m
.
get
(
5
));
m
.
put
(
5
,
"five"
);
assertEquals
(
"five"
,
m
.
get
(
5
));
m
.
put
(
5
,
"changed"
);
m
.
put
(
6
,
"six"
);
assertEquals
(
"changed"
,
m
.
get
(
5
));
assertEquals
(
"six"
,
m
.
get
(
6
));
}
/**
* testRemove tests map's remove function
*
* It tests if it can remove something that isnt in map, and removal of objects not in order.
*/
@
Test
public
void
testRemove
()
{
assertEquals
(
null
,
m
.
remove
(
"a"
));
m
.
put
(
5
,
"five"
);
m
.
put
(
4
,
"four"
);
m
.
put
(
3
,
"three"
);
assertEquals
(
"three"
,
m
.
remove
(
3
));
assertEquals
(
"five"
,
m
.
remove
(
5
));
assertEquals
(
"four"
,
m
.
remove
(
4
));
}
}
.project
assignment 8 org.eclipse.jdt.core.javabuilder org.eclipse.jdt.core.javanature
