def h1_func(key, table_size):
    res = 0
    for i in range(len(key)):
        res += (ord(key[-i - 1]) * (19 ** i)) % table_size
    return res % table_size


class Node:
    def __init__(self, key, data, next_element=None):
        self.key = key
        self.data = data
        self.next_element: Node = next_element


class Chain:
    def __init__(self, size=8):
        self.fill_factor = 0.7
        self.table_size = size  # Размер таблицы
        self.bucket_size = 0    # Количество головных узлов
        self.size = 0           # Количество элементов
        self.slots: list[Node] = [None] * self.table_size
        self.insert_iterations = []
        self.search_iterations = []
        self.remove_iterations = []

    def resize(self):
        self.table_size *= 2
        self.size = 0
        self.bucket_size = 0
        self.slots, old_slots = [None] * self.table_size, self.slots
        for i in old_slots:
            while i is not None:
                self.insert(i.key, i.data)
                i = i.next_element

    def insert(self, key, data):
        if (self.size + 1) > self.fill_factor * self.table_size:
            self.resize()
        h = h1_func(key, self.table_size)
        cell: Node = self.slots[h]
        node = Node(key, data)
        i = 1
        if cell is None:
            self.size += 1
            self.bucket_size += 1
            self.slots[h] = node
            self.insert_iterations.append(i)
            return
        while cell is not None:
            if cell.key == key:
                self.insert_iterations.append(i)
                return
            if cell.next_element is None:
                break
            cell = cell.next_element
            i += 1
        cell.next_element = node
        self.size += 1
        self.insert_iterations.append(i)

    def search(self, key):
        result = None
        h = h1_func(key, self.table_size)
        cell = self.slots[h]
        i = 1
        if not cell:
            self.search_iterations.append(i)
            return result
        while cell:
            if cell.key == key:
                result = cell.data
                break
            cell = cell.next_element
            i += 1
        self.search_iterations.append(i)
        return result

    def delete(self, key):
        h = h1_func(key, self.table_size)
        cell: Node = self.slots[h]
        i = 1
        if cell is None:
            self.remove_iterations.append(i)
            return
        if cell.key == key:
            if cell.next_element is None:
                self.bucket_size -= 1
            self.size -= 1
            self.slots[h] = cell.next_element
            self.remove_iterations.append(i)
            return
        while cell.next_element is not None:
            if cell.next_element.key == key:
                self.size -= 1
                cell.next_element = cell.next_element.next_element
                self.remove_iterations.append(i)
                return
            i += 1
            cell = cell.next_element
        self.remove_iterations.append(i)
        return

    def print(self):
        out: list[list[str]] = []
        for el in self.slots:
            arr: list[str] = []
            while el is not None:
                arr.append(f"{el.key} : {el.data}")
                el = el.next_element
            out.append(arr)
        print(f"Table size: {self.table_size}, Size: {self.size}, Bucket size: {self.bucket_size}")
        print(out)


if __name__ == '__main__':
    data: list[str] = []
    with open("test.txt", 'r') as f:
        s = f.readline().rstrip()
        while s != '':
            data.append(s)
            s = f.readline().rstrip()
    chain = Chain()

    print(data)
    for s in data:
        chain.insert(s, s)
    chain.print()