Code for Homework 02 of DAA

hw02.py

class Node:
    def __init__(self, data: int):
        self.data: int = data
        self.prev: Node = None
        self.next: Node = None

    def __repr__(self):
        return f'Node({self.data})'

    def __str__(self):
        return f'Node({self.data})'


class DoublyLinkedList:        
    def __init__(self):
        self.head = None
        self.tail = None
        self.num_elements = 0

    def append(self, data: int):
        if self.head is None:
            self.head = self.tail = Node(data)
        else:
            self.tail.next = Node(data)
            self.tail.next.prev = self.tail
            self.tail = self.tail.next
        self.num_elements += 1
        return self

    def insert_at_sorted_order(self, data: int):
        if self.head is None:
            self.head = self.tail = Node(data)
        else:
            if data < self.head.data:
                self.head.prev = Node(data)
                self.head.prev.next = self.head
                self.head = self.head.prev
            elif data > self.tail.data:
                self.tail.next = Node(data)
                self.tail.next.prev = self.tail
                self.tail = self.tail.next
            else:
                next_node: Node = self.head
                while next_node.data < data:
                    next_node = next_node.next
                prev_node: Node = next_node.prev
                cur_node: Node = Node(data)
                cur_node.next = next_node
                cur_node.prev = prev_node
                prev_node.next = cur_node
                next_node.prev = cur_node
        self.num_elements += 1
        return self

    def insert_before_node(self, data: int, node: Node):
        if node == self.head:
            self.head.prev = Node(data)
            self.head.prev.next = self.head
            self.head = self.head.prev
        else:
            prev_node = node.prev
            next_node = node
            cur_node = Node(data)

            cur_node.prev = prev_node
            cur_node.next = next_node

            prev_node.next = cur_node
            next_node.prev = cur_node
        self.num_elements += 1
        return self

    def insert_after_node(self, data: int, node: Node):
        if node == self.tail:
            self.tail.next = Node(data)
            self.tail.next.prev = self.tail
            self.tail = self.tail.next
        else:
            prev_node: Node = node
            next_node: Node = node.next
            cur_node: Node  = Node(data)

            prev_node.next = cur_node
            next_node.prev = cur_node

            cur_node.next = next_node
            cur_node.prev = prev_node
        self.num_elements += 1
        return self

    def insert_node_after_node(self, node: Node, prev_node: Node):
        if prev_node == self.tail:
            prev_node.next = node
            node.prev = prev_node
            self.tail = node
        else:
            next_node: Node = prev_node.next
            node.prev = prev_node
            node.next = next_node

            prev_node.next = node
            next_node.prev = node
        return self

    def insert_node_before_node(self, node: Node, next_node: Node):
        if next_node == self.head:
            next_node.prev = node
            node.next = next_node
            self.head = node
        else:
            prev_node: Node = next_node.prev
            prev_node.next = next_node.prev = node
            node.prev = prev_node
            node.next = next_node
        return self

    def __repr__(self):
        rep = '['
        cur_node: Node = self.head
        while cur_node is not None:
            rep += str(cur_node) + ', '
            cur_node = cur_node.next
        rep += ']'
        return rep

    def __len__(self):
        return self.num_elements
    
    
  import typing
import math


class HTInfo:
    """"
    This class stores augmented information in hashtable
    It stores
            1. reference to min (and max) elements as specified in question
            2. whether the number is really present in Linked List (called S)
            3. Decimal representation of number
    """
    def __init__(self, mini: Node, maxi: Node, in_s: bool, number: int):
        self.min: Node = mini
        self.max: Node = maxi
        self.in_s: bool = in_s
        self.number: int = number

    def __repr__(self):
        return f'MinMax(min: {self.min},\t max: {self.max},\t in S:{"Yes" if self.in_s else "No"},\t number: {self.number})'


