from abstracts.searchproblem import SearchProblem
from utility.datastructures import Stack
from utility.auxilliary import traverse_path


def search(searchproblem: SearchProblem, *args, **kwargs) -> [list, None]:
	"""
	Depth First Search - deepest node first.

	:param searchproblem: instance of a search problem
	:return: a list of actions to reach from start to goal node if found, else None
	"""

	# Stack
	frontier = Stack()
	# visited set
	explored = set()
	# to keep track of each node's parent and extra info
	meta_map = dict()

	startnode = searchproblem.get_start_state()
	meta_map[startnode] = (None, None)
	frontier.push(startnode)

	if searchproblem.is_goal_state(startnode):
		return list()

	while not frontier.is_empty():

		node = frontier.pop()

		for (child, action, _) in searchproblem.successor_states(node):
			if child in explored:
				continue

			if child not in frontier:
				if child not in meta_map:
					meta_map[child] = (node, action)

				if searchproblem.is_goal_state(child):
					action_list = traverse_path(child, meta_map)
					return action_list

				frontier.push(child)

		explored.add(node)

	return None
