//This one uses the left hand rule.  The robot always goes straight when there
//is only one possible way to move, and then it turns left whenever it has the
//option.  If not, it goes stright.  If not, it goes right.  Don't consider a
//two way intersection to be an intersection
public class LeftHandRuleSolver
{
    //keep track of which way you are facing
    private enum facing {NORTH, SOUTH, EAST, WEST};
    private Maze maze;
    private boolean solutionFound;
    private facing direction;
    private int[][] robotMaze;
    private int currentRow;
    private int currentColumn;


    public LeftHandRuleSolver(Maze m)
    {
        maze=m;
        solutionFound = false;
        direction=facing.NORTH;
        robotMaze=m.getMaze();
        currentRow=m.getStartRow();
        currentColumn=m.getStartColumn();
    }

    public void solveMaze()
    {
        while (!solutionFound)
        {
            System.out.println(direction);
            move();
        }
    }

    public void move()
    {
        //base case: stop when you arrive at an end
        if(currentRow==maze.getEndRow() && currentColumn==maze.getEndColumn())
        {
            solutionFound=true;
            System.out.println("Found");
            return;
        }

        //find which spot to take
        if(isIntersection(currentRow,currentColumn))
        {
            System.out.println("intersection");
            if( isLeftTurnAvailable(currentRow,currentColumn) )
            {
                turnLeft();
                stepForward();
                System.out.println("turn L, step");
            }
            else if (isStraightAvailable(currentRow,currentColumn))
            {
                stepForward();
                System.out.println("step");
            }
            else
            {
                turnRight();
                stepForward();
                System.out.println("turn R, step");
            }
        }
        else if(isLeftHandTurn(currentRow,currentColumn))
        {
            turnLeft();
            stepForward();
            System.out.println("turn L, step");
        }
        else if(isRightHandTurn(currentRow,currentColumn))
        {
            turnRight();
            stepForward();
            System.out.println("turn R, step");
        }
        else if(isStraightPath(currentRow, currentColumn))
        {
            stepForward();
            System.out.println(" step");
        }
        else if (isDeadEnd(currentRow,currentColumn))
        {
            turnAround();
            stepForward();
            System.out.println("turn around, step");
        }
 
    }

   

    public void stepForward()
    {
        if(direction.equals(facing.NORTH))
            currentRow=currentRow-1;
        if(direction.equals(facing.SOUTH))
            currentRow=currentRow+1;
        if(direction.equals(facing.EAST))
            currentColumn=currentColumn+1;
        if(direction.equals(facing.WEST))
            currentColumn=currentColumn-1;
    }

    //changes what way you are facing due to a left turn
    public void turnLeft()
    {
        if(direction.equals(facing.NORTH))
            direction=facing.WEST;
        else if(direction.equals(facing.SOUTH))
            direction=facing.EAST;
        else if(direction.equals(facing.EAST))
            direction=facing.NORTH;
        else if(direction.equals(facing.WEST))
            direction=facing.SOUTH;
    }

    //changes what way you are facing due to a right turn
    public void turnRight()
    {
        if(direction.equals(facing.NORTH))
            direction=facing.EAST;
        else if(direction.equals(facing.SOUTH))
            direction=facing.WEST;
        else if(direction.equals(facing.EAST))
            direction=facing.SOUTH;
        else if(direction.equals(facing.WEST))
            direction=facing.NORTH;
    }

    //changes what way you are facing due to reaching a dead end
    public void turnAround()
    {
        if(direction.equals(facing.NORTH))
            direction=facing.SOUTH;
        else if(direction.equals(facing.SOUTH))
            direction=facing.NORTH;
        else if(direction.equals(facing.EAST))
            direction=facing.WEST;
        else if (direction.equals(facing.WEST))
            direction=facing.EAST;
    }
 
    //Returns true if the spot you are planning to go to next exists and is not
    //a wall or off the edge of the map.
    public boolean isValidMove(int nextRow, int nextColumn)
    {
        return maze.indexExists(nextRow, nextColumn)&&
                !maze.isWall(nextRow, nextColumn) ;
    }


    //Returns true if the spot you plan to move to next is an interseciton
    //with two paths that are not the one you are currently on.
    public boolean isIntersection(int nextRow, int nextColumn)
    {
        int nuOfPaths= nuPaths(nextRow, nextColumn);

        //return true if its an intersection
        if(nuOfPaths<=2)
            return false;
        else
            return true;

    }//end method

    //when you are at an intersection, we need to know if a left hand
    //turn is available.
    public boolean isLeftTurnAvailable(int nextRow, int nextColumn)
    {
        boolean answer = false;
            if(direction.equals(facing.NORTH))
            {
                if(isValidMove(nextRow, nextColumn-1) )
                    if (robotMaze[nextRow][nextColumn-1]==1)
                    {
                        answer=true;
                    }
            }
            else if(direction.equals(facing.SOUTH))
            {
                if(isValidMove(nextRow,nextColumn+1))
                    if(robotMaze[nextRow][nextColumn+1]==1)
                        answer=true;
            }
            else if (direction.equals(facing.EAST))
            {
                if(isValidMove(nextRow-1,nextColumn))
                    if(robotMaze[nextRow-1][nextColumn]==1)

                        answer=true;
                        
            }
            else if(direction.equals(facing.WEST))
            {
                if(isValidMove(nextRow+1,nextColumn))
                    if(robotMaze[nextRow+1][nextColumn]==1)
                        answer=true;
            }
        return answer;
    }

