cs_survival_kit.data_structures ¶

@abstractmethod
def __len__(self) -> int:
    """Return the number of elements in the list.

    Returns:
        The number of elements, which is 0 for an empty list.
    """
    raise NotImplementedError

@abstractmethod
def __iter__(self) -> Iterator[T]:
    """Iterate over the elements in position order.

    Yields:
        Each element, starting with the one at position 0.
    """
    raise NotImplementedError

@abstractmethod
def __getitem__(self, index: int) -> T:
    """Return the element at position `index`.

    Args:
        index: The position of the element. Every implementation accepts
            `0 <= index < len(self)`; whether it accepts anything else,
            such as a negative index, is up to the implementation.

    Returns:
        The element at `index`.

    Raises:
        IndexError: If there is no element at `index`.
    """
    raise NotImplementedError

@abstractmethod
def __contains__(self, item: object) -> bool:
    """Return whether `item` is in the list.

    Args:
        item: The value to look for.

    Returns:
        `True` if some element is `item` or equals it, otherwise `False`.
    """
    raise NotImplementedError

@abstractmethod
def __repr__(self) -> str:
    """Return a string showing the class name and the elements in order.

    Returns:
        A string such as `DynamicArray([1, 2, 3])`.
    """
    raise NotImplementedError

@abstractmethod
def append(self, item: T) -> None:
    """Add `item` to the end of the list.

    Afterwards `item` is the last element and `len(self)` is one greater.

    Args:
        item: The element to add.
    """
    raise NotImplementedError

def __len__(self) -> int:
    """Return the number of elements in the array.

    Returns:
        The number of elements in the array.

    Complexity:
        - Time: O(1)
        - Space: O(1)
    """
    return self._size

def __getitem__(self, index: int) -> T:
    """Return the element at `index`.

    Args:
        index: The position of the element. Must satisfy
            `0 <= index < len(self)`.

    Returns:
        The element at `index`.

    Raises:
        IndexError: If `index` is negative or not less than `len(self)`.

    Complexity:
        - Time: O(1)
        - Space: O(1)
    """
    if index < 0 or index >= self._size:
        raise IndexError("index out of range")

    return typing.cast(T, self._items[index])

def __setitem__(self, index: int, item: T) -> None:
    """Replace the element at `index` with `item`.

    Only overwrites an existing element. Use `append` to add one.

    Args:
        index: The position of the element to replace. Must satisfy
            `0 <= index < len(self)`.
        item: The new element.

    Raises:
        IndexError: If `index` is negative or not less than `len(self)`.

    Complexity:
        - Time: O(1)
        - Space: O(1)
    """
    if index < 0 or index >= self._size:
        raise IndexError("index out of range")

    self._items[index] = item

def __iter__(self) -> Iterator[T]:
    """Iterate over the elements from index 0 to `len(self) - 1`.

    Yields:
        Each element, in index order.

    Complexity:
        - Time: O(n) to exhaust the iterator
        - Space: O(1)
    """
    for i in range(self._size):
        yield typing.cast(T, self._items[i])

def __contains__(self, item: object) -> bool:
    """Return whether `item` is in the array.

    Checks the elements in index order and stops at the first match. An
    element matches if it is `item` or equals it, the same rule that
    `list` uses. Unused slots are never examined, so `None in a` is
    `True` only if `None` was actually stored.

    Args:
        item: The value to look for.

    Returns:
        `True` if some element is `item` or equals it, otherwise `False`.

    Complexity:
        - Time: O(n), since the elements are not ordered and each one may
          have to be checked; O(1) if the first element matches
        - Space: O(1)

    Examples:
        >>> a = DynamicArray[int]()
        >>> a.append(1)
        >>> 1 in a, 2 in a
        (True, False)
    """
    for i in range(self._size):
        element = self._items[i]
        if element is item or element == item:
            return True

    return False

def __repr__(self) -> str:
    """Return a string showing the class name and the elements, like `list`.

    Unused slots and the capacity are not shown. Use `capacity` to inspect
    the backing storage.

    Returns:
        A string such as `DynamicArray([1, 2, 3])`.
    """
    return f"{type(self).__name__}({list(self)})"

