#!/usr/bin/python

from argparse import ArgumentParser, RawTextHelpFormatter
from queue import Queue
import os.path, time, sys

# global
visited = {}
cycle = False
delay = 0
verbosity = 1

# main method
# initiate variables and run search
def main(args):
	global visited, cycle, delay, verbosity

	lines = args.file.readlines()
	mapmap = {}
	y = 0
	for line in lines:
		x = 0
		for c in line:
			if c in ['s','g','x',' ']:
				mapmap[(x,y)] = c
			x += 1
		y += 1

	delay = args.time

	if args.quiet:
		verbosity = 0
	elif args.verbose:
		verbosity = 2

	cycle = args.cycle
	for (a,b) in mapmap.keys():
		visited[(a,b)] = False

	if args.depth:
		dfs(mapmap, x, y)
	else:
		bfs(mapmap, x, y)

# depth-first search
def dfs(mapmap, width, height):
	global visited
	sys.setrecursionlimit(100000) # seg fault may occur
	def dfs_visit(node, depth):
		if verbosity == 2:
			print ("recursion depth: " + str(depth))
		visualize(node)
		visited[node] = True
		for (x,y) in neighbors(*node):
			if valid_coord(x,y,width,height):
				if mapmap[(x,y)] == 'g':
					print ("found goal: " + str((x,y)))
					if verbosity == 2:
						print ("nodes processed: " + str(depth + 1))
					exit(0)
				elif mapmap[(x,y)] == ' ':
					depth += 1
					dfs_visit((x,y), depth)
	dfs_visit(find_start(mapmap), 0)
	print ("there is no solution!")

# breadth-first search
def bfs(mapmap, width, height):
	global visited
	q = Queue()
	q.put(find_start(mapmap))
	i = 0
	while not q.empty():
		i += 1
		node = q.get()
		visualize(node)
		for (x,y) in neighbors(*node):
			if valid_coord(x,y,width,height):
				if mapmap[(x,y)] == 'g':
					print ("found goal: " + str((x,y)))
					if verbosity == 2:
						print ("nodes processed: " + str(i))
					exit(0)
				elif mapmap[(x,y)] == ' ':
					q.put((x,y))
					if verbosity == 2:
						print ("enqueueing " + str((x,y)))
					visited[(x,y)] = True
	print ("there is no solution!")

# get neighboring nodes in range 1
def neighbors(x, y):
	result = [(a,b) for a in [x-1,x,x+1] for b in [y-1,y,y+1]]
	result.remove((x,y))
	return result

# check if coordinates still in map
# check if node has been visited before (only if cycle=True)
def valid_coord(x, y, width, height):
	return 0 <= x < width-1 and 0 <= y < height and not (cycle and visited[(x,y)])

# get coordinates of 's'
def find_start(mapmap):
	for (x,y), v in mapmap.items():
		if v == 's':
			return (x,y)
	parser.error("map doesn't contain start position!")

# print node after possible delay
def visualize(node):
	if verbosity > 0:
		time.sleep(delay)
		print(node)

# check if target file does exist
def is_valid_file(parser, f):
	if not os.path.exists(f):
		parser.error("The file %s does not exist!"%f)
	else:
		return open(f, 'r')

# parse arguments for main method
if __name__ == "__main__":
	parser = ArgumentParser(description="read ascii map and search for path from s to g\n(default strategy: breadth-first)",
							formatter_class=RawTextHelpFormatter)
	parser.add_argument("-c", "--cycle", action="store_true",
							help="use cycle detection")
	parser.add_argument("-d", "--depth", action="store_true",
							help="use depth-first search")
	parser.add_argument("-t", "--time", type=float, metavar="delay", default=0,
							help="set time delay in seconds (default: 0)")
	vq = parser.add_mutually_exclusive_group()
	vq.add_argument("-q", "--quiet", action="store_true",
							help="display result only (overrules --time)")
	vq.add_argument("-v", "--verbose", action="store_true",
							help="display additional information")
	parser.add_argument("file", type=lambda f: is_valid_file(parser,f),
							help="file which contains the ascii map")
	main(parser.parse_args())