import random
import matplotlib.pyplot as plt

class ChainingHashMap:
    def __init__(self, size = 10):
        self.elementsAmount = 0
        self.MAX_PER_LIST = 10
        self.size = size
        self.data = [[] for _ in range(size)]
        self.operationToFind = 0

    def key(self, element):
        return element[0]

    def findIndex(self, k):
        self.operationToFind = 0
        h = hash(k) % len(self.data)
        for i in range (len(self.data[h])):
            self.operationToFind += 1
            if self.key(self.data[h][i]) == k:
                return h, i
        return h, -1

    def find(self, k):
        h, i = self.findIndex(k)
        if i == -1: return None
        return self.data[h][i]

    def createNewData(self, newSize):
        newData = [[] for _ in range(newSize)]
        for tab in self.data:
            for el in tab:
                arrIndex = hash(self.key(el)) % len(newData)
                newData[arrIndex].append(el)
        return newData

    def insert(self, *element):
        h, i = self.findIndex(self.key(element))
        if i == -1:
            self.data[h].append(element)
            self.elementsAmount += 1
            if self.elementsAmount > self.size * self.MAX_PER_LIST:
                self.size *= 2
                self.data = self.createNewData(self.size)
        else:
            self.data[h][i] = element

    def delete(self, value):
        h, i = self.findIndex(value)
        if i != -1:
            self.data[h][i] = self.data[h][-1]
            del self.data[h][-1]
            self.elementsAmount -= 1
            isRehashPossible = 4 * self.elementsAmount < self.size * self.MAX_PER_LIST
            if self.elementsAmount > 1 and self.size > 1 and isRehashPossible:
                self.size //= 2
                self.data = self.createNewData(self.size)



def simulateFindOperation():
    mapForSimulation = ChainingHashMap()
    x = []
    y = []
    for i in range(1, 1000):
        operationAverage = 0
        mapForSimulation.insert(i, i)
        for j in range(20):
            rand = random.randint(0, i)
            mapForSimulation.find(rand)
            operationAverage += mapForSimulation.operationToFind
        operationAverage /= 20
        x.append(i)
        y.append(operationAverage)
    plt.plot(x,y)
    plt.show()

simulateFindOperation()

map = ChainingHashMap()
map.insert(5, 1)
map.insert(25, 4)
map.insert(13, 1)
map.insert(15, 7)
map.insert(11, 4)
map.insert(27, 1)
map.insert(19, 7)
print(map.data)
x = map.find(5)
map.delete(5)
map.delete(25)
map.delete(13)
map.delete(15)
map.delete(11)
map.delete(27)
print(x, map.data, sep='\n')