# Exercise 4B
# Family trees.
#
# Author: David Watt.

my_family =                        \
    ('Frank', [                 \
        ('David', [             \
            ('Susanne', []),    \
            ('Jeff', [])    ]), \
        ('Margaret', []),       \
        ('Ann', [              \
            ('Emma', []),       \
            ('Jon', [])     ])  ])

def gen1 (family):
    "Return the name of the 1st generation of family."
    return family[0]

def gen2 (family):
    "Return a list of the names of the 2nd generation of family."
    return [child[0] for child in family[1]]

def all (family):
    "Return a list of names of all persons in the tree family."
    (name, children) = family
    descendants = concat([all(child) for child in children])
    return [name] + descendants

def search (family, name):
    "Search family for the named person and return the corresponding subtree. \
     Return () if name is not found. Assume that names are unique."
    (fname, fchildren) = family
    if fname == name:
        return family
    else:
        return search_list(fchildren, name)

def search_list (families, name):
    "Search the list families for the named person with name and \
     return the corresponding subtree. Return () if name is not found."
    if len(families) == 0:
        return ()
    else:
        fam = search(families[0], name)
        if fam != ():
            return fam
        else:
            return search_list(families[1:], name)

def generation (family, k):
    "Return a list of persons in the k'th generation of family."
    (name, children) = family
    if k == 1:
        return [name]
    else:
        return concat([generation(child, k-1) for child in children])

def parent (family, name1, name2):
    "Return True iff the person named name1 is a parent of \
     the person named name2 in family."
    subfamily = search(family, name1)
    if subfamily != ():
        for child in subfamily[1]:
            if child[0] == name2:
                return True
        return False
    else:
        return False

def descendants (family, name):
    "Return a list of names of all descendants of the named person in family."
    subfamily = search(family, name)
    if subfamily != ():
        return all(subfamily)
    else:
        return []

def concat (lists):
    "Return the concatenation of a list of lists."
    cat = []
    for l in lists:
        cat += l
    return cat