01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package algs35;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac IndexSET.java
 *  Execution:    java IndexSET
 *  Dependencies: ST.java
 *
 *  Indexed set. Assigns an integer index to each new element.
 *
 *  Remarks
 *  -------
 *   - could use generic array for ts
 *
 *  % java IndexSET
 *
 *************************************************************************/

public class XIndexSET<K extends Comparable<? super K>> {
  private int N;
  private final ST<K, Integer> st = new ST<>();
  private final ST<Integer, K> ts = new ST<>();

  public void add(K key) {
    if (!st.contains(key)) {
      st.put(key, N);
      ts.put(N, key);
      N++;
    }
  }

  public int indexOf(K key) {
    return st.get(key);
  }

  public K keyOf(int index) {
    return ts.get(index);
  }

  public boolean contains(K key) { return st.contains(key);  }
  public int size()              { return st.size();         }
  public Iterable<K> keys()      { return st.keys();         }


  /* *********************************************************************
   * Test routine.
   **********************************************************************/
  public static void main(String[] args) {
    XIndexSET<String> set = new XIndexSET<>();

    // insert some keys
    set.add("www.cs.princeton.edu");
    set.add("www.princeton.edu");
    set.add("www.yale.edu");
    set.add("www.amazon.com");
    set.add("www.simpsons.com");

    // does given key exist?
    StdOut.println(set.contains("www.cs.princeton.edu"));
    StdOut.println(set.contains("www.amazon.com"));
    StdOut.println(!set.contains("www.amazon.edu"));
    StdOut.println();

    // print out all keys in the set
    for (String s : set.keys()) {
      StdOut.println(s + " : " + set.indexOf(s));
    }

  }

}