package CSC301SP18Homework; // change the package if you want public class Sorte
ID: 3756637 • Letter: P
Question
package CSC301SP18Homework; // change the package if you want
public class SortedArrayST<Key extends Comparable<Key>, 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,
// 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<Key>[] keysArray() {
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;
}
/**
* shiftRight
*
* preconditons ?
*
* Shifts the keys (and values) at indices r and larger to the right by one
* The key and value at position r do not change.
* This function must call the resize method (if needed) to increase the size of the
* underlying keys,vals arrays
*
*/
private void shiftRight(int r) {
return; // ToDo1: fix this
}
/**
* 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
}
Explanation / Answer
/* I have fixed TODO1 & TODO2
* NOTE: rank() function you have used here is not in your given code make sure you have implemented it.
*
*/
package CSC301SP18Homework; // change the package if you want
public class SortedArrayST<Key extends Comparable<Key>, 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,
// 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<Key>[] keysArray() {
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;
}
/**
* shiftRight
*
* preconditons
*
* 0 <= r <= N
*
* Shifts the keys (and values) at indices r and larger to the right by one
* The key and value at position r do not change.
* This function must call the resize method (if needed) to increase the size of the
* underlying keys,vals arrays
*
*/
private void shiftRight(int r) {
// ToDo1: fixed
if(r<0 || r>N) throw new IllegalArgumentException();
resize(N+1);
N = N + 1;// here N will be increase by 1 after resize
for (int i = N-1; i > r; i--) {
vals[i] = vals[i-1];
keys[i] = keys[i-1];
}
}
/**
* 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: fixed
if(r < 0) throw new IllegalArgumentException(); //Change the exception as per your requirement
if(N==0) throw new IllegalArgumentException(); //Change the exception as per your requirement
for (int x = r; x+1 < N; x++) {
vals[x] = vals[x+1];
keys[x] = keys[x+1];
}
vals[N-1] = null;
keys[N-1] = null;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.