/************************************************************************
 * This library is free software; you can redistribute it and/or        *
 * modify it under the terms of the GNU Library General Public          *
 * License as published by the Free Software Foundation; either         *
 * version 2 of the License, or (at your option) any later version.     *
 *                                                                      *
 * This library is distributed in the hope that it will be useful,      *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of       *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU    *
 * Library General Public License for more details.                     *
 *                                                                      *
 * You should have received a copy of the GNU Library General Public    *
 * License along with this library; if not, write to the                *
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,         *
 * Boston, MA  02111-1307, USA.                                         *
 *                                                                      *
 * The GNU Library General Public License file is included in           *
 * Online-Documentation                                                 *
 *                                                                      *
 * GNU's Homepage - http://www.gnu.org/                                 *
 *                                                                      *
 * Questions & comments referring to Hexi: please contact us:           *
 *                                                                      *
 * eMail:                                                               *
 *      ramsey@dbai.tuwien.ac.at                                        *
 * WWW:                                                                 *
 *      http://www.dbai.tuwien.ac.at/proj/ramsey/                       *
 *                                                                      *
 * (c) Wolfgang Slany 1987, Bidan Zhu 1996, Andreas Beer 1999           *
 * HexiUtility.java               Version 2.1                14.07.1999 *
 ***********************************************************************/

import java.io.*;

public class HexiUtility
{
	final static byte ptc1[] = {0,0,0,0,0,1,1,1,1,2,2,2,3,3,4};
	final static byte ptc2[] = {1,2,3,4,5,2,3,4,5,3,4,5,4,5,5};
	final static byte pt_to_edge[][] = { {0,0,1,2,3,4},{0,0,5,6,7,8},{1,5,0,9,10,11},{2,6,9,0,12,13},{3,7,10,12,0,14},{4,8,11,13,14,0} };
	byte new_posi[]  = new byte[15];
	byte best_now[]  = new byte[15];
	byte perm[]      = new byte[6];
	Hexi hexi;

	public HexiUtility ( Hexi parent )
	{
		hexi = parent ;
	}

	public byte whowins ( byte position[], byte me )
	{
		byte who;

		if (me == 0) who = hexi.winner[0][hash (pack(normalize(position)),me)];
		else who = hexi.winner[me][hash (pack(normalize(position)),me)];
		if (who == 0) return 1;
		else if (who != 127) return 2;
		else
		{
			System.out.println ("********************** 0 **************************");
			return 0;
		}
	}

	public byte[] normalize(byte position[])
	{
		byte normed[] = new byte[15];
		byte weight[];
		byte paar[][][];
		byte j;
		weight = weigh(position);
		paar   = paar(weight);

		for ( j=0;j<15;j++ ) best_now[j] = 2;
		perm_paar (position,(byte)0,(byte)0,paar);
		for ( j=0;j<15;j++ ) normed[j] = best_now[j];
		return normed;
	} // normalize

	public byte[] weigh( byte position[] )
	{
		byte ordner[] = new byte[6];
		byte who,i,j; //  is 1 or 2 ?

		for ( i = 0; i<6; i++ )
		{
 			for ( j = 0; j<6; j++ ) if ( j != i )
			{
				who = position[pt_to_edge[i][j]];
				if  (who == 2 ) ordner[i] += (byte)8;
				else ordner[i] += who;
			}
			ordner[i] ++ ;
		}
		return ordner; //  return the points with weight
  	} // weigh

	public byte[] sort ( byte ord[] )
	{
		byte sorted[] = new byte[6];
		byte trans,i;

		for ( i=0;i<6;i++ ) sorted[i] = ord[i];
		boolean not_finish = true;
		while ( not_finish )
		{
			not_finish = false;
			for ( i = 0 ; i<5 ; i++ ) if ( sorted[i] > sorted[i+1] )
			{
				trans = sorted[i] ; sorted[i] = sorted[i+1] ; sorted[i+1] = trans;
				not_finish = true;
			}
		}
		return sorted;
 	} // sort

