from queue_code import Queue
from twiddleNode import Node
from explored_set import ExploredSet

def BFS(start):
    goal = "123456789"
    
    #initialize the frontier using the initial state of the problem
    frontier = Queue()
    startNode = Node(start,None,None) #Since this is the start it doesn't have a parent or a move
    frontier.enqueue(startNode)
    
    #initialize the explored set to be empty
    explored = ExploredSet()
    
    #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.dequeue()
        
        #if the node contains a goal state
        if currentNode.getValue()==goal:
            #return the corresponding solution
            #I changed this to make a nicer looking output
            path = ""
            while currentNode.getMove()!=None:
                path = currentNode.getMove() + " " + path
                currentNode = currentNode.getParent()
            return "Solution: "+path
        
        #add the node to the explored set
        explored.add(currentNode)

        #expand the chosen node
        expansion = children(currentNode)

        
        #foreach resulting node in the expansion if not in  the explored set, add to the frontier
        for child in expansion:
            if not (explored.isIn(child)):
                frontier.enqueue(child)


moves=["A","A'","B","B'","C","C'","D","D'"]
transition= [ [3,0,2,4,1,5,6,7,8],
              [1,4,2,0,3,5,6,7,8],
              [0,4,1,3,5,2,6,7,8],
              [0,2,5,3,1,4,6,7,8],
              [0,1,2,6,3,5,7,4,8],
              [0,1,2,4,7,5,3,6,8],
              [0,1,2,3,7,4,6,8,5],
              [0,1,2,3,5,8,6,4,7]]


def children(node):
    board = node.getValue()
    output = []
    for index in range(8):
        newboard =""
        for j in transition[index]:
            newboard += board[j]
        output.append(Node(newboard,node,moves[index]))
    return output

       

###
def findParentNode(exSet,node):
    lookingFor = node.getParent()
    return exSet.retrive(lookingFor)