import sys

class Node():
    def __init__(self, state, parent, action):
        self.state = state
        self.parent = parent
        self.action = action

class StackFrontier():
    def __init__(self):
        self.frontier = []

    def add(self, node):
        self.frontier.append(node)

    def contains_state(self, state):
        return any(node.state == state for node in self.frontier)

    def empty(self):
        return len(self.frontier) == 0

    def remove(self):
        if self.empty():
            raise Exception("empty frontier")
        else:
            node = self.frontier[-1]
            self.frontier = self.frontier[:-1]
            return node

class QueueFrontier(StackFrontier):

    def remove(self):
        if self.empty():
            raise Exception("empty frontier")
        else:
            node = self.frontier[0]
            self.frontier = self.frontier[1:]
            return node

class Maze():

    def __init__(self, filename):

        # Read file and set height and width of maze
        with open(filename) as f:
            contents = f.read()

        # Validate start and goal
        if contents.count("A") != 1:
            raise Exception("maze must have exactly one start point")
        if contents.count("B") != 1:
            raise Exception("maze must have exactly one goal")

        # Determine height and width of maze
        contents = contents.splitlines()
        self.height = len(contents)
        self.width = max(len(line) for line in contents)

        # Keep track of walls
        self.walls = []
        for i in range(self.height):
            row = []
            for j in range(self.width):
                try:
                    if contents[i][j] == "A":
                        self.start = (i, j)
                        row.append(False)
                    elif contents[i][j] == "B":
                        self.goal = (i, j)
                        row.append(False)
                    elif contents[i][j] == " ":
                        row.append(False)
                    else:
                        row.append(True)
                except IndexError:
                    row.append(False)
            self.walls.append(row)

        self.solution = None


    def print(self):
            """
        Prints the maze to the console, displaying walls, the start and goal positions, 
        and the solution path if it exists.

        The method uses different characters to represent various elements in the maze:
        - '█' for walls
        - 'A' for the start position
        - 'B' for the goal position
        - '*' for the solution path, if available
        - ' ' for open spaces

        If a solution has been found, the path from the start to the goal will be shown
        with asterisks ('*').

        Returns:
            None
        """
            raise NotImplementedError("neighbors method is not implemented yet")


    def neighbors(self, state):
              """
        Returns a list of neighboring states in the maze that can be reached 
        from the current state.

        Args:
            state (tuple): The current position in the maze as (row, col).

        Returns:
            list: A list of tuples representing neighboring positions 
                  that can be moved to.
        """
              raise NotImplementedError("neighbors method is not implemented yet")


    def solve(self):
        """
        Finds a solution to the maze using breadth-first search (BFS) if one exists.

        Returns:
            None: Modifies the class attributes to store the solution path 
                  and number of states explored.
        """

        raise NotImplementedError("solve method is not implemented yet")


    def output_image(self, filename, show_solution=True, show_explored=False):
        raise NotImplementedError("output_image method is not implemented yet")


if len(sys.argv) != 2:
    sys.exit("Usage: python Path_Finding_L2.py maze.txt")

m = Maze(sys.argv[1])
print("Maze:")
m.print()
print("Solving...")
m.solve()
print("States Explored:", m.num_explored)
print("Solution:")
m.print()
#m.output_image("maze.png", show_explored=True)