Question: * CS 301 Homework Assignment 3 verison 1.0 * * Instructions: * * This class is a simple variation on the BinarySearchST class from section
* 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)
The class:
package CSC301SP18Homework; // change the package if you want
import stdlib.StdOut;
public class SortedArrayST
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,
// 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")
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 keys list is not sorted in (strictly) increasing order,
* then the input is discarded and an empty symbol table is initialized.
*/
public SortedArrayST(Key[] keys, Value[] vals) {
this(keys.length < MIN_SIZE ? MIN_SIZE : keys.length);
N = (keys.length == vals.length ? keys.length : 0);
int i;
for (i = 1; i < N && keys[i].compareTo(keys[i - 1]) > 0; i++);
if (i < N) { // input is not sorted
System.err.println("SortedArrayST(Key[], Value[]) constructor error:");
System.err.println("Given keys 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] = keys[i];
this.vals[i] = vals[i];
}
}
}
/**
* keysArray
*
* Returns the keys array of this symbol table.
*/
public Comparable
return keys;
}
/**
* valsArray
*
* Returns the values array of this symbol table.
*/
public Object[] valsArray() {
return vals;
}
/**
* size
*
* Returns the number of keys in this symbol table.
*/
public int size() {
return N;
}
/**
* checkFor
*
* Returns whether the given key is contained in this symbol table at index r.
*/
private boolean checkFor(Key key, int r) {
return (r >= 0 && r < N && key.equals(keys[r]));
}
/**
* get
*
* Returns the value associated with the given key in this symbol table.
*/
public Value get(Key key) {
int r = rank(key);
if (checkFor(key, r)) return vals[r];
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 key, Value val) {
int r = rank(key);
if (!checkFor(key, r)) {
shiftRight(r); // make space for new key/value pair
keys[r] = key; // put the new key in the table
}
vals[r] = val; // ?
}
/**
* 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 key) {
int r = rank(key);
if (checkFor(key, r)) {
shiftLeft(r); // remove the specified key/value
}
}
/**
* contains
*
* return true if key is in the table
*/
public boolean contains(Key key) {
return ( this.get(key)!= null);
}
/**
* resize
*
* resize the underlying arrays to the specified size
* copy old contents to newly allocated storage
*/
@SuppressWarnings("unchecked")
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;
}
/**
* 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);
// ToDo3 : replace the above call to linearTimeRank with
// a logarithmic time implementation
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help