/*
 * Turnablock.java
 *      The turnablock game
 *      Usage:  <applet code="Turnablock.class width=100 height=100>
 *              </applet>
 *
 * Ken Shirriff         ken.shirriff@eng.sun.com
 *
 * Copyright (c) 1996 Sun Microsystems, Inc. All Rights Reserved.
 *
 * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 *
 * Please refer to the file "license.txt"
 * for further important copyright and licensing information.
 */

import java.awt.*;
import java.awt.image.*;
import java.applet.Applet;

public class Turnablock extends Applet implements Runnable {
	Color bg = Color.black;
	Color fg = Color.white;
	Thread th;
	int x,y;
	Board board = null;
	Panel toppanel = null;
	Button startButton = null;
	String imgpath = "";
	TextField xf, yf;
	int data[][];
	Image bpic,wpic;
	GridBagLayout topGridbag;
	GridBagConstraints topGc;
	Strategy strategy = null;
	Choice skill;
	Thread thread= null;

	//Initialize everything
	public void init() {
		imgpath = getParameter("img");
		bpic = getImage(getDocumentBase(), getParameter("black_img"));
		wpic = getImage(getDocumentBase(), getParameter("white_img"));
		toppanel = new Panel();
		topGridbag = new GridBagLayout();
		topGc = new GridBagConstraints();
		toppanel.setLayout(topGridbag);
		board = new Board(bpic,wpic);
		constrain(topGridbag, topGc, toppanel, board,
			GridBagConstraints.REMAINDER);
		Label l1 = new Label("Grid size");
		Label l2 = new Label(" ");
		Label l3 = new Label(" ");
		setBackground(bg);
		setForeground(fg);
		xf = new TextField("3");
		yf = new TextField("3");
		skill = new Choice();
		skill.addItem("Easy");
		skill.addItem("Hard");
		startButton = new Button("restart");
		topGc.weightx=0;
		constrain(topGridbag, topGc, toppanel, l1, 1);
		constrain(topGridbag, topGc, toppanel, xf, 1);
		constrain(topGridbag, topGc, toppanel, yf, 1);
		constrain(topGridbag, topGc, toppanel, l2, 1);
		constrain(topGridbag, topGc, toppanel, skill, 1);
		constrain(topGridbag, topGc, toppanel, l3, 1);
		constrain(topGridbag, topGc, toppanel, startButton,
			GridBagConstraints.REMAINDER);
		Panel key = new Panel();
		key.add(new Label("Base:"));
		key.add(new ImgCanvas(20,20,bpic));
		key.add(new Label("   Target:"));
		key.add(new ImgCanvas(20,20,wpic));
		constrain(topGridbag, topGc, toppanel, key,
			GridBagConstraints.REMAINDER);
		add(toppanel);
		restart();
	}

	// Start a new game
	public void restart() {
		x = Integer.parseInt(xf.getText());
		y = Integer.parseInt(yf.getText());
		if (x<3) {
			x=3;
			xf.setText("3");
		} else if (x>8) {
			x=8;
			xf.setText("8");
		}
		if (y<3) {
			y=3;
			yf.setText("3");
		} else if (y>8) {
			y=8;
			yf.setText("8");
		}
		data = new int[x][y];
		board.restart(x,y,data);
		strategy = new Strategy(data,x,y);
		strategy.setSkill(skill.getSelectedIndex());
		layout();
		toppanel.layout();
		if (thread != null) {
			thread.stop();
		}
		thread = new Thread(this);
		thread.start();
	}

	// Helper function for GridBagLayout
        public void constrain(GridBagLayout gridbag, GridBagConstraints gc, Container parent, Component c, int w) {
                gc.gridwidth = w;
                gridbag.setConstraints(c,gc);
                parent.add(c);
        }

	// Test if the board is in a winning position
	public boolean win() {
		for (int i=0;i<x;i++) {
			for (int j=0;j<y;j++) {
				if (data[i][j]==1) {
					return false;
				}
			}
		}
		return true;
	}

	// Make sure the move is not bogus
	public boolean checkmove(Rectangle move) {
		boolean ok = true;
		if (data[move.x][move.y] != 1) {
			System.out.println("Error: piece is not black");
			ok = false;
		}
		if (move.width<1 || move.width>move.x+1 || move.height<1
			|| move.height>move.y+1) {
			System.out.println("Error: bad move region");
			ok = false;
		}
		return ok;
	}

	// Flip the specified rectangle
	void flip(Rectangle mv) {
		for (int i=0;i<mv.width;i++) {
			for (int j=0;j<mv.height;j++) {
				data[mv.x-i][mv.y-j] = 1-data[mv.x-i][mv.y-j];
			}
		}
	}

