import java.lang.*;

public class HashDictionary implements LocatorDictionary {
	public int size;
	int M;
	public Position[] table;
	IntegerComparator ic;
	StringComparator sc;

	public HashDictionary(Comparator c) {
		ic = (IntegerComparator) c;
		sc = new StringComparator();
		M = 10007;		/* Total size of Hash table */
		table = new Node[M];
		size = 0;
	}

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

 	public Position find(Object k) {
		Integer key = new Integer(formkey(k));
		int intkey = key.intValue();
		String elem = formelem(k);
		int hcode = hfunction(intkey);	/* Compute hash code */
		int gvalue = Math.max(1,gfunction(intkey));

		while(table[hcode]!=null) {
		  if(ic.isEqualTo(key,((Item)table[hcode].element()).key()) &&
		    sc.isEqualTo(elem,((Item)table[hcode].element()).element()))
			    return table[hcode];
		  hcode+=gvalue;
		  if(hcode>=M)
		     hcode %= M;
		}
		return null;
	}

 	public Position insert(Object k, Object o) {
		if(size>=M)	/* The hash table is full */
		  return null;	
		int key = ((Integer)k).intValue();
		int hcode = hfunction(key);
		int gvalue = Math.max(1,gfunction(key));

		int pos = getFreePosition( hcode, gvalue );
		if(table[pos]==null) 
		  table[pos] = new Node(new Item(k,o), null, null, null, null); 
		else {
		  Item item = (Item) table[pos].element();
		  item.setKey(k);
		  item.setElement(o);
		} 
		size++;
		return table[pos];
	}

	public int getFreePosition(int hcode, int key) {
		if( table[hcode] == null)
			return hcode;
		else if( ic.isEqualTo( ((Item)table[hcode].element()).key(), 
				      new Integer(-1) ) )
			return hcode;
		return getFreePosition( (hcode+key)%M, key);
	}

 	public Object remove(Position p) {
		Item item = (Item) p.element();	
		item.setKey(new Integer(-1));
		size--;
		return item.element();
	}

	public int hfunction(int x) {
		return x%M;
	}

	public int gfunction(int x) {
		return (x/M) % M;
	}

	public int formkey(Object o) {
		Board b = (Board) o;
		int key = 0;
		for(int i=0; i<4; i++)
		  for(int j=0; j<4; j++)
			key += b.PuzzBoard[i][j]*(i*4+j);
		return key;
 	}	

	public String formelem(Object o) {
		Board b = (Board) o;
		String strkey = "";
           	for(int i=0; i<4; i++)
                   for(int j=0; j<4; j++)
                        strkey += Integer.toHexString(b.PuzzBoard[i][j]);
           	return strkey;
   	}

}