/*
* hash queue
*
* @see	ox.java game.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 game {
	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;				// game 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 (game 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 (game 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 (game d1, game 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 (game 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 (game 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 game 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);
	}
}