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. Must satisfy
            `0 <= index < len(self)`.

    Returns:
        The element at `index`.

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

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

    Only overwrites an existing element; the length does not change. Use
    `insert` 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 there is no element at `index`.
    """
    raise NotImplementedError

@abstractmethod
def insert(self, index: int, item: T) -> None:
    """Add `item` at position `index`, moving later elements along by one.

    Afterwards `self[index]` is `item` and `len(self)` is one greater.
    `index == len(self)` adds the item after the current last one.

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

    Raises:
        IndexError: If `index` is negative or greater than `len(self)`.
    """
    raise NotImplementedError

@abstractmethod
def pop(self, index: int) -> T:
    """Remove and return the element at position `index`.

    Later elements move back by one, so afterwards `len(self)` is one
    less and the element that was at `index + 1` is at `index`.

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

    Returns:
        The element that was at `index`.

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

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

    Checks the elements in position order 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: one iteration, stopping at the first match
        - 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 in order.

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

def __reversed__(self) -> Iterator[T]:
    """Iterate over the elements from the last position down to 0.

    This is what the built-in `reversed(a)` calls. The list is not
    changed; compare `reverse`, which some structures offer to rewire
    themselves in place.

    The default iterates forward once into a buffer, then yields the
    buffer from its end. The buffer costs O(n) auxiliary space, and that
    is a deliberate trade. The alternative, reading `a[i]` from the last
    position down, needs no extra memory but is only as cheap as
    indexing, which is quadratic on a linked list that walks to each
    index. A linear default that every implementation can inherit beats
    a constant-space default that some cannot afford. A structure that
    can walk backward in O(1) space overrides this: an array reads by
    index, and a doubly linked list follows its backward links.

    The buffer is filled when iteration starts, not when `reversed(a)`
    is called, and it is a snapshot: changes made to the list after the
    first element has been yielded do not affect the rest.

    Yields:
        Each element, starting with the one at position `len(self) - 1`.

    Complexity:
        - Time: O(n), one iteration plus one pass over the buffer
        - Space: O(n) for the buffer
    """
    buffer = list(self)
    yield from reversed(buffer)

