cs_survival_kit.data_structures.abstract_list ¶

@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")