class HomeWorkDataStructure:
    def __init__(self, u: int):
        self.u: int = u
        self.binary_length: int = int(math.log2(u))
        self.S: DoublyLinkedList = DoublyLinkedList()
        # Store smallest and largest values at head and tail
        self.S.insert_at_sorted_order(-1).insert_at_sorted_order(u)
        self.hash_table: typing.Dict[str, HTInfo] = dict()

    def is_in_s(self, number: int):
        binary_str = format(number, 'b').zfill(self.binary_length)
        return (binary_str in self.hash_table) and self.hash_table[binary_str].in_s

    def insert(self, data: int):
        # First of all handle special case of 0
        if data == 0:
            cur_node = Node(0)
            self.hash_table['0' * self.binary_length] = HTInfo(cur_node, cur_node, True, 0)
            self.S.insert_node_after_node(cur_node, self.S.head)
            return self

        cur_node = Node(data)
        prefix = data
        # lower_bound: Node = self.S.head
        node_before_which_to_insert: Node = self.S.tail
        while prefix:
            binary_str = format(prefix, 'b').zfill(self.binary_length)
            # if prefix is not in hash_table just set min max to cur_node
            if binary_str not in self.hash_table:
                self.hash_table[binary_str] = HTInfo(cur_node, cur_node, prefix == data, prefix)
            else:
                hash_table_node: HTInfo = self.hash_table[binary_str]
                hash_table_node.in_s |= prefix == data
                # if you're less than min set higher bound to min and update min
                # also set lower bound to lowest
                if data < hash_table_node.min.data:
                    node_before_which_to_insert = hash_table_node.min
                    hash_table_node.min = cur_node
                elif data > hash_table_node.max.data:
                    hash_table_node.max = cur_node
                elif hash_table_node.max.data < node_before_which_to_insert.data:
                    node_before_which_to_insert = hash_table_node.max
            prefix = prefix // 2
        # Now add the item to linked list
        self.S.insert_node_before_node(cur_node, node_before_which_to_insert)

        return self

    def lcp(self, number: int) -> str:
        binary_str = format(number, 'b').zfill(self.binary_length)
        if binary_str in self.hash_table:
            return binary_str

        search_range_low = 0
        search_range_high = len(binary_str)
        while search_range_low < search_range_high:
            mid = (search_range_low + search_range_high) // 2
            if binary_str[:mid].zfill(self.binary_length) in self.hash_table:
                search_range_low = mid + 1
            else:
                search_range_high = mid
        return None if search_range_low == 0 else binary_str[:search_range_low - 1].zfill(self.binary_length)

    def predecessor(self, number: int) -> int or None:
        # if number is less than min (head) there's no predecessor
        if number <= self.S.head.next.data:
            return None
        # if number is greater than max (tail), max is the predecessor
        elif number > self.S.tail.prev.data:
            return self.S.tail.prev.data
        binary_str = format(number, 'b').zfill(self.binary_length)

        if self.is_in_s(number):
            # if number is in S, its predecessor is simply the prev node
            return self.hash_table[binary_str].min.prev.data
        else:
            one_less = number - 1
            one_less_binary = format(one_less, 'b').zfill(self.binary_length)
            if self.is_in_s(one_less):
                return one_less
            else:
                lcp = self.lcp(one_less)
                return self.hash_table[lcp].max.data

    def __repr__(self):
        s = 'List: ' + str(self.S) + '\n'
        for key in self.hash_table:
            s += f'{key}: {self.hash_table[key]}\n'
        return s


if __name__ == '__main__':
    ds = HomeWorkDataStructure(16)
    # ds.insert(1)
    ds.insert(8).insert(3).insert(2).insert(7).insert(11).insert(0)
    print(ds)
    # print(ds.lcp(15))
    print(ds.S)
    for i in range(16):
        binary_str_rep = format(i, 'b').zfill(ds.binary_length)
        print(f'prefix({i} -> {binary_str_rep}): {ds.lcp(i)}\t\t{"IN S" if binary_str_rep in ds.hash_table and ds.hash_table[binary_str_rep].in_s else "NOT IN S"} -> Predecessor of {i} is {ds.predecessor(i)}')
        # print(f'lcp({i}: {binary_str_rep}) = {ds.lcp(i)}')