// Author: Alyce Brady
//
// License Information:
//   This class is free software; you can redistribute it and/or modify
//   it under the terms of the GNU General Public License as published by
//   the Free Software Foundation.
//
//   This class is distributed in the hope that it will be useful,
//   but WITHOUT ANY WARRANTY; without even the implied warranty of
//   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//   GNU General Public License for more details.

import java.util.ArrayList;
import java.util.Random;

import edu.kzoo.grid.Grid;
import edu.kzoo.grid.Location;
import edu.kzoo.util.RandNumGenerator;

/**
 *  Mouse in a Maze Program:<br>
 *      The BacktrackingMouse class defines a mouse that uses backtracking
 *      to move methodically through a maze.
 *
 *  @author  Alyce Brady
 *  @version 4 October 2025
 **/
public class BacktrackingMouse extends Mouse
{
  // Instance variable:  A Stack to keep track of locations to visit.
    K_Stack<Location> theStack;

  // Inherit everything except the constructor; redefine the nextLocation
  // method.

    /** Constructs a BacktrackingMouse object.
     **/
    public BacktrackingMouse()
    {
        super();

        // ADD CODE HERE !!!
    }

    /** {@inheritDoc}
     *  <p>
     *  At the start, a new BacktrackingMouse initializes the stack
     *  with the places it could move from its starting location.
     *  </p>
     */
    @Override
    protected void addToGrid(Grid grid, Location loc)
    {
        super.addToGrid(grid, loc);
        if ( loc.equals(maze().getStartLoc()) )
        {
            // ADD CODE HERE !!!
        }
    }

    /** {@inheritDoc}
     *  <p>
     *  A Backtracking mouse leaves markers behind in the locations it is
     *  moving from so that it doesn't return to a location it has already
     *  visited.
     *  </p>
     */
    @Override
    public void move()
    {
        // Keep track of current location so we can place a marker here.
        Location oldLocation = location();

        super.move();

        if ( ! isStuck() )
        {
            // ADD CODE HERE !!!
        }
    }

    /** {@inheritDoc}
     *  <p>
     *  Gets the next location for this mouse off of the stack, and also
     *  pushes possible next locations (after this one) onto the stack.
     *  </p>
     **/
    @Override
    protected Location nextLocation()
    {
        // If the stack is empty, then we're done.
        if ( theStack.isEmpty() )
            return location();

        // ADD CODE HERE !!!
        return location();  // Temporary INCORRECT code so class will compile.
    }

    /** Pushes next possible move locations onto the stack.
     *      @param  baseLoc   location from which to move
     */
    protected void pushNextPossibleMoveLocs(Location baseLoc)
    {
        // ADD CODE HERE !!!
    }

}