Anyone? J unit test cases

Who can write them? 

 

I also need someone to help problems debug a little code. It needs to be finished before midnight tonight.. its 9 here. 

 

Instructions:

 

1. Use heap, heaptest, priorityqueue, priority queue test as examples for how to write junit tests. 

Please use the same commenting format etc.

 

Be thorough (hopefully more thorough than the examples)

 

2. Red Black tree, and huffman need to be broken in to individual java docs for each class. Debugged( im having a few issues) 

 

3. hashmap and inverted, red black, and huffman need to Have j unit tests written for them. 

 

4. Please divide each into files. Huffman, red black, hashmap, inverted with their java docs and junit test java dogs. 

 

5. return to me by midnight. 

   

import java.lang.reflect.Array;
import java.util.NoSuchElementException;

public class Heap> {
int s;
Object[] h;
int maxS;
/**
* Heap takes in the initial size of the heap.
* @param i the integer value of the size of the heap.
*/
public void Heap(int i){
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;
obj f= (obj) first;
obj l= (obj) last;
System.out.println(“this is first: “+ f.getPriority() + ” and this is last: “+ l.getPriority());
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];
obj b= (obj) below;
obj ab= (obj) above;
if(below.compareTo(above)>0){
// System.out.println(ab.getPriority()+ ” is being switched with ” + b.getPriority());
// System.out.println(“its compareTo value is: “+ below.compareTo(above));
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(above.compareTo(belowL)<0 && belowL.compareTo(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(above.compareTo(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(above.compareTo(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(above.compareTo(belowR)<0){ h[a+1]= above; h[n]=belowR; n=a; }else{ inPlace=true; } } } } }

import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;
/**
* HeapTest tests Heap
* @author tai-lanhirabayashi
*
*/
public class HeapTest {
Heap h;

/**
* SetUp initializes a heap with the values (1,2,3,4,5)
* insert and heap() are assumed to be working in order for the other functions to work
*/
@Before
public void setUp(){
h=new Heap();
h.Heap(10);
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]);
System.out.println(“this is 5”);
h.insert(5);

System.out.println(h.h[0] + “,”+h.h[1] + “,”+h.h[2] + “,”+h.h[3] + “,”+h.h[4]);
}

/**
* testFindMax tests the findMax function of heap
*/
@Test
public void testFindMax() {
assertEquals(5, h.findMax());
}

/**
* testSize tests the size function of heap
*/
@Test
public void testSize() {
assertEquals(5, h.size());
}

/**
* testRemoveMax tests the remove max function of heap.
*/
@Test
public void testRemoveMax() {
h.removeMax();
assertEquals(4, h.findMax());
}
/**
* testNegative tests how heap handles negative numbers.
*/
@Test
public void testNegative(){
h=new Heap();
h.Heap(10);
h.insert(0);
h.insert(-1);
h.insert(-2);
assertEquals(0, h.findMax());

}
}

public class PriorityQueue {
Heap q;
boolean high;
/**
* The constructor creates a heap. Mode flags if larger values or lower values are of priority.
* @param mode of priority value
*/
public PriorityQueue(PriorityType mode){
q=new Heap();
q.Heap(10);
high=true;

if(mode.equals(PriorityQueue.PriorityType.LOW_VALUE_PRIORITY)){
high=false;
}

}

/**
* getFirst returns the next item in the queue.
* If the queue is empty it returns null.
* @return E the object in the first position
*/
public E getFirst(){
if(q.size()==0){
return null;
}
return (E) q.findMax();
}
/**
* getPriority returns the priority of the next item in the queue.
* It returns Integer.MIN_VALUE if the queue is empty.
* @return int of the highest priority
*/
public int getPriority(){
if(q.size()==0){
return Integer.MIN_VALUE;
}
obj o = (obj) q.findMax();

int a= o.getPriority();
if(high==false){
a=a*(-1);
}
return a;
}

/**
* remove removes the first item from the queue.
* @return E the object in the first position of the queue
*/
E remove(){
if(q.size()==0){
return null;
}

return (E) q.removeMax();
}

/**
* This adds an item to the queue with the priority priority passed in.
* @param item to be added into the queue
* @param priority of the item being added
*/
void add(E item, int priority){
obj o;
if(high){
o = new obj(item, priority);
}else{
o = new obj(item, (-priority));
}
q.insert(o);
}

/**
* isEmpty returns if the queue is empty or not.
* @return boolean if it is empty or not
*/
boolean isEmpty(){
if(q.size()!= 0){
return false;
}
return true;
}

/**
* size returns the size of the queue
* @return the integer size.
*/
int size(){
return q.size();
}

public static enum PriorityType {HIGH_VALUE_PRIORITY, LOW_VALUE_PRIORITY};
}

import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;
/**
* PriorityQueueTest tests the priority queue.
* @author tai-lanhirabayashi
*
*/
public class PriorityQueueTest {
PriorityQueue p;

/**
* setUp initializes the test
*/
@SuppressWarnings(“unchecked”)
@Before
public void setUp(){
p=new PriorityQueue(PriorityQueue.PriorityType.HIGH_VALUE_PRIORITY);
p.add(“zero”,0);
p.add(“one”,1);
p.add(“two”,2);
p.add(“three”,3);
p.add(“four”,4);
p.add(“five”,5);
System.out.println(“this is the tree: “+ ((obj) p.q.h[0]).getPriority() + ” ” + ((obj) p.q.h[1]).getPriority()+” “+((obj) p.q.h[2]).getPriority()+ ” ” + ((obj) p.q.h[3]).getPriority()+ ” ” + ((obj) p.q.h[4]).getPriority()+ ” ” + ((obj) p.q.h[5]).getPriority());
}

/**
* tests the getFirst() function
*/
// @Test
public void testGetFirst() {
obj a = (obj) p.getFirst();
assertEquals(5, a.getPriority());
}
/**
* tests the getPriority function
*/
@Test
public void testGetPriority() {
obj a= (obj) p.getFirst();
assertEquals(5, a.getPriority());
p.remove();
p.remove();
p.remove();
p.remove();
p.remove();
a=(obj) p.getFirst();
assertEquals(0, a.getPriority());

}
/**
* tests the is empty function
*/
@Test
public void testIsEmpty() {
assertFalse(p.isEmpty());
p.remove();
p.remove();
p.remove();
p.remove();
p.remove();
p.remove();
assertTrue(p.isEmpty());
}
/**
* tests the remove function
*/
@Test
public void testRemove() {
p.remove();
obj a= (obj) p.getFirst();
assertEquals(4,a.getPriority());
p.remove();
p.remove();
p.remove();
p.remove();
p.remove();
assertEquals(null, p.remove());
}
/**
* tests the size function
*/
@Test
public void testSize() {
assertEquals(6,p.size());
p.remove();
assertEquals(5,p.size());
p.remove();
assertEquals(4,p.size());
p.remove();
p.remove();
p.remove();
p.remove();
assertEquals(0,p.size());

}

@Test
@SuppressWarnings({ “unchecked”, “rawtypes” })
public void testLow(){
p=new PriorityQueue(PriorityQueue.PriorityType.LOW_VALUE_PRIORITY);
p.add(“zero”, 0);
p.add(“one”, 1);
p.add(“negative one”, -1);
p.add(“2”, 2);
assertEquals(-1, p.getPriority());
}
}

/**
* @(#)Red_Black_Tree.java
*
* Red_Black_Tree application
*
* @author
* @version 1.00 2013/1/8
*/

import java.util.Random;
import java.util.Stack;
class RedBlackTree
{
/* *************************************************** *
* PRIVATE FIELDS *
* *************************************************** */

private RedBlackTree tree;
private int size;

/* If during an insert() or delete() it is found that
* the key is present in the tree, keyFound will be true
* and prevValue will contain the previous value
* associated with the key before the update.
*/
private boolean keyFound;
private Object prevValue;

/* *************************************************** *
* PUBLIC INTERFACE *
* *************************************************** */

/*
* Constructs a new empty red-black tree.
*/
public RedBlackTree() {
tree = null;
size = 0;
}

/**
* Maps the key to the specified value in this red-black tree.
* Neither the key, nor the value can be
* null.
* @return the previous value to which the key was mapped,
* or null if the key did not have a previous
* mapping in the red-black tree.
*/
public synchronized Object put(String key, Object value) {
if (key == null || value == null)
throw new NullPointerException();

RBTree node = new RBTree();
node.key = key;
node.value = value;
keyFound = false;
tree = insert(node, tree);
if (keyFound)
return prevValue;
else {
size++;
return null;
}
}

/**
* Gets the object associated with the specified key in the red-black tree.
* @return the value to which the key is mapped in the red-black tree, or
* null if the key is not mapped to any value in
* this red-black tree.
*/
public synchronized Object get(String key) {
RBTree t = tree;
int comp;

while (t != null && (comp = key.compareTo(t.key)) != 0)
if (comp < 0) t = t.left; else t = t.right; return t != null ? t.value : null; } /** * Returns true if this red-black tree contains no mappings.
*/
public boolean isEmpty() {
return tree == null;
}

/**
* Removes tke key (and its corresponding value) from this red-black tree.
* This method does nothing if the key is not in the red-black tree.
* @return the value to which the key had been mapped in this red-black tree,
* or null if the key did not have a mapping.
*/
public synchronized Object remove(String key) {
RBTree node = tree;
while (node != null) {
int comp = key.compareTo(node.key);
if (comp < 0) node = node.left; else if (comp > 0)
node = node.right;
else {
prevValue = node.value;
tree = delete(node, tree);
size–;
return prevValue;
}
}
return null;
}

/**
* Clear the red-black tree so that it contains no mappings.
*/
public synchronized void clear() {
tree = null;
size = 0;
}

/**
* Returns the number of keys in this red-black tree.
*/
public int size() {
return size;
}

/* 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].*/
public String toString()
{
if (key != null || value != null)
throw new NullPointerException();
RBTree node = new RBTree();
node.key = key;
node.value = value;
keyFound = true;
while (node != null)
{
if(node.color == RBTree.RED && node.key() = node.value())
{
string x = “R”;
System.out.println(“[” + value +”:” + x + “]”+ ” “);

if(node.color == RBTree.BLACK && node.key() = node.value())
{
string x = “B”;
System.out.println(“[” + value +”:” + x + “]”+ ” “);
}
return key;
}
}
}

/**
* Returns a string displaying the tree structure
* and the priority numbers.
*/
public synchronized String printDebug() {
StringBuffer strbuf = new StringBuffer();
String newline = System.getProperty(“line.separator”);
strbuf.append(“size: ” + size + newline);
if (tree != null)
tree.printDebug(0, strbuf);
return strbuf.toString();
}

public String printStat() {
StatStruct stat = new StatStruct();
collectStat(tree, 0, stat);
StringBuffer strbuf = new StringBuffer();
String newline = System.getProperty(“line.separator”);
strbuf.append(“Aver depth: ” +
(float) stat.totDepth / this.size + newline);
strbuf.append(“Max depth: ” + stat.maxDepth + newline);
return strbuf.toString();
}

/* *************************************************** *
* PRIVATE METHODS *
* *************************************************** */

/* Inserts a node into tree and returns the updated red-black tree */
private RBTree insert(RBTree node, RBTree tree) {
RBTree father = null, son = tree;
/* Insert the new node into the tree. */
while (son != null) {
father = son;
int comp = node.key.compareTo(son.key);
if (comp < 0) son = son.left; else if (comp > 0)
son = son.right;
else {
keyFound = true;
prevValue = son.value;
son.value = node.value;
return tree;
}
}
node.parent = father;
if (father == null)
tree = node;
else if (node.key.compareTo(father.key) < 0) father.left = node; else father.right = node; /* Inforce the color invariants of the red-black tree. */ node.color = RBTree.RED; while (node != tree && node.parent.color == RBTree.RED) { if (node.parent == node.parent.parent.left) { son = node.parent.parent.right; if (son != null && son.color == RBTree.RED) { node.parent.color = RBTree.BLACK; son.color = RBTree.BLACK; node = node.parent.parent; node.color = RBTree.RED; } else { if (node == node.parent.right) { node = node.parent; tree = node.rotateLeft(tree); } node.parent.color = RBTree.BLACK; node.parent.parent.color = RBTree.RED; tree = node.parent.parent.rotateRight(tree); } } else { son = node.parent.parent.left; if (son != null && son.color == RBTree.RED) { node.parent.color = RBTree.BLACK; son.color = RBTree.BLACK; node = node.parent.parent; node.color = RBTree.RED; } else { if (node == node.parent.left) { node = node.parent; tree = node.rotateRight(tree); } node.parent.color = RBTree.BLACK; node.parent.parent.color = RBTree.RED; tree = node.parent.parent.rotateLeft(tree); } } } tree.color = RBTree.BLACK; return tree; } { /* Deletes a node from a red-black tree and * returns the updated red-black tree. */ private RBTree delete(RBTree node, RBTree tree) { RBTree x, y; if (node.left == null || node.right == null) y = node; else y = node.successorGet(); if (y.left != null) x = y.left; else x = y.right; if (x != null) x.parent = y.parent; if (y.parent == null) tree = x; else if (y == y.parent.left) y.parent.left = x; else y.parent.right = x; if (y != node) { node.key = y.key; node.value = y.value; } /* If the node to be removed is BLACK, * restore the red-black tree invariants. * The color of a null leaf is BLACK. */ if (y.color == RBTree.BLACK) { RBTree father = y.parent; while (x != tree && (x == null || x.color == RBTree.BLACK)) { if (x == father.left) { RBTree w = father.right; if (w == null) x = tree; else { if (w.color == RBTree.RED) { w.color = RBTree.BLACK; father.color = RBTree.RED; tree = father.rotateLeft(tree); continue; } if ((w.left == null || w.left.color == RBTree.BLACK) && (w.right == null || w.right.color == RBTree.BLACK)) { w.color = RBTree.RED; x = father; father = x.parent; } else { if (w.right == null || w.right.color == RBTree.BLACK) { if (w.left != null) { w.left.color = RBTree.BLACK; w.color = RBTree.RED; tree = w.rotateRight(tree); w = father.right; } } w.color = father.color; father.color = RBTree.BLACK; if (w.right != null) w.right.color = RBTree.BLACK; tree = father.rotateLeft(tree); x = tree; } } } else { RBTree w = father.left; if (w == null) x = tree; else { if (w.color == RBTree.RED) { w.color = RBTree.BLACK; father.color = RBTree.RED; tree = father.rotateRight(tree); continue; } if ((w.right == null || w.right.color == RBTree.BLACK) && (w.left == null || w.left.color == RBTree.BLACK)) { w.color = RBTree.RED; x = father; father = x.parent; } else { if (w.left == null || w.left.color == RBTree.BLACK) { if (w.right != null) { w.right.color = RBTree.BLACK; w.color = RBTree.RED; tree = w.rotateLeft(tree); w = father.left; } } w.color = father.color; father.color = RBTree.BLACK; if (w.left != null) w.left.color = RBTree.BLACK; tree = father.rotateRight(tree); x = tree; } } } } if (x != null) x.color = RBTree.BLACK; } return tree; } } private class StatStruct { int totDepth = 0; int maxDepth = 0; } private void collectStat(RBTree t, int depth, StatStruct stat) { if (t == null) return; else { if (depth > stat.maxDepth)
stat.maxDepth = depth;
stat.totDepth += depth;
collectStat(t.left, depth + 1, stat);
collectStat(t.right, depth + 1, stat);
}
}
/*This method will traverse the tree and return true if any red node has a red child.*/
public boolean redViolationExists()
{
node.color = RBTree.RED;
while (node != tree && node.parent.color == RBTree.RED)
{
if (node.parent == node.parent.parent.left)
{
son = node.parent.parent.right;
if (son != null && son.color == RBTree.RED)
{
return true;
}

}
}
}
/** The following function checks the red black tree black height
* @param n the root node is inputed then a traversal is done to calculate the black-height
* @return Return an error message / mesages informing the user whether or not the black height was maintained
* @author
*/
public static void getCount (SkaRedBlackTreeNode skaRedBlackTreeNode) {
VizRedBlackTreeNode n = skaRedBlackTreeNode.getVizRep();
if (validRoot(n))
{
static int lcount = leftCount(n);
static int rcount = rightCount(n);
if (rcount == lcount) {
n.displayMsg(“Black height maintained”);
}
else
// n.displayWarning(“rcount ” + rcount + ” lcount ” + lcount);
n.displayError(“Red Black Tree is unbalanced”);
}
}
/** The following function counts all the black node of the left side of the tree
* @param n the left child is inputed and a traversal is done to count all the black nodes
* */
public static int leftCount (VizRedBlackTreeNode n)
{
if (n == null)
return 0;
else if (n.getrbtColr() == Color.black)
return 1 + leftCount(n.getLeft());
else
leftCount(n.getLeft());
}
/** The following function counts all the black node of the right side of the tree
* @param n the right child is inputed and a traversal is done to count all the black nodes
* */
public static int rightCount (VizRedBlackTreeNode n)
{
if (n == null)
return 0;
else if (n.getrbtColr() == Color.black) {
return 1 + rightCount (n.getRight());
else
rightCount(n.getRight());
}
}

}

// Table.java: Huffman code frequency table

import java.io.*;

import java.util.TreeSet

class Table

{

public final int MAXT = 100; // maximum number of different symbols

public int currTableSize; // current size as table is constructed

public Entry[] tab; // the table array, not allocated

private Reader in; // internal file name for input stream

String file = “”; // the whole input file as a String

private boolean fileOpen = false; // is the file open yet?

private String fileName; // name of input file, if present

private int totalChars = 0; // total number of chars read

char markerChar = ‘@’; // sentinal at end of file

// Table: constructor, input parameter: input file name or null

public Table(String f) {

fileName = f;

currTableSize = 0;

tab = new Entry[MAXT];

}

// dumpTable: debug dump of contents of Table

public void dumpTable() {

int i;

System.out.println(“\nDump of Table —–>”);

System.out.println(” Size: ” + currTableSize);

for (i = 0; i < currTableSize; i++) {

System.out.println(“Entry ” + i + “. Symbol: ” +

tab[i].symb + “, Weight: ” + tab[i].weight +

“, Representation: ” + tab[i].rep);

}

System.out.println(“—-> End Dump of Table\n”);

}

// getNextChar: fetches next char. Also opens input file

private char getNextChar() {

char ch = ‘ ‘; // = ‘ ‘ to keep compiler happy

if (!fileOpen) {

fileOpen = true;

if (fileName == null)

in = new InputStreamReader(System.in);

else

{

try {

in = new FileReader(fileName);

}

catch (IOException e) {

System.out.println(“Exception opening ” + fileName);

}

}
}
try {

ch = (char)in.read();

}

catch (IOException e) {

System.out.println(“Exception reading character”);

}

return ch;

}

// buildFromFile: read file and build the map of the character frequencies

private void buildFromFile(File file) throws FileNotFoundException {

//

Map freqMap = new BSTMap();Scanner scanner = new Scanner(file);

scanner.useDelimiter(“”);

String character;

while (scanner.hasNext()){

character = scanner.next();

Integer count = freqMap.get(character);

if (count == null){

count = Integer.valueOf(0);

}

freqMap.put(character, count+1);

}

// for each key, make a tree and load it into the priority queue

PriorityQueue> treeQueue = new PriorityQueue>(freqMap.keySet().size(), new CountPairTreeComparator

BinaryTree tmpTree;

for (String key: freqMap.keySet()){

int frequency = freqMap.get(key);

tmpTree = new BinaryTree(null, new CountPair(key, frequency), null);

treeQueue.add(tmpTree);

}

Public interface Map,V>

{

//This should load the value value into the map at the location //associated with the key, replacing any preexisting value

//already associated with the key.

void put(K key, V value)

{
Map freqMap = new BSTMap();Scanner scanner = new Scanner(file);
scanner.useDelimiter(“”);
String character;
while (scanner.hasNext()){
character = scanner.next();
Integer count = freqMap.get(character);
if (count == null){
count = Integer.valueOf(0);
}
freqMap.put(character, count+1);

}}

//This should fetch the value V associated with the key key, or //null, if no match can be found.

int V get(K key)

{

int e = freqMap.get(key);

List l = new ListNode;

if( l.nextList.compareTo(e) != null){

V = e;

return V;

}

//This will report if there is a value associated with the value //key in the map.

boolean containsKey(K key)

{
int e = freqMap.get(key);
List l = new ListNode;
if( l.nextList.compareTo(e) != null){

return true;

else
{

return false;

}

//This method should remove the entry associated with key and //return the associated value. Return null if the key is

//not found.

public V remove(K key)

{
int e = freqMap.get(key);
List l = new ListNode;
if( l.nextList.compareTo(e) != null){

l.nextList = null;

return e;

}
else
{

return null;

}}

//This method should return a Set of all available keys in the //map. You may use the java.util.TreeSet class to return

//these. You can build these on the fly using a traversal, or //collect them as new keys are added to the map.

Set keySet()

{
BinaryTree tmpTree;

while (void put(K key, V value) = 0)

{

Return K;

}}

//buildFromFile: fetch each character and build the Table

public void buildTable() {

char ch = getNextChar();

while (ch != 65535 && ch != markerChar) { // EOF or special sentinal #

totalChars++;

file += ch;

int i = lookUp(ch);

if (i == -1) { // new entry

tab[currTableSize] = new Entry();

tab[currTableSize].symb = ch;

tab[currTableSize].weight = 1.0;

tab[currTableSize].rep = “”;

currTableSize++;

}

else

{ // existing entry

tab[i].weight += 1.0;

}

// System.out.print(ch); // for debug

ch = getNextChar();

} // while

// finish calculating the weights

for (int j = 0; j < currTableSize; j++)

tab[j].weight /= (double)totalChars;

// System.out.println(); // for debug

}

// lookUp: loop up the next char in the Table tab

public int lookUp(char ch) {

for (int j = 0; j < currTableSize; j++)

if (tab[j].symb == ch) return j;

return -1;

}

// log2: Logarithm base 2

public double log2(double d) {

return Math.log(d) / Math.log(2.0);

}

// entropy: calculate entropy of the Table

public double entropy() {

double res = 0.0;

for (int i = 0; i < currTableSize; i++)

res += tab[i].weight * log2(1.0/tab[i].weight);

return res;

}

// aveCodeLen: calculate average code length

public double aveCodeLen() {

double res = 0.0;
for (int i = 0; i < currTableSize; i++)

res += tab[i].weight * tab[i].rep.length();

return res;
}
}

// TreeNode.java: node in the Huffman tree, used for encode/decode

class TreeNode {

public double weight; // probability of symb occurring

public char symb; // the symbol to be encoded

public String rep; // string of 0’s and 1’s, the huffman code word

public TreeNode left, right; // tree pointeres

public int step; // step number in construction (just for displaying tree)

}

// ListNode.java: node in the linked list of trees, initially root node trees

class ListNode {

public TreeNode hufftree;

public ListNode next;

}

// PriorityQueue.java: implement a priority queue as a linked list of trees

// Initialize it as a linked list of singleton trees

class PriorityQueue {

private int initialCapacity;

public PriorityQueue(int initialCapacity,Comparator comparator)

{

ListNode list = null; // this points to the main list

// insert: void add(E item) insert new entry into the list

public void insert(TreeNode t) {

ListNode l = new ListNode();

l.hufftree = t;

l.next = list;

list = l;

}

//Obviously, this says if the queue is empty or not.

public boolean isEmpty()

{
ListNode l = new ListNode();
l.hufftree = t;

if(l.next == null)

{

Return true;

}

else

{

Return false;

}
list = l;
}

//This should return the size of the queue.

public int size()

{

int count = 0;

ListNode l = new ListNode();

if(l.hasnext()){

count++;

return count;

}

// buildList: create the initial list with singleton trees

public void buildList(Entry[] tab, int n) {

int i;

TreeNode tNode;

for (i = 0; i < n; i++) {

tNode = new TreeNode();

tNode.weight = tab[i].weight;

tNode.left = tNode.right = null;

tNode.symb = tab[i].symb;

tNode.rep = “”;

insert(tNode);

}
}

//This returns the next item without removing it. This returns //null if the queue is empty.

public E peek()

{

ListNode l = list;

while (l != null) {

return l.next;

}

// dumpList: debug dump of the list

public void dumpList() {

System.out.println(“\nDump of List —–>”);

ListNode l = list;

while (l != null) {

System.out.print(“Symb: ” + l.hufftree.symb);

System.out.println(“, Weight: ” + l.hufftree.weight);

l = l.next;

}

System.out.println(“—-> End Dump of List\n”);

}

//This removes the first item from the queue.

public E remove()

{

ListNode l;

if(l != null) {

l.next == null;

}

// least: Remove and return from the list tree with greatest root weight

// sort of a pain in the ass to write

public TreeNode least() {

ListNode l, oldl, minl = null, oldminl = null; // = null: for compiler

double minw = 1000000;

oldl = list;

l = list;

while (l != null) {

if (l.hufftree.weight < minw) {

minw = l.hufftree.weight;

oldminl = oldl;

minl = l;

}

oldl = l;

l = l.next;
}

if (minl == oldminl) {

list = list.next;

return minl.hufftree;

}

oldminl.next = minl.next;

return minl.hufftree;
}
}

// Huffman.java: the Huffman tree algorithm

import java.text.DecimalFormat;

class Huffman {

public TreeNode tree; // the decoding tree

public Table t; // the frequency and encoding table

public PriorityQueue p; // priority queue for building the Huffman tree

private int depth; // depth variable for debug printing of tree

String encodedFile, decodedFile; // files as Strings

char markerChar = ‘@’; // sentinal at end of file

public DecimalFormat fourDigits = new DecimalFormat(“0.0000”);

// Huffman: constructor, does all the work

public Huffman(String fileName) {

t = new Table(fileName);

t.buildTable();

// t.dumpTable();

p = new PriorityQueue();

p.buildList(t.tab, t.currTableSize);

// p.dumpList();

tree = huffman(t.currTableSize);

insertRep(tree, t.tab, t.currTableSize, “”);

displayTree(tree);

t.dumpTable();

// System.out.println(“\nInput file (as a String):”);

// System.out.println(t.file);

encodedFile = encode(t.file);

// System.out.println(“\nEncoded file (as a String):”);

// System.out.println(encodedFile);

// decodedFile = decode(encodedFile);

// System.out.println(“\nDecoded file (as a String):”);

// System.out.println(decodedFile);

System.out.println(“Entropy: ” + t.entropy() +

“, Ave. Code Length: ” + t.aveCodeLen());

}

// encode: translate the input file to binary Huffman file

public String encode(String file) {

String returnFile = “”; // encoded file to return (as a String)

for (int i = 0; i < file.length(); i++) {

int loc = t.lookUp(file.charAt(i));

if (loc == -1) {

System.out.println(“Error in encode: can’t find: ” +

file.charAt(i));

System.exit(0);

}

returnFile += t.tab[loc].rep;

}

return returnFile;

}

// decode: translate the binary file (as a string) back to chars

public String decode(String file) {

String returnFile = “”; // decoded file to return (as a String)

TreeNode treeRef; // local tree variable to keep chasing into tree

int i = 0; // index in the Huffman String

while (i < file.length()) { // keep going to end of String

treeRef = tree; // start at root of tree

while (true) {

if (treeRef.symb != markerChar) { // at a leaf node

returnFile += treeRef.symb;

break;

}

else if (file.charAt(i) == ‘0’) { // go left with ‘0’

treeRef = treeRef.left;

i++;

}

else { // go right with ‘1’

treeRef = treeRef.right;

i++;
}

} // while (true)

} // while
return returnFile;
}

// huffman: construct the Huffman tree, for decoding

public TreeNode huffman(int n) {

int i;

TreeNode tree = null; // = null for compiler

for (i = 0; i < n-1; i++) {

tree = new TreeNode();

tree.left = p.least();

tree.left.step = i + 1; // just for displaying tree

tree.right = p.least();

tree.right.step = i + 1; // just for displaying tree

tree.weight = tree.left.weight +

tree.right.weight;

tree.symb = markerChar; // must not use ‘@’ in input //file

tree.rep = “”;

p.insert(tree);

}

return tree;

}

// displayTree: print out the tree, with initial and final comments

public void displayTree(TreeNode tree) {

System.out.println(“\nDisplay of Huffman coding tree\n”);

depth = 0;

displayTreeRecurs(tree);

}

// displayTreeRecurs: need recursive function for inorder traveral

public void displayTreeRecurs(TreeNode tree) {

depth++; // depth of recursion

String s = “”;

if (tree != null) {

s = display(tree.rep + “0”);

System.out.println(s);

displayTreeRecurs(tree.left);

s = display(tree.rep);

System.out.print(s + “+—“);

if (depth != 1)

{

if (tree.symb == markerChar) System.out.print(“+—“);

}

System.out.print(tree.symb + “: ” +

fourDigits.format(tree.weight) + “, ” + tree.rep);

if (depth != 1)

System.out.println(” (step ” + tree.step + “)”);

else System.out.println();

displayTreeRecurs(tree.right);

s = display(tree.rep + “1”);

System.out.println(s);
}

depth–;

}

// display: output blanks and verical lines to display tree

private String display(String rep) {

// tricky use of rep string to display correctly

String s = ” “;

for (int i = 0; i < rep.length() - 1; i++) { // initial chars

if (rep.charAt(i) != rep.charAt(i+1) ) s += “|”;

else s += ” “;

s += ” “;

}

return s;

}

// insertRep: tricky function to use Huffman tree to create representation

public void insertRep(TreeNode tree, Entry tab[], int n, String repr) {

//recursive function to insert Huffman codewords at each node.

// this could just insert at the leaves.

String s1, s2;

tree.rep = repr;

if ((tree.left) == null && (tree.right) == null) {

for (int i = 0; i < n; i++)

if (tree.symb == tab[i].symb)

tab[i].rep = tree.rep;

return;

}

s1 = repr;

s1 += “0”;

insertRep(tree.left, tab, n, s1); // recursive call to the left

s2 = repr;

s2 += “1”;

insertRep(tree.right, tab, n, s2); // recursive call to the right

}

// main: doesn’t do much; just feeds in input file name

public static void main(String[] args) {

Huffman huff;

// pass an input file name if present on command line

if (args.length > 0)

huff = new Huffman(args[0]);

else

huff = new Huffman(null);

}
}

package indexinvertor;
/*
* To change this template, choose Tools | Templates and open the template in
* the editor.
*/
import java.util.*;
/**
*
* @author AN
*/
public class HashMap implements Map {
private int size;
private float loadFactor;
private int count;
private int maxChainLength;
class Entry implements Map.Entry {
int hash;
Object key;
Object value;
protected Entry(int hash, Object key, Object firstValue) {
this.hash = hash;
this.key = key;
this.value = firstValue;
}
@Override
public Object getKey() {
return key;
}
@Override
public Object getValue() {
return value;
}
@Override
public Object setValue(Object value) {
Object temp = this.value;
this.value = value;
return temp;
}
};
private ArrayList> hashTable;

/*
* Returns the number of keys in this hashtable.
*/
@Override
public int size() {
return size;
}
/*
* Tests if this hashtable maps no keys to values.
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/*
* Tests if the specified object is a key in this hashtable.
* returns true if and only if the specified object
*/
@Override
public boolean containsKey(Object key) {
return get(key) != null;
}
/*
* Tests if some key maps into the specified value in this hashtable.
* returns true if and only if some key maps to the value argument & false otherwise.
*/
@Override
public boolean containsValue(Object value) {
if (value != null) {
for (int i = 0; i < hashTable.size(); i++) { for (int j = 0; j < hashTable.get(i).size(); j++) { Entry e = hashTable.get(i).get(j); if (e.value.equals(value)) { return true; } } } } else { System.out.println(" VALUE CANNOT BE NULL"); } return false; } /* * Returns the list of values to which the specified key is mapped, * or null if this map contains no mapping for the key. */ @Override public Object get(Object key) { try { if (key != null) { String keyString = (String) key; int hash = (keyString.hashCode() & 0x7FFFFFFF) % Math.max(size, hashTable.size()); List