Implement the following Symbol Table in Java, all methods should be fully implemented and working and with
Question:
Implement the following Symbol Table in Java, all methods should be fully implemented and working and with exception handling,
import java.util.Iterator;
public class STv2, Value> implements ST {
private Key[] keys; // keep the keys in sorted order private Value[] values; private int n;
public STv2() { n = 0; keys = (Key[]) new Comparable[8]; values = (Value[]) new Object[8]; }
@Override public void put(Key key, Value val) { // O(n) if (key == null || val == null) throw new IllegalArgumentException();
int i = rank(key); // O(log N)
if (i < n && keys[i].compareTo(key) == 0) { values[i] = val; return; }
if (n == keys.length) resize(2 * keys.length);
for (int j = n; j > i; j--) { // O(n) keys[j] = keys[j - 1]; values[j] = values[j - 1]; } keys[i] = key; values[i] = val; n++;
}
@Override public Value get(Key key) { /// O (log n) // i can use binary search here because of sorting if (key == null) throw new IllegalArgumentException(); if (n == 0) return null; int i = rank(key); // O(log n) .. my position if (i < n && keys[i].compareTo(key) == 0) return values[i]; return null; }
public int rank(Key key) { // O(log n) // number of keys in the symbol table that is < key if (key == null) throw new IllegalArgumentException(); int lo = 0, hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; int cmp = key.compareTo(keys[mid]); if (cmp < 0) hi = mid - 1; else if (cmp > 0) lo = mid + 1; else return mid; } return lo; }
@Override public boolean contains(Key key) { // O(logN) return get(key) != null; }
@Override public void delete(Key key) { // O(N) if (key == null) throw new IllegalArgumentException(); if (n == 0) return;
int i = rank(key);
if (i == n || keys[i].compareTo(key) != 0) { return; }
for (int j = i; j < n - 1; j++) { keys[j] = keys[j + 1]; values[j] = values[j + 1]; }
n--; keys[n] = null; // to avoid loitering values[n] = null;
// resize if 1/4 full if (n > 2 && n == keys.length / 4) resize(keys.length / 2); }
private void resize(int capacity) { 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] = values[i]; } values = tempv; keys = tempk; }
@Override public int size() { return n; }
activities to be completed
@Override public Iterable keys() { }
// Key min() // return minimum key
// Key max() // return maximum key
// Key select(int k) // return key of rank k
// void deleteMin() // delete min key
// void deleteMax() // delete max key
// Key floor(Key key) // return largest Key <= key
// Key ceiling(Key key) // return smallest key >= key
// int size(Key lo, Key hi) // return number of keys between hi and lo, // inclusive }
Accounting Information Systems
ISBN: 978-0133428537
13th edition
Authors: Marshall B. Romney, Paul J. Steinbart