def append(self, item: T) -> None:
    """Add `item` to the end of the array.

    If the array is full, it first resizes to the capacity returned by the
    growth policy, copying every element, and then stores the item in the
    first free slot. Resizing only when there is no room means every
    allocated slot gets used before the array grows.

    The growth policy's result is checked before anything changes. If it
    is not greater than the current capacity, `ValueError` is raised and
    the array is left exactly as it was.

    Args:
        item: The element to add.

    Raises:
        ValueError: If the array is full and the growth policy returns a
            capacity that is not greater than the current capacity.

    Complexity:
        - Time: O(1) amortized with a geometric growth policy; O(n) for
          the append that triggers a resize
        - Space: O(1) amortized; O(n) for the append that triggers a resize

    Examples:
        >>> a = DynamicArray[str](capacity=2)
        >>> a.append("x")
        >>> a.append("y")  # fills the last free slot; no resize yet
        >>> a.capacity
        2
        >>> a.append("z")  # no free slot, so the array grows first
        >>> a.capacity
        4

        A growth policy that doesn't grow is rejected:

        >>> stuck = DynamicArray[int](capacity=1, growth=lambda c: c)
        >>> stuck.append(1)
        >>> stuck.append(2)
        Traceback (most recent call last):
            ...
        ValueError: growth policy must increase capacity (1 -> 1)
        >>> list(stuck), stuck.capacity
        ([1], 1)
    """
    # if the array is full, resize it according to the growth policy before
    # inserting the new item
    if self._size == self._capacity:
        new_capacity: int = self._growth(self._capacity)

        # validate the growth policy's result before mutating any state so a
        # bad policy leaves the array unchanged
        if new_capacity <= self._capacity:
            raise ValueError(
                "growth policy must increase capacity "
                f"({self._capacity} -> {new_capacity})"
            )

        self._resize(new_capacity)

    # insert the item into the array by its index in the first open position
    self._items[self._size] = item

    # update the size of the array
    self._size = self._size + 1

def pop(self) -> T:
    """Remove and return the last element.

    The freed slot is cleared, so the array no longer holds a reference to
    the element. Capacity is unchanged.

    Returns:
        The element that was at index `len(self) - 1`.

    Raises:
        IndexError: If the array is empty.

    Complexity:
        - Time: O(1)
        - Space: O(1)

    Examples:
        >>> a = DynamicArray[int]()
        >>> a.append(1)
        >>> a.pop()
        1
        >>> a.pop()
        Traceback (most recent call last):
            ...
        IndexError: pop from empty array
    """
    if self._size == 0:
        raise IndexError("pop from empty array")

    pos: int = self._size - 1
    item: T = typing.cast(T, self._items[pos])
    self._items[pos] = None
    self._size = pos

    return item

def __len__(self) -> int:
    """Return the number of elements in the list.

    Returns:
        The number of elements in the list.

    Complexity:
        - Time: O(1), from the stored size count
        - Space: O(1)
    """
    return self._size

def __iter__(self) -> Iterator[T]:
    """Iterate over the elements from head to tail.

    Yields:
        Each element, in list order.

    Complexity:
        - Time: O(n) to exhaust the iterator
        - Space: O(1)
    """
    # establish a node pointer to traverse the linked list
    current_node: _Node[T] | None = self._head

    # while the node pointer points to valid nodes, continue
    # traversing and yielding the current node as you progress
    while current_node is not None:
        yield current_node.item
        current_node = current_node.next

def __getitem__(self, index: int) -> T:
    """Return the element at `index`.

    Nodes are scattered in memory and each one only knows where the next
    node is, so there is no way to compute where element `index` lives.
    The lookup walks `index` links from the head. An array can jump
    straight there because its elements sit at evenly spaced positions.

    Args:
        index: The position of the element. Must satisfy
            `0 <= index < len(self)`.

    Returns:
        The element at `index`.

    Raises:
        IndexError: If `index` is negative or not less than `len(self)`.

    Complexity:
        - Time: O(n); O(index) links are followed
        - Space: O(1)
    """
    # verify that the given index is within the valid range
    if index < 0 or index >= self._size:
        raise IndexError("index out of range")

    # walk forward from the head one link at a time until reaching the
    # target position; the bounds check above guarantees the node exists
    current_node = self._head
    for _ in range(index):
        assert current_node is not None
        current_node = current_node.next

    assert current_node is not None
    return current_node.item

def __contains__(self, item: object) -> bool:
    """Return whether `item` is in the list.

    Checks the elements from the head onward and stops at the first match.
    An element matches if it is `item` or equals it, the same rule that
    `list` uses.

    Args:
        item: The value to look for.

    Returns:
        `True` if some element is `item` or equals it, otherwise `False`.

    Complexity:
        - Time: O(n)
        - Space: O(1)
    """
    for element in self:
        if element is item or element == item:
            return True
    return False

def __repr__(self) -> str:
    """Return a string showing the class name and the elements, like `list`.

    Returns:
        A string such as `SinglyLinkedList([1, 2, 3])`.
    """
    return f"{type(self).__name__}({list(self)})"

def prepend(self, item: T) -> None:
    """Add `item` to the front of the list.

    The new node links to the current head and becomes the new head. No
    existing element moves. An array must shift every element one slot to
    the right to make room at index 0, which costs O(n).

    Args:
        item: The element to add.

    Complexity:
        - Time: O(1)
        - Space: O(1) for the new node

    Examples:
        >>> a = SinglyLinkedList[str](["b"])
        >>> a.prepend("a")
        >>> a
        SinglyLinkedList(['a', 'b'])
    """
    node = _Node(item)

    # an empty list's new node is both the head and the tail
    if self._head is None or self._tail is None:
        self._head = node
        self._tail = node
    else:
        node.next = self._head
        self._head = node

    self._size += 1

