//
//
// alternative version based on Hashtable,
// scales much better (linear instead of quadratic, O(n) vs O(n^2))
//
//

import java.util.*;

public final class Set3 {

  private Hashtable items;

  private int hashCode = 17;

  public Set3() { items = new Hashtable();}
  public Set3(int size) { items = new Hashtable(size);}

  public int cardinality() { return items.size(); }

  public boolean isEmptySet() { return items.isEmpty();}

  public boolean addItem(Object o) {

    if (items.put(o,o) == null) { // was new
      hashCode += o.hashCode();
      return true;
    } else {
      return false;
    }
  }

  public boolean containsItem(Object o) {

    return items.containsKey(o);

  }

  public boolean removeItem(Object o) {

    if (items.remove(o) != null) { // was there
      hashCode -= o.hashCode();
      return true;
    } else {
      return false;
    }
  }

  public int hashCode() { return hashCode;}

  public boolean equals(Object o) {

    if (this == o) return true;
    if (o == null) return false;
    if (!(o instanceof Set3)) return false;
    if (hashCode != o.hashCode()) return false;
    Set3 s = (Set3) o;
    if (cardinality() != s.cardinality()) return false;
    Enumeration myKeys = items.keys();
    while (myKeys.hasMoreElements()) 
      if (!s.containsItem(myKeys.nextElement())) return false;
    return true;
  }


  public static void main(String[] args) {

    int n = 10;
    int different = -1;

    if (args.length >= 1)
      n = Integer.parseInt(args[0]);
    if (args.length >= 2)
      different = Integer.parseInt(args[1]);

    long time0 = System.currentTimeMillis();

    Set3 s0 = makeSet(n);
    Set3 s1 = makeSet(n);
    if (different > -1) {
      s1.removeItem(new Integer(different));
      s1.addItem(new Integer(-1));
    }

    long time1 = System.currentTimeMillis();

    boolean eq0 = s0.equals(s1);
    boolean eq1 = s1.equals(s0);

    long time2 = System.currentTimeMillis();

    System.out.println("s0.equals(s1) = " + eq0);
    System.out.println("s1.equals(s0) = " + eq1);
    System.out.println("s0.hashCode() = " + s0.hashCode());
    System.out.println("s1.hashCode() = " + s1.hashCode());
    System.out.println("t0 = " + (time1-time0) + " / t1 = " + (time2-time1));
  }

  public static Set3 makeSet(int max) {

    Set3 s = new Set3(2*max);
    for(int i = 0; i<max; i++) 
      s.addItem(new Integer(i));
    return s;
  }
}