import java.lang.Object;
import java.awt.Color;
import java.awt.Image;
import java.awt.Graphics;



public class Knight extends Piece
{
    //  jump directions
    //
    //      0   1
    //  7           2
    //       i,j
    //  6           3
    //      5   4
    //
    final static int   JUMPS = 8;
    //Position    start = new Position(-1, -1);
    Position    start;

    int   i;
    int   j;
    int[] di = {-1, +1, +2, +2, +1, -1, -2, -2};
    int[] dj = {-2, -2, -1, +1, +2, +2, +1, -1};
    int[] directions = new int[path.Size()];
    boolean[][] directionss = new boolean[path.Size()][JUMPS];
    private  String  FindPathStatus = new String();



	public Knight(int _value, Color _color, Image _image, Board _board, Position _start, int _speed)
	{
        super(_value, _color, _image, _board);
        start = _start;
	}



	protected synchronized boolean LegalMove(Position _from, Position _to)
	{
        if ( !(board.Squares[_to.i][_to.j].visited()) )
        {
		    if ( (_from.i == -1) || (_from.j == -1) ) // from outside board can go anywhere
    		{
    			return true;
    		}

    		if (
    		      ( (Math.abs(_to.i - _from.i) == 1) && (Math.abs(_to.j - _from.j) == 2) )
    		    ||
    		      ( (Math.abs(_to.i - _from.i) == 2) && (Math.abs(_to.j - _from.j) == 1) )
    		   )
    		{
    			return true;
    		}
        }

		return false;
	}




	public synchronized void Move(Position _to)
	{
   	    board.Visit(_to);
        path.Add(_to);
    }



	public synchronized void UndoMove()
	{
   	    board.UndoVisit(path.Last());
        path.UndoAdd();
    }



	public synchronized void Draw(Graphics _g)
	{
        // Not Yet Implemented
	}





	public String FindPathStatus()
	{
        return FindPathStatus;
    }




	protected boolean FindPath(Position _start, Thread _thread, int _search_speed)
	{
        Move(_start);   // calls Visit(_start) which passes number_of_visits to square

        Position Prior   = new Position(-1, -1);
        Position Current = new Position(_start.i, _start.j);
        Position Next    = new Position(-1, -1);

        boolean  can_jump_forward;
        int      current_direction; //  0..7



        long    search_tries = 0L;
        int     highest      = 0;
        int     lowest       = path.Size();

        while(!path.Full())
        {

            // Sleep for sometime...
            try
            {
                if (_search_speed != 0)
                {
                    _thread.sleep(1000 / _search_speed);
                }
            }
            catch (InterruptedException e) { }


            can_jump_forward = false;
            current_direction        = 0;

            // try all jump directions to find a "can_jump_forward" current_direction
            while ( (current_direction = NextDirection(directionss[path.Count()])) != -1 )
            {
                directionss[path.Count()][current_direction] = true;

                i = Current.i + di[current_direction];
                j = Current.j + dj[current_direction];

                // check if i,j are inside board
                if ( (i>=0) && (i<board.rows()) && (j>=0) && (j<board.columns()) )
                {
                    Next = new Position(i, j);
                }
                else
                {
                    continue;   // try next direction
                }

                // check if Next is not visited
                if (LegalMove(Current, Next))
                {
                    can_jump_forward = true;
                    break;
                }
            }


            if (can_jump_forward)   // jump forward
            {
                Move(Next);
                Prior   = new Position(Current.i, Current.j);
                Current = new Position(Next.i, Next.j);

                if (path.Count() > highest)
                {
                    highest = path.Count();
                }
            }


            if ((!can_jump_forward) || (AnyPositionInaccessible(Current))) // backtrack
            {
                //reset tried directions
                for (int i=0; i<JUMPS; i++)
                {
                    directionss[path.Count()][i] = false;
                }

                UndoMove();
                if (Prior == null)
                {
                    return false;  // no solution can be found
                }
                else
                {
                    Current = new Position(Prior.i, Prior.j);
                    Prior   = path.BeforeLast();
                }
                lowest  = Math.min(lowest, path.Count());
            }



            search_tries++;

            FindPathStatus  =
                                "Iteration: "   + Long.toString(search_tries)
                              + "   Lowest: "  + lowest
                              + "   Current: " + Integer.toString(path.Count())
                              + "   Highest: " + highest
                              ;

        }

        // solution found
        return true;
    }






