# read in definitions from Queues module
from Queues 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 total path cost g from
    the start node to this node.
    """
    def __init__(self, state, parent=None, action=None):
        self.state = state
        self.parent = parent
        self.action = action
        self.g = 0

    def expand(self):
        successors = []
        for (newState, action) in self.state.applyOperators():
            newNode = Node(newState, self, action)
            successors.append(newNode)
        return successors

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

def UninformedSearch(initialState, goalState, fringe):
    start = Node(initialState)
    fringe.insert(start)
    closedStates = []
    while not fringe.isEmpty():
        current = fringe.remove()
        if current.state in closedStates:
            # we've encountered the state before, so ignore it
            continue
        # states must have an __eq__ method to test equality
        elif current.state == goalState:
            print 'Found a solution...'
            printSolution(current)
            return
        else:
            closedStates.append(current.state)
            for successor in current.expand():
                # we are assuming step costs of 1
                successor.g = current.g + 1
                fringe.insert(successor)
    print 'Search failed'

def printSolution(node):
    numSteps = node.g
    path = []
    while node is not None:
        path.insert(0, node)
        node = node.parent
    print path[0].state
    for n in path[1:]:
        print '%s\n%s' % (n.action, n.state)
    print 'Solution took %d steps' % numSteps

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

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

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

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