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 `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])

def insert(self, index: int, item: T) -> None:
    """Add `item` at `index`, shifting every later element one slot right.

    If the array is full, it first resizes to the capacity returned by the
    growth policy, copying every element, and only then makes room.
    Resizing only when there is no free slot means every allocated slot
    gets used before the array grows. The shift then runs from the last
    element down to `index`, so no element is overwritten before it has
    been moved.

    Inserting at `len(self)` shifts nothing, which is why the inherited
    `append` is O(1) amortized. Inserting at 0 shifts every element, which
    is why the inherited `prepend` is O(n).

    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:
        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)`.
        ValueError: If the array is full and the growth policy returns a
            capacity that is not greater than the current capacity.

    Complexity:
        - Time: O(n - index) to shift, plus O(n) for the insert that
          triggers a resize; O(1) amortized at the end with a geometric
          growth policy
        - Space: O(1) amortized; O(n) for the insert that triggers a resize

    Examples:
        >>> a = DynamicArray[str](capacity=2)
        >>> a.append("x")
        >>> a.append("z")  # fills the last free slot; no resize yet
        >>> a.capacity
        2
        >>> a.insert(1, "y")  # no free slot, so the array grows first
        >>> a, a.capacity
        (DynamicArray(['x', 'y', 'z']), 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)
    """
    # verify that the given index is within the valid range; one past the
    # last element is allowed, which adds at the end
    if index < 0 or index > self._size:
        raise IndexError("index out of range")

    # 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)

    # shift the elements from the end down to the index one slot to the
    # right, walking backwards so that each element is moved before the
    # element behind it overwrites its old slot
    for i in range(self._size, index, -1):
        self._items[i] = self._items[i - 1]

    # store the item in the slot the shift opened up
    self._items[index] = item

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

def pop(self, index: int) -> T:
    """Remove and return the element at `index`, shifting later ones left.

    The shift runs from `index + 1` up to the last element, so each slot
    is overwritten only after its element has moved. The slot freed at
    the end is cleared, so the array no longer holds a reference to the
    element. Capacity is unchanged.

    Popping at `len(self) - 1` shifts nothing, which is why the inherited
    `pop_back` is O(1). Popping at 0 shifts every remaining element, which
    is why the inherited `pop_front` is O(n).

    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 `index` is negative or not less than `len(self)`.

    Complexity:
        - Time: O(n - index) to shift; O(1) at the end
        - Space: O(1)

    Examples:
        >>> a = DynamicArray[int]()
        >>> for item in (1, 2, 3):
        ...     a.append(item)
        >>> a.pop(0)
        1
        >>> a
        DynamicArray([2, 3])
        >>> a.pop(2)
        Traceback (most recent call last):
            ...
        IndexError: index out of range
    """
    # verify that the given index is within the valid range
    if index < 0 or index >= self._size:
        raise IndexError("index out of range")

    item: T = typing.cast(T, self._items[index])

    # shift the elements after the index one slot to the left, walking
    # forwards so that each slot is overwritten only after its element has
    # already been moved
    for i in range(index, self._size - 1):
        self._items[i] = self._items[i + 1]

    # clear the slot freed at the end so the array does not keep a stale
    # reference to the last element, then update the size
    self._size = self._size - 1
    self._items[self._size] = None

    return item