Instructions
Requirements and Specifications
Source Code
package edu.uwm.cs351.ps;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;
import junit.framework.TestCase;
public class Dictionary {
private static class Node {
Name key;
Object data;
Node left, right;
Node(Name k, Object d) { key = k; data = d; }
}
private Node root;
private int size;
private static boolean doReport = true;
private static boolean report(String s) {
if (doReport) System.err.println("Invariant error: " + s);
return false;
}
// This method is useful for checkTree if errors are found.
private static int reportNeg(String s) {
report(s);
return -1;
}
/**
* Check if a subtree is well formed.
* None of the keys may be null and all of the keys must be
* in the given range (lo,hi) exclusive, except that a null bound means
* there is no bound in that direction, and finally all subtrees
* must also be well formed.
* @param r root of the subtree, may be null
* @param lo exclusive lower bound. If null, then no lower bound.
* @param hi exclusive upper bound. If null, then no upper bound.
* @return number of nodes in subtree, if well formed, -1 otherwise.
*/
private static int checkTree(Node r, String lo, String hi) {
if (r == null) {
return 0;
}
if (r.key == null) {
return -1;
}
if (lo != null && r.key.rep.compareTo(lo) <= 0) {
return -1;
}
if (hi != null && r.key.rep.compareTo(hi) >= 0) {
return -1;
}
int lres = checkTree(r.left, lo, r.key.rep);
int rres = checkTree(r.right, r.key.rep, hi);
if (lres == -1 || rres == -1) {
return -1;
}
return 1 + lres + rres;
}
private boolean wellFormed() {
// NB: If you correct check for things in range (and no duplicates)
// then cycles will be automatically detected (they will be duplicates).
int checkSize = checkTree(root, null, null);
if (checkSize == -1) {
return false;
}
return size == checkSize;
}
/**
* Create an empty dictionary.
*/
public Dictionary() {
size = 0;
root = null;
assert wellFormed() : "invariant broken in constructor";
}
private Object[] get(Node currNode, Name n) {
if (currNode == null) {
return null;
}
String currName = currNode.key.rep;
int diff = currName.compareTo(n.rep);
if (diff > 0) {
return get(currNode.left, n);
}
else if (diff < 0) {
return get(currNode.right, n);
}
else {
return new Object[]{currNode.data};
}
}
/**
* Return the definition of a name in this dictionary
* @param n name to lookup, may not be null
* @return definition for the name
* @throws ExecutionException if there is no definition, or if the name is null
*/
public Object get(Name n) throws ExecutionException {
assert wellFormed() : "invariant broken at start of get()";
if (n == null) {
throw new ExecutionException();
}
Object[] result = get(root, n);
if (result != null) {
return result[0];
}
throw new ExecutionException("undefined");
}
/**
* Return whether the parameter is a name in the dictionary
* @param n name to look up, may be null
* @return whether n is a name in the dictionary
*/
public boolean known(Name n) {
assert wellFormed() : "invariant broken at start of known()";
if (n == null) {
return false;
}
return get(root, n) != null;
}
/**
* Return the number of names defined in the dictionary.
* @return number of names in dictionary.
*/
public int size() {
assert wellFormed() : "invariant broken at start of size()";
return size;
}
private void put(Node currNode, Name n, Object x) {
String currName = currNode.key.rep;
int diff = currName.compareTo(n.rep);
if (diff > 0) {
if (currNode.left == null) {
currNode.left = new Node(n, x);
size++;
}
else {
put(currNode.left, n, x);
}
}
else if (diff < 0) {
if (currNode.right == null) {
currNode.right = new Node(n, x);
size++;
}
else {
put(currNode.right, n, x);
}
}
else {
currNode.data = x;
}
}
/**
* Define a name in the dictionary.
* If the name already has a definition, the old definition is replaced
* with the new definition.
* @param n name to defined (must not be null)
* @param x (new) definition of the name (may be null)
* @exception ExecutionException if the name is null
*/
public void put(Name n, Object x) {
assert wellFormed() : "invariant broken at start of put()";
if (n == null) {
throw new ExecutionException();
}
if (root == null) {
root = new Node(n, x);
size = 1;
return;
}
put(root, n, x);
assert wellFormed() : "invariant broken at end of put()";
}
private void copy(Node currNode) {
if (currNode == null) {
return;
}
put(currNode.key, currNode.data);
copy(currNode.left);
copy(currNode.right);
}
/**
* Copy all the definitions from the argument into this dictionary
* replacing previous definitions (if any).
* @param dict1 dictionary whose definition we copy (must not be null)
* NB: Behavior if the argument is null is not defined.
*/
public void copy(Dictionary dict1) {
assert wellFormed() : "invariant broken at start of copy()";
if (dict1 == null) {
return;
}
copy(dict1.root);
assert wellFormed() : "invariant broken at start of copy()";
}
private void values(Node currNode, Collection