// CuckooHashing.  Our h1 and h2 are compressions of hashCode(), so
// this fails if we have, e.g., three keys with the same hashCode.

import java.util.Random;        // random number generator (sets h1, h2)

class CuckooHash implements Set
{
    protected Object[] array;   // array[h] is an item, or null
    protected int size = 0;     // number of items stored overall
    protected Random gen;       // RNG for computing new hash functions

    // Constructor: sets the initial array size.
    // Optionally let the user specify a random number generator.
    public CuckooHash() { this(new Random()); }
    public CuckooHash(Random g) { array = new Object[17]; gen = g; }

    // Generic MAD hashing: ((int)(code*mul+add)) mod array.length
    protected int mad(int code, int mul, int add) {
        int len = array.length, rem = (code * mul + add) % len;
        return rem<0 ? rem+len : rem; // fix sign if necessary
    }
    // Our two hash functions are both based on x.hashCode().
    protected int mul1=1, add1=0, mul2=65537, add2=1234567;
    protected int h1(Object x) { return mad(x.hashCode(), mul1, add1); }
    protected int h2(Object x) { return mad(x.hashCode(), mul2, add2); }

    // Euclid's gcd:
    protected int gcd(int a, int b) { return b==0 ? a : gcd(b, a%b); }

    protected int rebuildCount = 0;
    void rebuild(int newLen) {
        // Redefine our two hash functions, using the RNG.
        add1 = gen.nextInt(newLen);
        add2 = gen.nextInt(newLen);
        do { mul1 = 1+2*gen.nextInt(newLen); } while (gcd(mul1, newLen)>1);
        do { mul2 = 1+2*gen.nextInt(newLen); } while (gcd(mul2, newLen)>1);
        System.err.printf("Rebuild to %d (size=%d m1=%d a1=%d m2=%d a2=%d)\n",
                          newLen, size, mul1, add1, mul2, add2);
        if (++rebuildCount >= 50)
            throw new RuntimeException("Too many rebuilds!");
        Object[] oldArray = array;
        array = new Object[newLen];
        // Now populate the new array from oldArray.
        // Although rare, this could recurse!
        size = 0;
        for (Object x: oldArray) if (x != null) add(x);
    }

    // Implement the Set interface.
    public int size() { return size; }

    public Object find(Object x) {
        Object o = array[h1(x)];
        if (o!=null && x.equals(o)) return o;
        o = array[h2(x)];
        if (o!=null && x.equals(o)) return o;
        return null;
    }

    public boolean add(Object x) {
        if (find(x)!=null) return false;
        int h=h1(x);
        // Note x changes inside this loop: it is always the object we
        // currently want to (re)insert, at position h.
        for (int i=0; i<=size; ++i) {
            Object y = array[h];
            array[h] = x;
            if (y==null) { ++size; return true; }
            x = y;
            h = h1(x)+h2(x)-h;
        }
        // Rebuild, growing array (a lot if dense, else just a bit).
        int len = array.length;
	rebuild(4*size>len ? 2*len : len+1); // many variations possible
        return add(x);
    }

    public boolean remove(Object x) {
        int h = h1(x);
        if (x.equals(array[h])) { array[h]=null; --size; return true; }
        h = h2(x);
        if (x.equals(array[h])) { array[h]=null; --size; return true; }
        return false;
    }
}