001// Exercise 3.1.16 3.1.17 3.1.30 (Solution published at http://algs4.cs.princeton.edu/) 002package algs31; 003import stdlib.*; 004import algs13.Queue; 005/* *********************************************************************** 006 * Compilation: javac BinarySearchST.java 007 * Execution: java BinarySearchST 008 * Dependencies: StdIn.java StdOut.java 009 * Data files: http://algs4.cs.princeton.edu/31elementary/tinyST.txt 010 * 011 * Symbol table implementation with binary search in an ordered array. 012 * 013 * % more tinyST.txt 014 * S E A R C H E X A M P L E 015 * 016 * % java BinarySearchST < tinyST.txt 017 * A 8 018 * C 4 019 * E 12 020 * H 5 021 * L 11 022 * M 9 023 * P 10 024 * R 3 025 * S 0 026 * X 7 027 * 028 *************************************************************************/ 029 030public class BinarySearchST<K extends Comparable<? super K>, V> { 031 private static final int INIT_CAPACITY = 2; 032 private K[] keys; 033 private V[] vals; 034 private int N = 0; 035 036 // create an empty symbol table with default initial capacity 037 public BinarySearchST() { this(INIT_CAPACITY); } 038 039 // create an empty symbol table with given initial capacity 040 @SuppressWarnings("unchecked") 041 public BinarySearchST(int capacity) { 042 keys = (K[]) new Comparable[capacity]; 043 vals = (V[]) new Object[capacity]; 044 } 045 046 // resize the underlying arrays 047 @SuppressWarnings("unchecked") 048 private void resize(int capacity) { 049 if (capacity <= N) throw new IllegalArgumentException (); 050 K[] tempk = (K[]) new Comparable[capacity]; 051 V[] tempv = (V[]) new Object[capacity]; 052 for (int i = 0; i < N; i++) { 053 tempk[i] = keys[i]; 054 tempv[i] = vals[i]; 055 } 056 vals = tempv; 057 keys = tempk; 058 } 059 060 061 // is the key in the table? 062 public boolean contains(K key) { return get(key) != null; } 063 064 // number of key-value pairs in the table 065 public int size() { return N; } 066 067 // is the symbol table empty? 068 public boolean isEmpty() { return size() == 0; } 069 070 // return the value associated with the given key, or null if no such key 071 public V get(K key) { 072 if (isEmpty()) return null; 073 int i = rank(key); 074 if (i < N && keys[i].compareTo(key) == 0) return vals[i]; 075 return null; 076 } 077 078 // return the number of keys in the table that are smaller than given key 079 public int rank(K key) { 080 int lo = 0, hi = N-1; 081 while (lo <= hi) { 082 int m = lo + (hi - lo) / 2; 083 int cmp = key.compareTo(keys[m]); 084 if (cmp < 0) hi = m - 1; 085 else if (cmp > 0) lo = m + 1; 086 else return m; 087 } 088 return lo; 089 } 090 091 092 // Search for key. Update value if found; grow table if new. 093 public void put(K key, V val) { 094 if (val == null) { delete(key); return; } 095 096 int i = rank(key); 097 098 // key is already in table 099 if (i < N && keys[i].compareTo(key) == 0) { 100 vals[i] = val; 101 return; 102 } 103 104 // insert new key-value pair 105 if (N == keys.length) resize(2*keys.length); 106 107 for (int j = N; j > i; j--) { 108 keys[j] = keys[j-1]; 109 vals[j] = vals[j-1]; 110 } 111 keys[i] = key; 112 vals[i] = val; 113 N++; 114 115 //assert check(); 116 } 117 118 119 // Remove the key-value pair if present 120 public void delete(K key) { 121 if (isEmpty()) return; 122 123 // compute rank 124 int i = rank(key); 125 126 // key not in table 127 if (i == N || keys[i].compareTo(key) != 0) { 128 return; 129 } 130 131 for (int j = i; j < N-1; j++) { 132 keys[j] = keys[j+1]; 133 vals[j] = vals[j+1]; 134 } 135 136 N--; 137 keys[N] = null; // to avoid loitering 138 vals[N] = null; 139 140 // resize if 1/4 full 141 if (N > 0 && N == keys.length/4) resize(keys.length/2); 142 143 //assert check(); 144 } 145 146 // delete the minimum key and its associated value 147 public void deleteMin() { 148 if (isEmpty()) throw new Error("Symbol table underflow error"); 149 delete(min()); 150 } 151 152 // delete the maximum key and its associated value 153 public void deleteMax() { 154 if (isEmpty()) throw new Error("Symbol table underflow error"); 155 delete(max()); 156 } 157 158 159 /* *************************************************************************** 160 * Ordered symbol table methods 161 *****************************************************************************/ 162 public K min() { 163 164 if (isEmpty()) return null; 165 return keys[0]; 166 } 167 168 public K max() { 169 if (isEmpty()) return null; 170 return keys[N-1]; 171 } 172 173 public K select(int k) { 174 if (k < 0 || k >= N) return null; 175 return keys[k]; 176 } 177 178 public K floor(K key) { 179 int i = rank(key); 180 if (i < N && key.compareTo(keys[i]) == 0) return keys[i]; 181 if (i == 0) return null; 182 else return keys[i-1]; 183 } 184 185 public K ceiling(K key) { 186 int i = rank(key); 187 if (i == N) return null; 188 else return keys[i]; 189 } 190 191 public int size(K lo, K hi) { 192 if (lo.compareTo(hi) > 0) return 0; 193 if (contains(hi)) return rank(hi) - rank(lo) + 1; 194 else return rank(hi) - rank(lo); 195 } 196 197 public Iterable<K> keys() { 198 return keys(min(), max()); 199 } 200 201 public Iterable<K> keys(K lo, K hi) { 202 Queue<K> queue = new Queue<>(); 203 if (lo == null && hi == null) return queue; 204 if (lo == null) throw new Error("lo is null in keys()"); 205 if (hi == null) throw new Error("hi is null in keys()"); 206 if (lo.compareTo(hi) > 0) return queue; 207 for (int i = rank(lo); i < rank(hi); i++) 208 queue.enqueue(keys[i]); 209 if (contains(hi)) queue.enqueue(keys[rank(hi)]); 210 return queue; 211 } 212 213 214 /* *************************************************************************** 215 * Check internal invariants 216 *****************************************************************************/ 217 218 private boolean check() { 219 return isSorted() && rankCheck(); 220 } 221 222 // are the items in the array in ascending order? 223 private boolean isSorted() { 224 for (int i = 1; i < size(); i++) 225 if (keys[i].compareTo(keys[i-1]) < 0) return false; 226 return true; 227 } 228 229 // check that rank(select(i)) = i 230 private boolean rankCheck() { 231 for (int i = 0; i < size(); i++) 232 if (i != rank(select(i))) return false; 233 for (int i = 0; i < size(); i++) 234 if (keys[i].compareTo(select(rank(keys[i]))) != 0) return false; 235 return true; 236 } 237 238 239 /* *************************************************************************** 240 * Test client 241 *****************************************************************************/ 242 public static void main(String[] args) { 243 StdIn.fromFile("data/tiny.txt"); 244 245 BinarySearchST<String, Integer> st = new BinarySearchST<>(); 246 for (int i = 0; !StdIn.isEmpty(); i++) { 247 String key = StdIn.readString(); 248 st.put(key, i); 249 } 250 for (String s : st.keys()) 251 StdOut.println(s + " " + st.get(s)); 252 } 253}