Hash tables

from time import time


class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

    def __str__(self):
        return "<Node: (%s, %s), next: %s>" % (self.key, self.value, self.next != None)

    def __repr__(self):
        return str(self)


class HashTable:
    def __init__(self, initial_capacity):
        self.capacity = initial_capacity
        self.size = 0
        self.buckets = [None] * self.capacity

    def hash(self, key):
        hashsum = 0
        for idx, c in enumerate(key):
            hashsum += (idx + len(key)) ** ord(c)
            hashsum = hashsum % self.capacity
        return hashsum

    def insert(self, key, value,):
        self.size += 1
        index = self.hash(key)
        node = self.buckets[index]
        if node is None:
            self.buckets[index] = Node(key, value,)
            return
        prev = node
        while node is not None:
            prev = node
            node = node.next
        prev.next = Node(key, value,)

    def find(self, key):
        index = self.hash(key)
        node = self.buckets[index]
        while node is not None and node.key != key:
            node = node.next
        if node is None:
            print("Не знайдено")
            return None
        else:
            return node.key, node.value,

    def remove(self, key):
        index = self.hash(key)
        node = self.buckets[index]
        prev = None
        while node is not None and node.key != key:
            prev = node
            node = node.next
        if node is None:
            return None
        else:
            self.size -= 1
            result = node.value
            if prev is None:
                self.buckets[index] = node.next
            else:
                prev.next = prev.next.next
            return result


class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.child = []


