Below is the code where public V remove(Object obj) needs to be added (it's the last method):

package util;

import java.util.AbstractMap; import java.util.Collection; import java.util.Comparator; import java.util.Iterator; import java.util.LinkedList; import java.util.Map; import java.util.Set; import java.util.TreeSet;

import adapter.NavMapAdapter; import adapter.SetAdapter;

public class SearchTreeMap extends NavMapAdapter { private static final long serialVersionUID = 1L;

private static class Node { K key; V value; Node left, right;

Node(K key, V value, Node left, Node right) { this.key = key; this.value = value; this.left = left; this.right = right; } } private Node root = null; private int size = 0; private Comparator super K> cmp = null;

public SearchTreeMap(Comparator super K> cmp) { this.cmp = cmp; }

public SearchTreeMap() { }

@SuppressWarnings("unchecked") private int myCompare(K lhs, K rhs) { if (cmp == null) { return ((Comparable) lhs).compareTo(rhs); } else { return cmp.compare(lhs, rhs); } }

@Override public java.util.Comparator super K> comparator() { return cmp; }

@Override public int size() { return size; }

@Override public void clear() { root = null; size = 0; }

@Override public boolean isEmpty() { return root == null; }

private Node seach(Node n, K key) { if (n == null) { return null; } int comp = myCompare(key, n.key); if (comp 0) { return seach(n.right, key); } return n; }

@Override @SuppressWarnings("unchecked") public V get(Object obj) { K key = (K) obj; Node n = seach(root, key); if (n == null) { return null; } return n.value; }

private Node put(Node n, K key, V value) { if (n == null) { return new Node(key, value, null, null); } int comp = myCompare(key, n.key); if (comp 0) { n.right = put(n.right, key, value); return n; } // we never get here based on the public put call return n; }

@Override public V put(K key, V value) { Node n = seach(root, key); if (n == null) { // key was not in tree root = put(root, key, value); // we must add it ++size; return null; } else { // key was in tree, we replace value V old_value = n.value; n.value = value; return old_value; // return the old value } }

@Override @SuppressWarnings("unchecked") public boolean containsKey(Object obj) { K key = (K) obj; return seach(root, key) != null; }

@SuppressWarnings("unchecked") private int entryArray(Object[] arr, int index, Node n) { if (n == null) { return index; } else { index = entryArray(arr, index, n.left); arr[index++] = new AbstractMap.SimpleEntry(n.key, n.value); return entryArray(arr, index, n.right); } }

public class EntrySet extends SetAdapter { Object[] arr;

EntrySet(Object[] arr) { this.arr = arr; }

@Override public Iterator> iterator() { return new Iterator>() { int i = 0;

@Override public boolean hasNext() { return i

@Override @SuppressWarnings("unchecked") public Map.Entry next() { return (Map.Entry) arr[i++]; }

@Override public void remove() { throw new UnsupportedOperationException("Not supported."); } }; } }

@Override public String toString() { Object[] arr = new Object[size]; entryArray(arr, 0, root); String str = java.util.Arrays.toString(arr); str = "{" + str.substring(1,str.length()-1) + "}"; return str; }

@Override @SuppressWarnings("unchecked") public Set> entrySet() { Object[] arr = new Object[size]; entryArray(arr, 0, root); return new EntrySet(arr); }

@Override public Collection values() { Collection vals = new LinkedList(); addToValues(root, vals); return vals; }

private void addToValues(Node n, Collection vals) { if (n == null) { return; } vals.add(n.value); addToValues(n.left, vals); addToValues(n.right, vals); }

@Override public Set keySet() { Set kset = new TreeSet(); addToKeySet(root, kset); return kset; }

private void addToKeySet(Node n, Set kset) { if (n == null) { return; } kset.add(n.key); addToKeySet(n.left, kset); addToKeySet(n.right, kset); } private String indentString = " ";

public void setIndentString(String indentString) { this.indentString = indentString; }

public void reverseInorderOutput() { reverseInorderOutput(root, 0); }

private void reverseInorderOutput(Node n, int level) { if (n != null) { reverseInorderOutput(n.right, level + 1); System.out.println(repeat(indentString, level) + n.key + "=" + n.value); reverseInorderOutput(n.left, level + 1); } }

private static String repeat(String str, int times) { return new String(new char[times]).replace("\0", str); }

//----------------------- added by YOUR NAME (please set this) @Override public V remove(Object obj){ return null; }

}

This programming assignment involves adding functionality to the searchTreeMap class found in the setMap project. Specifically, you will edit the file: util.SearchTreeMap and write a Java-correct implementation of the remove method. The main goal is to make the remove method behave like it would for a Java TreeMap. Additionally: 1. The remove operation must be O(log(n)) time on the average. In particular, avoid approaches which involve processing the entire tree. 2. The remove operation should never increase the height of the tree. Use the code of the remove function in searchTreeset.java as a basis, and modify it to work for the map. Skeleton Program Add the following starter code at the end of the class, and set YOUR NAME: util.Search TreeMap public class SearchTreeMap extonds NavMapAdapter f //Add the following starter code AT THE END of this class added by YOUR NAME (please set this) @Override public v remove (object obj) return null; This programming assignment involves adding functionality to the searchTreeMap class found in the setMap project. Specifically, you will edit the file: util.SearchTreeMap and write a Java-correct implementation of the remove method. The main goal is to make the remove method behave like it would for a Java TreeMap. Additionally: 1. The remove operation must be O(log(n)) time on the average. In particular, avoid approaches which involve processing the entire tree. 2. The remove operation should never increase the height of the tree. Use the code of the remove function in searchTreeset.java as a basis, and modify it to work for the map. Skeleton Program Add the following starter code at the end of the class, and set YOUR NAME: util.Search TreeMap public class SearchTreeMap extonds NavMapAdapter f //Add the following starter code AT THE END of this class added by YOUR NAME (please set this) @Override public v remove (object obj) return null