/** A finite mapping from type K to type V. Null keys are not allowed. */ interface MapI { /** create a new empty map of the same type MapI. */ MapI newMap(); /** @return true if the map is empty, i.e., contains no entries (key-value pairs). */ boolean isEmpty(); /** Set this map to the empty map. */ void clear(); /** @return the value for key if there is an entry (key,value) in the map; null otherwise. */ V get(K key); /** Puts the entry (key, value) in the map, replacing the old entry for key if one existed. * @return the old value for key or null if no old value existed in the map. */ V put(K key, V value); /** Deletes the entry for key. * @return the value of the removed entry if such an entry existed, null otherwise. */ V remove(K key); /** @return true iff an entry for key exists in the map. */ public boolean containsKey(K key); /** Returns the number of entries (keys) in this map. */ int size(); } /** A map over a totally-ordered domain K. */ interface SortedMapI, V> extends MapI { K firstKey(); K lastKey(); } /** A mutable binary search tree of elements of type T. */ class TreeMap, V> implements SortedMapI { /** Number of entries in the map. */ private int size; /** Root of the binary search tree. */ private Node root; /* Relying on default constructor. Sets root to null; size to 0. */ /** create a new empty map of the same type. */ public MapI newMap() { return new TreeMap(); } /** @return true if the map is empty (contains no key-value pairs). */ public boolean isEmpty() { return root == null; } /** Set this map to the empty map. */ public void clear() { root = null; } /** Requires: root != null. * @returns the node containing key if key exists in map; otherwise * null if ! findInsertLocation * the location where key would be inserted in map if findInsertLocation */ private Node find(K key, boolean findInsertLocation) { assert root != null; Node current = root; Node parent = null; do { int compareFlag = key.compareTo(current.key); if (compareFlag == 0) break; parent = current; if (compareFlag < 0) current = current.left; else current = current.right; } while (current != null); assert current == null || current.key.equals(key); if (current == null && findInsertLocation) return parent; return current; } /** @return the value for key if there is an entry (key,value) in the map; null otherwise. */ public V get(K key) { if (root == null) return null; Node match = find(key, false); if (match == null) return null; return match.value; } /** Puts the entry (key, value) in the map, replacing the old entry for key if one existed. * @return the old value for key or null if no old value existed in the map. */ public V put(K key, V value) { if (root == null) { root = new Node(key, value); size = 1; return null; } // location is either matching node or node immediately above where new node must be inserted Node location = find(key, true); int compareFlag = key.compareTo(location.key); if (compareFlag == 0) { // exact match; key already exists in map V oldValue = location.value; location.value = value; // size is unchanged return oldValue; } else { // Key is not present, must add new node if (compareFlag < 0) location.left = new Node(key, value); else location.right = new Node(key, value); size++; return null; } } /* Deletes the entry for key. * @return the value of the removed entry if such an entry existed, null otherwise. */ public V remove(K key) { if (root == null) return null; if (key.equals(root.key)) { // deleting root V returnVal; // Decrement size; removing node using remove() method which does not decrement size size--; returnVal = root.value; if (root.right == null) { if (root.left == null) { // root is only node root = null; return returnVal; } // left subtree is remaining tree root = root.left; return returnVal; } assert root.right != null; return root.remove(); // removes entry in tree rooted at root; does not change size } ; Node matchNode = findAndDeleteIfConvenient(key); if (matchNode == null) return null; // no matching entry found if (matchNode.left == null || matchNode.right == null) { // node was deleted return matchNode.value; } assert matchNode.right != null; size--; // decrement size; matching node will be removed V returnVal = matchNode.remove(); // removes entry in matchNode; does NOT affect size return returnVal; } /** Requires root != null && ! root.key.equals(key) * Finds the node matching key or returns null if no match exists. * In addition, deletes the matching node n if it is degenerate (n.left == null || n.right == null). * @returns the matching node if one exists (node n where n.key.equals(key)); * null if there is no matching node. */ private Node findAndDeleteIfConvenient(K key) { assert root != null && ! root.key.equals(key); Node parent = null; // used in delete operations Node current = root; do { int compareFlag = key.compareTo(current.key); if (compareFlag == 0) break; parent = current; if (compareFlag < 0) current = current.left; else current = current.right; } while (current != null); if (current == null) return null; // no matching node exists assert current != root && parent != null; if (current.right == null) { // update parent to delete current size--; parent.updateChild(current, current.left); } else if (current.left == null) { // update parent to delete current parent.updateChild(current, current.right); size--; } else { /* deletion is not convenient */ } return current; } /** Requires: root != null * @returns the first non-empty Node in this or null if no such node exists. */ private Node findFirst() { assert root != null; Node current = root; Node next = root.left; while (true) { if (next == null) return current; current = next; next = next.left; } } /** Requires: root != null * @returns the last non-empty RefNode in this. */ private Node findLast() { assert root != null; Node current = root; Node next = root.right; while (true) { if (next == null) return current; current = next; next = next.right; } } /** Requires: root != null * @returns the first key in this. */ public K firstKey() { assert root != null; return findFirst().key; } /** Requires: root != null * @returns the last key. */ public K lastKey() { assert root != null; return findLast().key; } /** @return true iff an entry for key exists in the map. */ public boolean containsKey(K key) { V value = get(key); return value != null; } /** @return the size of this map. */ public int size() { return size; } /** Deletes the entry (key,value) with the minimum key if tree is non-empty. * @return the value of the deleted entry if it exists; null if tree is empty. */ public V removeMin() { if (isEmpty()) return null; // Node will be deleted; cannot use findFirst because parent of first is inaccessible size--; if (root.left == null) { // root is min node V returnVal = root.value; root = root.right; return returnVal; } assert root.left != null; Node removedNode = root.removeMinNode(); // does not affect size assert removedNode != null; // since root is non-empty, minimum node must exist return removedNode.value; } public String toString() { if (isEmpty()) { return "{}"; } StringBuilder sb = new StringBuilder(); toStringHelp(sb, root); /* sb has a leading space */ sb.setCharAt(0, '{'); sb.append('}'); return sb.toString(); } private void toStringHelp(StringBuilder sb, Node n) { if (n != null) { toStringHelp(sb, n.left); sb.append(" [" + n.key + "," + n.value + "]"); toStringHelp(sb, n.right); } } private static class Node, V> { Node left, right; K key; V value; Node(K k, V v) { key = k; value = v; } /** Requires: right != null. * Removes entry in this Node by finding mininum node in right, removing it, and copying its contents to this. * size is unchanged because it is not accessible! * @return this.value */ V remove() { assert right != null; // Remove minimum node from right and bind rightMin to this node Node rightMin; if (right.left == null) { // right is minimum node in right subtree // remove right rightMin = right; right = right.right; // remove node rightMin } else rightMin = right.removeMinNode(); // Save this.value V thisVal = value; // Copy entry from rightMin to this key = rightMin.key; value = rightMin.value; assert thisVal != null; return thisVal; } void updateChild(Node child, Node newChild) { if (left == child) left = newChild; else right = newChild; } /** Requires: left != null. * Deletes the minimum entry in the subtree rooted at this. Does not change size! * @return the deleted Node. */ Node removeMinNode() { assert left != null; /* Find minimum Node, tracing the parent */ Node parent = this; Node next = left; /** Invariant: for all Nodes n in root\(next.right) (next.key <= n.key). */ while (next.left != null) { parent = next; next = next.left; } // next is minimum node in tree rooted at this assert parent.left == next; parent.left = next.right; // remove next return next; } } }