set_ds.py

from typing import List, Any


class Node:
    def __init__(self, key, nxt=None):
        self.key: str = key
        self.nxt: Node = nxt

    def __repr__(self):
        return str(self.key)


class LinkedList:
    def __init__(self, head=None):
        self.head: Node = head

    def insert(self, key):
        new_node = Node(key, self.head)
        self.head = new_node

    def search(self, key):
        node = self.head
        while node:
            if node.key == key:
                return node
            node = node.nxt
        return None

    def delete(self, key):
        if self.head and self.head.key == key:
            self.head = self.head.nxt
            return True
        else:
            node = self.head
            while node and node.nxt and node.nxt.key != key:
                node = node.nxt
            if node:
                node.nxt = node.nxt.nxt
                return True
        return False

    def __repr__(self):
        res = ''
        head = self.head
        while head:
            res += str(head) + ' - > '
            head = head.nxt
        res += 'null'
        return res


class Set:
    def __init__(self):
        self.capacity: int = 30
        self.size: int = 0
        self.load_factor: float = 0.75
        self.slots: List[LinkedList] = [LinkedList() for _ in range(self.capacity)]

    def hash_func(self, key):
        total = 0
        for ch in key:
            total += ord(ch)
        return total % self.capacity

    def rehash(self):
        old = self.slots
        self.capacity *= 2
        self.size = 0
        self.slots = [LinkedList() for _ in range(self.capacity)]
        for slot in old:
            node = slot.head
            while node:
                self.insert(node.key)
                node = node.nxt

    def insert(self, key):
        index = self.hash_func(key)
        node = self.slots[index].search(key)
        if not node:
            self.slots[index].insert(key)
            self.size += 1
            if self.size/self.capacity > self.load_factor:
                self.rehash()

    def search(self, key):
        index = self.hash_func(key)
        node = self.slots[index].search(key)
        return node is not None

    def get(self, key):
        index = self.hash_func(key)
        node = self.slots[index].search(key)
        return node.value if node else None

    def delete(self, key):
        index = self.hash_func(key)
        if self.slots[index].delete(key):
            self.size -= 1

    def elems(self):
        elems_arr = []
        for ll in self.slots:
            ptr = ll.head
            while ptr:
                elems_arr.append(ptr.key)
                ptr = ptr.nxt
        return elems_arr

    def union(self, other):
        union_set = Set()
        for elem in self.elems():
            union_set.insert(elem)
        for elem in other.elems():
            union_set.insert(elem)
        return union_set

    def intersection(self, other):
        intersection_set = Set()
        for elem in self.elems():
            if other.search(elem):
                intersection_set.insert(elem)
        return intersection_set

    def difference(self, other):
        difference_set = Set()
        for elem in self.elems():
            if not other.search(elem):
                difference_set.insert(elem)
        return difference_set

    def is_subset(self, other):
        for elem in self.elems():
            if not other.search(elem):
                return False
        return True

    def __repr__(self):
        return str(self.elems()).replace('[', '{').replace(']', '}')


set_1 = Set()
for elem in ['A', 'C', 'A', 'D', 'E', 'A', 'D', 'F', 'C']:
    set_1.insert(elem)
print(set_1)  # {'A', 'C', 'D', 'E', 'F'}
set_2 = Set()
for elem in ['A', 'B', 'D', 'X', 'R', 'R', 'R']:
    set_2.insert(elem)
print(set_2)  # {'A', 'B', 'D', 'R', 'X'}
print(set_1.search('C'))  # True
print(set_2.search('C'))  # False
print(set_1.union(set_2))  # {'A', 'B', 'C', 'D', 'E', 'F', 'R', 'X'}
print(set_1.intersection(set_2))  # {'A', 'D'}
print(set_1.difference(set_2))  # {'C', 'E', 'F'}
print(set_2.difference(set_1))  # {'B', 'R', 'X'}