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