	// This is the main game loop.
	// It gets a player move, then the machine moves, until someone wins.
	public void run() {
		Rectangle mv;
		while (true) {
			// Wait for player to move
			mv = board.getplayermove();
			// Make sure the move is ok
			if (mv==null || !checkmove(mv)) {
				board.winner(3);
				break;
			}
			// Flip player pieces
			pause(200);
			flip(mv);
			board.repaint();
			pause(500);
			board.highlight(0);
			if (win()) {
				// Player won
				board.winner(2);
				break;
			}
			// Move computer
			pause(500);
			mv =strategy.move();
			// Make sure the move is ok
			if (mv==null || !checkmove(mv)) {
				board.winner(3);
				break;
			}
			board.highlight(1,mv);
			pause(500);
			flip(mv);
			board.repaint();
			pause(500);
			board.highlight(0,mv);
			if (win()) {
				// Computer won
				board.winner(1);
			}
		}
	}

	// Pause for n ms
	public void pause(int n) {
		try {
			Thread.currentThread().sleep(n);
		} catch (InterruptedException e) {}
	}

        public boolean action(Event e, Object o) {
                if (e.target.equals(startButton)) {
			restart();
		}
                return super.action(e,o);
        }

        public boolean handleEvent(Event e) {
		if (e.target.equals(skill)) {
			strategy.setSkill(skill.getSelectedIndex());
		}
		return super.handleEvent(e);
	}

}

// This class manages the game board.
// Its important methods are:
// restart: initialize the board
// getplayermove: get the player's move
// highlight: draw a rectangle around the selected region
// winner: announce a winner
class Board extends Canvas implements ImageObserver {
	int xsize,ysize;
	int xpix,ypix;
	int data[][];
	Image bpic, wpic;
	int sz = 50;
	int skill = 0;
	final int margin = 10;
	final int maxw = 300;
	final int maxh = 180;
	Image back = null;
	Graphics backgr = null;
	Thread th;

	Board(Image ibpic, Image iwpic) {
		bpic = ibpic;
		wpic = iwpic;
	}

	// Set winner to computer (1), player (2)
	public void winner(int n) {
		win_who = n;
		repaint();
	}


	public void restart(int x0, int y0, int indata[][]) {
		sz = maxw/x0;
		if (sz>maxh/y0) {
			sz = maxh/y0;
		}
		if (sz>50) {
			sz=50;
		}
		xsize = x0;
		ysize = y0;
		xpix = xsize*sz+2*margin;
		ypix = ysize*sz+3*margin;
		resize(xpix,ypix);
		back = null;
		data = indata;
		hilite_who=0;
		win_who=0;
		for (int i=0;i<xsize;i++) {
			for (int j=0;j<ysize;j++) {
				data[i][j] = (xsize+ysize+1+i+j)%2;
			}
		}
		repaint();
	}

	public boolean imageUpdate(Image img, int infoflags, int x, int y, int w,
	int h) {
		if ((infoflags & ImageObserver.ERROR)==0) {
			repaint();
		}
		return true;
	}


	// Return value of piece at xp,yp in unit coords
	private int piece(int xp, int yp) {
		if (xp<xsize && yp<ysize) {
			return data[xp][yp];
		} else {
			return -1;
		}
	}


	// mousemode: 0: other stuff
	// mousemode: 1: waiting for mouse down
	// mousemode: 2: user selecting
	int mousemode=0;
	int hilite_who=0; // 1==computer, 2==player
	int win_who=0; // 1==computer, 2==player
	Rectangle hilite = new Rectangle();
	Thread waitthread = null;

	// This routine gets the player's move
	public Rectangle getplayermove() {
		mousemode=1;
		waitthread = Thread.currentThread();
		while (mousemode==1) {
			try {
				synchronized(waitthread) {
					waitthread.wait();
				}
			} catch (InterruptedException e) {};
		}
		mousemode=0;
		return hilite;
	}

	public boolean mouseDown(Event evt, int xm, int ym) {
		int xright = (xm-margin)/sz;
		int ybot = (ym-margin)/sz;
		int p = piece(xright, ybot);
		if (mousemode==1 && p==1) {
			mousemode=2;
			hilite.x = xright;
			hilite.y = ybot;
			hilite.width = 1;
			hilite.height = 1;
			hilite_who = 2;
		}
		repaint();
		return true;
	}

