CS310 Dictionary ADT

The Project:

The data structures we have studied previously are not suitable for managing large data sets. For this assignment, you will write three implementations of the DictionaryADT interface, which is provided.

• Hash Table
• Binary Search Tree
• Red Black Tree

Your project will consist of the following files which must go in a package named data_structures:

• DictionaryADT.java (provided) The Dictionary interface
• Hashtable.java Your Hashtable implementation of the DictionaryADT, with chaining.
• ListADT.java The list ADT, which is provided.
• LinkedListDS.java The linked list, which is provided. (Since your previous implementations of a linked list were priority queues, I'm not asking you to write another linked list implementation.)
• BinarySearchTree.java A standard Binary Search Tree implementation of the DictionaryADT.
• BalancedTreeDictionary.java A red/black tree implementation of the DictionaryADT, using the Java API class java.util.TreeMap

Additional Details:

• Your project will consist of exactly the files/classes named in this assignment. You may not have any additional classes or public methods. (Inner classes and private methods are okay).
• For the BinarySearchTree and Hashtable implementations, you must write your own code; you may import only:

java.util.Iterator,
java.util.NoSuchElementException, and
java.util.ConcurrentModificationException.

• For the red/black tree implementation, you will use the Java API class java.util.TreeMap. For this implementation only, you may use any classes in the Java API.
• Your Hashtable implementation must use chaining, and use class LinkedListDS
• Your Dictionary implementation methods should be as efficient as possible.
• Each source code file should begin with comments, including your name and class account number.
• Your class names and methods and method signatures must match the specifications exactly.
• Your iterators must be 'fail-fast'.
• Projects that fail to compile will receive very little or no credit.
• Your project will be graded with a driver program not available to you, and will use the instructor's versions of the supplied files.
• A sample driver program will be made available to you for testing.

The Report:

You will submit a written report in addition to your source code files. The report should include an analysis of the runtime complexity of the get/put/delete methods in your three DictionaryADT implementations. Additionally, you will do empirical timing tests to show that your data structures perform as expected. Use graphs to highlight the performance differences between the data structures.

The DictionaryADT:

package data_structures;

import java.util.Iterator;
import java.util.NoSuchElementException;

public interface DictionaryADT< K, V> {

// Adds the given key/value pair to the dictionary. Returns
// false if the dictionary is full, or if the key is a duplicate.
// Returns true if addition succeeded.
public boolean put(K key, V value);

// Deletes the key/value pair identified by the key parameter.
// Returns true if the key/value pair was found and removed,
// otherwise false.
public boolean delete(K key);

// Returns the value associated with the parameter key. Returns
// null if the key is not found or the dictionary is empty.
public V get(K key);

// Returns the key associated with the parameter value. Returns
// null if the value is not found in the dictionary. If more
// than one key exists that matches the given value, returns the
// first one found.
public K getKey(V value);

// Returns the number of key/value pairs currently stored
// in the dictionary
public int size();

// Returns true if the dictionary is full
public boolean isFull();

// Returns true if the dictionary is empty
public boolean isEmpty();

// Makes the dictionary empty
public void clear();

// Returns an Iterator of the keys in the dictionary, in ascending
// sorted order
public Iterator< K> keys();

// Returns an Iterator of the values in the dictionary. The
// order of the values must match the order of the keys.
public Iterator< V> values();
}

The ListADT:

package data_structures;

import java.util.Iterator;

public interface ListADT< E> extends Iterable< E> {

// Adds the Object obj to the beginning of the list
public void addFirst(E obj);

// Adds the Object obj to the end of the list
public void addLast(E o);

// Removes the first Object in the list and returns it.
// Returns null if the list is empty.
public E removeFirst();

// Removes the last Object in the list and returns it.
// Returns null if the list is empty.
public E removeLast();

// Returns the first Object in the list, but does not remove it.
// Returns null if the list is empty.
public E peekFirst();

// Returns the last Object in the list, but does not remove it.
// Returns null if the list is empty.
public E peekLast();

// Removes the specific Object obj from the list, if it exists.
// Returns true if the Object obj was found and removed, otherwise false
public boolean remove(E obj);

// The list is returned to an empty state.
public void makeEmpty();

// Returns true if the list contains the Object obj, otherwise false
public boolean contains(E obj);

// Returns the object obj if it exists in the list, otherwise returns
// null. Does not modify the list in any way.
public E search(E obj);

// Returns true if the list is empty, otherwise false
public boolean isEmpty();

// Returns true if the list is full, otherwise false
public boolean isFull();

// Returns the number of Objects currently in the list.
public int size();

// Returns an Iterator of the values in the list, presented in
// the same order as the list.
public Iterator< E> iterator();
}

The LinkedListDS:

package data_structures;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedListDS< E> implements ListADT< E> {

/////////////////////////////////////////////////////////////////
class Node< E> {

E data;
Node< E> next;

public Node(E obj) {
data = obj;
next = null;
}
}

// END CLASS NODE ///////////////////////////////////////////////

/////////////////////////////////////////////////////////////////
class ListIteratorHelper implements Iterator< E> {

Node< E> index;

public ListIteratorHelper() {
index = head;
}

public boolean hasNext() {
return index != null;
}

public E next() {
if(!hasNext())
throw new NoSuchElementException();
E tmp = index.data;
index = index.next;
return tmp;
}

public void remove() {
throw new UnsupportedOperationException();
}
}
// END CLASS LIST_ITERATOR_HELPER //////////////////////////////

private Node< E> head, tail;
private int currentSize;

public LinkedListDS() {
head = tail = null;
currentSize = 0;
}

public void addFirst(E obj) {
Node< E> newNode = new Node< E>(obj);
if(isEmpty())
head = tail = newNode;
else {
newNode.next = head;
head = newNode;
}
currentSize++;
}

public void addLast(E obj) {
Node< E> newNode = new Node< E>(obj);
if(isEmpty())
head = tail = newNode;
else {
tail.next = newNode;
tail = newNode;
}
currentSize++;
}

public E removeFirst() {
if(isEmpty())
return null;
E tmp = head.data;
head = head.next;
// if(head == null)
// head = tail = null;
currentSize--;
return tmp;
}

public E removeLast() {
if(isEmpty())
return null;
E tmp = tail.data;
if(head == tail) // only one element in the list
head = tail = null;
else {
Node< E> previous = null, current = head;
while(current != tail) {
previous = current;
current = current.next;
}
previous.next = null;
tail = previous;
}
currentSize--;
return tmp;
}

public E peekFirst() {
if(head == null)
return null;
return head.data;
}

public E peekLast() {
if(tail == null)
return null;
return tail.data;
}

public boolean remove(E obj) {
if(isEmpty())
return false;
Node< E> previous = null, current = head;
while(current != null) {
if( ((Comparable< E>)current.data).compareTo(obj) == 0) {
if(current == head)
removeFirst();
else if(current == tail)
removeLast();
else {
previous.next = current.next;
currentSize--;
}
return true;
}
previous = current;
current = current.next;
}
return false;
}

// not in the interface. Removes all instances of the key obj
public boolean removeAllInstances(E obj) {
Node< E> previous = null, current = head;
boolean found = false;
while(current != null) {
if(((Comparable< E>)obj).compareTo(current.data) == 0) {
if(previous == null) { // node to remove is head
head = head.next;
if(head == null) tail = null;
}
else if(current == tail) {
previous.next = null;
tail = previous;
}
else
previous.next = current.next;
found = true;
currentSize--;
current = current.next;
}
else {
previous = current;
current = current.next;
}
} // end while
return found;
}

public void makeEmpty() {
head = tail = null;
currentSize = 0;
}

public boolean contains(E obj) {
Node current = head;
while(current != null) {
if( ((Comparable< E>)current.data).compareTo(obj) == 0)
return true;
current = current.next;
}
return false;
}

public E search(E obj) {
Node current = head;
while(current != null) {
if( ((Comparable< E>)current.data).compareTo(obj) == 0)
return (E) current.data;
current = current.next;
}
return null;
}

public boolean isEmpty() {
return head == null;
}

public boolean isFull() {
return false;
}

public int size() {
return currentSize;
}

public Iterator< E> iterator() {
return new ListIteratorHelper();
}
}