001package algs35;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac IndexSET.java
005 *  Execution:    java IndexSET
006 *  Dependencies: ST.java
007 *
008 *  Indexed set. Assigns an integer index to each new element.
009 *
010 *  Remarks
011 *  -------
012 *   - could use generic array for ts
013 *
014 *  % java IndexSET
015 *
016 *************************************************************************/
017
018public class XIndexSET<K extends Comparable<? super K>> {
019        private int N;
020        private final ST<K, Integer> st = new ST<>();
021        private final ST<Integer, K> ts = new ST<>();
022
023        public void add(K key) {
024                if (!st.contains(key)) {
025                        st.put(key, N);
026                        ts.put(N, key);
027                        N++;
028                }
029        }
030
031        public int indexOf(K key) {
032                return st.get(key);
033        }
034
035        public K keyOf(int index) {
036                return ts.get(index);
037        }
038
039        public boolean contains(K key) { return st.contains(key);  }
040        public int size()              { return st.size();         }
041        public Iterable<K> keys()      { return st.keys();         }
042
043
044        /* *********************************************************************
045         * Test routine.
046         **********************************************************************/
047        public static void main(String[] args) {
048                XIndexSET<String> set = new XIndexSET<>();
049
050                // insert some keys
051                set.add("www.cs.princeton.edu");
052                set.add("www.princeton.edu");
053                set.add("www.yale.edu");
054                set.add("www.amazon.com");
055                set.add("www.simpsons.com");
056
057                // does given key exist?
058                StdOut.println(set.contains("www.cs.princeton.edu"));
059                StdOut.println(set.contains("www.amazon.com"));
060                StdOut.println(!set.contains("www.amazon.edu"));
061                StdOut.println();
062
063                // print out all keys in the set
064                for (String s : set.keys()) {
065                        StdOut.println(s + " : " + set.indexOf(s));
066                }
067
068        }
069
070}
071