""" Week8-1 Notes """

t = {   "contents" : 3,
        "left" : {  "contents" : 1,
                    "left" : None,
                    "right" : { "contents" : 2,
                                "left" : None,
                                "right" : None } },
        "right" : { "contents" : 5,
                    "left" : {  "contents" : 4,
                                "left" : None,
                                "right" : None },
                    "right" : { "contents" : 8,
                                "left" : {  "contents" : 6,
                                            "left" : None,
                                            "right" : None },
                                "right" : None } } }

###



#print(search(t, 8))
#print(search(t, 9))

###



#print(binarySearch(t, 8))
#print(binarySearch(t, 9))

###

g = { "A" : [ "B", "D", "F" ],
      "B" : [ "A", "E" ],
      "C" : [ ],
      "D" : [ "A", "E" ],
      "E" : [ "A", "B", "D" ],
      "F" : [ "A" ]
    }

###

def breadthFirstSearch(g, start, target):
    # Set up two lists for visited nodes and to-visit nodes
    visited = [ ]
    nextNodes = [ start ]

    # Repeat while there are nodes to visit
    while len(nextNodes) > 0:
        next = nextNodes[0]

        if next == target: # If it's what we're looking for- we're done!
            return True
        else: # Otherwise, add unvisited neighbors
            for node in g[next]:
                if node not in visited and node not in nextNodes: # Not seen before
                    nextNodes = nextNodes + [ node ] # Add to the BACK of the list

        nextNodes.remove(next)
        visited.append(next) # We've visited the node now
        print(next, "visited:", visited, "nextNodes:", nextNodes)
    return False # When no nodes left- we're done!

#print(breadthFirstSearch(g, "A", "C"))

###

def depthFirstSearch(g, start, target):
    # Set up two lists for visited nodes and to-visit nodes
    visited = [ ]
    nextNodes = [ start ]

    # Repeat while there are nodes to visit
    while len(nextNodes) > 0:
        next = nextNodes[0]

        if next == target: # If it's what we're looking for- we're done!
            return True
        else: # Otherwise, add unvisited neighbors
            for node in g[next]:
                if node in nextNodes: # seen before, but higher-priority now
                    nextNodes.remove(node)
                if node not in visited and node not in nextNodes: # Not seen before
                    nextNodes = [ node ] + nextNodes # Add to the FRONT of the list
        nextNodes.remove(next)
        visited.append(next) # We've visited the node now
        print(next, "visited:", visited, "nextNodes:", nextNodes)
    return False # When no nodes left- we're done!

#print(depthFirstSearch(g, "A", "C"))