

import frontiers
import search_strategies


#Depth Bound Search


def solve( problem ) :
    """ *** YOUR CODE HERE *** """
    return IDS(problem)


#Iterative Deepening Search
def IDS(problem):
    bound = 0
    while True:
        result = DLS(problem,bound)
        if result != "cutoff":
            return result
        bound+=1
#Iteration
def  DLS(problem, bound):
    initialNode = search_strategies.SearchNode(problem.get_initial_state())
    frontier = frontiers.Stack()
    frontier.push(initialNode)
    cutoff = False
    problem.heuristic_info = {}
    while True:
        if cutoff and frontier.is_empty():
            return "cutoff"
        currentNode = frontier.pop()
        if currentNode.depth == bound:
            cutoff = True
            if problem.goal_test(currentNode.state):
                return actionsList(currentNode)
        else:
            for state, action, cost in problem.get_successors(currentNode.state):
                """we need to store the heuristic for every successor node and
                # if the same node is generated the second time, we need to compare
                # compare the heuristic cost for the two times and choose the one with less
                # heuristic cost."""

                # if the successor node haven't be generated by other path before (in which case, its heuristic will be None)
                # or its current heuristic cost is less than its previous heuristic cost (which is developed by other path):
                if problem.heuristic_info.get(state) is None or currentNode.path_cost+cost<problem.heuristic_info.get(state):
                    """In each path, check is there is duplicated steps taken"""
                    # if the successor state is in the path, stop adding successor to the path
                    # use statesList(currentNode) to get the path
                    # the idea of checking duplicated moves in a path is from u5640420 Godfrey Gong
                    if not pathExploredNode(statesList(currentNode), state):
                        problem.heuristic_info[state] = currentNode.path_cost+cost
                        successorNode = search_strategies.SearchNode(state, action, currentNode.path_cost+cost, currentNode, currentNode.depth+1)
                        frontier.push(successorNode)

# this function is to check if the next node is already added in the path before
# its purpose is to ensure that the bird will only visit a state once and never go back to visited state
def pathExploredNode(curNodePath, nextNodeState):

    if nextNodeState in curNodePath:
        return True
    else: return False

# this function is to get the states of the whole path and save it into a list
# giving the current node
def statesList(curNode):
    states = []
    linkedNode = curNode
    while linkedNode.parent != None:
        # calling parent to chase back
        states.append(linkedNode.state)
        linkedNode = linkedNode.parent
    return states

# this function is to get the actions of the whole path and save it into a list
# giving the current node
def actionsList(node):
    actions = []
    linkedNode = node
    while linkedNode.parent != None:
        actions.append(linkedNode.action)
        linkedNode = linkedNode.parent
    actions.reverse()
    return actions


#Depth Limited Search (recursion)
"""def DLS(problem, bound):
    return recursiveDLS(search_strategies.SearchNode(problem.get_initial_state()), problem, bound )


#Recursive Depth Limited Search
def recursiveDLS(currentNode, problem, bound):
    cutoff = False
    if problem.goal_test(currentNode.state):
        actions = []
        linkedNode = currentNode
        while linkedNode.parent != None:
            actions.append(linkedNode.action)
            linkedNode = linkedNode.parent
        actions.reverse()
        return actions
    elif currentNode.depth == bound:
        return "cutoff"
    else:
        for state, action, cost in problem.get_successors(currentNode.state):
            successorNode = search_strategies.SearchNode(state,action, currentNode.path_cost+cost, currentNode, currentNode.depth+1)
            print(successorNode)
            result = recursiveDLS(successorNode, problem, bound)
            if result =="cutoff":
                cutoff = True
            elif result!=None:
                return result

    if cutoff:
        return "cutoff"
    else:
        return None"""


