""" Week7-3 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 } } }

###

def search(t, target):
    print(t)
    if t == None:
        return False
    elif t["contents"] == target:
        return True
    else:
        leftCheck = search(t["left"], target)
        rightCheck = search(t["right"], target)
        return leftCheck or rightCheck

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

###

def binarySearch(t, target):
    print(t)
    if t == None:
        return False
    elif t["contents"] == target:
        return True
    else:
        if target < t["contents"]:
            return binarySearch(t["left"], target)
        else: # t["contenst"] < target
            return binarySearch(t["right"], target)

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"))