# File: Maze.py
# CS 42 HW8, problem 3
# Author:
# Date:
# Time Spent:

# After compiling this program, the program is executed by typing
# python Maze test0.maze
# where "test0.maze" may be replaced by
# another text file in the same directory with a legal description
# of a maze.

# The initial line in a maze file's description needs to have two integers:
# first, the height of the maze, followed by the width
#
# Then, there should be at least "height" rows of characters, 
# each of which should be at least "width" wide - those characters
# will make up the maze 

# The characters are ' ' for empty space and asterisks '*' for walls.
# Other characters represent special empty spaces, for example 'S'
# for the starting location and 'D' for the destination (of spam!).
# The outer edge of the maze should consist of walls - this eases 
# the burden of checking to stay in bounds...

import sys              # for getting command line arguments
from Queue import *     #import our queue code from problem 2, or just use a deque
# if you want to use a deque you can just import collections

# MazeCell - a class supporting Maze
#
# The following convention is used in mazes:
# Walls are represented by '*'
# Empty area is represented by the blank symbol ' '
# Starting point is represented by 'S'
# Destination (SPAM!) is represented by 'D'
class MazeCell(object):
    ''' A class to support Maze containing one cell of the maze '''
    def __init__(self, row, col, contents):
        self.row = row
        self.col = col
        self.contents = contents
        self.visited = False
        self.parent = None

    def __repr__(self):
        return "[" + str(self.row) + "," + str(self.col) + "," + self.contents + "]"

    def isWall(self):
        return self.contents == Maze.WALL
    
class Maze(object):
    # USE THESE RATHER THAN MAGIC VALUES!
    WALL = '*';
    EMPTY = ' ';
    START = 'S';
    DESTINATION = 'D';
    FOOTSTEP = 'o';

    def __init__(self, filename):
        ''' Initialize a maze from a file '''
        self.maze = None
        self.rows = 0
        self.columns = 0
        self.loadMazeFromFile(filename)
        
    def findMazeCell(self, charToFind):
        ''' Takes a char token (either 'S' or 'D') and returns the
            MazeCell containing the location of the token in the maze'''
        for r in range(self.rows):
            for c in range(self.columns):
                if self.maze[r][c].contents == charToFind:
                    return self.maze[r][c]
    
    def BFS(self, start, dest):
        ''' BFS method takes the start MazeCell and the destination MazeCell
            as input and performs the breadth-first search algorithm in the
            maze beginning at location start.  When the method ends, each
            reachable empty (' ') MazeCell should have its "parent" data member
            set to the MazeCell from which it was visited.'''
        return None  # To be implemented by you
				
    def __repr__(self):
        ''' Return a string representation of the maze, for printing'''
        result = "\n";
        for r in range(self.rows):
            for c in range(self.columns):
                result += self.maze[r][c].contents
            result += "\n"
        result += "\n"
        return result

    
    ## PROVIDED METHOD.  NO NEED TO ALTER.
    def loadMazeFromFile(self, filename):
        ''' loadMaze method takes the maze and a String with the name of the
            10 by 10 maze file to open and loads that file into the maze array.'''

        try:  # in case the file isn't there or misnamed
            f = open(filename, 'r')
            fileline = f.readline()
            # The first line should have two integers...
            dimensions = fileline.strip().split() #split on whitespace
            self.rows = int(dimensions[0])
            self.columns = int(dimensions[1])
	    # create the maze cell references ... but not the MazeCells themselves
            self.maze = []  
            for r in range(self.rows):
                fileline = f.readline()
                self.maze.append([])
                for c in range(self.columns):
                    ch = fileline[c]
                    self.maze[r].append(MazeCell(r,c,ch))
        except IOError as (errno, strerror):
            print "I/O error({0}): {1}".format(errno, strerror)
        except ValueError:
            print "Could not convert data to an integer."
        except:
            print "Unexpected error:", sys.exc_info()[0]
            raise
        else:
            f.close()


def main(args):
    # make sure there's a maze to solve!
    if len(args) != 2:
        print "You need to specify a maze on the command line (not in IDLE)"
        print "such as: python Maze.py test1.maze"
    else:
	#The filename comes from the command line
        filename = args[1]   
        M = Maze(filename)  # this creates the maze
        start = M.findMazeCell('S')  # get the Source
        destination = M.findMazeCell('D')  # get the Destination (SPAM!)
        print "Start at", start, "with destination", destination
        M.BFS(start, destination)
        print "M is\n" + str(M)

    
# You must run this program from the command line and pass it
# The name of a file as an argument.
if __name__ == "__main__" :
    main(sys.argv)