import java.awt.GridLayout;
import java.awt.BorderLayout;
import java.awt.Button;
import java.awt.Panel;
import java.awt.Event;
import java.awt.Component;
import java.awt.Graphics;
import java.awt.Canvas;
import java.awt.Color;
import java.awt.Font;
import java.awt.Label;
import java.applet.Applet;

/**
 * A PuzzleObserver has a method to respond to the
 * completion of a puzzle, and a method to respond
 * to the puzzle moving from a complete to an incomplete
 * state.
 */
interface PuzzleObserver  {
	/**
	 * Called when the Puzzle is completed
	 */
	abstract public void notifyComplete();
	
	/**
	 * Called when the Puzzle is scrambled
	 */
	abstract public void notifyScrambled();
}


public class Fifteen extends Applet implements PuzzleObserver  {
	MessagePanel topPanel;
	Puzzle puz;
	Panel bottomPanel;
	Button shuffleButton;
	Button cheatButton;
	
	public void init()  {
		int rows = getIntParameter("rows", 4);
		int columns = getIntParameter("columns", 4);
		
		this.setLayout(new BorderLayout());
		
		topPanel = new MessagePanel("Congratulations!!!", 
							this.getBackground(), Color.red, 1000,
							new Font("Helvetica", Font.BOLD, 14));
		this.add("North", topPanel);
		
		bottomPanel = new Panel();
		shuffleButton = new Button("Shuffle");
		cheatButton = new Button("Cheat");
		
		// note: bottomPanel uses default FlowLayout
		bottomPanel.add(shuffleButton); 
		bottomPanel.add(cheatButton);
		
		this.add("South", bottomPanel);
		
		// create a puzzle with "this" as the PuzzleObserver
		puz = new Puzzle(rows, columns, this);
		this.add("Center", puz);
		puz.shuffle();
		puz.showPuzzle();
	}
	
	public int getIntParameter(String param, int defValue) {
		int value;

		try	{
			value = Integer.parseInt(getParameter(param));
		} catch (Exception e) {
			// if the parameter wasn't specified,
			// or if it was not a valid int, use the default
			value = defValue;
		}
		
		return value;
	}

	
	public boolean action(Event e, Object what)  {
		if (e.target.equals(shuffleButton))  {
			puz.shuffle();
			puz.showPuzzle();
			return true;
		} else if (e.target.equals(cheatButton))  {
			puz.cheat();
			puz.showPuzzle();
			return true;
		} else {
			return false;
		}
	}
	
	public void notifyComplete()  {
		topPanel.turnOn();
	}
	
	public void notifyScrambled()  {
		topPanel.turnOff();
	}
}

class TileButton extends Button  {
	private int pos;	// position in puzzle
	Color default_bg;	// default background for visible tiles
	
	TileButton()  {
		// default constructor: no label, no position
		this(" ", -1);
	}
	
	TileButton(String label, int position)  {
		super(label);
		pos = position;
		default_bg = getBackground();
	}
		
	int getPos()  {
		return pos;
	}
}

/** 
 * A Panel with a flashing message that can be turned on and off
 */
class MessagePanel extends Panel implements Runnable  {
	protected String message;			// the message to display
	protected Color bgColor;			// background color
	protected Color fgColor;			// foreground color
	protected int delay;				// milliseconds between flashes
	protected Font font;				// a font for the message
	
	private boolean on = false;		// is the message showing (and flashing)?
	private Thread flashThread;		// a thread for flashing the message
	private boolean flashState = true; // toggled back and forth to flash message
	
	private Label msgLabel;
	
		
	/**
	 * Default constructor: no message, gray background, black foreground, 1 second delay
	 */
	MessagePanel()  {
		this("", Color.gray, Color.black, 1000, 
			new Font("Helvetica", Font.BOLD, 14));
	}
	
	/**
	 * Construct a MessagePanel
	 * @param mes: the message to flash
	 * @param bg: the background color
	 * @param del: delay between flashes
	 * @param fnt: the Font to use
	 */
	MessagePanel(String mes, Color bg, Color fg, int del, Font f)  {
		message = mes;
		bgColor = bg;
		fgColor = fg;
		delay = del;
		
		this.setLayout(new BorderLayout());
		msgLabel = new Label(" ", Label.CENTER);
		msgLabel.setFont(f);
		this.add("Center", msgLabel);
		layout();
	}
		
	
	/**
	 * Returns true if the message has been turned on.
	 */
	synchronized boolean isOn()  {
		return on;
	}
	
