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

}

}

"Get 15% discount on your first 3 orders with us"
Use the following coupon
"FIRST15"

Order Now