[TODO] DSAL_AS Ass 1 - Quad Probing

#### Quadratic Probing method for handling collisions

def insert(hasht, n):
    key = int(input("Enter the value to be inserted: "))
    loc = key % n
    if (hasht[loc] == -1):
        hasht[loc] = key
    else:
        i = 0
        mloc = loc
        while (hasht[mloc] != -1):
            mloc = loc
            mloc = (mloc + (i ** 2)) % n
            i += 1
        hasht[mloc] = key

def display(hasht):
    print("\nHashtable: ", hasht)


def search(hasht, size):
    key = int(input("Enter the element to be searched: "))
    start = key % size
    i = start
    flag = 0
    found = -1
    while (True):
        if (hasht[i] == key):
            flag = 1
            found = i
            break
        else:
            flag = 0
            inc = 0
        inc += 1
        i = (i + (inc ** 2)) % size
        if (inc > size):
            flag = 0
            break

    if (flag == 0):
        print("\nKey not found")
    if (flag == 1):
        print("\nKey found at position: ", found)

def main():
    size = int(input("Enter the size of the Hash Table: "))

    hasht = []
    for i in range(0, size):
        hasht.append(-1)

    count = 0

    while (True):
        print("\n----- MENU -----")
        print("1. Insert")
        print("2. Display")
        print("3. Search")
        print("4. Exit")
        ch = input("Enter your choice: ")
        if ch == "1":
            if (count >= size):
                print("\nCannot Insert! The Hash Table is full")
            else:
                insert(hasht, size)
                display(hasht)
                count += 1
        elif ch == "2":
            display(hasht)
        elif ch == "3":
            search(hasht, size)
        elif ch == "4":
            return4
        else:
            print("Invalid Input")


main()