import java.util.*;

// This is a simple linear-probing hash table.
public class HashSet extends AbstractSet implements Set{
  private final static Object SKIP = new Object();
  Object[] buckets;
  int size;
  final int capacity;
  
  // This counts modifications to the hashtable so the iterator can abort
  // if somebody changes it while we're iterating.
  private int modCount = 0;

  public HashSet(int capacity) {
    buckets = new Object[capacity];
    size = 0; this.capacity = capacity;
  }
  public HashSet() {
    this(10);
  }

  // This is required by AbstractCollection, but it provides an isEmpty
  // method.
  public int size() {
    return size;
  }
  public void clear() {
    Arrays.fill(buckets, null);
    size = 0;
  }
  private int hash(int hashcode, int iteration) {
    return (hashcode + iteration) % capacity; // linear probing
    // Quadratic probing:
    //   return (hashcode + iteration*iteration) % capacity;
    // Double hashing:
    //   return (hashcode + i * f(hashcode)) % capacity;
  }
  
  public boolean add(Object o) {
    if (o == null) throw new NullPointerException("nulls disallowed");
    if (size == capacity)
      throw new RuntimeException("hash table full");
    for (int i = 0; i < buckets.length; i++) {
      int attempt = hash(o.hashCode(), i);
      
      // If we find the object already there, stop now
      if (o.equals(buckets[attempt])) return false; // no dups
      
      // If a bucket is empty or SKIP, we can put the object here
      if (buckets[attempt] == null || buckets[attempt] == SKIP) {
        buckets[attempt] = o; size++; modCount++; return true;
      }
      
      // Otherwise we found another object, so probe again
    }
    return false;
  }
  
  public boolean remove(Object o) {
    if (o == null) return false;
    for (int i = 0; i < buckets.length; i++) {
      int attempt = hash(o.hashCode(), i);
      
      // If we find an empty bucket, the object isn't here
      if (buckets[attempt] == null) return false;
      
      // If we find the object, replace it with SKIP
      if (o.equals(buckets[attempt])) {
        buckets[attempt] = SKIP; size--; modCount++; return true;
      }
      
      // Otherwise we found something else, so probe again
    }
    return false;
  }
  
  public boolean contains(Object o) {
    if (o == null) return false;
    for (int i = 0; i < buckets.length; i++) {
      int attempt = hash(o.hashCode(), i);
      
      // If we find the object, we're done
      if (o.equals(buckets[attempt])) return true;
      
      // If the bucket is empty, the object isn't here
      if (buckets[attempt] == null) return false;
      
      // Otherwise we found something else, so probe again
    }
    return false;
  }
  
  public Iterator iterator() { // required by AbstractCollection
    return new Iterator() {
      private int expectedModCount = modCount;
      // currentPos points to the current bucket; at each call to next(), we
      // increment currentPos until we find another used bucket, so currentPos
      // should initially be -1.
      private int currentPos = -1;

      public boolean hasNext() {
        // Start at currentPos+1 and look for a used bucket.
        for (int attempt = currentPos + 1; attempt < buckets.length; attempt++) {
          if (buckets[attempt] != null && buckets[attempt] != SKIP)
            return true;
        }
        return false;
      }
      public Object next() {
        // Make sure nothing changed while we weren't looking.
        if (modCount != expectedModCount)
          throw new ConcurrentModificationException();
        // Increment currentPos until we find another used bucket.
        for (currentPos++; currentPos < buckets.length; currentPos++) {
          if (buckets[currentPos] != null && buckets[currentPos] != SKIP)
            return buckets[currentPos];
        }
        throw new NoSuchElementException();
      }
      public void remove() {
        // Make sure nothing changed while we weren't looking.
        if (modCount != expectedModCount)
          throw new ConcurrentModificationException();
        // Make sure we're pointing to a valid bucket, and then put SKIP there.
        if (currentPos == -1 || buckets[currentPos] == SKIP)
          throw new IllegalStateException();
        buckets[currentPos] = SKIP;
        // We made a change...
        modCount++; expectedModCount++;
      }
    };
  }
}