Please help implement BST and the interface

Here are the texts of the code:

import java.util.List;

/**

*

* @author Juan Dominguez

* @author Qiyue Wang

*

* @param The type of the keys in this DefaultMap

* @param The type of the values in this DefaultMap

*/

public interface DefaultMap {

String ILLEGAL_ARG_NULL_KEY = "Keys must be non-null";

/**

* Internal Representation of every (key, value) pair in this DefaultMap

*/

interface Entry {

K getKey();

V getValue();

void setValue(V value);

}

/**

* Adds the specified key, value pair to this DefaultMap

* Note: duplicate keys are not allowed

*

* @return true if the key value pair was added to this DefaultMap

* @throws IllegalArgumentException if the key is null

*/

boolean put(K key, V value) throws IllegalArgumentException;

/**

* Replaces the value that maps to the key if it is present

* @param key The key whose mapped value is being replaced

* @param newValue The value to replace the existing value with

* @return true if the key was in this DefaultMap

* @throws IllegalArgumentException if the key is null

*/

boolean replace(K key, V newValue) throws IllegalArgumentException;

/**

* Remove the entry corresponding to the given key

*

* @return true if an entry for the given key was removed

* @throws IllegalArgumentException if the key is null

*/

boolean remove(K key) throws IllegalArgumentException;

/**

* Adds the key, value pair to this DefaultMap if it is not present,

* otherwise, replaces the value with the given value

* @throws IllegalArgumentException if the key is null

*/

void set(K key, V value) throws IllegalArgumentException;

/**

* @return the value corresponding to the specified key

* @throws IllegalArgumentException if the key is null

*/

V get(K key) throws IllegalArgumentException;

/**

*

* @return The number of (key, value) pairs in this DefaultMap

*/

int size();

/**

*

* @return true iff this.size() == 0 is true

*/

boolean isEmpty();

/**

* @return true if the specified key is in this DefaultMap

* @throws IllegalArgumentException if the key is null

*/

boolean containsKey(K key) throws IllegalArgumentException;

/**

*

* @return an array containing the keys of this DefaultMap. If this DefaultMap is

* empty, returns array of length zero.

*/

List keys();

}

import java.util.ArrayList; import java.util.List; import java.util.Stack;