class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t

    def search(self, k, x=None):
        if x is not None:
            i = 0
            while i < len(x.keys) and k > x.keys[i][0]:
                i += 1
            if i < len(x.keys) and k == x.keys[i][0]:
                return (x, i)
            elif x.leaf:
                return None
            else:
                return self.search(k, x.child[i])
        else:
            return self.search(k, self.root)

    def printTree(self, x, l=0):
        print("Level ", l, " ", len(x.keys), end=":")
        for i in x.keys:
            print(i, end=" ")
        print()
        l += 1
        if len(x.child) > 0:
            for i in x.child:
                self.printTree(i, l)

    def insert(self, k):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            temp = BTreeNode()
            self.root = temp
            temp.child.insert(0, root)
            self.splitChild(temp, 0)
            self.insertNonFull(temp, k)
        else:
            self.insertNonFull(root, k)

    def insertNonFull(self, x, k):
        i = len(x.keys) - 1
        if x.leaf:
            x.keys.append((None, None))
            while i >= 0 and k[0] < x.keys[i][0]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = k
        else:
            while i >= 0 and k[0] < x.keys[i][0]:
                i -= 1
            i += 1
            if len(x.child[i].keys) == (2 * self.t) - 1:
                self.splitChild(x, i)
                if k[0] > x.keys[i][0]:
                    i += 1
            self.insertNonFull(x.child[i], k)

    def splitChild(self, x, i):
        t = self.t
        y = x.child[i]
        z = BTreeNode(y.leaf)
        x.child.insert(i + 1, z)
        x.keys.insert(i, y.keys[t - 1])
        z.keys = y.keys[t: (2 * t) - 1]
        y.keys = y.keys[0: t - 1]
        if not y.leaf:
            z.child = y.child[t: 2 * t]
            y.child = y.child[0: t - 1]

    def delete(self, x, k):
        t = self.t
        i = 0
        while i < len(x.keys) and k[0] > x.keys[i][0]:
            i += 1
        if x.leaf:
            if i < len(x.keys) and x.keys[i][0] == k[0]:
                x.keys.pop(i)
                return
            return
        if i < len(x.keys) and x.keys[i][0] == k[0]:
            return self.deleteInternalNode(x, k, i)
        elif len(x.child[i].keys) >= t:
            self.delete(x.child[i], k)
        else:
            if i != 0 and i + 2 < len(x.child):
                if len(x.child[i - 1].keys) >= t:
                    self.deleteSibling(x, i, i - 1)
                elif len(x.child[i + 1].keys) >= t:
                    self.deleteSibling(x, i, i + 1)
                else:
                    self.deleteMerge(x, i, i + 1)
            elif i == 0:
                if len(x.child[i + 1].keys) >= t:
                    self.deleteSibling(x, i, i + 1)
                else:
                    self.deleteMerge(x, i, i + 1)
            elif i + 1 == len(x.child):
                if len(x.child[i - 1].keys) >= t:
                    self.deleteSibling(x, i, i - 1)
                else:
                    self.deleteMerge(x, i, i - 1)
            self.delete(x.child[i], k)

    def deleteInternalNode(self, x, k, i):
        t = self.t
        if x.leaf:
            if x.keys[i][0] == k[0]:
                x.keys.pop(i)
                return
            return
        if len(x.child[i].keys) >= t:
            x.keys[i] = self.deletePredecessor(x.child[i])
            return
        elif len(x.child[i + 1].keys) >= t:
            x.keys[i] = self.deleteSuccessor(x.child[i + 1])
            return
        else:
            self.deleteMerge(x, i, i + 1)
            self.deleteInternalNode(x.child[i], k, self.t - 1)

    def deletePredecessor(self, x):
        if x.leaf:
            return x.pop()
        n = len(x.keys) - 1
        if len(x.child[n].keys) >= self.t:
            self.deleteSibling(x, n + 1, n)
        else:
            self.deleteMerge(x, n, n + 1)
        self.deletePredecessor(x.child[n])

    def deleteSuccessor(self, x):
        if x.leaf:
            return x.keys.pop(0)
        if len(x.child[1].keys) >= self.t:
            self.deleteSibling(x, 0, 1)
        else:
            self.deleteMerge(x, 0, 1)
            self.deleteSuccessor(x.child[0])

    def deleteMerge(self, x, i, j):
        cnode = x.child[i]
        if j > i:
            rsnode = x.child[j]
            cnode.keys.append(x.keys[i])
            for k in range(len(rsnode.keys)):
                cnode.keys.append(rsnode.keys[k])
                if len(rsnode.child) > 0:
                    cnode.child.append(rsnode.child[k])
            if len(rsnode.child) > 0:
                cnode.child.append(rsnode.child.pop())
            new = cnode
            x.keys.pop(i)
            x.child.pop(j)
        else:
            lsnode = x.child[j]
            lsnode.keys.append(x.keys[j])
            for i in range(len(cnode.keys)):
                lsnode.keys.append(cnode.keys[i])
                if len(lsnode.child) > 0:
                    lsnode.child.append(cnode.child[i])
            if len(lsnode.child) > 0:
                lsnode.child.append(cnode.child.pop())
            new = lsnode
            x.keys.pop(j)
            x.child.pop(i)
        if x == self.root and len(x.keys) == 0:
            self.root = new

    def deleteSibling(self, x, i, j):
        cnode = x.child[i]
        if i < j:
            rsnode = x.child[j]
            cnode.keys.append(x.keys[i])
            x.keys[i] = rsnode.keys[0]
            if len(rsnode.child) > 0:
                cnode.child.append(rsnode.child[0])
                rsnode.child.pop(0)
            rsnode.keys.pop(0)
        else:
            lsnode = x.child[j]
            cnode.keys.insert(0, x.keys[i - 1])
            x.keys[i - 1] = lsnode.keys.pop()
            if len(lsnode.child) > 0:
                cnode.child.insert(0, lsnode.child.pop())
def main():
    test = HashTable(50)
    n = int(input("Уведіть розмір\n"))
    start = time()
    for i in range(0, n):
        test.insert("Name " + str(i),("City " + str(i),i))
    end = time()
    for k in range(0,n):
        print(test.find("Name " + str(k)))
    print("Час заповнення елементами: {}".format(end-start))
    a = int(input("З якого елемента починаєм пошук\n"))
    b = int(input("З якого елемента закінчуєм пошук\n"))
    start = time()
    for k in range(a, b):
        print(test.find(str(k)))
    end = time()
    print("Час знаходження елементів:{}".format(end - start))
    print("----------------------------------------------")
    print('B tree з послідовними елементами')
    B1 = BTree(100)
    start = time()
    for i in range(0, n):
        B1.insert((i, 2 * i))
    end = time()
    B1.printTree(B1.root)
    print('Час заповнення елементами: {}'.format(end - start))
    a1 = int(input("З якого елемента починаєм пошук\n"))
    b1 = int(input("З якого елемента закінчуєм пошук\n"))
    start = time()
    for k in range(a1,b1):
        if B1.search(k) is None:
            print("Не знайдено")
        else:
            print("Знайдено")
    end = time()
    print('Час пошуку:{}'.format(end - start))


if __name__ == "__main__":
    main()