	public boolean mouseDrag(Event evt, int xm, int ym) {
		if (mousemode==2) {
			int xleft = (xm-margin)/sz;
			int ytop = (ym-margin)/sz;
			if (xleft>hilite.x) {
				xleft = hilite.x;
			}
			if (xleft <0) {
				xleft = 0;
			}
			if (ytop <0) {
				ytop = 0;
			}
			if (ytop >hilite.y) {
				ytop = hilite.y;
			}
			hilite.width=hilite.x-xleft+1;
			hilite.height=hilite.y-ytop+1;
			repaint();
		}
		return true;
		
	}

	public boolean mouseUp(Event evt, int xm, int ym) {
		if (mousemode==2) {
			synchronized(waitthread) {
				waitthread.notify();
			}
		}
		return true;
	}

	public void highlight(int who) {
		hilite_who = who;
		repaint();
	}

	public void highlight(int who, Rectangle rect) {
		hilite = rect;
		hilite_who = who;
		repaint();
	}

	public void update(Graphics g) {
		if (back == null) {
			back = createImage(xpix,ypix);
			backgr = back.getGraphics();
			backgr.setColor(getBackground());
			backgr.fillRect(0,0,xpix,ypix);
		}
		paint(backgr);

		g.drawImage(back,0,0,this);
		
		if (hilite_who>0) {
			g.setColor(hilite_who==1?Color.green:Color.red);
			g.drawRect(margin+(hilite.x-hilite.width+1)*sz,
				margin+(hilite.y-hilite.height+1)*sz,
				hilite.width*sz-1,hilite.height*sz-1);
			g.drawRect(margin+(hilite.x-hilite.width+1)*sz+2,
				margin+(hilite.y-hilite.height+1)*sz+2,
				hilite.width*sz-5,hilite.height*sz-5);
			g.drawRect(margin+(hilite.x-hilite.width+1)*sz+4,
				margin+(hilite.y-hilite.height+1)*sz+4,
				hilite.width*sz-9,hilite.height*sz-9);
		}
	}
	public void paint(Graphics g) {
		for (int i=0;i<xsize;i++) {
			for (int j=0;j<ysize;j++) {
				g.drawImage((data[i][j]==0)?wpic:bpic,margin+sz*i,margin+sz*j,sz,sz,this);
			}
		}
		g.setColor(Color.yellow);
		g.drawRect(3,3,xpix-2*3,ypix-margin-2*3);
		g.drawRect(5,5,xpix-2*5,ypix-margin-2*5);
		if (win_who==1) {
			g.setColor(Color.black);
			g.fillRect(margin,margin,xpix-2*margin,20);
			g.setColor(Color.white);
			g.drawString("I win!",margin+20,margin+15);
		} else if (win_who==2) {
			g.setColor(Color.black);
			g.fillRect(margin,margin,xpix-2*margin,40);
			g.setColor(Color.white);
			g.drawString("Congratulations!",margin+20,margin+15);
			g.drawString("You win!",margin+20,margin+25);
		} else if (win_who==3) {
			g.setColor(Color.black);
			g.fillRect(margin+15,margin+15,xpix-2*margin-15,40);
			g.setColor(Color.white);
			g.drawString("Apologies.",margin+20,margin+15);
			g.drawString("The program encountered a bug",margin+20,margin+25);
			g.drawString("Please email Ken",margin+20,margin+35);
		}
	}
}

// This class is just a Canvas with an image on it
class ImgCanvas extends Canvas implements ImageObserver {
	int x,y;
	Image img=null;
	ImgCanvas(int inx, int iny, Image inimg) {
		x = inx;
		y = iny;
		img = inimg;
		resize(x,y);
	}
	public void update(Graphics g) {
		paint(g);
	}
	public void paint(Graphics g) {
		g.drawImage(img,0,0,x,y,this);
	}

	public boolean imageUpdate(Image img, int infoflags, int x, int y, int w,
	int h) {
		if ((infoflags & ImageObserver.ERROR)==0) {
			repaint();
		}
		return true;
	}
}

// This class holds the computer's strategy for the game.
// The application calls strategy.move() to get the computer's move
// The application calls strategy.setSkill(n) to set the skill level
class Strategy {
	int data[][];
	int x,y;
	int skill;
	int values[][] = {
		{1,2,1,4,1,2,1,8},
		{2,3,2,8,2,3,2,12},
		{1,2,1,4,1,2,1,8},
		{4,8,4,6,4,8,4,11},
		{1,2,1,4,1,2,1,8},
		{2,3,2,8,2,3,2,12},
		{1,2,1,4,1,2,1,8},
		{8,12,8,11,8,12,8,13}
	};

	Strategy(int indata[][], int inx, int iny) {
		data = indata;
		x = inx;
		y = iny;
	}

