package be.qanar.slidingPuzzle;

import java.util.*;

public class PuzzleState extends Object
{
	/* Schematic with index of state for a size 9
	 *    | 0 | 1 | 2 
	 * ---+---+---+---
	 *  0 | 0 | 1 | 2 
	 * ---+---+---+---
	 *  1 | 3 | 4 | 5 
	 * ---+---+---+---
	 *  2 | 6 | 7 | 8 
	 */
	
	/* Correct solution for a size 9
	 *  1 | 2 | 3 
	 * ---+---+---
	 *  4 | 5 | 6 
	 * ---+---+---
	 *  7 | 8 | _ 
	 */
	
	// constructor for a solved puzzle with side of 'length'
	public PuzzleState( int length )
	{
		this.length = length ;
		this.state = new Vector< Integer >() ;
		for( int i = 1; i < length * length; i++ ) { this.state.add( i ) ; }
		this.state.add( 0 ) ;
		
		assert( hasValidState() ) ;
		assert( isCorrect()     ) ;
	}
	
	/* DEPRECATED
	// constructor for a puzzle with a specific state. State must be valid. 
	public PuzzleState( Vector< Integer > state )
	{
		this.state = state ;
		this.length  = ( int )java.lang.Math.sqrt( state.size() ) ;
		
		assert( java.lang.Math.sqrt( state.size() ) % 1 == 0 ) ; // Make sure we got a square grid
		assert( hasValidState() ) ;
	}
	*/
	// returns the value of a specific square. The row and column of the position must be positive and smaller then the length of the side. 
	public int getSquare( Position p )
	{
		assert( p.column >= 0 && p.column < length ) ;
		assert( p.row    >= 0 && p.row    < length ) ;
		
		return state.get( makeIndexFromPosition( p ) ) ;
	}
	
	// return true if the puzzle is correctly solved
	public boolean isCorrect()
	{
		boolean isCorrect = state.get( length * length  - 1 ) == 0 ;
		for ( int i = 0; i < length * length - 1 && isCorrect ; i++ ) { isCorrect = state.get( i ) == i + 1 ; }
		return isCorrect ;
	}
	
	// returns the position of the empty square
	public Position getEmptySquare()
	{
		for( int i = 0; i < length * length; i++ )
		{
			if( state.elementAt( i ) == 0 )
			{
				return makePositionFromIndex( i ) ;
			}
		}
		assert( false ) ; // it's not possible there isn't an empty square
		return null ;
	}
	
	// defines the possible directions for a move. 
	public enum direction
	{
		UP, DOWN, LEFT, RIGHT
	}
	
	// returns the puzzlestate following at the moving the piece at the specified direction into the empty space
	// if a move should not be possible, (being at the edge) the function will return null
	
	/* example of the result of a moving the piece to the left of the empty square
	 *  1 | 2 | 3 
	 * ---+---+---
	 *  4 | _ | 6 
	 * ---+---+---
	 *  7 | 8 | 5 
	 *  
	 *  1 | 2 | 3 
	 * ---+---+---
	 *  _ | 4 | 6 
	 * ---+---+---
	 *  7 | 8 | 5 
	 */

	public PuzzleState makeMove( direction dir )
	{
		Position emptySquare = getEmptySquare() ;
		Position newSquare   = new Position( -99, -99 ) ;
		
		switch( dir )
		{
			case UP:
			{
				newSquare = emptySquare.toTop() ;
				break ;
			}
			case DOWN:
			{
				newSquare = emptySquare.toBottom() ;
				break ;
			}
			case LEFT:
			{
				newSquare = emptySquare.toLeft() ;
				break ;
			}
			case RIGHT:
			{
				newSquare = emptySquare.toRight() ;
				break ;
			}
		}
		
		if(    newSquare.row    >= 0 && newSquare.row    < length 
			&& newSquare.column >= 0 && newSquare.column < length )
		{
			return new PuzzleState( switchItems( makeIndexFromPosition( emptySquare ), makeIndexFromPosition( newSquare ), state ) ) ;
		}
		return null ;
	}
	
	// returns a vector with PuzzleStates that contains all possible moves. 
	public Vector< PuzzleState > getPossibleMoves()
	{
		Vector< PuzzleState > possibleMoves = new Vector< PuzzleState >() ;
		
		if ( makeMove( direction.DOWN  ) != null ) possibleMoves.add( makeMove( direction.DOWN  ) ) ;
		if ( makeMove( direction.UP    ) != null ) possibleMoves.add( makeMove( direction.UP    ) ) ;
		if ( makeMove( direction.LEFT  ) != null ) possibleMoves.add( makeMove( direction.LEFT  ) ) ;
		if ( makeMove( direction.RIGHT ) != null ) possibleMoves.add( makeMove( direction.RIGHT ) ) ;
		
		return possibleMoves ;
	}
	
	// compares this puzzle state with another object
	@Override public boolean equals( Object obj ) 
	{
		if( obj instanceof PuzzleState )
		{
			return toString().equals( obj.toString() ) ;
		}
		return false ;
	}
	
	// returns a string representation of the puzzlestate
	@Override public String toString() 
	{
		String str = "" ;
		int    cnt = 0 ;
		
		for( int value : state ) 
		{
			str += ( value != 0 ? value : "_" ) + " " ;
			
			cnt++;
			if( cnt == length )
			{
				str += "\n" ;
				cnt = 0;
			}
		}
		
		return str ;
	}
	
	// creates a random, but CORRECT state
	public static PuzzleState createRandom( int length, int numberOfMoves )
	{
		PuzzleState state = new PuzzleState( length ) ;
		Random generator  = new Random();
		
		for( int i = 0; i < numberOfMoves; i++ )
		{
			Vector< PuzzleState > moves = state.getPossibleMoves() ;
			state = moves.get( generator.nextInt( moves.size() ) ) ;
		}
		
		return state ;
	}
	
	// makes a position for an index in the state vector
	private Position makePositionFromIndex( int index )
	{
		assert( index >= 0               ) ;
		assert( index <  length * length ) ;
		
		Position pos = new Position( index / length, index % length ) ;
		assert( makeIndexFromPosition( pos ) == index ) ;
		
		return pos ;
	}
	
	// turns a position into an index that can be used for the state vector
	private int makeIndexFromPosition( Position p )
	{
		assert( p.column >= 0 && p.column < length ) ;
		assert( p.row    >= 0 && p.row    < length ) ;
		
		return p.row * length + p.column ;
	}
	
	// switches the location of two items in a vector
	private static < T > Vector< T > switchItems( int alpha, int beta, Vector< T > items )
	{
		T item1 = items.get( alpha ) ;
		T item2 = items.get( beta  ) ;
		
		Vector< T > newItems = new Vector< T >( items );
		newItems.setElementAt( item1, beta  ) ;
		newItems.setElementAt( item2, alpha ) ;
		
		return newItems ;
	}
	
	private boolean hasValidState()
	{
		return length * length == state.size() ;
	}
	
	private Vector< Integer > state  ; // current order of the numbers in the grid. 0 is the empty square.
	private int               length ; // number of squares on an edge.
	
}