* CS 301 Homework Assignment 3 verison 1.0 * * Instructions: * * This class is a simple variation on the BinarySearchST class from section 3.1 * Like the BinarySearchST, this class stores a sybmol table in ordered form in two parallel arrays * many of the basic API functions are provided for you. For example: contains, get. * put and delete rely on two functions shiftright, shiftleft that you need to complete . See the * Misc. Note below * * Your assignment is to complete the ToDo items:some are coding questions, the others require you * to construct test cases. Search for ToDo. The header comment for each ToDo contain more * specific instructions for that function * As provided, the program will run, but the most of the test cases will fail. * One exception is the rank function tests. These should all pass because a linear-time * version of the rank function is supplied. One of the ToDos is to replace the linear-time rank * function with a logarithmic time version (i.e. binary search). Since the rank function is used by other functions in the class, * if your new version of rank is incorrect, other parts of the program may break. * * Misc. Note. put *may* increase the size of the symbol table. You will need add code to record this fact * There are two 'reasonable' places to put such code; one of these places would be the put function * Likewise, delete will decrease the size of the table and you will need to add code for this as well. * One place (of the two places) to do this would be in the delete function * * Your code may have to resize the underlying arrays - a resize function has been provided for you - look through the file! * You may not modify methods in this file except as indicated. If you are unsure, ask. * You may add additional methods for modularity * You may not use other Java data structures (e.g. ArrayList, HashSet, etc)

/**

* shiftLeft

*

* preconditions:

* r >=0

* N > 0

* postcondition:

* the keys (and values) at indices x > r shifted to the left by one

* in effect, removing the key and value at index r

* '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 r) {

// TODO2: fix this

}