	public byte[][][] paar ( byte ordner[] )
	{
		byte paar_num  = 0;
		byte num_every = 1;
		byte order,i,j;
		byte sorted[]  = new byte[6];
		byte ready[]   = new byte[6];
		byte num[]     = new byte[6];
		byte help[][][]  = new byte[6][6][2];

		sorted = sort(ordner);
		for ( i=0;i<6;i++ ) if ( ready[i] == 0 )
		{
			order = 0;
			while ( ordner[i] != sorted[order] ) order++;
			num_every = 0;
			for ( j=i;j<6;j++ ) if ( ordner[i] == ordner[j] )
			{
				help[paar_num][num_every][0] = j;
				help[paar_num][num_every][1] = (byte)(order + num_every++);
				ready[j] = 1;
			}
			num[paar_num++] = num_every;
		}
		byte paar[][][] = new byte[paar_num][][];
		for ( i=0;i<paar_num;i++ )
		{
			paar[i] = new byte[num[i]][2];
			for ( j=0;j<num[i];j++ ) paar[i][j] = help[i][j];
		}
		return paar;
	} // paar

	public void perm_paar (byte position[],byte paar_num,byte num_every,byte paar[][][] )
	{
		boolean already,stop;
		byte num,i,j;

		for ( i=0; i<paar[paar_num].length;i++ )
		{
			already = false;
			num = (byte)(num_every-1);
			while ( !already && num > -1 ) if ( perm[paar[paar_num][num--][0]] == paar[paar_num][i][1] ) already = true;
			if ( !already )
			{
				perm[paar[paar_num][num_every][0]] = paar[paar_num][i][1];
				if ( num_every != paar[paar_num].length-1 ) perm_paar (position,paar_num,(byte)(num_every+1),paar);
				else if ( paar_num != paar.length-1 ) perm_paar (position,(byte)(paar_num+1),(byte)0,paar);
				else
				{
					// The last paar scope and the last element of the paar ==> exit
					for ( j=0;j<15;j++ ) new_posi[pt_to_edge[perm[ptc1[j]]][perm[ptc2[j]]]] = position[j];
					num = 0;
					stop = false;
 					while ( !stop && num<15 ) if (best_now[num] != new_posi[num]) stop = true;
					else num++;
					if ( stop && best_now[num] > new_posi[num] ) for ( j=num;j<15;j++ )best_now[j] = new_posi[j];
				}
			}
		}
	} // perm_paar

	public static byte is_triangle (byte position[], byte newdraw , byte who )
	{
		byte p1 = ptc1[newdraw];
		byte p2 = ptc2[newdraw];
		for ( byte i=0;i<6;i++ ) if ( i!=p1 && i!=p2 && position[pt_to_edge[i][p1]]==who &&position[pt_to_edge[i][p2]]==who) return i;
		return -1;
	} // is_triangle

	public byte max_random (int evaluation[] )
	{
		byte max_num = 0;
		byte max_index[] = new byte[15];
		byte max_Random;
		int  max = evaluation[0];

		for ( byte i=1;i<15;i++ ) if ( evaluation[i] > max ) max = evaluation[i];
		for ( byte i=0;i<15;i++ ) if ( evaluation[i] == max ) max_index[max_num++] = i;
		max_Random = (byte)(Math.random() * max_num);
		return max_index[max_Random];
	}

	public byte[] pack ( byte position[] )
	{
		byte packed[] = new byte[3];
		int  sum=0,i;

		for ( i=0;i<15;i++ )  sum = sum*3 + position[i];
		i = sum / 65536; packed[0] = (byte)(i-128); // 2^16 = 65536
		sum =  sum % 65536;
		i = sum / 256 ;
		packed[1] = (byte)(i-128); // 2^8 = 256
		i = sum % 256;
		packed[2] = (byte)(i-128);
		return packed;
	} // pack

