# provided by GitHub user devinryu

def entry(tree):
    return head(tree)

def left_branch(tree):
    return head(tail(tree))

def right_branch(tree):
    return head(tail(tail(tree)))

def make_tree(entry, left, right):
    return llist(entry, left, right)

# kv is llist(key, value)
def adjoin_set(kv, set):
    return (make_tree(kv, None, None)
            if is_none(set)
            else set
            if head(kv) == head(entry(set))
            else make_tree(entry(set),
                           adjoin_set(kv, left_branch(set)),
                           right_branch(set))
            if head(kv) < head(entry(set))
            else make_tree(entry(set),
                           left_branch(set),
                           adjoin_set(kv, right_branch(set))))

def make_table():
    local_table = None
    def lookup(given_key, tree_of_records):
        if is_none(tree_of_records):
            return None
        else:
            this_entry = entry(tree_of_records)
            this_key = head(this_entry)
            return (this_entry
                    if given_key == this_key
                    else lookup(given_key,
                                left_branch(tree_of_records))
                    if given_key < this_key
                    else lookup(given_key,
                                right_branch(tree_of_records)))
    def insert(k, v):
        nonlocal local_table
        record = lookup(k, local_table)
        if is_none(record):
            local_table = adjoin_set(llist(k, v), local_table)
        else:
            set_tail(record, llist(v))
    def get(k):
        return head(tail(lookup(k, local_table)))
    def print():
        return display(local_table)
    def dispatch(m):
        return (get if m == "lookup"
                else insert if m == "insert"
                else print if m == "print"
                else error("error", m))
    return dispatch

t = make_table()
get = t("lookup")
put = t("insert")
print = t("print")

# The test results

put(3, "d")
put(1, "a")
put(2, "b")
put(2, "c")
put(4, "e")
put(5, "f")

print()

print(display(get(2)))  # displays: "c"
