Séminaire 6 : Structures de données — Tableaux, Listes chaînées, Files, Piles, Tables de hachage

# ---------------------------------------------------------------------------
# Singly Linked List implementation
# ---------------------------------------------------------------------------

class Node:
    """A single node in a singly linked list."""

    def __init__(self, data):
        self.data = data   # The payload stored in this node
        self.next = None   # reference to the next node (None = end of list)


class LinkedList:
    """Singly linked list: O(1) prepend at head, O(n) append at tail (traverse to end)."""

    def __init__(self):
        self.head = None   # The first node; None when the list is empty
        self.size = 0      # Track length to avoid O(n) traversal for len()

    # ------------------------------------------------------------------
    # Insertion operations
    # ------------------------------------------------------------------

    def prepend(self, data):
        """Insert a new node at the FRONT of the list — O(1)."""
        new_node = Node(data)
        new_node.next = self.head   # New node points to old head
        self.head = new_node        # Head now points to new node
        self.size += 1

    def append(self, data):
        """Insert a new node at the BACK of the list — O(n)."""
        new_node = Node(data)
        if self.head is None:       # Empty list: new node becomes head
            self.head = new_node
        else:
            # Traverse to the last node
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = new_node  # Attach new node at the tail
        self.size += 1

    def insert_after(self, target_data, new_data):
        """Insert new_data immediately after the first node with target_data — O(n)."""
        current = self.head
        while current is not None:
            if current.data == target_data:
                new_node = Node(new_data)
                new_node.next = current.next
                current.next = new_node
                self.size += 1
                return
            current = current.next
        raise ValueError(f"Value {target_data} not found in list.")

    # ------------------------------------------------------------------
    # Deletion
    # ------------------------------------------------------------------

    def delete(self, data):
        """Remove the first node containing data — O(n)."""
        if self.head is None:
            raise IndexError("Cannot delete from an empty list.")

        # Special case: the node to delete is the head
        if self.head.data == data:
            self.head = self.head.next
            self.size -= 1
            return

        # General case: traverse until we find the predecessor of the target node
        current = self.head
        while current.next is not None:
            if current.next.data == data:
                current.next = current.next.next  # Bypass the target node
                self.size -= 1
                return
            current = current.next
        raise ValueError(f"Value {data} not found in list.")

    # ------------------------------------------------------------------
    # Traversal / utility
    # ------------------------------------------------------------------

    def to_list(self):
        """Return the linked list contents as a Python list — O(n)."""
        result = []
        current = self.head
        while current is not None:
            result.append(current.data)
            current = current.next
        return result

    def __repr__(self):
        return ' -> '.join(str(v) for v in self.to_list()) + ' -> None'


# ---------------------------------------------------------------------------
# Demonstration
# ---------------------------------------------------------------------------
ll = LinkedList()
for val in [10, 20, 30, 40, 50]:
    ll.append(val)
print("After appending 10..50 :", ll)

ll.prepend(5)
print("After prepend(5)       :", ll)

ll.insert_after(20, 25)
print("After insert_after(20,25):", ll)

ll.delete(25)
print("After delete(25)       :", ll)

# ---------------------------------------------------------------------------
# Stack implementation using a Python list as the underlying storage.
# The END of the list is the TOP of the stack (append/pop are both O(1)).
# ---------------------------------------------------------------------------

class Stack:
    """LIFO stack backed by a Python list."""

    def __init__(self, capacity=None):
        """
        Parameters
        ----------
        capacity : int or None
            Maximum number of elements (None = unbounded).
        """
        self._data = []            # Internal storage
        self._capacity = capacity  # Optional fixed capacity

    def push(self, item):
        """Push item onto the top of the stack — O(1) amortised."""
        if self._capacity is not None and len(self._data) >= self._capacity:
            raise OverflowError("Stack overflow: capacity exceeded.")
        self._data.append(item)

    def pop(self):
        """Remove and return the top element — O(1)."""
        if self.is_empty():
            raise IndexError("Stack underflow: cannot pop from an empty stack.")
        return self._data.pop()  # list.pop() removes from the end in O(1)

    def peek(self):
        """Return the top element without removing it — O(1)."""
        if self.is_empty():
            raise IndexError("Stack is empty.")
        return self._data[-1]

    def is_empty(self):
        """Return True if the stack contains no elements — O(1)."""
        return len(self._data) == 0

    def size(self):
        """Return the number of elements in the stack — O(1)."""
        return len(self._data)

    def __repr__(self):
        if self.is_empty():
            return "Stack(empty)"
        return "Stack(bottom -> top): " + str(self._data)


