Instructions
Requirements and Specifications
Screenshots
Source Code
package edu.uwm.cs351.util;
import java.security.Key;
import java.util.*;
import java.util.function.Consumer;
import junit.framework.TestCase;
public class TreeMap extends AbstractMap {
// Here is the data structure to use.
private static class Node extends DefaultEntry {
Node left, right;
Node parent;
Node(K k, V v) {
super(k, v);
parent = left = right = null;
}
}
private Comparator comparator;
private Node dummy;
private int numItems = 0;
private int version = 0;
/// Invariant checks:
private static Consumer reporter = (s) -> {
System.err.println("Invariant error: " + s);
};
private boolean report(String error) {
reporter.accept(error);
return false;
}
/**
* Return whether nodes in the subtree rooted at the given node have correct parent
* and have keys that are never null and are correctly sorted and are all in the range
* between the lower and upper (both exclusive).
* If either bound is null, then that means that there is no limit at this side.
* The first problem is found will be reported.
*
* @param node root of subtree to examine
* @param p parent of subtree to examine
* @param lower value that all nodes must be greater than. If null, then
* there is no lower bound.
* @param upper value that all nodes must be less than. If null,
* then there is no upper bound.
* @return whether the subtree is fine. If false is
* returned, there is a problem, which has already been reported.
*/
private boolean checkInRange(Node node, Node p, K lower, K upper) {
if (node == null) {
return true;
}
if (node.parent != p) {
return false;
}
if (lower != null && comparator.compare(lower, node.key) >= 0) {
return false;
}
if (upper != null && comparator.compare(upper, node.key) <= 0) {
return false;
}
return checkInRange(node.left, node, lower, node.key) && checkInRange(node.right, node, node.key, upper);
}
/**
* Return the number of nodes in a binary tree.
*
* @param r binary (search) tree, may be null but must not have cycles
* @return number of nodes in this tree
*/
private int countNodes(Node r) {
if (r == null) return 0;
return 1 + countNodes(r.left) + countNodes(r.right);
}
/**
* Check the invariant, printing a message if not satisfied.
*
* @return whether invariant is correct
*/
private boolean wellFormed() {
// 1. check that comparator is not null
if (comparator == null) {
return report("comparator is null");
}
// 2. check that dummy is not null
if (dummy == null) {
return report("dummy is null");
}
// 3. check that dummy's key, right subtree and parent are null
if (dummy.getKey() != null || dummy.right != null || dummy.parent != null) {
return report("dummy's key or dummy's right subtree or dummy's parent is not null");
}
// 4. check that all (non-dummy) nodes are in range
// 5. check that all nodes have correct parents
// 6. check that number of items matches number of (non-dummy) nodes
// "checkInRange" will help with 4,5
if (!checkInRange(dummy.left, dummy, null, null)) {
return report("wrong ranges or parent");
}
if (numItems != countNodes(dummy.left)) {
return report("wrong size");
}
return true;
}
/// constructors
private TreeMap(boolean ignored) {
} // do not change this.
public TreeMap() {
this(null);
assert wellFormed() : "invariant broken after constructor()";
}
public TreeMap(Comparator c) {
// Update the parameter comparator if necessary
// Create the dummy node.
this.comparator = c == null ? (Comparator) Comparator.naturalOrder() : c;
this.dummy = new Node<>(null, null);
assert wellFormed() : "invariant broken after constructor(Comparator)";
}
@SuppressWarnings("unchecked")
private K asKey(Object x) {
if (dummy.left == null || x == null) return null;
try {
comparator.compare(dummy.left.key, (K) x);
comparator.compare((K) x, dummy.left.key);
return (K) x;
} catch (ClassCastException ex) {
return null;
}
}
/**
* Find the node for a given key. Return null if the key isn't present
* in the tree. This helper method assumes that the tree is well formed,
* but doesn't check that.
*
* @param o object treated as a key.
* @return node whose data is equal to o,
* or null if no nodes in the tree have this property.
*/
private Node findKey(Object o) {
K k = asKey(o);
if (k == null) {
return null;
}
Node curr = dummy.left;
while (curr != null) {
int diff = comparator.compare(curr.key, k);
if (diff < 0) {
curr = curr.right;
} else if (diff > 0) {
curr = curr.left;
} else {
return curr;
}
}
return null;
}
// TODO: many methods to override here:
// size, containsKey(Object), get(Object), clear(), put(K, V), remove(Object)
// make sure to use @Override and assert wellformedness
// plus any private helper methods.
// Our solution has getNode(Object)
// Increase version if data structure if modified.
@Override
public int size() {
assert wellFormed();
return numItems;
}
@Override
public boolean containsKey(Object o) {
assert wellFormed();
return findKey(o) != null;
}
@Override
public V get(Object o) {
assert wellFormed();
Node node = findKey(o);
if (node == null) {
return null;
}
return node.value;
}
@Override
public void clear() {
assert wellFormed();
if (size() > 0) {
version++;
dummy.left = null;
numItems = 0;
}
assert wellFormed();
}
@Override
public V put(K key, V value) {
assert wellFormed();
if (key == null) {
throw new NullPointerException();
}
Node current = dummy;
while(true) {
if (dummy == current) {
if (dummy.left == null) {
dummy.left = new Node<>(key, value);
dummy.left.parent = dummy;
numItems++;
version++;
assert wellFormed();
return null;
}
current = current.left;
}
else {
int diff = comparator.compare(current.key, key);
if (diff < 0) {
if (current.right == null) {
Node node = new Node<>(key, value);
current.right = node;
node.parent = current;
numItems++;
version++;
assert wellFormed();
return null;
}
current = current.right;
}
else if (diff > 0) {
if (current.left == null) {
Node node = new Node<>(key, value);
current.left = node;
node.parent = current;
numItems++;
version++;
assert wellFormed();
return null;
}
current = current.left;
}
else {
V oldValue = current.value;
current.value = value;
assert wellFormed();
return oldValue;
}
}
}
}
public V remove(Node r, K key) {
if (r == null) {
return null;
}
int diff = comparator.compare(r.key,key);
if (diff > 0) {
return remove(r.left, key);
}
else if (diff < 0) {
return remove(r.right, key);
}
else {
numItems--;
V result = r.value;
Node parent = r.parent;
boolean leftChild = parent.left == r;
if (r.left == null && r.right == null) {
if (leftChild) {
parent.left = null;
}
else {
parent.right = null;
}
return result;
}
if (r.left != null && r.right == null) {
r.left.parent = parent;
if (leftChild) {
parent.left = r.left;
}
else {
parent.right = r.left;
}
return result;
}
if (r.left == null && r.right != null) {
r.right.parent = parent;
if (leftChild) {
parent.left = r.right;
}
else {
parent.right = r.right;
}
return result;
}
Node leftMost = r.right;
Node pp = null;
while(leftMost.left != null) {
pp = leftMost;
leftMost = leftMost.left;
}
if (pp == null) {
r.left.parent = r.right;
r.right.left = r.left;
r.right.parent = parent;
if (leftChild) {
parent.left = r.right;
}
else {
parent.right = r.right;
}
return result;
}
else {
if (leftMost.right != null) {
leftMost.right.parent = pp;
}
pp.left = leftMost.right;
r.left.parent = leftMost;
leftMost.left = r.left;
r.right.parent = leftMost;
leftMost.right = r.right;
leftMost.parent = parent;
if (leftChild) {
parent.left = leftMost;
}
else {
parent.right = leftMost;
}
return result;
}
}
}
@Override
public V remove(Object o) {
K key = asKey(o);
if (key == null) {
return null;
}
assert wellFormed();
version++;
V value = remove(dummy.left, key);
assert wellFormed();
return value;
}
private Node getNode(Node node) {
if (node == null) {
return null;
}
if (node == dummy) {
return dummy;
}
return getNode(dummy.left, node);
}
private Node getNode(Node curr, Node node) {
if (curr == null) {
return null;
}
int diff = comparator.compare(curr.key, node.key);
if (diff < 0) {
return getNode(curr.right, node);
}
else if (diff > 0) {
return getNode(curr.left, node);
}
else {
return curr;
}
}
private volatile Set> entrySet;
@Override
public Set> entrySet() {
assert wellFormed() : "invariant broken at beginning of entrySet";
if (entrySet == null) {
entrySet = new EntrySet();
}
return entrySet;
}
/**
* The set for this map, backed by the map.
* By "backed: we mean that this set doesn't have its own data structure:
* it uses the data structure of the map.
*/
private class EntrySet extends AbstractSet> {
// Do NOT add any fields!
@Override
public int size() {
return TreeMap.this.size();
}
@Override
public Iterator> iterator() {
return new MyIterator();
}
@Override
public boolean contains(Object o) {
assert wellFormed() : "Invariant broken at start of EntrySet.contains";
// TODO if o is not an entry (instanceof Entry), return false
if (!(o instanceof Entry)) {
return false;
}
// Otherwise, check the entry for this entry's key.
Entry entry = (Entry) o;
K key = asKey(entry.getKey());
if (key == null) {
return false;
}
Node found = getNode(new Node<>(key, null));
if (found == null) {
return false;
}
return (entry.getValue() == null && found.getValue() == null) || entry.getValue().equals(found.getValue());
// If there is no such entry return false;
// Otherwise return whether the entries match (use the equals method of the Node class).
// N.B. You can't check whether the key is of the correct type
// because K is a generic type parameter. So you must handle any
// Object similarly to how "get" does.
// return false;
}
@Override
public boolean remove(Object x) {
// TODO: if the tree doesn't contain x, return false
// otherwise do a TreeMap remove.
// make sure that the invariant is true before returning.
if(!contains(x)) {
return false;
}
Entry entry = (Entry) x;
TreeMap.this.remove(entry.getKey());
assert wellFormed();
return true;
}
@Override
public void clear() {
TreeMap.this.clear();
}
}
/**
* Iterator over the map.
* We use parent pointers.
* current points to node (if any) that can be removed.
* next points to dummy indicating no more next.
*/
private class MyIterator implements Iterator> {
Node current, next;
int colVersion = version;
boolean removed = false;
boolean wellFormed() {
// (1) check the outer wellFormed()
if (!TreeMap.this.wellFormed()) {
return report("outer wellformed broken");
}
// (2) If version matches, do the remaining checks:
// (a) current should either be null or a non-dummy node in the tree
// (b) next should never be null and should be in the tree (maybe dummy).
// (c) if current is not null, make sure it is the last node before where next is.
if (colVersion == version) {
if (current != null) {
Node found = getNode(current);
if (found == null) {
if (!removed) {
return report("wrong current");
}
}
else {
if (found != current || found == dummy) {
return report("wrong current");
}
if (next != findNext(current)) {
return report("current and next are not adjacent");
}
}
}
if (next == null || getNode(next) == null) {
return report("wrong next");
}
}
return true;
}
MyIterator(boolean ignored) {
} // do not change this
MyIterator() {
Node curr = dummy;
while(curr.left != null) {
curr = curr.left;
}
next = curr;
assert wellFormed() : "invariant broken after iterator constructor";
}
public void checkVersion() {
if (version != colVersion) throw new ConcurrentModificationException("stale iterator");
}
public boolean hasNext() {
checkVersion();
assert wellFormed() : "invariant broken before hasNext()";
return next != dummy;
}
public Entry next() {
assert wellFormed() : "invariant broken at start of next()";
checkVersion();
if (!hasNext()) {
throw new NoSuchElementException();
}
// We don't use (non-existent)nextInTree:
// but rather parent pointers in the second case.
current = next;
next = findNext(next);
removed = false;
assert wellFormed() : "invariant broken at end of next()";
return current;
}
public void remove() {
assert wellFormed() : "invariant broken at start of iterator.remove()";
// TODO: check that there is something to remove.
// Use the remove method from TreeMap to remove it.
// (See handout for details.)
// After removal, record that there is nothing to remove any more.
// Handle versions.
checkVersion();
if (current == null || removed) {
throw new IllegalStateException();
}
TreeMap.this.remove(current.key);
removed = true;
colVersion++;
assert wellFormed() : "invariant broken at end of iterator.remove()";
}
private Node findNext(Node curr) {
if (curr.right != null) {
Node n = curr.right;
while(n.left != null) {
n = n.left;
}
return n;
}
else {
Node n = curr;
while(n.parent.right == n) {
n = n.parent;
}
return n.parent;
}
}
}
/// Junit test case of private internal structure.
// Do not change this nested class.
public static class TestSuite extends TestCase {
protected Consumer getReporter() {
return reporter;
}
protected void setReporter(Consumer c) {
reporter = c;
}
protected static class Node extends TreeMap.Node {
public Node(K k, V v) {
super(k, v);
}
public void setLeft(Node n) {
this.left = n;
}
public void setRight(Node n) {
this.right = n;
}
public void setParent(Node n) {
this.parent = n;
}
}
protected class MyIterator extends TreeMap.MyIterator {
public MyIterator() {
tree.super(false);
}
public void setCurrent(Node c) {
this.current = c;
}
public void setNext(Node nc) {
this.next = nc;
}
public void setColVersion(int cv) {
this.colVersion = cv;
}
@Override // make visible
public boolean wellFormed() {
return super.wellFormed();
}
}
protected TreeMap tree;
@Override // implementation
protected void setUp() {
tree = new TreeMap<>(false);
}
protected boolean wellFormed() {
return tree.wellFormed();
}
protected void setDummy(Node d) {
tree.dummy = d;
}
protected void setNumItems(int ni) {
tree.numItems = ni;
}
protected void setComparator(Comparator c) {
tree.comparator = c;
}
protected void setVersion(int v) {
tree.version = v;
}
protected Node findKey(Object key) {
return (Node) tree.findKey(key);
}
}
}