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}