Create A Standard Map Interface in Java Assignment Solution
- Instructions
- Requirements and Specifications
Instructions
Requirements and Specifications
Source Code
package edu.uwm.cs351.ps;
import java.util.*;
import edu.uwm.cs351.SortedSequence;
import edu.uwm.cs351.util.AbstractEntry;
import junit.framework.TestCase;
public class Dictionary extends AbstractMap{
private static class Node extends AbstractEntry{
Name key;
Object data;
Node left, right;
Node(Name k, Object d) {
key = k;
data = d;
}
@Override
public Name getKey() {
return key;
}
@Override
public Object getValue() {
return data;
}
@Override
public Object setValue(Object o) {
Object result = data;
data = o;
return result;
}
}
private Node root;
private int size;
private EntrySet entrySet;
private String version;
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 || r.key.rep == null) return reportNeg("null key found");
if (lo != null && lo.compareTo(r.key.rep) >= 0 ||
hi != null && hi.compareTo(r.key.rep) <= 0) {
return reportNeg("key out of place: " + r.key + " in (" + lo + "," + hi + ")");
}
int n1 = checkTree(r.left, lo, r.key.rep);
int n2 = checkTree(r.right, r.key.rep, hi);
if (n1 < 0 || n2 < 0) return -1;
return n1 + n2 + 1;
}
private boolean wellFormed() {
int n = checkTree(root, null, null);
if (n < 0) return false;
if (n != size) return report("Size wrong: " + size + " should be " + n);
return true;
}
/**
* Create an empty dictionary.
*/
public Dictionary() {
root = null;
size = 0;
entrySet = new EntrySet();
version = toString();
assert wellFormed() : "invariant broken in constructor";
}
private Node getNode(Node r, Name n) {
if (r == null) return r;
if (n == null) return null;
int c = r.key.rep.compareTo(n.rep);
if (c == 0) return r;
if (c > 0) return getNode(r.left, n);
else return getNode(r.right, n);
}
/**
* 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()";
Node r = getNode(root, n);
if (r != null) return r.data;
throw new ExecutionException("undefined");
}
@Override
public Object get(Object o) throws ExecutionException {
assert wellFormed() : "invariant broken at start of get()";
if (o instanceof Name) {
Node r = getNode(root, (Name) o);
if (r == null) {
return null;
}
return r.data;
}
return null;
}
/**
* 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()";
Node r = getNode(root, n);
if (r != null) return true;
return false;
}
/**
* 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 Node doPut(Node r, Name n, Object d) {
if (r == null) {
r = new Node(n, d);
++size;
} else {
int c = r.key.rep.compareTo(n.rep);
if (c == 0) r.data = d;
else if (c > 0) r.left = doPut(r.left, n, d);
else r.right = doPut(r.right, n, d);
}
return r;
}
/**
* 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)
* @throws ExecutionException if the name is null
*/
public Object put(Name n, Object x) {
assert wellFormed() : "invariant broken at start of put()";
if (n == null || n.rep == null) throw new ExecutionException("null key not allowed");
Object oldValue = get((Object) n);
root = doPut(root, n, x);
assert wellFormed() : "invariant broken at end of put()";
version = toString();
return oldValue;
}
private void doCopy(Node r) {
if (r == null) return;
put(r.key, r.data);
doCopy(r.left);
doCopy(r.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()";
doCopy(dict1.root);
assert wellFormed() : "invariant broken at start of copy()";
}
@Override
public Set> entrySet() {
return entrySet;
}
private Node getParent(Node curr, Node target) {
if (curr == null) {
return null;
}
Name currValue = curr.getKey();
Name targetValue = target.getKey();
int diff = currValue.rep.compareTo(targetValue.rep);
if (diff > 0) {
if (curr.left == target) {
return curr;
}
return getParent(curr.left, target);
} else {
if (curr.right == target) {
return curr;
}
return getParent(curr.right, target);
}
}
@Override
public Object remove(Object key) {
if (!(key instanceof Name)) {
return null;
}
Node current = getNode(root, (Name) key);
if (current == null) {
return null;
}
Object result = current.getValue();
Node parent = getParent(root, current);
if (current.right == null && current.left == null) {
if (parent == null) {
root = null;
} else if (parent.left == current) {
parent.left = null;
} else {
parent.right = null;
}
size--;
} else if (current.right == null) {
if (parent == null) {
root = current.left;
} else if (parent.left == current) {
parent.left = current.left;
} else {
parent.right = current.left;
}
size--;
} else if (current.left == null) {
if (parent == null) {
root = current.right;
} else if (parent.left == current) {
parent.left = current.right;
} else {
parent.right = current.right;
}
size--;
} else {
Node curr = current.right;
if (curr.left == null) {
curr.left = current.left;
if (parent == null) {
root = curr;
} else if (parent.left == current) {
parent.left = curr;
} else {
parent.right = curr;
}
size--;
} else {
Node par = null;
while (curr.left != null) {
par = curr;
curr = curr.left;
}
Node newNode = par.left;
par.left = newNode.right;
newNode.left = current.left;
newNode.right = current.right;
if (parent == null) {
root = newNode;
} else if (parent.left == current) {
parent.left = newNode;
} else {
parent.right = newNode;
}
size--;
}
}
version = toString();
return result;
}
@Override
public void clear() {
root = null;
size = 0;
entrySet = new EntrySet();
version = toString();
}
@Override
public boolean containsKey(Object o) {
if (!(o instanceof Name)) {
return false;
}
return known((Name) o);
}
private void doToString(Node r, StringBuilder into) {
if (r == null) return;
doToString(r.left, into);
into.append(' ');
into.append(r.key);
into.append(' ');
into.append(r.data);
doToString(r.right, into);
}
/**
* Return a string of the form << name1 value1 name2 value2 ... namek valuek >>
* where the names are in order and everything is separated by single spaces.
*
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("<<");
doToString(root, sb);
sb.append(" >>");
return sb.toString();
}
private class EntrySet extends AbstractSet> {
@Override
public Iterator> iterator() {
return new MyIterator();
}
@Override
public int size() {
return size;
}
@Override
public void clear() {
Dictionary.this.clear();
}
}
private class MyIterator implements Iterator> {
private Stack cursorStack;
private Stack prevStack;
private String version;
MyIterator() {
version = Dictionary.this.version;
cursorStack = new Stack<>();
prevStack = null;
Node curr = root;
while (curr != null) {
cursorStack.add(curr);
curr = curr.left;
}
}
/**
* Returns {@code true} if the iteration has more elements.
* (In other words, returns {@code true} if {@link #next} would
* return an element rather than throwing an exception.)
*
* @return {@code true} if the iteration has more elements
*/
@Override
public boolean hasNext() {
if (!version.equals(Dictionary.this.version)) {
throw new ConcurrentModificationException();
}
return !cursorStack.empty();
}
/**
* Returns the next element in the iteration.
*
* @return the next element in the iteration
* @throws NoSuchElementException if the iteration has no more elements
*/
@Override
public AbstractEntrynext() {
if (!version.equals(Dictionary.this.version)) {
throw new ConcurrentModificationException();
}
if (cursorStack.empty()) {
throw new NoSuchElementException();
}
prevStack = new Stack<>();
for (Node node : cursorStack) {
prevStack.push(node);
}
Node result = cursorStack.peek();
Node curr = cursorStack.pop().right;
while (curr != null) {
cursorStack.push(curr);
curr = curr.left;
}
return result;
}
@Override
public void remove() {
if (!version.equals(Dictionary.this.version)) {
throw new ConcurrentModificationException();
}
if (prevStack == null) {
throw new IllegalStateException();
}
Node current = prevStack.peek();
Node parent = getParent(root, current);
if (current.right == null && current.left == null) {
if (parent == null) {
root = null;
} else if (parent.left == current) {
parent.left = null;
} else {
parent.right = null;
}
prevStack.pop();
size--;
} else if (current.right == null) {
if (parent == null) {
root = current.left;
} else if (parent.left == current) {
parent.left = current.left;
} else {
parent.right = current.left;
}
prevStack.pop();
size--;
} else if (current.left == null) {
if (parent == null) {
root = current.right;
} else if (parent.left == current) {
parent.left = current.right;
} else {
parent.right = current.right;
}
prevStack.pop();
Node curr = current.right;
while (curr != null) {
prevStack.push(curr);
curr = curr.left;
}
size--;
} else {
Node curr = current.right;
if (curr.left == null) {
prevStack.pop();
prevStack.push(curr);
curr.left = current.left;
if (parent == null) {
root = curr;
} else if (parent.left == current) {
parent.left = curr;
} else {
parent.right = curr;
}
size--;
} else {
Node par = null;
while (curr.left != null) {
par = curr;
curr = curr.left;
}
Node newNode = par.left;
par.left = newNode.right;
newNode.left = current.left;
newNode.right = current.right;
prevStack.pop();
prevStack.push(newNode);
if (parent == null) {
root = newNode;
} else if (parent.left == current) {
parent.left = newNode;
} else {
parent.right = newNode;
}
size--;
}
}
cursorStack = new Stack<>();
for (Node node : prevStack) {
cursorStack.push(node);
}
prevStack = null;
Dictionary.this.version = Dictionary.this.toString();
version = Dictionary.this.version;
}
}
public static class TestInvariant extends TestCase {
protected Dictionary self;
private Node[] n;
private Name n0 = new Name("N");
protected Name n(int i) {
return new Name("N" + (1000 + i));
}
@Override
protected void setUp() {
self = new Dictionary();
self.root = null;
self.size = 0;
n = new Node[15];
for (int i = 0; i < 15; ++i) {
n[i] = new Node(n(i * 10), i);
}
n[0].key = null;
n[6].left = n[2];
n[6].right = n[10];
n[2].left = n[1];
n[2].right = n[5];
n[5].left = n[3];
n[3].right = n[4];
n[10].left = n[9];
n[10].right = n[12];
n[9].left = n[7];
n[7].right = n[8];
n[12].left = n[11];
n[12].right = n[13];
doReport = false;
}
public void testA() {
assertEquals(0, checkTree(null, null, null));
assertEquals(-1, checkTree(n[0], null, null));
assertEquals(1, checkTree(n[1], null, null));
assertEquals(0, checkTree(null, "bar", "foo"));
}
public void testB() {
assertEquals(1, checkTree(n[1], n(9).rep, n(11).rep));
assertEquals(1, checkTree(n[1], n(0).rep, null));
assertEquals(1, checkTree(n[1], null, n(20).rep));
assertEquals(-1, checkTree(n[1], n(9).rep, n(10).rep));
assertEquals(-1, checkTree(n[1], n(10).rep, n(11).rep));
assertEquals(-1, checkTree(n[1], n(10).rep, null));
assertEquals(-1, checkTree(n[1], null, n(10).rep));
}
public void testC() {
assertEquals(13, checkTree(n[6], null, null));
assertEquals(13, checkTree(n[6], n(0).rep, n(140).rep));
assertEquals(-1, checkTree(n[6], n(15).rep, null));
assertEquals(-1, checkTree(n[6], null, n(125).rep));
}
public void testD() {
self.root = null;
self.size = 0;
doReport = true;
assertTrue(self.wellFormed());
}
public void testE() {
self.root = n[1];
self.size = 0;
assertFalse(self.wellFormed());
self.size = 2;
assertFalse(self.wellFormed());
self.size = -1;
assertFalse(self.wellFormed());
self.size = 1;
doReport = true;
assertTrue(self.wellFormed());
}
public void testF() {
self.root = n[0];
self.size = 1;
assertFalse(self.wellFormed());
n[0].key = n0;
doReport = true;
assertTrue(self.wellFormed());
}
public void testG() {
self.root = n[14];
self.size = 2;
n[14].right = n[1];
assertFalse(self.wellFormed());
n[14].right = null;
n[14].left = n[1];
doReport = true;
assertTrue(self.wellFormed());
}
public void testH() {
self.root = n[1];
self.size = 2;
n[1].left = n[14];
assertFalse(self.wellFormed());
n[1].left = null;
n[1].right = n[14];
doReport = true;
assertTrue(self.wellFormed());
}
public void testI() {
self.root = n[3]; // n[3]'s right is n[4]
self.size = 3;
n[4].left = n[0];
assertFalse(self.wellFormed());
self.size = 0;
assertFalse(self.wellFormed());
n[0].key = n0;
assertFalse(self.wellFormed());
self.size = 3;
assertFalse(self.wellFormed());
n[4].left = null;
n[4].right = n[14];
doReport = true;
assertTrue(self.wellFormed());
}
public void testJ() {
self.root = n[5]; //n[5].left = n[3]; n[3].right = n[4]
self.size = 4;
n[4].right = n[14];
assertFalse(self.wellFormed());
self.size = 1;
assertFalse(self.wellFormed());
n[0].key = n0;
assertFalse(self.wellFormed());
self.size = 4;
assertFalse(self.wellFormed());
n[4].right = null;
assertFalse(self.wellFormed());
self.size = 3;
doReport = true;
assertTrue(self.wellFormed());
}
public void testK() {
self.root = n[5]; //n[5].left = n[3]; n[3].right = n[4]
self.size = 4;
n[4].left = n[0];
assertFalse(self.wellFormed());
self.size = 1;
assertFalse(self.wellFormed());
n[0].key = n0;
assertFalse(self.wellFormed());
self.size = 4;
assertFalse(self.wellFormed());
n[0].key = n(35);
doReport = true;
assertTrue(self.wellFormed());
}
// The following tests concern the tree
// (((10)20(((30(40))50)60((70(80))90)))100((110)120(130)))
public void testL() {
self.root = n[6]; // whole tree
self.size = 13;
doReport = true;
assertTrue(self.wellFormed());
}
public void testM() {
self.root = n[6];
self.size = 14;
n[1].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(10);
assertFalse(self.wellFormed());
n[1].left = n[1];
assertFalse(self.wellFormed());
n[1].left = n[0];
n[0].key = n(05);
doReport = true;
assertTrue(self.wellFormed());
}
public void testN() {
self.root = n[6];
self.size = 14;
n[1].right = n[14];
assertFalse(self.wellFormed());
n[1].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(20);
assertFalse(self.wellFormed());
n[1].right = n[2];
assertFalse(self.wellFormed());
n[1].right = n[0];
n[0].key = n(15);
doReport = true;
assertTrue(self.wellFormed());
}
public void testO() {
self.root = n[6];
self.size = 14;
n[3].left = n[1];
assertFalse(self.wellFormed());
n[3].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(20);
assertFalse(self.wellFormed());
n[3].left = n[2];
assertFalse(self.wellFormed());
n[3].left = n[0];
n[0].key = n(25);
doReport = true;
assertTrue(self.wellFormed());
}
public void testP() {
self.root = n[6];
self.size = 14;
n[4].left = n[1];
assertFalse(self.wellFormed());
n[4].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(30);
assertFalse(self.wellFormed());
n[4].left = n[3];
assertFalse(self.wellFormed());
n[4].left = n[0];
n[0].key = n(35);
doReport = true;
assertTrue(self.wellFormed());
}
public void testQ() {
self.root = n[6];
self.size = 14;
n[4].right = n[14];
assertFalse(self.wellFormed());
n[4].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(50);
assertFalse(self.wellFormed());
n[4].right = n[5];
assertFalse(self.wellFormed());
n[4].right = n[0];
n[0].key = n(45);
doReport = true;
assertTrue(self.wellFormed());
}
public void testR() {
self.root = n[6];
self.size = 14;
n[5].right = n[14];
assertFalse(self.wellFormed());
n[5].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(60);
assertFalse(self.wellFormed());
n[5].right = n[6];
assertFalse(self.wellFormed());
n[5].right = n[0];
n[0].key = n(55);
doReport = true;
assertTrue(self.wellFormed());
}
public void testS() {
self.root = n[6];
self.size = 14;
n[7].left = n[1];
assertFalse(self.wellFormed());
n[7].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(60);
assertFalse(self.wellFormed());
n[7].left = n[6];
assertFalse(self.wellFormed());
n[7].left = n[0];
n[0].key = n(65);
doReport = true;
assertTrue(self.wellFormed());
}
public void testT() {
self.root = n[6];
self.size = 14;
n[8].left = n[1];
assertFalse(self.wellFormed());
n[8].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(70);
assertFalse(self.wellFormed());
n[8].left = n[7];
assertFalse(self.wellFormed());
n[8].left = n[0];
n[0].key = n(75);
doReport = true;
assertTrue(self.wellFormed());
}
public void testU() {
self.root = n[6];
self.size = 14;
n[8].right = n[14];
assertFalse(self.wellFormed());
n[8].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(90);
assertFalse(self.wellFormed());
n[8].right = n[9];
assertFalse(self.wellFormed());
n[8].right = n[0];
n[0].key = n(85);
doReport = true;
assertTrue(self.wellFormed());
}
public void testV() {
self.root = n[6];
self.size = 14;
n[9].right = n[14];
assertFalse(self.wellFormed());
n[9].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(100);
assertFalse(self.wellFormed());
n[9].right = n[10];
assertFalse(self.wellFormed());
n[9].right = n[0];
n[0].key = n(95);
doReport = true;
assertTrue(self.wellFormed());
}
public void testW() {
self.root = n[6];
self.size = 14;
n[11].left = n[1];
assertFalse(self.wellFormed());
n[11].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(100);
assertFalse(self.wellFormed());
n[11].left = n[10];
assertFalse(self.wellFormed());
n[11].left = n[0];
n[0].key = n(105);
doReport = true;
assertTrue(self.wellFormed());
}
public void testX() {
self.root = n[6];
self.size = 14;
n[11].right = n[14];
assertFalse(self.wellFormed());
n[11].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(120);
assertFalse(self.wellFormed());
n[11].right = n[12];
assertFalse(self.wellFormed());
n[11].right = n[0];
n[0].key = n(115);
doReport = true;
assertTrue(self.wellFormed());
}
public void testY() {
self.root = n[6];
self.size = 14;
n[13].left = n[1];
assertFalse(self.wellFormed());
n[13].left = n[0];
assertFalse(self.wellFormed());
n[0].key = n(120);
assertFalse(self.wellFormed());
n[13].left = n[12];
assertFalse(self.wellFormed());
n[13].left = n[0];
n[0].key = n(125);
doReport = true;
assertTrue(self.wellFormed());
}
public void testZ() {
self.root = n[6];
self.size = 14;
n[13].right = n[0];
assertFalse(self.wellFormed());
n[0].key = n(130);
assertFalse(self.wellFormed());
n[13].right = n[13];
assertFalse(self.wellFormed());
n[13].right = n[14];
doReport = true;
assertTrue(self.wellFormed());
}
}
}
Related Samples
Discover our Java Assignment Samples showcasing expert solutions to diverse programming challenges. These examples span basic algorithms to advanced data structures, embodying clarity, efficiency, and adherence to coding standards. Strengthen your Java programming skills with our comprehensive collection and excel in your assignments effortlessly.
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java