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 (this is different from
 * previous semester's code used in CPS 108 at Duke University).
 * <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>
 * This means that making a move is an O(n^2) operation for an n x n grid.
 */
public class PuzzleModel
{
    private int mySize;
    private int myBlank;
    private int[] myNumbers;
    private LinkedList myMoves;
    private PuzzleController myControl;


    /**
     * 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;
        myControl.setModel(this);

        mySize = size;
        myBlank = size * size - 1;
        myMoves = new LinkedList();
        myNumbers = new int[size * size];
        for (int k = 0; k < size * size; k++ )
        {
            myNumbers[k] = k;
        }
    }


    /**
     * 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;
        return ((aRow == bRow && Math.abs(aCol - bCol) == 1) || 
                (aCol == bCol && Math.abs(aRow - bRow) == 1));
    }

    /**
     * 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) myMoves.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 (myMoves.size() != 0)
        {
            doMove((PuzzleMove)myMoves.removeLast(), false);
        }
        return (myMoves.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;
    }
}