search: BinarySearchST

OneCodeMonkey · OneCodeMonkey · commit 97f7228a62f7 · 2019-08-19T15:33:41.000+08:00
diff --git a/Algorithm_full_features/search/BinarySearchST.java b/Algorithm_full_features/search/BinarySearchST.java
@@ -0,0 +1,281 @@
+import java.util.NoSuchElementException;
+
+public class BinarySearchST<Key extends Comparable<Key>, value> {
+	private static final int INIT_CAPACITY = 2;
+	private Key[] keys;
+	private Value[] vals;
+	private int n = 0;
+
+	public BinarySearchST() {
+		this(INIT_CAPACITY);
+	}
+
+	// Initializes an empty symbol table with the specified initial capacity.
+	public BinarySearchST(int capacity) {
+		keys = (Key[]) new Comparable[capacity];
+		vals = (Value[]) new Object[capacity];
+	}
+
+	private void resize(int capacity) {
+		assert capacity >= n;
+		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;
+	}
+
+	// returns the number of key-value pairs in this symbol table.
+	public int size() {
+		return n;
+	}
+
+	// returns true if this symbol table is empty.
+	public boolean isEmpty() {
+		return size() == 0;
+	}
+
+	// does this symbol table contain the given key?
+	public boolean contains(Key key) {
+		if(key == null)
+			throw new IllegalArgumentException("argument to contains() is null");
+		return get(key) != null;
+	}
+
+	// returns the value associated with the given key in this symbol table.
+	public Value get(Key key) {
+		if(key == null)
+			throw new IllegalArgumentException("argument to get() is null");\
+		if(isEmpty())
+			return null;
+		int i = rank(key);
+		if(i < n && keys[i].compareTo(key) == 0)
+			return vals[i];
+		return null;
+	}
+
+	// returns the number of keys in this symbol table strictly less than `key`
+	public int rand(Key key) {
+		if(key == null)
+			throw new IllegalArgumentException("argument to rank() is null");
+		int low = 0, high = n - 1;
+		while(low <= high) {
+			int mid = low + (high - low) / 2;
+			int cmp = key.compareTo(keys[mid]);
+			if(cmp < 0)
+				high = mid - 1;
+			else if(cmp > 0)
+				low = mid + 1;
+			else
+				return mid;
+		}
+		return low;
+	}
+
+	// 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 IllegalArgumentException("first argument to put() is null");
+		if(val == null) {
+			delete(key);
+			return;
+		}
+		int i = rank(key);
+
+		// key is already in table
+		if(i < n && keys[i].compareTo(key) == 0) {
+			vals[i] = val;
+			return;
+		}
+
+		// insert new key-value pair
+		if(n == keys.length)
+			resize(2 * keys.length);
+
+		for(int j = n; j > i; j--) {
+			keys[j] = keys[j - 1];
+			vals[j] = vals[j - 1];
+		}
+		keys[i] = key;
+		vals[i] = val;
+		n++;
+
+		assert check();
+	}
+
+	// removes the specified key and associated value from this symbol table.
+	// (if the key is in the symbol table)
+	public void delete(Key key) {
+		if(key == null)
+			throw new IllegalArgumentException("argument to delete() is null");
+		if(isEmpty())
+			return;
+
+		// compute rank
+		int i = rank(key);
+		// key not in table
+		if(i == n | keys[i].compareTo(key) != 0) {
+			return;
+		}
+
+		for(int j = i; j < n - 1; j++) {
+			keys[j] = keys[j + 1];
+			vals[j] = vals[j + 1];
+		}
+
+		n--;
+		keys[n] = null;
+		vals[n] = null;
+
+		// resize if 1/4 full
+		if(n > 0 && n == keys.length / 4)
+			resize(keys.length / 2);
+
+		assert check();
+	}
+
+	// Removes the smallest key and associated value from this symbol table.
+	public void deleteMin() {
+		if(isEmpty())
+			throw new NoSuchElementException("Symbol table underflow error");
+		delete(min());
+	}
+
+	// removes the largest key and associated value from this symbol table.
+	public void deleteMax() {
+		if(isEmpty())
+			throw new NoSuchElementException("Symbol table underflow error");
+		delete(max());
+	}
+
+	/********************************
+	 * Ordered symbol table methods *
+	 *                              *
+	 ********************************/
+	
+	// returns the smallest key in this symbol table
+	public Key min() {
+		if(isEmpty())
+			throw new NoSuchElementException("called min() with empty symbol table");
+		return keys[0];
+	}
+
+	// Returns the largest key in this symbol table.
+	public Key max() {
+		if(isEmpty())
+			throw new NoSuchElementException("called max() with empty symbol table");
+		return keys[n - 1];
+	}
+
+	// Returns the kth smallest key in this symbol table.
+	public Key select(int k) {
+		if(k < 0 || k >= size)
+			throw new IllegalArgumentException("called select() with invalid argument: " + k);
+		return keys[k];
+	}
+
+	// Returns the largest key in this symbol table less than or equal to `key`
+	public Key floor(Key key) {
+		if(key == null)
+			throw new IllegalArgumentException("argument to floor() is null");
+		int i = rank(key);
+		if(i < n && key.compareTo(keys[i]) == 0)
+			return keys[i];
+		if(i == 0)
+			return null;
+		else
+			return key[i - 1];
+	}
+
+	public Key ceiling(Key key) {
+		if(key == null)
+			throw new IllegalArgumentException("argument to ceiling() is null");
+		int i = rank(key);
+		if(i == n)
+			return null;
+		else
+			return keys[i];
+	}
+
+	// Returns the number of keys in this symbol table int the specified range.
+	public int size(Key low, Key high) {
+		if(low == null)
+			throw new IllegalArgumentException("first argument to size() is null");
+		if(high == null)
+			throw new IllegalArgumentException("second argument to size() is null");
+		if(low.compareTo(high) > 0)
+			return 0;
+		if(contains(high))
+			return rank(high) - rank(low) + 1;
+		else
+			return rank(high) - rank(low);
+	}
+
+	// Returns all keys in this symbol table as an `Iterable`
+	// To iterate over all of the keys in the symbol table named `st`
+	// use the foreach notation `for(Key key : st.keys())`
+	public Iterable<Key> keys() {
+		return keys(min(), max());
+	}
+
+	// Returns all keys in this symbol table in the given range as an `Iterable`
+	public Iterable<Key> keys(Key low, Key high) {
+		if(low == null)
+			throw new IllegalArgumentException("first arugment to keys() is null");
+		if(high == null)
+			throw new IllegalArgumentException("second argument to keys() is null");
+		Queue<Key> queue = new Queue<Key>()
+		if(low.compareTo(high) > 0)
+			return queue;
+		for(int i = rank(low); i < rank(high); i++)
+			queue.enqueue(keys[i]);
+		if(contains(high))
+			queue.enqueue(keys[rank(high)]);
+		return queue;
+	}
+
+	/*****************************
+	 * check internal invariants *
+	 *	                         *
+	 *****************************/
+	private boolean check() {
+		return isSorted() && rankCheck();
+	}
+
+	// are the items in the array in ascending order?
+	private boolean isSorted() {
+		for(int i = 1; i < size(); i++)
+			if(keys.compareTo(keys[i - 1]) < 0)
+				return false;
+		return true;
+	}
+
+	// check that rank(select(i)) = i
+	private boolean rankCheck() {
+		for(int i = 0; i < size(); i++)
+			if(i != rank(select(i)))
+				return false;
+		for(int i = 0; i < size(); i++)
+			if(keys[i].compareTo(select(rank(keys[i]))) != 0)
+				return false;
+
+		return true;
+	}
+
+	// test
+	public static void main(String[] args) {
+		BinarySearchST<String, Integer> st = new BinarySearchST<String, Integer>();
+		for(int i = 0; !StdIn.isEmpty(); i++) {
+			String key = StdIn.readString();
+			st.put(key, i);
+		}
+		for(String s:st.keys())
+			StdOut.println(s + " " + st.get(s));
+	}
+}