	public void setSkill(int sk) {
		if (sumboard()==0) {
			System.out.println("I can win from this position");
		} else {
			System.out.println("You can win from this position");
		}
		skill = sk;
	}

	public Rectangle move() {
		Rectangle mv;
		if (skill==0) {
			mv =  moveeasy();
		} else {
			mv = movehard();
		}
		return mv;
	}

	// See if there is a winning move from the current position.
	// Returns null or the winning move.  Also sets the c0 and c1 corners.
	public Rectangle haswin(Point c0, Point c1) {
		int cnt=0;
		c0.x=-1;
		c0.y=-1;
		c1.x=-1;
		c1.y=-1;
		// Find the corners and count the number of 1's.
		for (int i=0;i<x;i++) {
			for (int j=0;j<y;j++) {
				if (data[i][j]==1) {
					if (c0.x==-1) {
						c0.x = i;
						c0.y = j;
					}
					cnt ++;
					c1.x = i;
					c1.y = j;
				}
			}
		}
		//Now see if the corners describe all the 1's
		if ((c1.x-c0.x+1)*(c1.y-c0.y+1) != cnt) {
			return null;
		}
		for (int i=c0.x;i<=c1.x;i++) {
			for (int j=c0.y;j<=c1.y;j++) {
				if (data[i][j]==0) {
					return null;
				}
			}
		}
		return new Rectangle(c1.x,c1.y,c1.x-c0.x+1,c1.y-c0.y+1);
	}

	//Perform a move in easy mode
	public Rectangle moveeasy() {
		Point c0 = new Point(-1,-1), c1 = new Point(-1,-1);
		// See if we have a winning move
		Rectangle rwin = haswin(c0,c1);
		if (c0.x==-1) {
			return null;
		}

		if (rwin != null) {
			// We can win
			return rwin;
		}

		// Try random moves until we find one that doesn't leave
		// us in a losing position
		int tries=0;
		while (true) {
			Rectangle mv, win;
			Point t0 = new Point(0,0), t1 = new Point(0,0); // placeholders
			int x1,y1;
			// Try a random move, from either first or last black piece
			if (Math.random()<.5) {
				x1 = c0.x;
				y1 = c0.y;
			} else {
				x1 = c1.x;
				y1 = c1.y;
			}
			// Now generate a random rectangle
			mv = new Rectangle(x1,y1,(int)(Math.random()*(x1+1)+1),
				(int)(Math.random()*(y1+1)+1));
			// Try again if we're leaving a winning position
			flip(mv);
			win = haswin(t0,t1);
			flip(mv);
			if (win == null) {
				return mv;
			}
			tries++;
			if (tries==20) {
				// Give up and do a random move
				return mv;
			}
		}
	}

	// Sum the "nim value" of the black pieces
	public int sumboard() {
		int t=0;
		for (int i=0;i<x;i++) {
			for (int j=0;j<y;j++) {
				if (data[i][j]==1) {
					t ^= values[i][j];
				}
			}
		}
		return t;
	}

	// Implement the winning algorithm
	public Rectangle movehard() {
		Point c0 = new Point(-1,-1), c1 = new Point(-1,-1);
		// See if we have a winning move
		Rectangle rwin = haswin(c0,c1);
		if (c0.x==-1) {
			return null;
		}

		if (rwin != null) {
			// We can win
			return rwin;
		}
		rwin = new Rectangle();

		int sum = sumboard();

		if (sum==0) {
			// We're in a losing position
			System.out.println("You've got me cornered!");
			return moveeasy();
		}

		//Start searching from a random offset to make it more 
		//interesting.
		int ioff=(int)(Math.random()*x);
		int joff=(int)(Math.random()*y);
		for (int i0=0;i0<x;i0++) {
			int i = (i0+ioff)%x;
			for (int j0=0;j0<y;j0++) {
				int j = (j0+joff)%y;
				if (data[i][j]==0) {
					continue;
				}
				rwin.x = i;
				rwin.y = j;
				for (int w=1;w<=i+1;w++) {
					rwin.width=w;
					for (int h=1;h<=j+1;h++) {
						rwin.height = h;
						flip(rwin);
						if (sumboard()==0) {
							flip(rwin);
							System.out.println("I think you're in trouble!");
							return rwin;
						}
						flip(rwin);
					}
				}
			}
		}
		System.out.println("Bug: I can't find a good move!!!!");
		return moveeasy();
	}

	// flip the rectangle
	void flip(Rectangle mv) {
                for (int i=0;i<mv.width;i++) {
                        for (int j=0;j<mv.height;j++) {
                                data[mv.x-i][mv.y-j] = 1-data[mv.x-i][mv.y-j];
                        }
                }
        }
}