'''
15-110 Homework 4
Name:
Andrew ID:
'''

################################################################################

'''
#1 - findParents(t, name)
Parameters: binary tree of strings, string
Returns: list of strings
'''

def findParents(t, name):
    return


'''
#2 - getPrereqs(g, course)
Parameters: directed graph of strings, string
Returns: list of strings
'''

def getPrereqs(g, course):
    return


################################################################################
''' Test Functions '''

def testFindParents():
    print("Testing findParents()...", end="")
    t1 = { "contents" : "Arya",
        "left"  : { "contents" : "Ned",
                    "left"  : { "contents" : "Rickard",
                                "left"  : None, "right" : None },
                    "right" : { "contents" : "Lyarra",
                                "left"  : None, "right" : None } },
        "right" : { "contents" : "Catelyn",
                    "left"  : { "contents" : "Hoster",
                                "left"  : None, "right" : None },
                    "right" : { "contents" : "Minisa",
                                "left"  : None, "right" : None } } }
    # An order of names is not specified, so we'll
    # sort your result before checking it
    assert(findParents(t1, "Ned") != None)
    assert(sorted(findParents(t1, "Ned")) == ["Lyarra", "Rickard"])
    assert(sorted(findParents(t1, "Catelyn")) == ["Hoster", "Minisa"])
    assert(findParents(t1, "Rickard") == [ ])
    assert(findParents(t1, "Lyarra") == [ ])
    assert(findParents(t1, "Hoster") == [ ])
    assert(findParents(t1, "Minisa") == [ ])
    assert(findParents(t1, "Jon") == None)

    t2 = { "contents" : "Neville",
        "left"  : { "contents" : "Frank",
                    "left"  : None,
                    "right" : { "contents" : "Augusta",
                                "left"  : None, "right" : None } },
        "right" : { "contents" : "Alice",
                    "left"  : None, "right" : None} }
    assert(sorted(findParents(t2, "Neville")) == ["Alice", "Frank"])
    assert(findParents(t2, "Frank") == ["Augusta"])
    assert(findParents(t2, "Alice") == [])
    assert(findParents(t2, "Augusta") == [])
    assert(findParents(t2, "Hermione") == None)

    t3 = { "contents" : "Shallan",
        "left" : { "contents" : "Lin",
                   "left"  : None, "right" : None },
        "right" : None }
    assert(findParents(t3, "Shallan") == ["Lin"])
    assert(findParents(t3, "Lin") == [])
    assert(findParents(t3, "Kaladin") == None)
    print("... done!")

def testGetPrereqs():
    print("Testing getPrereqs()...", end="")
    g = { "110" : [],
        "112" : ["122", "150"],
        "122" : ["213", "210", "251", "281"],
        "150" : ["210", "251"],
        "151" : ["150", "251", "281"],
        "210" : [],
        "213" : [],
        "251" : [],
        "281" : [] }
    # An order of courses is not specified, so we'll
    # sort your result before checking it
    assert(getPrereqs(g, "210") != None)
    assert(sorted(getPrereqs(g, "210")) == ["122", "150"])
    assert(sorted(getPrereqs(g, "251")) == ["122", "150", "151"])
    assert(getPrereqs(g, "213") == ["122"])
    assert(getPrereqs(g, "150") == ["112", "151"])
    assert(getPrereqs(g, "112") == [])
    assert(getPrereqs(g, "110") == [])

    g2 = { "Differential and Integral Calculus" : ["Integration and Approximation",
                                                   "Multivariate Analysis"],
           "Integration and Approximation" : ["Calculus in Three Dimensions",
                                              "Differential Equations",
                                              "Operations Research I"],
           "Concepts of Mathematics" : ["Discrete Mathematics"],
           "Discrete Mathematics" : ["Operations Research I"],
           "Matrices and Linear Transformations" : ["Operations Research I"],
           "Multivariate Analysis" : [],
           "Calculus in Three Dimensions" : [],
           "Differential Equations" : [],
           "Operations Research I" : [] }
    assert(sorted(getPrereqs(g2, "Operations Research I")) == ["Discrete Mathematics", "Integration and Approximation", "Matrices and Linear Transformations"])
    assert(getPrereqs(g2, "Discrete Mathematics") == ["Concepts of Mathematics"])
    assert(getPrereqs(g2, "Matrices and Linear Transformations") == [])
    print("... done!")

def testAll():
    testFindParents()
    testGetPrereqs()

testAll()