hash table and stacks stub

hash_table_and_stacks.py

# Python program to demonstrate stack implementation using a linked list. #


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


class Stack:

    def __init__(self):
        """
        Initialize a stack. 
        
        Use a dummy node, which is 
        easier for handling edge cases. 
        """
        self.head = Node("head")
        self.size = 0

    def __str__(self):
        """String representation of the stack"""
        cur = self.head.next
        values_as_str = []
        while cur:
            values_as_str.append(str(cur.value))
            cur = cur.next
        return "->".join(values_as_str)

    def __len__(self):
        """Get the current size of the stack"""
        return self.size
        
    def __bool__(self):
        """Return False if and only if the stack is empty."""
        return bool(len(self))

    def push(self, value):
        """Push a value into the stack."""
        node = Node(value)
        node.next = self.head.next
        self.head.next = node
        self.size += 1
        
    def pop(self):
        """Remove a value from the stack and return."""
        if not len(self):
            raise Exception("Popping from an empty stack")
        remove = self.head.next
        self.head.next = self.head.next.next
        self.size -= 1
        return remove.value


class HashTable:
    """Table de hachage utilisant des stacks en cas de collision entre valeurs."""

    # HASH_TABLE_LENGTH est ici une propriété de CLASSE et non d'INSTANCE
    # Elle peut être "masquée" par une instance qui ferait self.HASH_TABLE_LENGTH = <autre-valeur>
    HASH_TABLE_LENGTH = 100  

    def __init__(self):
        self._hash_array = [Stack() for _ in range(self.HASH_TABLE_LENGTH)]
    
    def insert_value(self, item):
        """
        Insère la valeur `item` dans la Stack située à la 
        position `hash(item) % self.HASH_TABLE_LENGTH` de self._hash_array, 
        seulement si cette valeur n'y existe pas déjà.
        """
        pass

    def __contains__(self, item):
        """Retourne True si et seulement si `item` se trouve dans cette HashTable.""" 
        pass

    def display_items(self):
        """Affiche à l'écran toutes les stacks contenues dans cette HashTable, avec leur position dans self._hash_array"""
        pass


if __name__ == "__main__":

    print("\nTEST de la Stack")
    stack = Stack()
    assert not stack
    
    for i in range(1, 11):
        stack.push(i)
    print(f"Stack: {stack}")
    assert stack
    
    for _ in range(1, 6):
        remove = stack.pop()
        print(f"Pop: {remove}")
    print(f"Stack: {stack}")
    assert stack
    
    print("\nTEST de la HashTable")
    hashtable = HashTable()
    hashtable.display_items()  # Devra afficher quelque chose à l'écran
    hashtable.insert_value(33), "implémentation de la hashtable incorrecte"
    assert 33 in hashtable