def reverse(self) -> None:
    """Reverse the order of the elements in place.

    Afterwards the element that was last is at position 0, and so on.
    Compare `reversed(a)`, which visits the elements backward and changes
    nothing.

    The default is the array algorithm: swap the first element with the
    last, the second with the second-to-last, and so on, meeting in the
    middle after `n // 2` swaps. It needs nothing but indexing, so on an
    array it is O(n) with O(1) extra space. A linked list cannot index
    cheaply, so it overrides this with an algorithm suited to links: a
    singly linked list re-points every `next` at the node before it, and
    a doubly linked list swaps `prev` and `next` on every node.

    Complexity:
        - Time: `n // 2` swaps, each two reads and two writes of `a[i]`
          at that index's cost
        - Space: O(1)
    """
    count = len(self)
    for index in range(count // 2):
        mirror = count - 1 - index
        self[index], self[mirror] = self[mirror], self[index]

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.

    Complexity:
        - Time: the cost of `insert` at index `len(self)`
        - Space: the cost of `insert` at index `len(self)`
    """
    self.insert(len(self), item)

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

    Afterwards `item` is at position 0, every other element is one
    position later, and `len(self)` is one greater.

    Args:
        item: The element to add.

    Complexity:
        - Time: the cost of `insert` at index 0
        - Space: the cost of `insert` at index 0
    """
    self.insert(0, item)

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

    Returns:
        The element that was at position 0.

    Raises:
        IndexError: If the list is empty.

    Complexity:
        - Time: the cost of `pop` at index 0
        - Space: the cost of `pop` at index 0
    """
    if len(self) == 0:
        raise IndexError("pop_front from empty list")
    return self.pop(0)

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

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

    Raises:
        IndexError: If the list is empty.

    Complexity:
        - Time: the cost of `pop` at index `len(self) - 1`
        - Space: the cost of `pop` at index `len(self) - 1`
    """
    if len(self) == 0:
        raise IndexError("pop_back from empty list")
    return self.pop(len(self) - 1)

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

    Only the first match, scanning from position 0, is removed. An
    element matches if it is `item` or equals it, as in `item in a`.

    Args:
        item: The value to remove.

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

    Complexity:
        - Time: one iteration to find the match, plus the cost of `pop`
          at that index
        - Space: O(1)
    """
    for index, element in enumerate(self):
        if element is item or element == item:
            self.pop(index)
            return
    raise ValueError("item not in list")

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

    Returns:
        The number of elements currently stored.

    Complexity:
        - Time: O(1)
        - 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) for complete iteration
        - Space: O(1) auxiliary space
    """
    current_node: _Node[T] | None = self._head

    while current_node is not None:
        yield current_node.item
        current_node = current_node.next

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

    Each node stores a reference to its predecessor, allowing traversal
    backward from the tail without first reversing the list or repeatedly
    searching from the head. A singly linked list does not have these
    backward references.

    Yields:
        Each element in reverse list order.

    Complexity:
        - Time: O(n) for complete iteration
        - Space: O(1) auxiliary space

    Examples:
        >>> values = DoublyLinkedList([1, 2, 3])
        >>> list(reversed(values))
        [3, 2, 1]
    """
    current_node: _Node[T] | None = self._tail

    while current_node is not None:
        yield current_node.item
        current_node = current_node.prev

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

    Traversal begins at whichever end of the list is closer to `index`.
    This reduces the number of nodes visited for positions near the tail,
    although indexed access remains O(n) in the worst case.

    Args:
        index: Zero-based index of the element to retrieve.

    Returns:
        The element stored at `index`.

    Raises:
        IndexError: If `index` is outside the range `[0, n)`.

    Complexity:
        - Time: O(min(index, n - 1 - index)); O(n) worst case
        - Space: O(1)
    """
    return self._node_at(index).item

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

    Args:
        index: Zero-based index of the element to replace.
        item: New element to store at `index`.

    Raises:
        IndexError: If `index` is outside the range `[0, n)`.

    Complexity:
        - Time: O(min(index, n - 1 - index)); O(n) worst case
        - Space: O(1)
    """
    self._node_at(index).item = item

def insert(self, index: int, item: T) -> None:
    """Insert an element at the given index.

    Insertion at the head or one position past the tail requires no
    traversal and runs in O(1) time. For an interior insertion, the node
    currently at `index` is located by traversing from the nearer end.
    Its `prev` reference identifies the predecessor, after which the four
    links surrounding the new node are updated in O(1) time.

    Args:
        index: Zero-based position at which to insert the element. An
            index equal to the current size appends the element.
        item: Element to insert.

    Raises:
        IndexError: If `index` is outside the range `[0, n]`.

    Complexity:
        - Time: O(min(index, n - index)); O(n) worst case
        - Space: O(1) auxiliary space

    Examples:
        >>> values = DoublyLinkedList([1, 3])
        >>> values.insert(1, 2)
        >>> list(values)
        [1, 2, 3]
    """
    # Verify that the index is within the valid range. One position past
    # the final element is allowed because it represents an append.
    if index < 0 or index > self._size:
        raise IndexError("index out of range")

    node = _Node[T](item)

    if self._head is None or self._tail is None:
        self._head = node
        self._tail = node

    elif index == 0:
        node.next = self._head
        self._head.prev = node
        self._head = node

    elif index == self._size:
        node.prev = self._tail
        self._tail.next = node
        self._tail = node

    else:
        # Locate the node that will follow the newly inserted node.
        next_node = self._node_at(index)

        # An interior node necessarily has a predecessor.
        assert next_node.prev is not None
        previous_node = next_node.prev

        # Insert the new node between its predecessor and successor.
        previous_node.next = node
        next_node.prev = node
        node.next = next_node
        node.prev = previous_node

    self._size += 1

def pop(self, index: int) -> T:
    """Remove and return the element at the given index.

    Removing the head or tail requires only pointer updates and therefore
    runs in O(1) time. In particular, the tail's `prev` reference gives
    direct access to the new tail, whereas a singly linked list must
    traverse from the head to locate the tail's predecessor.

    Removing an interior element first locates its node by traversing from
    the nearer end. The node's `prev` and `next` references then provide
    direct access to both neighbors so it can be unlinked in O(1) time.

    Args:
        index: Zero-based index of the element to remove.

    Returns:
        The element removed from the list.

    Raises:
        IndexError: If `index` is outside the range `[0, n)`.

    Complexity:
        - Time: O(min(index, n - 1 - index)); O(n) worst case
        - Space: O(1)

    Examples:
        >>> values = DoublyLinkedList([1, 2, 3])
        >>> values.pop(1)
        2
        >>> list(values)
        [1, 3]
    """
    # Verify that the given index is within the valid range [0, n).
    if index < 0 or index >= self._size:
        raise IndexError("index out of range")

    if index == 0:
        removed_node = self._head
        assert removed_node is not None

        self._head = removed_node.next

        if self._head is None:
            self._tail = None
        else:
            self._head.prev = None

        removed_node.next = None

    elif index == self._size - 1:
        removed_node = self._tail
        assert removed_node is not None
        assert removed_node.prev is not None

        self._tail = removed_node.prev
        self._tail.next = None
        removed_node.prev = None

    else:
        removed_node = self._node_at(index)
        previous_node = removed_node.prev
        next_node = removed_node.next

        # An interior node necessarily has both neighbors.
        assert previous_node is not None
        assert next_node is not None

        previous_node.next = next_node
        next_node.prev = previous_node

        removed_node.prev = None
        removed_node.next = None

    self._size -= 1

    return removed_node.item

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

    Each node's `prev` and `next` references are swapped. After a node's
    links are swapped, its former `next` node is reachable through `prev`,
    which allows traversal to continue through the original list order.
    Once every node has been updated, the head and tail references are
    swapped to complete the reversal.

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

    Examples:
        >>> values = DoublyLinkedList([1, 2, 3])
        >>> values.reverse()
        >>> list(values)
        [3, 2, 1]
    """
    # Start traversal at the head of the list.
    current_node: _Node[T] | None = self._head

    # Swap each node's backward and forward references.
    while current_node is not None:
        current_node.prev, current_node.next = (
            current_node.next,
            current_node.prev,
        )

        # The original next node is now referenced by prev.
        current_node = current_node.prev

    # Swap the endpoints to complete the reversal.
    self._head, self._tail = self._tail, self._head

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 `insert` or `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`.

    Unused slots are never visited, so `None in a` is `True` only if
    `None` was actually stored.

    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 __reversed__(self) -> Iterator[T]:
    """Iterate over the elements from index `len(self) - 1` down to 0.

    Overrides the inherited default, which buffers one forward pass in
    O(n) auxiliary space so that it stays linear on structures that
    cannot index cheaply. An array indexes in O(1), so it walks backward
    by index instead and needs no buffer.

    Yields:
        Each element, starting with the one at index `len(self) - 1`.

    Complexity:
        - Time: O(n) to exhaust the iterator
        - Space: O(1)

    Examples:
        >>> a = DynamicArray[int]()
        >>> a.append(1)
        >>> a.append(2)
        >>> list(reversed(a))
        [2, 1]
    """
    for i in range(self._size - 1, -1, -1):
        yield typing.cast(T, self._items[i])