/*
* hash queue
*
* @see	ox.java desk.java
* @version    2.2, 16.06.2003
* @autor	Zbigniew Lisiecki, zbyszek@evot.org
*
*/
/******************************************************************
	This is a (general purpose) hash table
	The idea is from B.Stroustrup The C++ Programming Language
*******************************************************************/

public class hqueue extends desk {
	public	static int errval = Integer.MAX_VALUE;
	public	static final int maxply = 128;
	public	static boolean hdebug = false;
	public	static int hsize = 256;		// hash table size
	public	static int maxram = 128 * 1024 * 1024;
	public	static int ram;			// RAM currently used
			static int n;			// number of elements
			int	val;				// desk position value
			int	hcode;	
			hqueue	next;
			hqueue	hd[][];

	public hqueue(boolean init) {
		if (init) {
			ram = 0;
			n = 0;
			hd = new hqueue[maxply][hsize];
		}
	}
	protected int hashcode (desk d) {	// from Bjarne p.80
		int code = 0;
		for (int i = 0; i < d.xsize; i++)
		for (int j = 0; j < d.ysize; j++) {
			if (d.board[i][j] == white || d.board[i][j] == black ) {
				code <<= 1;
				code ^= i * j;
			}
		}
		if (code < 0)	code = -code;
		code %= hsize;
		return (code);
	}
	protected int ply (desk d) {
		int p = 0;
		for (int i = 0; i < d.xsize; i++)
		for (int j = 0; j < d.ysize; j++) {
			if (d.board[i][j] != empty) {
				p++;
			}
		}
		return (p);
	}
	protected boolean compare (desk d1, desk d2) {
		for (int i = 0; i < d1.xsize; i++)
		for (int j = 0; j < d1.ysize; j++) {
			if (d1.board[i][j] != d2.board[i][j])
				return (false);
		}
		return (true);
	}
	public int get (desk d) {
		int	code = hashcode (d);
		int	p = ply (d);
		if (hdebug) {
			System.out.print ("get:try ["+code+"]	");
			d.out (1);
		}
		if (p >= maxply) {
			System.out.println ("hqueue: maxply exceeded " + p);
			return (errval);
		}
		for (hqueue t = hd[p][code]; t != null; t = t.next) {
			if (compare (t, d)) {
				if (hdebug) {
					System.out.println ("got it: ["+code+"]	"+t.val);
					t.out (1);
				}
				return (t.val);
			}
		}
		return (errval);
	}
	/* This is get and insert together:
	 * insert if not found
	*/
	public boolean insert (desk d, int val) {
		int code = hashcode (d);
		int	p = ply (d);
		if (p >= maxply) {
			System.out.println ("hqueue: maxply exceeded " + p);
			return (false);
		}
/*
* it is a program error if the desk to insert is already in the queue
* we can spare this search here

		for (hqueue t = hd[p][code]; t != null; t = t.next) {
			if (compare (t, d) == true) {
				return (false);
			}
		}
*/
		ram += 8 + d.xsize * d.ysize + 24;		// find better solu.
		if (ram > maxram) {
			System.out.println ("hqueue: not enough RAM");
			return (false);
		}
		hqueue	h = new hqueue (false);
		for (int i = 0; i < d.xsize; i++)
		for (int j = 0; j < d.ysize; j++)
			h.board[i][j] = d.board[i][j];
		h.val = val;
		h.next = hd[p][code];
		hd[p][code] = h;
		n++;
		if (hdebug) {
			System.out.print ("insert: ["+code+"]	"+
			" val="+val+" n="+n+ " ");
			d.out (1);
		}
		return (true);
	}
}