package homework; import stdlib.StdOut; public class SortedArrayST { private static final int MIN_SIZE = 2; private Key[] keys; // the keys array private Value[] vals;

package homework;

import stdlib.StdOut;

public class SortedArrayST, 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[] 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) { if((N + 1) > keys.length) { resize(N + 1); N = N + 1; } for (int i = N-1; i > r; i--) { vals[i] = vals[i-1]; keys[i] = keys[i-1]; } } // ToDo1

/** * 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) { for (int i = r; i+1 < N; i++) { vals[i] = vals[i+1]; keys[i] = keys[i+1]; } vals[N-1] = null; keys[N-1] = null; N = N - 1; // ToDo2 }

/** * rank returns the number of keys in this symbol table that is less than the given key. */ public int rank(Key key) { return logTimeRank(key);

// ToDo3 : replace the above call to linearTimeRank with // a logarithmic time implementation } private int logTimeRank(Key key) { int lo = 0, hi = N-1; while (lo <= hi) { int m = lo + (hi - lo) / 2; int cmp = key.compareTo(keys[m]); if (cmp < 0) hi = m - 1; else if (cmp > 0) lo = m + 1; else return m; } return lo; } /** * 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; }*/

/** * floor * * floor returns the largest key in the symbol table that is less than or equal to key. * it returns null if there is no such key. * must be logarithmic time for full credit. Hint : rank */ public Key floor(Key key) { int i = rank(key); if (i < N && key.compareTo(keys[i]) == 0) return keys[i]; if (i == 0) return null; else return keys[i-1]; } /** * countRange * * countRange returns the number of keys in the table within the range [key1, key2] (inclusive) * note that keys may not be in order (key1 may be larger than key2): your code should still consider * this a valid range and report the result. * must run in logarithmic time for full credit. hint: rank */ public int countRange(Key key1, Key key2) {

}

countRange pls.