# contributed by GitHub user tttinkl

def assoc(key, records, same_key):
    return (None
            if is_none(records)
            else head(records)
            if same_key(key, head(head(records)))
            else assoc(key, tail(records), same_key))


def make_table(same_key):
    local_table = llist("*table")

    get_value = tail

    def is_table(t):
        return is_pair(t) and head(t) == "*table"

    def lookup(keys):
        def lookup_generic(keys, table):
            if is_none(keys):
                return table
            key_1 = head(keys)
            key_rest = tail(keys)
            record = assoc(key_1, tail(table), same_key)
            if is_none(record):
                return None
            if is_none(key_rest):
                return get_value(record)
            elif is_table(get_value(record)):
                return lookup_generic(key_rest, get_value(record))
            else:
                error("invalid key")
        return lookup_generic(keys, local_table)

    def insert(keys, value):
        def insert_generic(keys, value, table):
            key_1 = head(keys)
            key_rest = tail(keys)
            record = assoc(key_1, tail(table), same_key)
            if is_none(record):
                if is_none(key_rest):
                    set_tail(
                        table,
                        pair(pair(key_1, value), tail(table)))
                else:
                    new_subtable = llist("*table")
                    set_tail(
                        table,
                        pair(pair(key_1, new_subtable), tail(table))
                    )
                    insert_generic(key_rest, value, new_subtable)
            else:
                if is_none(key_rest):
                    set_tail(record, value)
                else:
                    if is_table(get_value(record)):
                        insert_generic(key_rest, value, get_value(record))
                    else:
                        new_subtable = llist("*table")
                        set_tail(record, new_subtable)
                        insert_generic(key_rest, value, new_subtable)
        insert_generic(keys, value, local_table)

    def dispatch(m):
        return (lookup if m == "lookup"
                else insert if m == "insert"
                else (lambda: display(local_table)) if m == "show"
                else error("unknow operation -- table", m))
    return dispatch

table = make_table(equal)

get = table("lookup")
put = table("insert")
show = table("show")

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

print(get(llist("a")))
print(get(llist("b", "c")))
print(get(llist("d", "e", "f")))

put(llist("a", "b"), 1)
print(get(llist("a")))
put(llist("b", "c", "d"), 2)
print(get(llist("b", "c")))
put(llist("b"), 1)
print(get(llist("b")))
