import timeit
import gc

def best_case_input(n: int) -> list:
    return [1 for i in range(n)]

def worst_case_input(n: int) -> list:
    return [i for i in range(n)]

def distinct1(l: list) -> list:
    d = []
    for x in l:
        if x not in d:
            d.append(x)
    return d

def distinct2(l: list) -> list:
    d = set()
    for x in l:
        if x not in d:
            d.add(x)
    return d

def time(fn, arg):
    gc.disable()
    start = timeit.default_timer()
    fn(arg)
    end = timeit.default_timer()
    gc.enable()
    return end - start

def graph(name: str, sizes: list, times: list):
    import matplotlib.pyplot as plt

    plt.figure()
    plt.scatter(sizes, times)
    plt.savefig(name + ".png")
    plt.close()

def generate_graphs():
    sizes = [100, 500, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000]

    # best case graphs

    inputs = [best_case_input(size) for size in sizes]
    results1 = [time(distinct1, arg) for arg in inputs]
    results2 = [time(distinct2, arg) for arg in inputs]
    graph("best1", sizes, results1)
    graph("best2", sizes, results2)

    # worst case graphs

    inputs = [worst_case_input(size) for size in sizes]
    results1 = [time(distinct1, arg) for arg in inputs]
    results2 = [time(distinct2, arg) for arg in inputs]
    graph("worst1", sizes, results1)
    graph("worst2", sizes, results2)

if __name__ == '__main__':
   generate_graphs()