import java.util.LinkedList;

/**
 * This is the model for a sliding puzzle game. The model
 * keeps track of the location of n^2 squares, for n specified
 * when the model is constructed.  A grid if n^2-1 visible squares 
 * is represented by the model, one square is "the blank square".
 * <P>
 * Clients click on a square adjacent to the blank square and the
 * clicked on square swaps with the blank. This simulates moving
 * the clicked square into the blank spot --- and the previous
 * location of the clicked square is now blank.
 *
 * All communication between a model and its views is handled
 * by the model's Controller. The controller can have multiple
 * views, but the model has a single controller in the current
 * architecture. 
 * <P>
 * <b>Notes on Implementation</b>
 * <P>
 * The model is conceptually a grid of n x n elements. However,
 * the current implementation models this as a single array
 * of n x n elements --- and the elements are int values.
 * <P>
 * The idea is that originally, array[k] == k where array is
 * the state that represents the model. When two values are swapped,
 * they change locations in the array. Thus, when a client wants
 * to move square number 7, this square must be searched for. That is
 * the value 7 is searched for in the array that represents the model.
 * This happens for the blank square too --- both the move and the
 * blank are searched for in the entire grid/array. Then the code
 * currently implemented determines if these elements (move and blank)
 * are neighbors. If so, they're swapped and the controller updates
 * the views.
 * <P>
 * <em>This means that making a move is an O(n^2)
 * operation for an n x n grid.</em>
 * 
 */

public class PuzzleModel
{
    /**
     * Creates a model with the specified controller and size. The
     * size parameter is one dimension of a 2D grid represented by
     * this model.
     * @param control mediates communication between model and its views     
     * @param size is the size of one square of the model
     */
    
    public PuzzleModel(PuzzleController control, int size)
    {
	myControl = control;
	myList = new LinkedList();	
	mySize = size;
	myNumbers = new int[size*size];
	for(int k=0; k < size*size; k++) {
	    myNumbers[k] = k;
	}
	myBlank = size*size - 1;
	myControl.setModel(this);
    }

    /**
     * Return the value associated with a Blank
     */
    private  int getBlankValue()
    {
	return myBlank;
    }

    /**
     * return location/index of number in myNumbers
     * @param number between 0 and mySize^2-1 (inclusive)
     * @return the index such that myNumbers[index] == number
     */

    private int getIndex(int number)
    {
	for(int k=0; k < myNumbers.length; k++) {
	    if (myNumbers[k] == number) {
		return k;
	    }
	}
	return -1;
    }

    /**
     * @param a index in [0..mySize^2-1)
     * @param b index in [0..mySize^2-1)
     * @return true if a and b are neighbors in grid, else returns false
     */
    private boolean isNeighbors(int a, int b)
    {
	int aRow = a / mySize;
	int bRow = b / mySize;
	int aCol = a % mySize;
	int bCol = b % mySize;

	if (aRow == bRow && Math.abs(aCol - bCol) == 1) {
	    return true;
	}
	if (aCol == bCol && Math.abs(aRow - bRow) == 1) {
	    return true;
	}
	return false;
    }
    
    /**
     * Attempts to make a move and returns true if the move
     * was successfully made, else returns false.
     * @param move is the move being attempted in this model
     * @return true if move succeeded, else returns false
     */

    public boolean makeMove(PuzzleMove move)
    {
	return doMove(move,true);
    }

    /**
     * Make the move by swapping the tile/square associated
     * with the move with the blank. Returns true iff successful.
     * @param doStore determines if the move will be stored and thus
     * undoable
     * @param move is the move being attempted
     * @return true iff making move succeeds
     */
    private boolean doMove(PuzzleMove move, boolean doStore)
    {
	int index = getIndex(move.getValue());
	int blankIndex = getIndex(getBlankValue());
	
	if (isNeighbors(index,blankIndex)) {
	    int temp = myNumbers[blankIndex];
	    myNumbers[blankIndex] = myNumbers[index];
	    myNumbers[index] = temp;

	    myControl.showBoard(myNumbers);
	    if (doStore){
		myList.add(move);
	    }
	    return true;
	}
	return false;	
    }

    /**
     * Undoes the last move (if there is one) and returns true iff
     * another undo is possible
     * @return true if another undo is possible, else returns false
     */
    public boolean undo()
    {
	if (myList.size() != 0) {
	    doMove((PuzzleMove) myList.removeLast(),false);
	}
	return myList.size() > 0;
    }

    /**
     * Returns the dimension of one side of the grid represented
     * by this model.
     * @return the dimension of one side of the puzzle model
     */
    public int getSize()
    {
	return mySize;
    }

    private int mySize;
    private int myBlank;
    private int myNumbers[];
    private LinkedList myList;
    private PuzzleController myControl;
}