Note: I need help with this code, the questions are marked as toDo such as toDo3 toDo4 and so on. Please make sure to complete them thats where i have problem.

package homework;

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++)

{

theKeys[i] = theKeys[i+1];

theVals[i] = theVals[i+1];

}

stSize--;

theKeys[stSize] = null; // to avoid loitering

theVals[stSize] = null;

if (stSize > 0 && stSize== theKeys.length/4) resize(theKeys.length/2);

return;

}

/**

* 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(2*stSize);

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

// ToDo3: document this function with comments

// that describe how your code solves the problem

}

/**

* 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 -1; // 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;

}

/**

* Driver program

*

* run all the tests

*/

public static void main(String[] args) {

allShiftLeftTests();

StdOut.println("Shift-left tests done ");

singlePutShiftRightTests();

multiPutShiftRightTests();

StdOut.println("Shift-right tests done ");

allsubFloorTests();

StdOut.println("subFloor tests done ");

allRangeCountTests();

StdOut.println("CountRange tests done ");

allRankTests();

StdOut.println("Rank tests done");

}

public static void allShiftLeftTests() {

// Testing the shiftLeft implementation by calling delete

// Inputs: String of keys, String of values, key to delete, expected keys & values

testDelete("EMPTY","12345", "E","MPTY","2345"); // delete first

testDelete("EMPTY","12345", "P","EMTY","1245"); // delete from 'middle'

testDelete("EMPTY","12345", "Y","EMPT","1234"); // delete last

// ToDo 1.1, 1.2 add two additional test cases substantively different from the above

// include comments to describe what your case is checking for

// try to think of an 'extreme' case

}

public static void singlePutShiftRightTests() {

// Testing the shiftRight implementation by calling put once

// Inputs: Sorted String of keys, String of values, key,value to insert, expected keys & values

testPut("EMPTY","12345", "Q","9", "EMPQTY","123945");

// ToDo 2.1 , 2.2 add at least two additional test cases substantively different from the above

// include comments to describe what your case is checking for

// try to think of an 'extreme/edge' case (hints: where key is inserted and/or size of table)

}

public static void allsubFloorTests() {

// Testing the ceilingPlusPlus function

// Inputs:String of keys, String of values, key to test, expected answer

// The 'answers' (last parameter) here are all wrong.

// A correct answer will be either null or one a String of length one from the keys string

// ToDo 3.1 determine the correct answers and

// update the last parameter accordingly

StdOut.println(" only 1 test case answer below is correct. Fix the rest and delete this print statement ");

testSubFloor("AEGILOPS","01234567", "A",null);

testSubFloor("AEGILOPS","01234567", "B","WRONG");

testSubFloor("AEGILOPS","01234567", "J","WRONG");

testSubFloor("AEGILOPS","01234567", "N","WRONG");

testSubFloor("AEGILOPS","01234567", "S","WRONG");

testSubFloor("AEGILOPS","01234567", "T","WRONG");

testSubFloor("AEGILOPS","01234567", "X","WRONG");

testSubFloor("AEGILOPS","01234567", "Z","WRONG");

}

public static void allRangeCountTests() {

// Testing the rangeCount function

// Inputs: String of keys, String of values, range: [key1,key2) expected answer

// [key1, key2) : the range includes key1, but not key2

// ToDo 4.1 fix all the answers in the test cases below

StdOut.println(" all the test case answers for rangeCount are incorrect. Fix them and delete this print statement ");

testRangeCount("BEIOU","13456", "A","Z", -2); // whole Range

testRangeCount("BEIOU","13456", "Z","A", -2); // whole Range

testRangeCount("BEIOU","13456", "J","N", -2); // empty Range

testRangeCount("BEIOU","13456", "C","O", -2); // partial Range

testRangeCount("BEIOU","13456", "B","O", -2); // partial Range

}

public static void allRankTests() {

// Testing the rank function

// Inputs: String of keys, String of values, Key to search on, expected answer

// ToDo 5.1 fix all the answers in the test cases below

StdOut.println(" all the test case answers for rank are incorrect. Fix them and delete this print statement ");

testRank("AEGILOPS","01234567", "A",1);

testRank("AEGILOPS","01234567", "B",2);

testRank("AEGILOPS","01234567", "C",-2);

testRank("AEGILOPS","01234567", "G",-4);

testRank("AEGILOPS","01234567", "P",9);

testRank("AEGILOPS","01234567", "Z", 3);

}