class CompactHashSet extends java.util.AbstractSet<E> {

  @Override
  public boolean add(Object o) {
    if (o == null) o = nullObject;

    int hash = o.hashCode();
    int index = (hash & 0x7FFFFFFF) % objects.length;
    int offset = 1;
    int deletedix = -1;
    
    // search for the object (continue while !null and !this object)
    while(objects[index] != null &&
          !(objects[index].hashCode() == hash &&
            objects[index].equals(o))) {

      // if there's a deleted object here we can put this object here,
      // provided it's not in here somewhere else already
      if (objects[index] == deletedObject)
        deletedix = index;
      
      index = ((index + offset) & 0x7FFFFFFF) % objects.length;
      offset = offset*2 + 1;

      if (offset == -1)
        offset = 2;
    }
    
    if (objects[index] == null) { // wasn't present already
      if (deletedix != -1) // reusing a deleted cell
        index = deletedix;
      else
        freecells--;

      modCount++;
      elements++;

      // here we face a problem regarding generics:
      // add(E o) is not possible because of the null Object. We cant do 'new E()' or '(E) new Object()'
      // so adding an empty object is a problem here
      // If (! o instanceof E) : This will cause a class cast exception
      // If (o instanceof E) : This will work fine

      objects[index] = (E) o;
      
      // do we need to rehash?
      if (1 - (freecells / (double) objects.length) > LOAD_FACTOR)
        rehash();
      return true;
    } else // was there already 
      return false;
  }

  public  CompactHashSet();
  public  CompactHashSet(int size);
  public  CompactHashSet(Collection<E> c);

}