# Quick demo (no plotting — see slides for LIFO animation)
s = Stack()
for v in [10, 20, 30, 40]:
    s.push(v)
print(s)

def is_balanced(expr):
    stack = Stack()
    for ch in expr:
        if ch == '(':
            stack.push(ch)
        elif ch == ')':
            if stack.is_empty():
                return False   # ')' with no matching '('
            stack.pop()
    return stack.is_empty()   # True only if all '(' were matched


print(is_balanced('((()))'))  # True
print(is_balanced('(()('))   # False
print(is_balanced('())'))    # False

from collections import deque

# ---------------------------------------------------------------------------
# Queue implementation using collections.deque
# deque (double-ended queue) provides O(1) appendleft and pop from either end.
# We use: append() to enqueue at the right, popleft() to dequeue from the left.
# ---------------------------------------------------------------------------

class Queue:
    """FIFO queue backed by collections.deque."""

    def __init__(self):
        self._data = deque()  # deque gives O(1) at both ends

    def enqueue(self, item):
        """Add item to the BACK of the queue — O(1)."""
        self._data.append(item)

    def dequeue(self):
        """Remove and return the FRONT element — O(1)."""
        if self.is_empty():
            raise IndexError("Queue underflow: cannot dequeue from an empty queue.")
        return self._data.popleft()

    def peek(self):
        """Return the front element without removing it — O(1)."""
        if self.is_empty():
            raise IndexError("Queue is empty.")
        return self._data[0]

    def is_empty(self):
        return len(self._data) == 0

    def size(self):
        return len(self._data)

    def __repr__(self):
        return "Queue(front -> back): " + str(list(self._data))


# ---------------------------------------------------------------------------
# Demonstrate FIFO vs LIFO
# ---------------------------------------------------------------------------
print("=== QUEUE (FIFO) ===")
q = Queue()
for v in [1, 2, 3, 4, 5]:
    q.enqueue(v)
    print(f"  enqueue({v}) -> {q}")

print()
for _ in range(3):
    val = q.dequeue()
    print(f"  dequeue() -> {val}  |  {q}")

print()
print("=== STACK (LIFO) ===")
st = Stack()
for v in [1, 2, 3, 4, 5]:
    st.push(v)
    print(f"  push({v}) -> {st}")

print()
for _ in range(3):
    val = st.pop()
    print(f"  pop()     -> {val}  |  {st}")

# ---------------------------------------------------------------------------
# Python's built-in hash() — used by dict, set, and our SimpleHashMap
# ---------------------------------------------------------------------------
# hash() maps a key to an integer. In one run of the program, the same key
# always gets the same hash (so lookups are consistent).

print("hash('hello') =", hash("hello"))
print("hash('hello') again =", hash("hello"))  # same value in one run
print("hash(42)       =", hash(42))
print("hash((1, 2))   =", hash((1, 2)))  # tuple OK if contents are hashable

# Tables only have finitely many "lockers" (buckets). Modulo picks which one:
M = 8
for key in ["cat", "dog", "bird", "Ada", "Bob"]:
    bucket = hash(key) % M
    print(f"{key!r:6}  ->  bucket {bucket}")

# Only *hashable* types work — lists and dicts are not allowed as dict keys:
# hash([])   # TypeError: unhashable type: 'list'

# ---------------------------------------------------------------------------
# A simple hash map from scratch using SEPARATE CHAINING for collision resolution.
# Each bucket is a list of (key, value) pairs (a chain).
# ---------------------------------------------------------------------------