/** * @param The type of the keys of this BST. They need to be comparable by nature of the BST * "K extends Comparable" means that BST will only compile with classes that implement Comparable * interface. This is because our BST sorts entries by key. Therefore keys must be comparable. * @param The type of the values of this BST. */ public class BST, V> implements DefaultMap { /* * TODO: Add instance variables * You may add any instance variables you need, but * you may NOT use any class that implements java.util.SortedMap * or any other implementation of a binary search tree */

@Override public boolean put(K key, V value) throws IllegalArgumentException { // TODO Auto-generated method stub return false; }

@Override public boolean replace(K key, V newValue) throws IllegalArgumentException { // TODO Auto-generated method stub return false; }

@Override public boolean remove(K key) throws IllegalArgumentException { // TODO Auto-generated method stub return false; }

@Override public void set(K key, V value) throws IllegalArgumentException { // TODO Auto-generated method stub }

@Override public V get(K key) throws IllegalArgumentException { // TODO Auto-generated method stub return null; }

@Override public int size() { // TODO Auto-generated method stub return 0; }

@Override public boolean isEmpty() { // TODO Auto-generated method stub return false; }

@Override public boolean containsKey(K key) throws IllegalArgumentException { // TODO Auto-generated method stub return false; }

// Keys must be in ascending sorted order // You CANNOT use Collections.sort() or any other sorting implementations // You must do inorder traversal of the tree @Override public List keys() { // TODO Auto-generated method stub return null; } private static class Node, V> implements DefaultMap.Entry { /* * TODO: Add instance variables */

@Override public K getKey() { // TODO Auto-generated method stub return null; }

@Override public V getValue() { // TODO Auto-generated method stub return null; }

@Override public void setValue(V value) { // TODO Auto-generated method stub } } }

You'll provide a fast implementation of an interface called DefaultMap in BST.java. You will implement all the methods defined in the DefaultMap interface. You must ensure that each has the specified big-O bound in the worst case, and argue why based on the documentation of any libraries you use, or based on your implementation. Note that these are big-O bounds, so doing better (like O(1) where O(log(n)) is required) is acceptable. In each, n represents the number of entries in the map. . . . put, required O(n) replace , required O(n) remove , required O(n) set , required O(n) get , required O(n) size , required O(1) isEmpty , required (1) containskey , required O(n) keys , required O(n) . . In BST , you will need come up with the proper instance variables to achieve the above runtime requirements. The specifications for the other methods are defined in header comments in the DefaultMap.java file, which you should follow. Important: for keys(), the returned result need to be in ascending order Note: You are not allowed to use the java SortedMap interface or Collections.sort, or any other implementations of BSTs or sorting!!! Your implementation of DefaultMap will be graded automatically by tests that we provide. We'll provide a very minimal sanity check in the grader. DO NOT rely on it for testing! 8 9 1+ import java.util.ArrayList; 4 56 /** 6 * @param The type of the keys of this BST. They need to be comparable by nature of the BST 7 * "K extends Comparable" means that BST will only compile with classes that implement comparable * interface. This is because our BST sorts entries by key. Therefore keys must be comparable. * @param The type of the values of this BST. 0 */ 1 public class BST, V> implements DefaultMap { 20 3 * TODO: Add instance variables 4 * You may add any instance variables you need, but 5 * you may NOT use any class that implements java.util.SortedMap 6 * or any other implementation of a binary search tree 7 */ 8 9 @Override 0 public boolean put(K key, V value) throws IllegalArgumentException { // TODO Auto-generated method stub return false; 3 } 4 5 6 7 8 9 @Override public boolean replace(K key, V newValue) throws IllegalArgumentException { // TODO Auto-generated method stub return false; } @Override public boolean remove (K key) throws IllegalArgumentException { // TODO Auto-generated method stub return false; } @Override public void set(K key, V value) throws IllegalArgumentException { // TODO Auto-generated method stub } 4 5 6 70 8 9 0 1 2 30 4 5 6 7 8 90 0 1 2 3 4 50 6 7 8 9 @Override public V get(K key) throws IllegalArgumentException { // TODO Auto-generated method stub return null; } @Override public int size() { // TODO Auto-generated method stub return 0; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return false; } 8 9 1+ import java.util.ArrayList; 4 56 /** 6 * @param The type of the keys of this BST. They need to be comparable by nature of the BST 7 * "K extends Comparable" means that BST will only compile with classes that implement comparable * interface. This is because our BST sorts entries by key. Therefore keys must be comparable. * @param The type of the values of this BST. 0 */ 1 public class BST, V> implements DefaultMap { 20 3 * TODO: Add instance variables 4 * You may add any instance variables you need, but 5 * you may NOT use any class that implements java.util.SortedMap 6 * or any other implementation of a binary search tree 7 */ 8 9 @Override 0 public boolean put(K key, V value) throws IllegalArgumentException { // TODO Auto-generated method stub return false; 3 } 4 5 6 7 8 9 @Override public boolean replace(K key, V newValue) throws IllegalArgumentException { // TODO Auto-generated method stub return false; } @Override public boolean remove (K key) throws IllegalArgumentException { // TODO Auto-generated method stub return false; } @Override public void set(K key, V value) throws IllegalArgumentException { // TODO Auto-generated method stub } 4 5 6 70 8 9 0 1 2 30 4 5 6 7 8 90 0 1 2 3 4 50 6 7 8 9 @Override public V get(K key) throws IllegalArgumentException { // TODO Auto-generated method stub return null; } @Override public int size() { // TODO Auto-generated method stub return 0; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return false; } @Override public boolean containskey (K key) throws IllegalArgumentException { // TODO Auto-generated method stub return false; } // Keys must be in ascending sorted order // You CANNOT use Collections. sort() or any other sorting implementations // You must do inorder traversal of the tree @Override public List keys () { // TODO Auto-generated method stub return null; } private static class Nodeck extends Comparable super k>, V> implements DefaultMap.Entry { * TODO: Add instance variables */ @Override public K getKey() { // TODO Auto-generated method stub return null; } @Override public V getValue() { // TODO Auto-generated method stub return null; } @Override public void setValue(V value) { // TODO Auto-generated method stub } } import java.util.List; /** * * * @author Juan Dominguez * @author Qiyue Wang. * @param The type of the keys in this DefaultMap * @param The type of the values in this DefaultMap public interface DefaultMap { String ILLEGAL_ARG_NULL_KEY = "Keys must be non-null"; /*** * Internal Representation of every (key, value) pair in this DefaultMap */ interface Entryck, V> { K getKey(); V getValue(); void setValue(V value); } * /*** * Adds the specified key, value pair to this DefaultMap * Note: duplicate keys are not allowed * @return true if the key value pair was added to this DefaultMap * @throws IllegalArgumentException if the key is null */ boolean put(K key, V value) throws IllegalArgumentException; /**** * Replaces the value that maps to the key if it is present * @param key The key whose mapped value is being replaced * @param newValue The value to replace the existing value with * @return true if the key was in this DefaultMap * @throws IllegalArgumentException if the key is null */ boolean replace(K key, V newValue) throws IllegalArgumentException; /** * Remove the entry corresponding to the given key * @return true if an entry for the given key was removed * athrows IllegalArgumentException if the key is null */ boolean remove(K key) throws IllegalArgumentException; /** * Adds the key, value pair to this DefaultMap if it is not present, * otherwise, replaces the value with the given value * @throws IllegalArgumentException if the key is null */ void set (K key, V value) throws IllegalArgumentException; * void set(K key, V value) throws IllegalArgumentException; /*** * @return the value corresponding to the specified key * @throws IllegalArgumentException if the key is null */ V get(K key) throws IllegalArgumentException; /** * @return The number of (key, value) pairs in this DefaultMap */ int size(); /** == 0 is true * @return true iff this.size() */ boolean isEmpty(); /** * @return true if the specified key is in this DefaultMap * @throws IllegalArgumentException if the key is null */ boolean containskey (K key) throws IllegalArgumentException; /*** * * @return an array containing the keys of this DefaultMap. If this DefaultMap is * empty, returns array of length zero. */ List keys(); }