Need help on ToDo 5. import stdlib.StdOut; public class SortedArrayST { private static final int MIN_SIZE = 2; private Key[] theKeys; // the keys array

Need help on ToDo 5.

import stdlib.StdOut;

public class SortedArrayST, Value> { private static final int MIN_SIZE = 2; private Key[] theKeys; // the keys array private Value[] theVals; // the values array private int stSize = 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) { theKeys = (Key[]) (new Comparable[size]); theVals = (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); stSize = (key.length == val.length ? key.length : 0); int i; for (i = 1; i < stSize && key[i].compareTo(key[i - 1]) > 0; i++); if (i < stSize) { // input array is not sorted System.err.println("SortedArrayST(Key[], Value[]) constructor error:"); System.err.println("Given key array of size " + stSize + " was not sorted!"); System.err.println("Initializing an empty symbol table!"); stSize = 0; } else { for (i = 0; i < stSize; i++) { this.theKeys[i] = key[i]; this.theVals[i] = val[i]; } } }

/** * keyArray * * Returns the keys array of this symbol table. */ public Comparable[] keyArray() { return theKeys; }

/** * valArray * * Returns the values array of this symbol table. */ public Object[] valArray() { return theVals; }

/** * size * * Returns the number of key in this symbol table. */ public int size() { return stSize; }

/** * checkFor * * 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 < stSize && aKey.equals(theKeys[pos])); }

/** * get * * 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 theVals[pos]; else return null; }

/** * put * * 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); // key should be (or be placed in) location pos if (!checkFor(aKey, pos)) { // if aKey is not there in location pos shiftRight(pos); // make space for new key/aValue pair theKeys[pos] = aKey; // put the new key in the table

} theVals[pos] = aVal; // ? }

/** * delete * * 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 * * 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 <= stSize) throw new IllegalArgumentException (); Key[] tempk = (Key[]) new Comparable[capacity]; Value[] tempv = (Value[]) new Object[capacity]; for (int i = 0; i < stSize; i++) { tempk[i] = theKeys[i]; tempv[i] = theVals[i]; } theVals = tempv; // ? theKeys = tempk; // ? }

/** * shiftLeft * * 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 < stSize - 1; i++) { theVals[i] = theVals[i+1]; //loops from i=pos to i = stSize-2 theKeys[i] = theKeys[i+1]; } theVals[stSize-1] = null; theKeys[stSize-1] = null; stSize--; } /** * 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(stSize == theKeys.length) { resize(theKeys.length*2); } for(int i = stSize; i > pos; i--) { theKeys[i] = theKeys[i-1]; theVals[i] = theVals[i-1]; } stSize++; }

/** * 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) {

return null; // ToDo3: implement this function

} /** * rangeCount * * rangeCount returns the number of keys in the table within the range [smallerKey, largerKey) * (i.e. including the left boundary but NOT the right boundary) * note that parameter keys may not be in order (key1 may be larger than key2): your code should still consider * this a valid range and report the result. * must run in logarithmic time for full credit. hint: rank */ public int rangeCount(Key key1, Key key2) { return -2; // ToDo4: implement this function }

/** * rank returns the number of keys in this symbol table that is less than the given key. */ public int rank(Key key) { return linearTimeRank(key); // ToDo5 : replace the above call to linearTimeRank with // a logarithmic time implementation }

/** * Linear time implementation of rank */ private int linearTimeRank(Key aKey) { int pos; for (pos = 0; pos < stSize && aKey.compareTo(theKeys[pos]) > 0; pos++); return pos; }