    //when you are at an intersection, we need to know if going straight
    // is available.
    public boolean isStraightAvailable(int nextRow, int nextColumn)
    {
       boolean answer = false;
            if(direction.equals(facing.NORTH))
            {
                if(isValidMove(nextRow-1, nextColumn) )
                    if (robotMaze[nextRow-1][nextColumn]==1)
                        answer=true;
            }
            else if(direction.equals(facing.SOUTH))
            {
                if(isValidMove(nextRow+1,nextColumn))
                    if(robotMaze[nextRow+1][nextColumn]==1)
                        answer=true;
            }
            else if (direction.equals(facing.EAST))
            {
                if(isValidMove(nextRow,nextColumn+1))
                    if(robotMaze[nextRow][nextColumn+1]==1)
                        answer=true;
            }
            else if(direction.equals(facing.WEST))
                if(isValidMove(nextRow,nextColumn-1))
                    if(robotMaze[nextRow][nextColumn-1]==1)
                        answer=true;
        return answer;
    }



    //detemines if the path curves to the left (not an actual turn)
    public boolean isLeftHandTurn(int nextRow, int nextColumn)
    {
        boolean leftTurn=false;
        if (nuPaths(nextRow, nextColumn)==2)
        {
            if(direction.equals(facing.NORTH))
                if(isValidMove(nextRow, nextColumn-1) )
                    if (robotMaze[nextRow][nextColumn-1]==1)
                        leftTurn=true;
            if(direction.equals(facing.SOUTH))
                if(isValidMove(nextRow,nextColumn+1))
                    if(robotMaze[nextRow][nextColumn+1]==1)
                        leftTurn=true;
            if (direction.equals(facing.EAST))
                if(isValidMove(nextRow-1,nextColumn))
                    if(robotMaze[nextRow-1][nextColumn]==1)
                        leftTurn=true;
            if(direction.equals(facing.WEST))
                if(isValidMove(nextRow+1,nextColumn))
                    if(robotMaze[nextRow+1][nextColumn]==1)
                        leftTurn=true;
                   

        }//end if

        return leftTurn;

    }


     //detemines if the path curves to the right (not an actual turn)
    public boolean isRightHandTurn(int nextRow, int nextColumn)
    {
        boolean rightTurn=false;
        if (nuPaths(nextRow, nextColumn)==2)
        {
            if(direction.equals(facing.SOUTH))
                if(isValidMove(nextRow, nextColumn-1) )
                    if (robotMaze[nextRow][nextColumn-1]==1)
                        rightTurn=true;
            if(direction.equals(facing.NORTH))
                if(isValidMove(nextRow,nextColumn+1))
                    if(robotMaze[nextRow][nextColumn+1]==1)
                        rightTurn=true;
            if (direction.equals(facing.WEST))
                if(isValidMove(nextRow-1,nextColumn))
                    if(robotMaze[nextRow-1][nextColumn]==1)
                        rightTurn=true;
            if(direction.equals(facing.EAST))
                if(isValidMove(nextRow+1,nextColumn))
                    if(robotMaze[nextRow+1][nextColumn]==1)
                        rightTurn=true;

        }//end if

        return rightTurn;

    }

    public boolean isStraightPath(int nextRow, int nextColumn)
    {
        boolean straight=false;
        if (nuPaths(nextRow, nextColumn)==2 || nuPaths(nextRow, nextColumn)==1)
        {
            if(direction.equals(facing.SOUTH))
            {
                if(isValidMove(nextRow+1, nextColumn) )
                    if (robotMaze[nextRow+1][nextColumn]==1)
                        straight=true;
            }
            else if(direction.equals(facing.NORTH))
            {
                if(isValidMove(nextRow-1,nextColumn))
                    if(robotMaze[nextRow-1][nextColumn]==1)
                        straight=true;
            }
            else if (direction.equals(facing.WEST))
            {
                if(isValidMove(nextRow,nextColumn-1))
                    if(robotMaze[nextRow][nextColumn-1]==1)
                        straight=true;
            }
            else if(direction.equals(facing.EAST))
            {
                if(isValidMove(nextRow,nextColumn+1))
                    if(robotMaze[nextRow][nextColumn+1]==1)
                        straight=true;
            }

        }//end if

        return straight;
    }

    //checks if we are at a dead end
    public boolean isDeadEnd(int nextRow, int nextColumn)
    {
        if(nuPaths(nextRow, nextColumn)==1)
            return true;

        else
            return false;
    }

    //determines how many paths are availabe from the spot you are
    //going to move to next
    private int nuPaths(int nextRow, int nextColumn)
    {
        int nuOfPaths=0;

        //check spots to right, left, top, bottom of nextSpot and increment
        if(isValidMove(nextRow+1, nextColumn))
            if(maze.getValue(nextRow+1, nextColumn)==1)
                nuOfPaths++;
        if(isValidMove(nextRow-1, nextColumn))
            if(maze.getValue(nextRow-1, nextColumn)==1)
                nuOfPaths++;
        if(isValidMove(nextRow, nextColumn+1))
            if(maze.getValue(nextRow, nextColumn+1)==1)
                nuOfPaths++;
        if(isValidMove(nextRow, nextColumn-1))
            if(maze.getValue(nextRow, nextColumn-1)==1)
                nuOfPaths++;

        System.out.println(nuOfPaths);//always 0
        return nuOfPaths;

    }

}//end class