def append(self, item: T) -> None:
    """Add `item` to the end of the list.

    The tail reference points straight at the last node, so the new node
    is linked after it and becomes the new tail. Without a tail reference,
    finding the last node would mean walking the whole chain, making
    `append` O(n).

    Args:
        item: The element to add.

    Complexity:
        - Time: O(1)
        - Space: O(1) for the new node

    Examples:
        >>> a = SinglyLinkedList[str](["a"])
        >>> a.append("b")
        >>> a
        SinglyLinkedList(['a', 'b'])
    """
    node = _Node(item)

    # if the head or tail pointer is not set, then the list is empty.
    # So, set the head and tail pointers to the new node that is to be
    # appended.
    #
    # a useful invariant here is the head pointer will only be not set when
    # the tail pointer is not set which implies the list is empty.
    if self._head is None or self._tail is None:
        self._head = node
        self._tail = node
    else:
        self._tail.next = node
        self._tail = node

    self._size += 1

def pop_front(self) -> T:
    """Remove and return the first element.

    The head moves to the second node. If that empties the list, the tail
    is cleared too.

    Returns:
        The element that was at the front of the list.

    Raises:
        IndexError: If the list is empty.

    Complexity:
        - Time: O(1)
        - Space: O(1)

    Examples:
        >>> a = SinglyLinkedList[int]([1])
        >>> a.pop_front()
        1
        >>> a.pop_front()
        Traceback (most recent call last):
            ...
        IndexError: pop_front from empty list
    """
    if self._head is None:
        raise IndexError("pop_front from empty list")

    front_node: _Node[T] = self._head
    self._head = front_node.next

    # maintain the invariant that the head pointer is only not set
    # when the tail pointer is not set as well
    #
    # this if statement is required for when the last remaining element
    # is popped and the head and tail pointers have to be cleared
    if self._head is None:
        self._tail = None

    self._size -= 1

    return front_node.item

def remove(self, item: T) -> None:
    """Remove the first element that matches `item`.

    Only the first match, scanning from the head, is removed. An element
    matches if it is `item` or equals it, as in `item in a`. Unlinking a
    node means pointing its predecessor's `next` past it, and nodes have no
    backward link, so the scan carries a reference to the previous node as
    it goes. The head and tail references are updated when the removed node
    is at either end.

    Args:
        item: The value to remove.

    Raises:
        ValueError: If no element matches `item`.

    Complexity:
        - Time: O(n)
        - Space: O(1)

    Examples:
        >>> a = SinglyLinkedList[int]([1, 2, 1])
        >>> a.remove(1)
        >>> a
        SinglyLinkedList([2, 1])
        >>> a.remove(5)
        Traceback (most recent call last):
            ...
        ValueError: item not in list
    """
    previous_node: _Node[T] | None = None
    current_node: _Node[T] | None = self._head

    while current_node is not None:
        if current_node.item is item or current_node.item == item:
            # if the target node has a predecessor, link it past the
            # target; otherwise the target is the head, so advance the head
            if previous_node is not None:
                previous_node.next = current_node.next
            else:
                self._head = current_node.next

            # if the target was the last node, its predecessor is the new
            # tail (None when the list is now empty)
            if current_node is self._tail:
                self._tail = previous_node

            self._size -= 1
            return

        # continue searching through the linked list while remembering
        # the predecessor nodes in case the target node is found
        previous_node = current_node
        current_node = current_node.next

    raise ValueError("item not in list")

def reverse(self) -> None:
    """Reverse the list in place.

    Walks the list once, re-pointing each node's `next` at the node before
    it. Three references track progress: the previous node, the current
    node, and the next node (saved before its link is overwritten). When
    the walk ends, the old tail is the new head and the old head is the new
    tail. No nodes are allocated or copied.

    Complexity:
        - Time: O(n)
        - Space: O(1)

    Examples:
        >>> a = SinglyLinkedList[int]([1, 2, 3])
        >>> a.reverse()
        >>> a
        SinglyLinkedList([3, 2, 1])
        >>> a.append(0)  # the tail reference was updated too
        >>> a
        SinglyLinkedList([3, 2, 1, 0])
    """
    # the current head will be the tail once every link is reversed
    self._tail = self._head

    previous_node: _Node[T] | None = None
    current_node: _Node[T] | None = self._head

    while current_node is not None:
        # save the rest of the list before overwriting the forward link
        next_node = current_node.next

        # point the current node backward, then advance both references
        current_node.next = previous_node
        previous_node = current_node
        current_node = next_node

    # the last node visited, the old tail, is the new head
    self._head = previous_node