cs_survival_kit.data_structures.dynamic_array ¶

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