package homework; import stdlib.StdOut; public class SortedArrayST { private static final int MIN_SIZE = 2; private Key[] Keys; // the keys array private Value[] Vals;

package homework; import stdlib.StdOut; public class SortedArrayST, Value> { private static final int MIN_SIZE = 2; private Key[] Keys; // the keys array private Value[] Vals; // the values array private int N = 0; // size of the symbol table, must be maintained by all methods // may be less than the size of the arrays /** * Constructor * * Initializes an empty symbol table. */ public SortedArrayST() { this(MIN_SIZE); } /** * Constructor * * Initializes an empty symbol table of given size. */ @SuppressWarnings("unchecked") // this tells the compiler that the Generic code below is actually okay public SortedArrayST(int size) { Keys = (Key[]) (new Comparable[size]); Vals = (Value[])(new Object[size]); } /** * Constructor * * Initializes a symbol table with given sorted key-value pairs. * If given key list is not sorted in (strictly) increasing order, * then the input is discarded and an empty symbol table is initialized. */ public SortedArrayST(Key[] key, Value[] val) { this(key.length < MIN_SIZE ? MIN_SIZE : key.length); N = (key.length == val.length ? key.length : 0); int i; for (i = 1; i < N && key[i].compareTo(key[i - 1]) > 0; i++); if (i < N) { // input array is not sorted System.err.println("SortedArrayST(Key[], Value[]) constructor error:"); System.err.println("Given key array of size " + N + " was not sorted!"); System.err.println("Initializing an empty symbol table!"); N = 0; } else { for (i = 0; i < N; i++) { this.Keys[i] = key[i]; this.Vals[i] = val[i]; } } } /** * keyArray * * Returns the keys array of this symbol table. */ public Comparable[] keyArray() { return Keys; } * Returns the values array of this symbol table. */ public Object[] valArray() { return Vals; } * Returns the number of key in this symbol table. */ public int size() { return N; } * Returns whether the given key is contained in this symbol table at index pos. */ private boolean checkFor(Key aKey, int pos) { return (pos >= 0 && pos < N && aKey.equals(Keys[pos])); } * Returns the value associated with the given key in this symbol table. */ public Value get(Key key) { int pos = rank(key); if (checkFor(key, pos)) return Vals[pos]; else return null; } * Inserts the specified key-value pair into the symbol table, overwriting the old * value with the new value if the symbol table already contains the specified key. * Deletes the specified key (and its associated value) from this symbol table * if the specified value is null. */ public void put(Key aKey, Value aVal) { int pos = rank(aKey); if (!checkFor(aKey, pos)) { shiftRight(pos); theKeys[pos] = aKey; } Vals[pos] = aVal; // ? } * Removes the specified key and its associated value from this symbol table * (if the key is in this symbol table). */ public void delete(Key aKey) { int pos = rank(aKey); // ? if (checkFor(aKey, pos)) { // ? shiftLeft(pos); // ? } } /** * contains * * return true if key is in the table */ public boolean contains(Key aKey) { return ( this.get(aKey)!= null); } * resize the underlying arrays to the specified capacity * copy old contents to newly allocated storage */ @SuppressWarnings("unchecked") // tell the compiler the following Generic code is okay private void resize(int capacity) { if (capacity <= N) throw new IllegalArgumentException (); Key[] tempk = (Key[]) new Comparable[capacity]; Value[] tempv = (Value[]) new Object[capacity]; for (int i = 0; i < N; i++) { tempk[i] = Keys[i]; tempv[i] = Vals[i]; } Vals = tempv; // ? Keys = tempk; // ? } * preconditions: * pos >=0 * stSize > 0 * postcondition: * the keys (and values) at indices p > pos shifted to the left by one * in effect, removing the key and value at index pos * 'clear' the original 'last' elements by setting them to null * this function does NOT need to decrease the size of the underlying arrays */ private void shiftLeft(int pos) { for(int i = pos; i < N - 1; i++) { Vals[i] = Vals[i+1]; Keys[i] = Keys[i+1]; } Vals[stSize-1] = null; Keys[stSize-1] = null; N--; } /** * ShiftRight * * preconditons ? * * Shifts the keys (and values) at indices pos and larger to the right by one * The key and value at position pos do not change. * This function must call the resize method (if needed) to increase the size of the * underlying key,val arrays * */ private void shiftRight(int pos) { if(N == Keys.length) { resize(Keys.length*2); } for(int i = N; i > pos; i--) { Keys[i] = Keys[i-1]; Vals[i] = Vals[i-1]; } N++; } /** * subFloor * Recall: floor(aKey) returns the largest key in the symbol table that is less than or equal to aKey * * subFloor returns the largest key (if any) that is *less than* the floor * it returns null if there is no such key. * must be logarithmic time for full credit. Hint : rank */ public Key subFloor(Key key) {  // ToDo3: implement this function } 

Need help on Todo3, don't know how to start this. Please don't alter the code above and only help on Todo 3. Thank you