	public int hash ( byte p[], byte who)
	{
		int key2 = 0;
		int shift, size;
		byte k1,k2,k3;
		int h0,h1,h2;
		boolean found;
		byte packed[];

		if (p.length == 15) packed = pack(normalize(p));
		else packed = p;
		h0 = packed[0]+128;
		h1 = packed[1]+128;
		h2 = packed[2]+128;
		if (who == 0)
		{
 			shift = 4; size = 4096;
		}
		else
		{
			shift = 5; size = 8192;
		}
		int key = ((h0 ^ h1) << shift ) ^ h2;
		while (true)
		{
			if (who == 0)
			{
				found = (hexi.winner[0][key] != 127);
				k1 = hexi.hashkey1[0][key];
				k2 = hexi.hashkey1[1][key];
				k3 = hexi.hashkey1[2][key];
			}
			else
			{
				found  = (hexi.winner[1][key] != 127 || hexi.winner[2][key] != 127);
				k1 = hexi.hashkey2[0][key];
				k2 = hexi.hashkey2[1][key];
				k3 = hexi.hashkey2[2][key];
			}
			if (found) if (k1 == packed[0] && k2 == packed[1] && k3 == packed[2]) break;
			else
			{
				// collision
				if (key2 == 0)	key2 = ( (h1 << shift) ^ h0 ^ h2) | 1;
				key += key2;
				if (key >= size) key -= size;
			}
			else break;
		}
		return key ;
	} // hash

	public byte Tree_Expand1 (byte position[], byte player, byte opponent, byte edge)
	{
		byte dup_pos[] = new byte[15];
		byte who_win,i,packed_position[];
		int  key;
		byte w;
		boolean playerwin = false, opponentwin = false;

		for (i=0;i<15;i++) dup_pos[i] = position[i];
		dup_pos[edge] = player; // make the move
		packed_position = pack(normalize(dup_pos));
		key = hash(packed_position,player);
		if ( (w = hexi.winner[player][key]) != 127) return (byte)(w+1);
		for (i=0;i<15;i++) if (dup_pos[i] == 0)
		{
			if (is_triangle(dup_pos,i,player) == -1 && Tree_Expand1(dup_pos,player,opponent,i) == player) playerwin = true;
			if (is_triangle(dup_pos,i,opponent) == -1 && Tree_Expand1(dup_pos,opponent,player,i) == opponent) opponentwin = true;
		}
		if (opponentwin && !playerwin) who_win = opponent;
		else who_win = player;
		key = hash(packed_position,player);
		hexi.winner[player][key] = (byte)(who_win-1);
		hexi.hashkey2[0][key]	= packed_position[0];
 		hexi.hashkey2[1][key]	= packed_position[1];
		hexi.hashkey2[2][key]	= packed_position[2];
		return	who_win;
	} // Tree_Expand1

	public byte Tree_Expand2 (byte position[], byte player, byte opponent, byte edge)
	{
		byte dup_pos[] = new byte[15];
		byte who_win,i,packed_position[];
		int  key;

		for (i=0;i<15;i++) dup_pos[i] = position[i];
		dup_pos[edge] = player;
		dup_pos = normalize(dup_pos);
		packed_position = pack(dup_pos);
		key = hash(packed_position,(byte)0);
		if  ( hexi.winner[0][key]!=127 ) return (byte)(hexi.winner[0][key]+1);
		who_win = player;
		for (i=0;i<15;i++)
			if( dup_pos[i] == 0 && is_triangle(dup_pos,i,opponent) == -1 && Tree_Expand2(dup_pos,opponent,player,i) == opponent )
				who_win= opponent;
		key = hash(packed_position,(byte)0);
		hexi.winner[0][key]		= (byte)(who_win-1);
		hexi.hashkey1[0][key]	= packed_position[0];
 		hexi.hashkey1[1][key]	= packed_position[1];
		hexi.hashkey1[2][key]	= packed_position[2];
		return	who_win;
	} // Tree_Expand2

	public int Heuristic (byte position[],byte me, byte he )
	{
		byte n[] = new byte[15];
  		int  w,I_win=0, he_win=0;
		byte k;

		for (k=0;k<15;k++) n[k] = position[k];
		for (k=0;k<15;k++ ) if (n[k] == 0)
		{
			if (is_triangle(n,k,he) != -1) 	I_win++;
			else
			{
				n[k] = he;
				if (whowins(n,hexi.Allow_More?he:0) == me)  I_win++;
				else he_win++;
				n[k] = 0;
			}
		}
		int h = 100*(I_win-he_win)/(I_win+he_win);
//		System.out.print("I: "+I_win+" He: "+he_win+"    "+h);
//		if ( h < 1 ) h = 1 ;
		return h ;
	} // Heuristic

} // end of class winner definition