import java.util.HashSet;
import java.util.ArrayList;
import java.util.Collection;

class Position
{
    public Position( int r, int c )
    {
        row = r;
        col = c;
    }

    public boolean equals( Object other )
    {
      //  System.out.println( "INVOKING equals" );
        if( !( other instanceof Position ) )
            return false;
        
        Position rhs = (Position) other;
        return row == rhs.row && col == rhs.col;
    }

    public int hashCode( )
    {
        return row + 136 * col;
    }

    public String toString( )
    {
        return "(" + row + "," + col + ")";
    }

    private int row;
    private int col;
}

class MyHashSet<AnyType>
{
    public MyHashSet( )
    {
        theLists = new Node[ 1024 ];
        theSize = 0;
    }

    /*
    public MyHashSet( int capacity )
    {
        theLists = new Node[ capacity ];
        theSize = 0;
    }
     * */

    public int size( )
    {
        return theSize;
    }

    public boolean isEmpty( )
    {
        return size( ) == 0;
    }

    public boolean contains( AnyType x )
    {
        return findNode( theLists[ myHashCode( x ) ], x ) != null;
    }

    final private Node<AnyType> findNode( Node<AnyType> p, AnyType x )
    {
        while( p != null && !p.data.equals( x ) )
            p = p.next;

        return p;
    }

    // Create a new table; appx 2x original
    // move all elements over
    private void rehash( )
    {
        Node<AnyType> [ ] old = theLists;
        theLists = new Node[ theLists.length * 2 ];

        theSize = 0;
        for( Node<AnyType> list : old )
            for( Node<AnyType> p = list; p != null; p = p.next )
                add( p.data );
    }

    public boolean add( AnyType x )
    {
        if( theSize >= theLists.length )
            rehash( );

        int whichList = myHashCode( x );

        if( contains( x ) )
            return false;

        theLists[ whichList ] = new Node<AnyType>( x, theLists[ whichList ] );
        theSize++;
        return true;
    }

    final private int myHashCode( AnyType x )
    {
        return x.hashCode( ) & ( theLists.length - 1 );
    }

    public String toString( )
    {
        StringBuilder sb = new StringBuilder( "[ " );

        for( Node<AnyType> list : theLists )
        {
            for( Node<AnyType> p = list; p != null; p = p.next )
                sb.append( p.data + " " );
        }

        sb.append( "]" );

        return new String( sb );
    }


    private static class Node<AnyType>
    {
        public Node( AnyType d, Node<AnyType> n )
        { data = d; next = n; }

        AnyType data;
        Node<AnyType> next;
    }

    private Node<AnyType> [ ] theLists;  // the length is always a power of 2
    private int theSize;
}

class HashDemo
{
    public static void main( String [ ] args )
    {
        MyHashSet<Position> c = new MyHashSet<Position>( );
        final int N = 1000;

        long start = System.currentTimeMillis( );
        for( int i = 0; i < N; i++ )
            for( int j = 0; j < N; j++ )
                c.add( new Position( i, j ) );
        long end = System.currentTimeMillis( );

        System.out.println( c.size( ) );
        System.out.println( c.contains( new Position( 0, N-1 ) ) );
        System.out.println( "Elapsed time is: " + ( end - start ) );
        
    }
}