	/**
	 * Turn on the message and start it flashing
	 */	
	synchronized void turnOn()  {
		on = true;
		msgLabel.setText(message);
		flashThread = new Thread(this);
		flashThread.start();
	}
	
	/**
	 * Turn off the flashing message.
	 */
	synchronized void turnOff()  {
		on = false;
		flashThread = null; // stop the thread
		remove(msgLabel);
		msgLabel.setText(" ");
		setBackground(bgColor);
		msgLabel.setBackground(bgColor);
		add("Center", msgLabel);
		layout();
	}
	
	/**
	 * The thread that flashes the message on the panel.
	 */
	public void run()  {
		try  {
			flashState = true;
			
			while (isOn())  {
				remove(msgLabel);
				setColors();
				add("Center", msgLabel);
				layout();
				flashState = !flashState; // invert the state
				flashThread.sleep(delay);
			}
			
		} catch (InterruptedException e)  {
			return;
		}
	}
	
	/**
	  * Set the foreground and background colors, dependent on the flash state
	  */
	void setColors() {
		setBackground((flashState)?bgColor:fgColor);
		msgLabel.setBackground((flashState)?bgColor:fgColor);

		setForeground((flashState)?fgColor:bgColor);
		msgLabel.setForeground((flashState)?fgColor:bgColor);
	}
}

class Puzzle extends Panel {

	int[] tiles;	// the values in the tiles
	int emptyPos;	// position of the empty tile
	int rows;		// number of rows of tiles
	int columns;	// number of columns of tiles
	
	PuzzleObserver myObserver;
	boolean wasCompleted = false;
	
	static final int EMPTY = -1;
	static final int INVALID_POS = -1;
	
	/**
	 * Default constructor constructs a Puzzle with
	 * 4 rows and 4 columns, and no observer.
	 */
	public Puzzle() {
		this(4, 4, null);
	}
	
	/** 
	 * Constructs a Puzzle with the specified rows, columns, and observer.
	 */
	public Puzzle(int rows, int columns, PuzzleObserver observer) {
		this.rows = rows;
		this.columns = columns;
		tiles = new int[rows * columns];
		myObserver = observer;
		
		setLayout (new GridLayout (rows, columns));
		// setBackground(Color.black);
		
		initTiles();
		shuffle();
	}
	
	/**
	 * Initializes the tiles as a grid of buttons, with
	 * the empty space represented by a hidden button.
	 * 
	 */
	public void initTiles() {
		
		// n-1 numbered tiles...
		for (int i = 0; i < tiles.length - 1; i++) {
			tiles[i] = i + 1;
			add(new TileButton(" " + tiles[i], i), i);
		}
		// ...and one empty space
		emptyPos = tiles.length - 1;
		tiles[emptyPos] = EMPTY;
		add (new TileButton(" " + EMPTY, emptyPos), emptyPos);
		
		shuffle();
		showPuzzle();
	}
	
	/**
	 * Arranges the puzzle in the winning position.  Useful for debugging the PuzzleObserver
	 */
	public void cheat() {
		// n-1 numbered tiles...
		for (int i = 0; i < tiles.length - 1; i++) {
			tiles[i] = i + 1;
		}
		// ...and one empty space
		emptyPos = tiles.length - 1;
		tiles[emptyPos] = EMPTY;
	}

	/**
	 * Shuffles the matrix of tile values by swapping
	 * each tile with a random tile.  The emptyPos variable
	 * is updated to reflect the new position of the empty
	 * space.  This method only updates the matrix, not the
	 * TileButtons.  For that, use showPuzzle().
	 */
	void shuffle() {
		for (int i = 0; i < tiles.length; i++) {
			// choose a random tile
			int r = (int)(Math.random() * 100.0) % 
				(rows * columns);
			
			// swap this tile with the random one
			int temp = tiles[i];
			tiles[i] = tiles[r];
			tiles[r] = temp;
			
			// track the empty position
			if (tiles[r] == EMPTY)  {
				emptyPos = r;
			} else if (tiles[i] == EMPTY)  {
				emptyPos = i;
			}	
		}
	}
	
