Java homework help | Computer Science homework help
,
/**
* Your homework is to complete the methods marked TODO.
* You must not change the declaration of any method.
*/
package hw2;
/**
* The SortedArrayST class represents an (ordered) symbol table of
* generic key-value pairs. It supports put, get, and delete methods.
*/
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
/**
* Initializes an empty symbol table.
*/
public SortedArrayST() {
this(MIN_SIZE);
}
/**
* Initializes an empty symbol table of given size.
*/
public SortedArrayST(int size) {
keys = (Key[])(new Object[size]);
vals = (Value[])(new Object[size]);
}
//
// the above constructor should be changed as below:
//
//public SortedArrayST(int size) {
//keys = (Key[])(new Comparable[size]);
//vals = (Value[])(new Object[size]);
//}
//
/**
* 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];
}
}
}
/**
* Returns the keys array of this symbol table.
*/
public Comparable<Key>[] keysArray() {
return keys;
}
/**
* Returns the values array of this symbol table.
*/
public Object[] valsArray() {
return vals;
}
/**
* Returns the number of keys in this symbol table.
*/
public int size() {
return N;
}
/**
* Returns whether the given key is contained in this symbol table.
*/
private boolean contains(Key key, int r) {
return (r >= 0 && r < N && key.equals(keys[r]));
}
/**
* Returns the value associated with the given key in this symbol table.
*/
public Value get(Key key) {
if (key == null) throw new NullPointerException(“argument to get() is null”);
int r = rank(key);
return (contains(key, r) ? vals[r] : null);
}
/**
* 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) {
if (key == null) throw new NullPointerException(“first argument to put() is null”);
if (val == null) {
delete(key);
return;
}
int r = rank(key);
if (contains(key, r)) {
vals[r] = val;
} else {
insert(key, val, r);
}
}
/**
* 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) {
if (key == null) throw new NullPointerException(“argument to delete() is null”);
int r = rank(key);
if (contains(key, r)) {
remove(r);
}
}
/**
* Inserts the given key value pair into this symbol table at index r
*/
private void insert(Key key, Value val, int r) {
// TODO
}
/**
* Removes the key at index r and its associated value from this symbol table
*/
private void remove(int r) {
// TODO
}
/**
* 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);
// TODO : logarithmic time implementation
}
/**
* Linear time implementation of rank
*/
private int linearTimeRank(Key key) {
int r;
for (r = 0; r < N && key.compareTo(keys[r]) > 0; r++);
return r;
}
/**
* ceiling returns the smallest key in the symbol table that is greater than or equal to key.
* it returns null if there is no such key.
*/
public Key ceiling(Key key) {
return null; // TODO
}
}
——————————————
And this is the test file:
package hw2;
import static org.junit.Assert.*;
import org.junit.Test;
import java.util.Random;
import java.lang.management.*;
public class HW2Test {
String border = “*******************************************\n”;
String passed = “* Passed! *\n”;
String failed = “* Failed! *\n”;
String test;
AssertionError ae;
Exception e;
int size, psize;
int p;
String[] keys;
Integer[] vals;
boolean[] picked;
String arg;
SortedArrayST<String, Integer> st;
private String keyvalsToString(boolean justPicked) {
int sz = justPicked ? psize : size;
StringBuilder s = new StringBuilder();
s.append(“size = ” + sz + “, key-value pairs = “);
int i, k;
for (i = 0, k = 0; i < sz – 1; i++, k++) {
if (justPicked) for (; p == k || !picked[k]; k++);
s.append(“(” + keys[k] + “, ” + vals[k] + “), “);
}
if (sz > 0) {
if (justPicked) for (; p == k || !picked[k]; k++);
s.append(“(” + keys[k] + “, ” + vals[k] + “)”);
}
return s.toString();
}
public static String twoLetterString(int val) {
char chars[] = new char[2];
chars[0] = (char)(‘A’ + ((val / 26) % 26));
chars[1] = (char)(‘A’ + (val % 26));
return String.valueOf(chars);
}
public static String randomTwoLetterAbove(Random rand, int threshold) {
int val = threshold + 1 + rand.nextInt(26 * 26 – threshold – 1);
return twoLetterString(val);
}
public static String randomTwoLetterBelow(Random rand, int threshold) {
int val = rand.nextInt(threshold);
return twoLetterString(val);
}
private void randomTwoLetterStringsAbove(Random rand, int i0, int i1, int threshold) {
threshold++;
int space = 26 * 26 – threshold;
int size = i1 – i0;
int i, val;
boolean[] taken = new boolean[space];
for (i = 0; i < size; i++) {
while(true) {
val = rand.nextInt(space);
if (!taken[val]) break;
}
taken[val] = true;
}
for (i = i0, val = 0; val < space; val++) {
if (taken[val]) keys[i++] = twoLetterString(val + threshold);
}
}
private void randomTwoLetterStringsBelow(Random rand, int i0, int i1, int threshold) {
int space = threshold;
int size = i1 – i0;
int i, val;
boolean[] taken = new boolean[space];
for (i = 0; i < size; i++) {
while(true) {
val = rand.nextInt(space);
if (!taken[val]) break;
}
taken[val] = true;
}
for (i = i0, val = 0; val < space; val++) {
if (taken[val]) keys[i++] = twoLetterString(val);
}
}
private void randomVals(Random rand, int size) {
vals = new Integer [size];
for (int i = 0; i < size; i++) vals[i] = rand.nextInt(200);
}
private SortedArrayST<String, Integer> createST() {
return new SortedArrayST<String, Integer>(keys, vals);
}
private void tstPut() {
SortedArrayST<String, Integer> st;
Random rand = new Random(0);
int i, k;
for (size = 1; size <= 100; size++) {
keys = new String[size];
randomVals(rand, size);
picked = new boolean[size];
randomTwoLetterStringsBelow(rand, 0, size, 26 * 26);
st = new SortedArrayST<String, Integer>();
for (psize = 0; psize < size; psize++) {
while(true) {
p = rand.nextInt(size);
if (!picked[p]) break;
}
picked[p] = true;
st.put(keys[p], vals[p]);
// testing size;
assertEquals(psize + 1, st.size());
Comparable<String>[] stKeys = st.keysArray();
Object[] stVals = st.valsArray();
// testing keys and vals
for (i = 0, k = 0; i <= psize; i++, k++) {
for (; !picked[k]; k++);
assertEquals(keys[k], stKeys[i]);
assertEquals(vals[k], stVals[i]);
}
}
}
}
private void tstDel() {
SortedArrayST<String, Integer> st;
Random rand = new Random(0);
int i, k;
for (size = 1; size <= 100; size++) {
keys = new String[size];
randomVals(rand, size);
picked = new boolean[size];
randomTwoLetterStringsBelow(rand, 0, size, 26 * 26);
st = createST();
for (psize = 0; psize < size; psize++) {
while(true) {
p = rand.nextInt(size);
if (!picked[p]) break;
}
picked[p] = true;
st.delete(keys[p]);
// testing size;
assertEquals(size – psize – 1, st.size());
Comparable<String>[] stKeys = st.keysArray();
Object[] stVals = st.valsArray();
// testing keys and vals
for (i = 0, k = 0; i < size – psize – 1; i++, k++) {
for (; picked[k]; k++);
assertEquals(keys[k], stKeys[i]);
assertEquals(vals[k], stVals[i]);
}
}
}
}
private void tstCeil() {
Random rand = new Random(0);
for (size = 0; size <= 100; size++) {
keys = new String[size];
randomVals(rand, size);
int threshold = rand.nextInt(13 * 13 * 2) + 13 * 13;
String randStr = twoLetterString(threshold);
int val = threshold + rand.nextInt(26 * 22 – threshold) + 1;
String above = twoLetterString(val);
String exp;
for (int j = 0; j < size; j++) {
randomTwoLetterStringsBelow(rand, 0, j, threshold – 1);
keys[j] = randStr;
if (j < size – 1) {
keys[j + 1] = above;
exp = above;
} else {
exp = null;
}
randomTwoLetterStringsAbove(rand, j + 2, size, val + 1);
SortedArrayST<String, Integer> st = createST();
arg = keys[j];
assertEquals(arg, st.ceiling(arg));
arg = twoLetterString(threshold – 1);
assertEquals(keys[j], st.ceiling(arg));
arg = twoLetterString(threshold + 1);
assertEquals(exp, st.ceiling(arg));
}
arg = above;
assertEquals(null, createST().ceiling(arg));
}
}
private void tstRank() {
Random rand = new Random(0);
for (size = 0; size <= 100; size++) {
keys = new String[size];
randomVals(rand, size);
int threshold = rand.nextInt(13 * 13 * 2) + 13 * 13;
String randStr = twoLetterString(threshold);
for (int j = size – 1; j >= 0; j–) {
randomTwoLetterStringsBelow(rand, 0, j, threshold – 1);
keys[j] = randStr;
randomTwoLetterStringsAbove(rand, j + 1, size, threshold + 1);
SortedArrayST<String, Integer> st = createST();
arg = keys[j];
assertEquals(j, st.rank(arg));
arg = twoLetterString(threshold – 1);
assertEquals(j, st.rank(arg));
arg = twoLetterString(threshold + 1);
assertEquals(j + 1, st.rank(arg));
}
arg = randStr;
assertEquals(0, createST().rank(arg));
}
tstRankPerformance();
}
private void randomKeyVals(int size) {
this.size = size;
int mask = 16;
for (mask = 16; mask < size; mask *= 16);
keys = new String[size];
vals = new Integer[size];
for (int i = 0; i < size; i++) {
keys[i] = Integer.toHexString(mask | i).toUpperCase().substring(1);
vals[i] = i;
}
}
private void printTimes(int l, int[] sizes, long[] times, long[] avg) {
for (int i = 0; i < l; i++) {
System.out.println(“Time elapsed for size ” + sizes[i] + “: ” + times[i] + ” => average (per key) : ” + avg[i]);
}
}
private void tstRankPerformance() {
ThreadMXBean thread = ManagementFactory.getThreadMXBean();
SortedArrayST<String, Integer> st;
String[] stKeys;
Integer[] stVals;
randomKeyVals(1024 * 1024);
System.out.println(“Testing efficiency for ” + size + ” keys in total.”);
int[] sizes = new int[11];
long[] times = new long[11];
long[] avg = new long[11];
long nanoTime = 0;
boolean usingNanoTime = false;
int beginInd = 0;
int failures = 0;
int i, j, l, sz;
for (l = 0; l < 11; l++) {
sizes[l] = size >> (10 – l);
stKeys = new String[sizes[l]];
stVals = new Integer[sizes[l]];
for (i = 0, j = 0, sz = size / sizes[l]; i < sizes[l]; i++, j += sz) {
stKeys[i] = keys[j];
stVals[i] = vals[j];
}
st = new SortedArrayST<String, Integer>(stKeys, stVals);
times[l] = thread.getCurrentThreadCpuTime();
nanoTime = System.nanoTime();
for (i = 0; i < size; i += (i % sz == 0 ? 1 : sz – 1)) {
assertEquals((i + sz – 1) / sz, st.rank(keys[i]));
}
times[l] = thread.getCurrentThreadCpuTime() – times[l];
if (times[l] == 0) usingNanoTime = true;
if (usingNanoTime) {
times[l] = System.nanoTime() – nanoTime;
}
avg[l] = times[l] / sizes[l];
if (usingNanoTime && l < 3) {
if (avg[beginInd] > 2 * avg[l]) beginInd = l;
} else {
if (avg[l] > avg[beginInd] * 8) failures++;
}
if ((!usingNanoTime && failures > 0) || failures > 2) {
if (usingNanoTime) System.out.println(“USING NANO TIME!!!”);
printTimes(l + 1, sizes, times, avg);
System.out.println(“Search takes more than logarithmic time.”);
System.out.println(“Failed rank performance test!”);
fail(“Rank computation is inefficient!”);
}
}
if (usingNanoTime) System.out.println(“USING NANO TIME!!!”);
printTimes(l, sizes, times, avg);
System.out.println(“Passed rank performance test!”);
}
private void tstInsDel() {
// first testing correctness
tstPut();
tstDel();
// then testing performance
ThreadMXBean thread = ManagementFactory.getThreadMXBean();
SortedArrayST<String, Integer> st = new SortedArrayST<String, Integer>();
randomKeyVals(1024 * 1024);
System.out.println(“Testing efficiency for ” + size + ” keys in total.”);
int[] sizes = new int[11];
long[] times = new long[11];
long[] avg = new long[11];
int beginInd = 0;
int failures = 0;
long timeBefore = thread.getCurrentThreadCpuTime();
long nanoTime = System.nanoTime();
boolean usingNanoTime = false;
int i, l;
for (l = 0; l < 11; l++) {
sizes[l] = size >> (10 – l);
times[l] = timeBefore;
for (i = 0; i < sizes[l]; i++) {
assertEquals(i, st.size());
st.put(keys[i], vals[i]);
}
for (i = sizes[l] – 1; i >= 0; i–) {
assertEquals(keys[i], st.keysArray()[i]);
assertEquals(vals[i], st.valsArray()[i]);
st.delete(keys[i]);
assertEquals(i, st.size());
}
assertTrue(st.size() < 128);
times[l] = thread.getCurrentThreadCpuTime() – times[l];
if (times[l] == 0) usingNanoTime = true;
if (usingNanoTime) {
times[l] = System.nanoTime() – nanoTime;
}
avg[l] = times[l] / sizes[l];
if (usingNanoTime && l < 3) {
if (avg[beginInd] > 2 * avg[l]) beginInd = l;
} else {
if (avg[l] > avg[beginInd] * 8) failures++;
}
if ((!usingNanoTime && failures > 0) || failures > 2) {
if (usingNanoTime) System.out.println(“USING NANO TIME!!!”);
printTimes(l + 1, sizes, times, avg);
System.out.println(“In order insert/delete takes more than logarithmic time.”);
System.out.println(“Failed insert/delete performance test!”);
fail(“In order insert/delete is inefficient!”);
}
}
if (usingNanoTime) System.out.println(“USING NANO TIME!!!”);
printTimes(l, sizes, times, avg);
System.out.println(“Passed in order insert/delete performance test!”);
}
private void testMethod(int methodID) throws Exception {
try {
System.out.print(border + test + border);
switch (methodID) {
case 0: tstPut(); break;
case 1: tstDel(); break;
case 2: tstCeil(); break;
case 3: tstRank(); break;
case 4: tstInsDel(); break;
}
} catch(AssertionError aerr) {
ae = aerr;
} catch(Exception err) {
e = err;
}
if (ae != null || e != null) {
if (size <= 100) {
System.out.println(“Fails on the below key value pairs:”);
System.out.println(keyvalsToString(false));
switch (methodID) {
case 0: System.out.println(“Failure in putting (” + keys[p] + “, ” + vals[p] + “) into the following symbol table:”);
System.out.println(keyvalsToString(true));
break;
case 1: System.out.println(“Failure in deleting key = ” + keys[p] + ” after successfully deleting the following:”);
System.out.println(keyvalsToString(true));
break;
case 2: System.out.println(“Failure while computing the ceiling of ” + arg); break;
case 3: System.out.println(“Failure while computing the rank of ” + arg); break;
case 4: System.out.println(“Failure in correctness of put or delete”); break;
}
}
System.out.print(“\n” + border + test + failed + border);
if (ae != null) throw ae;
if (e != null) throw e;
} else {
System.out.print(border + test + passed + border);
}
}
@Test
public void testPut() throws Exception {
test = “* Testing put *\n”;
testMethod(0);
}
@Test
public void testDelete() throws Exception {
test = “* Testing delete *\n”;
testMethod(1);
}
@Test
public void testCeiling() throws Exception {
test = “* Testing ceiling *\n”;
testMethod(2);
}
@Test
public void testRankPerformance() throws Exception {
test = “* Testing performance of rank *\n”;
testMethod(3);
}
@Test
public void testInsDelPerformance() throws Exception {
test = “* Testing performance of put and delete *\n”;
testMethod(4);
}
}
