## problem 3
import random
class Node:
    def __init__(self, value, levels):
        self.value = value
        self.next = [None]*(levels+1)

class SkipList:
    def __init__(self, no_of_levels, p):
        self.p = p
        self.no_of_levels = no_of_levels
        self.root = Node(-1, no_of_levels)

    def get_random_level(self):
        level = 0
        while True:
            if level+1 >= self.no_of_levels:
                break
            r = random.random()
            if r < self.p:
                level +=1
            else:
                break
        return level

    def insert(self, value):
        previous = [self.root]*(self.no_of_levels+1)
        current = self.root

        cur_level = self.no_of_levels

        while cur_level>=0:
            while current.next[cur_level] and current.next[cur_level].value < value:
                current = current.next[cur_level]
            previous[cur_level] = current
            cur_level-=1


        random_level = self.get_random_level()
        new_node = Node(value, random_level)

        for i in range(random_level+1):
            new_node.next[i] = previous[i].next[i]
            previous[i].next[i] = new_node

    def lookup_search(self, value):
        current = self.root
        cur_level = self.no_of_levels
        while cur_level>=0:
            while current.next[cur_level] and current.next[cur_level].value < value:
                current = current.next[cur_level]
            cur_level-=1
        if current.next[0] and current.next[0].value == value:
            return True
        else:
            self.insert(value)

    def delete(self, value):
        previous = [self.root]*(self.no_of_levels+1)
        current = self.root
        cur_level = self.no_of_levels

        while cur_level>=0:
            while current.next[cur_level] and current.next[cur_level].value < value:
                current = current.next[cur_level]
            previous[cur_level] = current
            cur_level-=1
        current = current.next[0]
        if current and current.value == value:
            for i in range(self.no_of_levels+1):
                if previous[i].next[i] != current:
                    break
                previous[i].next[i] = current.next[i]

    def print(self):
        head = self.root
        for level in range(self.no_of_levels+1):
            current = head.next[level]
            print(f"Level {level}: ")
            while current:
                print(current.value, end=" ")
                current = current.next[level]
            print()


sl = SkipList(3, 0.6)
sl.insert("iub")
sl.insert("usa")
sl.insert("there")
sl.insert("sort")
sl.lookup_search("god")
sl.lookup_search("word")
sl.lookup_search("iub")
sl.print()
sl.delete("there")
sl.print()
sl.insert("myhome")
sl.print()