	/**
	 * Steps through the TileButtons, updating their labels
	 * to match the values in the array, and making all of them
	 * visible, except the empty space, which contains a hidden
	 * TileButton.  If the puzzle is completed, or moves from
	 * a complete to incomplete configuration, then the
	 * PuzzleObserver is notified with the appropriate 
	 * method-call.
	 */
	void showPuzzle() {
		TileButton tempTile;
		
		for (int i = 0; i < tiles.length; i++) {
			tempTile = (TileButton) getComponent(i);
			
			if (tiles[i] != EMPTY)  {
				tempTile.setLabel(" " + tiles[i]);
				tempTile.setBackground(tempTile.default_bg);
				tempTile.show();
			} else {
				tempTile.setLabel(" ");
				tempTile.setBackground(Color.black);
				tempTile.hide();
			}
		}
		layout();
		
		try  {
			
			// Notify the observer if completed or scrambled
			
			if (isInOrder())  {
				wasCompleted = true;
				myObserver.notifyComplete();
				
			} else if (wasCompleted) {
				wasCompleted = false;
				myObserver.notifyScrambled();
			}
			
		} catch (NullPointerException e)  {
			// no observer.  don't care
		}
	}
	
	/**
	 * Returns the position of the tile above tile k,
	 * or INVALID_POS if k is in top row.
	 */
	int posAbove(int k)  {
		// returns the position of the tile above tile k
		// returns INVALID_POS if k is in top row
		if (k - columns >= 0)  {
			return (k - columns);
		} else {
			return INVALID_POS;
		}
	}
	
	/**
	 *	Returns the position of the tile below tile k,
	 *	or INVALID_POS if k is in the bottom row
	 */
	int posBelow(int k)  {
		if (k + columns < tiles.length)  {
			return (k + columns);
		} else {
			return INVALID_POS;
		}
	}
	
	/**
	 * Returns the position of the tile to the left of tile k,
	 * or INVALID_POS if k is in the far left column
	 */
	int posLeft(int k)  {
		if (k % columns != 0 )  {
			return k-1;
		} else {
			return INVALID_POS;
		}
	}
	
	/**
	 * Returns the position of the tile to the right of tile k,
	 * or INVALID_POS if k is in the far right column
	 */
	int posRight(int k)  {
		if (((k+1) % columns) != 0)  {
			return k+1;
		} else {
			return INVALID_POS;
		}
	}
	
	/**
	 * Returns true if tiles i and j are in the same row
	 */
	boolean sameRow(int i, int j)  {
		return ((i/columns) == (j/columns));
	}
	
	/**
	 * Returns true if tiles i and j are in the same column
	 */
	boolean sameColumn(int i, int j)  {
		return ((i % columns) == (j % columns));
	}
	
	/**
	 * Returns true if the puzzle is in order.
	 */
	public boolean isInOrder() {
		for (int i = 0; i < tiles.length - 2; i++) {
			if (tiles[i] > tiles[i + 1]) {
				return false;
			}
		}
		return true;
	}
	
	/**
	 *  Respond to button clicks.
	 */ 
	public boolean action(Event e, Object what)  {
		if (e.target instanceof TileButton) {
			int clickedPos = ((TileButton) e.target).getPos();
			if (sameColumn(clickedPos, emptyPos)) {
				if (clickedPos < emptyPos)  {
					// slide down
					for (int i = emptyPos; i > clickedPos; i = posAbove(i)) {
						// start at the empty position, 
						// and replace with the tile above
						tiles[i] = tiles[posAbove(i)];
					}
					tiles[clickedPos] = EMPTY;
					emptyPos = clickedPos;
					showPuzzle();
					return true;
				} else if (clickedPos > emptyPos) {
					// slide up
					for (int i = emptyPos; i < clickedPos; i = posBelow(i)) {
						// start at the empty position, 
						// and replace with the tile below
						tiles[i] = tiles[posBelow(i)];
					}
					tiles[clickedPos] = EMPTY;
					emptyPos = clickedPos;
					showPuzzle();
					return true;
				} else {
					return false;
				}
				
			} else if (sameRow(clickedPos, emptyPos)) {
				if (clickedPos < emptyPos) {
					// slide right
					for (int i = emptyPos; i > clickedPos; i = posLeft(i)) {
						// start at the empty position, 
						// and replace with the tile to the left
						tiles[i] = tiles[posLeft(i)];
					}
					tiles[clickedPos] = EMPTY;
					emptyPos = clickedPos;
					showPuzzle();
					return true;
				} else if (clickedPos > emptyPos) {
					// slide left
					for (int i = emptyPos; i < clickedPos; i = posRight(i)) {
						// start at the empty position, 
						// and replace with the tile to the right
						tiles[i] = tiles[posRight(i)];
					}
					tiles[clickedPos] = EMPTY;
					emptyPos = clickedPos;
					showPuzzle();
					return true;
				} else {
					return false;
				}
			} else {
				// not in same row or column as emtpy position
				return false;
			}
			
		} else {
			return false;
		}
	}
	
}