from stack_code import Stack
from cityNode import Node

def search(start,goal):
    #initialize the frontier using the initial state of the problem
    frontier = Stack()
    startNode = Node(start,None,0) #Since this is the start it doesn't have a parent or a move
    frontier.push(startNode)
    
    #initialize the explored set to be empty
    explored = []
    
    #loop do
    while True:
        #if the frontier is empty
        if frontier.is_empty(): 
            #return failure
            print("Failure.  Empty Frontier")
            return None 
        
        #choose a leaf node and remove it from the frontier
        currentNode = frontier.pop()
        
        #if the node contains a goal state
        if currentNode.getValue()==goal:
            total = currentNode.getCost()
            #return the corresponding solution
            path = [currentNode.getValue()]
            while currentNode.getParent()!=None:
                path.insert(0,currentNode.getParent())
                currentNode = findParentNode(explored,currentNode)
            #print("explored",len(explored))
            #print("frontier",frontier.size())
            return path,total
        
        #add the node to the explored set
        explored.append(currentNode)
        
        #expand the chosen node
        expansion = generateChildren(currentNode)

        #foreach resulting node in the expansion if not in  the explored set, add to the frontier
        for child in expansion:
            if not (alreadyExplored(explored,child)):
                frontier.push(child)
        
                
                
def findParentNode(exSet,node):
    lookingFor = node.getParent()
    for others in exSet:
        if others.getValue()==lookingFor:
            return others
    print("There is an error.  This shouldn't ever happen")
    return None

def generateChildren(current):
    roads = [['Arad', 'Sibiu', 140],
             ['Arad', 'Timsoara', 118],
             ['Arad', 'Zerind', 75],
             ['Bucharest', 'Fagaras', 211],
             ['Bucharest', 'Giurgiu', 90],
             ['Bucharest', 'Urziceni', 85],
             ['Bucharest', 'Pitesti', 101],
             ['Craiova', 'Dobreta', 120],
             ['Craiova', 'Pitesti', 138],
             ['Craiova', 'Rimnicu Vilcea', 146],
             ['Dobreta', 'Mehadia', 75],
             ['Eforie', 'Hirsova', 86],
             ['Fagaras', 'Sibiu', 99],
             ['Hirsova', 'Urziceni', 98],
             ['Iasi', 'Neamt', 87],
             ['Iasi', 'Vaslui', 92],
             ['Lugoj', 'Mehadia', 70],
             ['Lugoj', 'Timsoara', 111],
             ['Oradea', 'Sibiu', 151],
             ['Oradea', 'Zerind', 71],
             ['Pitesti', 'Rimnicu Vilcea', 97],
             ['Rimnicu Vilcea', 'Sibiu', 80],
             ['Urziceni', 'Vaslui', 142]]
             
    start = current.getValue()
    sofar = current.getCost()
    children = []
    for road in roads:
        if road[0]==start:
            children.append(Node(road[1],road[0],sofar+road[2]))
        elif road[1]==start:
             children.append(Node(road[0],road[1],sofar+road[2]))
    return children
                                
    
def alreadyExplored(exp,child):
    for node in exp:
        if node.getValue()==child.getValue():
            return True
    return False



res,total = search("Arad","Bucharest")
print(res)
print(total)