from Queues import *
from time import *

#----------------------------------------------------------------------

class Node:
    """
    This class is used to represent nodes of the search tree.  Each
    node contains a state representation, a reference to the node's
    parent node, a string that describes the action that generated
    the node's state from the parent state, and the path cost g from
    the start node to this node.
    """
    def __init__(self, state, parent):
        self.state = state
        self.parent = parent
        self.g = 0
    
    def expand(self):
        successors = []
        for newState in self.state.nbrs:
            newNode = Node(newState, self)
            successors.append(newNode)

        return successors

#----------------------------------------------------------------------
visited = "grey"

def wait(t):
    start = time()
    while time()-start < t:
	    pass
	    
def UninformedSearch(initialState, goalState, fringe):
    
    start = Node(initialState, None)
    fringe.insert(start)
    closedStates = []

    while not fringe.isEmpty():
        current = fringe.remove()
        # states must have an __eq__ method defined to test equality
        if current.state == goalState:
            current.state.colorState(visited)
            print 'Found a solution...'
            showSolution(current)
            return current
        elif current.state not in closedStates:
            current.state.colorState(visited)
            wait(0.5)
            closedStates.append(current.state)
            for successor in current.expand():
                # set path cost of successor
                successor.g = current.g + 1
                fringe.insert(successor)

    print 'Search failed'

def showSolution(node):
    print "Here is the solution..."
    numSteps = node.g
    path = []
    while node != None:
        path.insert(0, node)
        node = node.parent
    print path[0].state.getName()
    path[0].state.colorState("blue")
    for n in path[1:]:
        print '%s' % (n.state.getName())
        n.state.colorState("blue")
        wait(0.5)
    print 'Solution took %d steps' % numSteps

#----------------------------------------------------------------------
# Test functions for uninformed search

def BreadthFirst(initialState, goalState):
    fringe = Queue()
    return UninformedSearch(initialState, goalState, fringe)

def DepthFirst(initialState, goalState):
    fringe = Stack()
    return UninformedSearch(initialState, goalState, fringe)

def UniformCost(initialState, goalState):
    fringe = PriorityQueue(lambda node: node.g)
    return UninformedSearch(initialState, goalState, fringe)