from assignment_lists_sortingandsearching_f22 import DoublyLinkedList, Node
import matplotlib.pyplot as plt
from time import time
from random import randint

def binstest():
    min, max, offset = 0, 500, 20
    times = []
    dl = DoublyLinkedList()
    [ dl.add_last(Node(i+offset)) for i in range(max) ]
    print(dl)
    for i in range(min + offset, max + offset):
        t0 = time()
        s = dl.binary_search(i)
        times.append(time() - t0)
        j = i - offset
        print(f"{i}\t{j}\t{s}")
    times.sort()
    plt.yscale('log')
    plt.plot(times)
    plt.show()
    print("Searching for value not in list")
    print(dl.binary_search(0))

def bstest():
    max = 20
    dl = DoublyLinkedList()
    [ dl.add_first(Node(i)) for i in range(max)]
    print(dl)
    dl.bubble_sort()
    print(dl, "\n")

    dl = DoublyLinkedList()
    [ dl.add_first(Node(randint(0, max))) for i in range(max) ]
    l = dl.size()
    print(dl)
    dl.bubble_sort()
    print(dl, "\n")
    assert dl.size() == l

    dl = DoublyLinkedList()
    [ dl.add_last(Node(i)) for i in range(max)]
    print(dl)
    dl.bubble_sort()
    print(dl)

def itest():
    max = 20
    dl = DoublyLinkedList()
    [ dl.add_first(Node(i)) for i in range(max)]
    print(dl)
    dl.insertion_sort()
    print(dl, "\n")

    dl = DoublyLinkedList()
    [ dl.add_first(Node(randint(0, max))) for i in range(max) ]
    l = dl.size()
    print(dl)
    dl.insertion_sort()
    print(dl, "\n")
    assert dl.size() == l

    dl = DoublyLinkedList()
    [ dl.add_last(Node(i)) for i in range(max)]
    print(dl)
    dl.insertion_sort()
    print(dl)

def stest():
    max = 20
    dl = DoublyLinkedList()
    [ dl.add_first(Node(i)) for i in range(max)]
    print(dl)
    dl.selection_sort()
    print(dl, "\n")

    dl = DoublyLinkedList()
    [ dl.add_first(Node(randint(0, max))) for i in range(max) ]
    l = dl.size()
    print(dl)
    dl.selection_sort()
    print(dl, "\n")
    assert dl.size() == l

    dl = DoublyLinkedList()
    [ dl.add_last(Node(i)) for i in range(max)]
    print(dl)
    dl.selection_sort()
    print(dl)

def mtest():
    max = 20
    dl = DoublyLinkedList()
    [ dl.add_first(Node(i)) for i in range(max)]
    print(dl)
    dl.merge_sort()
    print(dl, "\n")

    dl = DoublyLinkedList()
    [ dl.add_first(Node(randint(0, max))) for i in range(max) ]
    l = dl.size()
    print(dl)
    dl.merge_sort()
    print(dl, "\n")
    assert dl.size() == l

    dl = DoublyLinkedList()
    [ dl.add_last(Node(i)) for i in range(max)]
    print(dl)
    dl.merge_sort()
    print(dl)

def qtest():
    max = 20
    dl = DoublyLinkedList()
    [ dl.add_first(Node(i)) for i in range(max)]
    print(dl)
    dl.quick_sort()
    print(dl, "\n")

    dl = DoublyLinkedList()
    [ dl.add_first(Node(randint(0, max))) for i in range(max) ]
    l = dl.size()
    print(dl)
    dl.quick_sort()
    print(dl, "\n")
    assert dl.size() == l

    dl = DoublyLinkedList()
    [ dl.add_last(Node(i)) for i in range(max)]
    print(dl)
    dl.quick_sort()
    print(dl)

def shtest():
    max = 20
    dl = DoublyLinkedList()
    [ dl.add_first(Node(i)) for i in range(max)]
    print(dl)
    dl.shell_sort()
    print(dl, "\n")

    dl = DoublyLinkedList()
    [ dl.add_first(Node(randint(0, max))) for i in range(max) ]
    l = dl.size()
    print(dl)
    dl.shell_sort()
    print(dl, "\n")
    assert dl.size() == l

    dl = DoublyLinkedList()
    [ dl.add_last(Node(i)) for i in range(max)]
    print(dl)
    dl.shell_sort()
    print(dl)

def atest():
    max = 20
    bub = DoublyLinkedList()
    ins = DoublyLinkedList()
    sel = DoublyLinkedList()
    mer = DoublyLinkedList()
    qui = DoublyLinkedList()
    she = DoublyLinkedList()

    for _ in range(max):
        i = randint(0, 100)
        bub.add_last(Node(i))
        ins.add_last(Node(i))
        sel.add_last(Node(i))
        mer.add_last(Node(i))
        qui.add_last(Node(i))
        she.add_last(Node(i))

    print(f"bub {bub}\nins {ins}\nsel {sel}\nmer {mer}\nqui {qui}\nshe {she}\n")

    bub.bubble_sort()
    print(f"bub {bub}")
    ins.insertion_sort()
    print(f"ins {ins}")
    sel.selection_sort()
    print(f"sel {sel}")
    mer.merge_sort()
    print(f"mer {mer}")
    qui.quick_sort()
    print(f"qui {qui}")
    she.shell_sort()
    print(f"she {she}")