class SimpleHashMap:
    """
    Hash map with separate chaining.
    Average-case O(1) get/set/delete (assuming a good hash and low load factor).
    """

    DEFAULT_CAPACITY = 16   # Number of buckets; should be a power of 2
    LOAD_FACTOR_THRESHOLD = 0.75  # Resize when this fraction of buckets are occupied

    def __init__(self, capacity=DEFAULT_CAPACITY):
        self._capacity = capacity
        self._buckets = [[] for _ in range(self._capacity)]  # Each bucket = a chain (list)
        self._size = 0   # Number of key-value pairs stored

    # ------------------------------------------------------------------
    # Internal hash function
    # ------------------------------------------------------------------

    def _bucket_index(self, key):
        """Map a key to a bucket index using Python's built-in hash."""
        return hash(key) % self._capacity

    # ------------------------------------------------------------------
    # Core operations
    # ------------------------------------------------------------------

    def put(self, key, value):
        """
        Insert or update key -> value.
        Average O(1); O(n) worst case (all keys collide into one bucket).
        """
        idx = self._bucket_index(key)
        chain = self._buckets[idx]

        # Check if key already exists in the chain -> update
        for i, (k, v) in enumerate(chain):
            if k == key:
                chain[i] = (key, value)   # Update value in place
                return

        # Key not found -> append new pair
        chain.append((key, value))
        self._size += 1

        # Resize if load factor exceeded
        if self._size / self._capacity > self.LOAD_FACTOR_THRESHOLD:
            self._resize()

    def get(self, key, default=None):
        """Return the value associated with key, or default if not found."""
        idx = self._bucket_index(key)
        for k, v in self._buckets[idx]:
            if k == key:
                return v
        return default

    def delete(self, key):
        """Remove key from the map. Raise KeyError if not found."""
        idx = self._bucket_index(key)
        chain = self._buckets[idx]
        for i, (k, v) in enumerate(chain):
            if k == key:
                chain.pop(i)
                self._size -= 1
                return
        raise KeyError(key)

    def _resize(self):
        """Double capacity and rehash all entries — O(n)."""
        old_buckets = self._buckets
        self._capacity *= 2
        self._buckets = [[] for _ in range(self._capacity)]
        self._size = 0
        for chain in old_buckets:
            for k, v in chain:
                self.put(k, v)   # Re-insert into new bucket array

    def load_factor(self):
        return self._size / self._capacity

    def __repr__(self):
        items = []
        for chain in self._buckets:
            items.extend(chain)
        return '{' + ', '.join(f'{k!r}: {v!r}' for k, v in items) + '}'


# ---------------------------------------------------------------------------
# Demonstrate the hash map
# ---------------------------------------------------------------------------
hm = SimpleHashMap(capacity=8)
students = [('Alice', 92), ('Bob', 85), ('Charlie', 78), ('Diana', 95), ('Eve', 88)]
for name, grade in students:
    hm.put(name, grade)

print("HashMap:", hm)
print(f"Load factor: {hm.load_factor():.2f}")
print(f"get('Alice') = {hm.get('Alice')}")
print(f"get('Zara')  = {hm.get('Zara', 'Not found')}")

hm.put('Alice', 97)   # Update existing key
print(f"After update, get('Alice') = {hm.get('Alice')}")

def merge_sorted(a: list, b: list) -> list:
    """Return merged sorted list in O(len(a)+len(b))."""
    out = []
    i, j = 0, 0
    # Merge while both lists still have elements
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            # YOUR CODE: append a[i] to out and increment i
            pass
        else:
            # YOUR CODE: append b[j] to out and increment j
            pass
    # Remainder of the longer list
    while i < len(a):
        # YOUR CODE: append from a
        pass
    while j < len(b):
        # YOUR CODE: append from b
        pass
    return out

def reverse_linked_list(ll: "LinkedList") -> None:
    """Reverse nodes; update ll.head (ll.size unchanged)."""
    # --- Level A (easier): rebuild using to_list + prepend (default skeleton) ---
    vals = ll.to_list()
    ll.head = None
    ll.size = 0
    for v in reversed(vals):
        pass  # YOUR CODE: prepend v onto ll

    # --- Level B (pointer reverse): comment out Level A above, then implement ---
    # prev = None
    # cur = ll.head
    # while cur is not None:
    #     nxt = cur.next
    #     cur.next = prev
    #     prev = cur
    #     cur = nxt
    # ll.head = prev

def is_balanced_brackets(expression: str) -> bool:
    """True if (), [], {} are all matched in LIFO order."""
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = Stack()
    for ch in expression:
        if ch in "([{":
            stack.push(ch)
        elif ch in ")]}":
            if stack.is_empty():
                return False
            # YOUR CODE: pop opening bracket and compare to pairs[ch]
            pass
        # else: ignore non-bracket characters
    return stack.is_empty()

def hot_potato(names: list[str], k: int) -> str:
    """Last remaining name using Queue and the rules in Exercise 2.4."""
    q = Queue()
    for n in names:
        q.enqueue(n)
    while q.size() > 1:
        for _ in range(k - 1):
            # YOUR CODE: move front player to the rear (same pattern as the slides)
            pass
        # YOUR CODE: eliminate the player at the front after those rotations
        pass
    return q.dequeue()

def word_counts(text: str) -> "SimpleHashMap":
    """Word frequencies using SimpleHashMap only."""
    m = SimpleHashMap()
    for w in text.split():
        c = m.get(w, 0)
        # YOUR CODE: store count + 1 for this word
        pass
    return m