    //////////////////////////////////////////////////////////////////////////////
    // Hint 01 .......... Check if any position has become inaccessible ........//
    //////////////////////////////////////////////////////////////////////////////

	private synchronized boolean AnyPositionInaccessible(Position _Current)
	{
        boolean  inaccessible = false;

        for (int a=0; a<board.rows(); a++)
        {
            for (int b=0; b<board.columns(); b++)
            {
                if (!board.Squares[a][b].visited())
                {
                    for (int n=0; n<JUMPS; n++)
                    {
                        i = a + di[n];
                        j = b + dj[n];

                        // check if i,j are inside board
                        if ( (i>=0) && (i<board.rows()) && (j>=0) && (j<board.columns()) )
                        {
                            // check if jump-from is not visited or is current
                            if ((!board.Squares[i][j].visited()) || ((i == _Current.i) && (j == _Current.j)) )
                            {
                                inaccessible = false;
                                break;
                            }
                            else
                            {
                                inaccessible = true;
                                continue;
                            }
                        }
                    }
                }
                if (inaccessible)   // if any position blocked
                {
                    break;
                }
            }
        }

        return inaccessible;
    }
    //////////////////////////////////////////////////////////////////////////////







    //////////////////////////////////////////////////////////////////////////////
    // Hint 02 ............. Continue in the same jump direction ...................//
    //////////////////////////////////////////////////////////////////////////////

    //
    //        TFFFFFTT    return i=1
    //        FFFFFFTF    return i=7
    //        FFFFFFTT    return 0
    //        TTTTTTTT    return -1 // all tried, must reset to FFFFFFFF and backtrack
    //        FFFFFFFF    if Empty return 0, else return Direction of Last
    private synchronized int NextDirection(boolean[] _directionss)
    {
        boolean foundF = false;
        boolean foundT = false;

        for (int i=0; i<JUMPS; i++)
        {
            if (_directionss[i] == true)
            {
                foundT = true;
                continue;      // skip T
            }
            else if (_directionss[i] == false)
            {
                foundF = true;
                if (foundT) // change form T to F
                {
                    return i;
                }
                continue;   // skip F
            }
        }



        // if have not returned by now check ...

        if (foundF && foundT)  // FFFFFFTT
        {
            return 0;
        }

        if (!foundF && foundT) // TTTTTTTT
        {
            return -1;
        }

        if (foundF && !foundT)  // FFFFFFFF
        {

            if (path.Count() > 1)
            {
                int next_direction_of_last_jump = NextDirection(directionss[path.Count() - 1]);

                int direction_of_last_jump =  next_direction_of_last_jump - 1;

                if (direction_of_last_jump < 0)
                {
                    direction_of_last_jump = direction_of_last_jump + JUMPS;
                }
                else if (direction_of_last_jump == -1) // last has TTTTTTTT
                {
                    // any direction will do for now for case of last is TTTTTTTT
                    direction_of_last_jump = NextDirection(directionss[path.Count() - 2]) - 1;
                }


                //  jump directions
                //
                //      0   1
                //  7           2
                //       i,j
                //  6           3
                //      5   4
                //
                //  if last jump is 0,1 return 0    NORTH
                //  if last jump is 2,3 return 2    EAST
                //  if last jump is 4,5 return 4    SOUTH
                //  if last jump is 6,7 return 6    WEST
                //
                direction_of_last_jump = (direction_of_last_jump / 2) * 2;
                int direction_of_next_jump = direction_of_last_jump - 1;
                if (direction_of_next_jump < 0)
                {
                    direction_of_next_jump = direction_of_next_jump + JUMPS;
                }

                return direction_of_next_jump ;
            }
            else
            {
                return 0;
            }
        }

        return 999; // never get here
    }

    //////////////////////////////////////////////////////////////////////////////



}