# Principled Programming / Tim Teitelbaum / Chapter 18.
class ArrayList:
    """A list of unbounded capacity containing items of type int."""
    # Representation.
    _A: list[int]     # _A[0..size-1] is a collection of list items of type int.
    _size: int        # _size is the current number of items in the list.
                      # The current list capacity is len(_A).

    # Constructor.
    def __init__(self, m: int = 20) -> None:
        """
        Construct an empty list for int items, with an initial capacity m>=0, or 20 if no m is given.
        Raise ValueError if m<0.
        """
        if m < 0: raise ValueError("Capacity must be non-negative int")
        self._A = [0 for _ in range(m)]
        self._size = 0

    # Size.
    def size(self)  -> int:
        """Return the number of items in the list."""
        return self._size

    def is_empty(self) -> bool:
        """Return True iff the list is empty."""
        return self._size == 0

    # Access.
    def get(self, k: int) -> int:
        """
        Return the list item at index k.
        Raise IndexError for an out-of-bounds k.
        """

        self._check_bound_exclusive(k)
        return self._A[k]

    def set(self, k: int, v: int) -> int:
        """
        Overwrite the list item at index k with v, and return the old item that was there.
        Raise IndexError for an out-of-bounds k.
        """

        self._check_bound_exclusive(k)
        old: int = self._A[k]
        self._A[k] = v
        return old

    # Insertion / Deletion.        
    def add(self, v: int, k: int = -1) -> None:
        """
        If no k is provided, append v to the end of the list, else right-shift items with
        indices k thru the end of the list one place, and insert v at index k.
        Raise IndexError on out-of-bound k.
        """

        if k == -1: k = self._size
        self._check_bound_inclusive(k)
        if self._size == len(self._A): self.ensure_capacity(self._size + 1)
        for j in range(self._size, k, -1): self._A[j] = self._A[j-1]
        self._A[k] = v
        self._size += 1

    def remove(self, k: int) -> int:
        """
        Return the list item with index k after left-shifting items with indices
        k+1 thru the end (if any) to remove the old k-th value from the list.
        Raise IndexError for an out-of-bounds k.
        """

        self._check_bound_exclusive(k)
        old: int = self._A[k]
        self._size -= 1
        for j in range(k, self._size): self._A[j] = self._A[j+1];
        return old

    def remove_by_value(self, v: int) -> bool:
        """
        Return False if v is not in the list, else remove (one copy of) v from the list and return True."""
        k = self.index_of(v)
        if k == -1: return False
        else: self.remove(k); return True

     # Capacity.
    def ensure_capacity(self, min_capacity: int) -> None:
        """
        Increase the list's capacity to the maximum of min_capacity or double its current capacity.
        N.B. Python's built-in type "list" has "array doubling" built in. We ignore that here for
        pedagogical purposes.
        """

        current_length: int = len(self._A)
        if min_capacity > current_length:
            B: list[int] = [0] * max(2 * current_length, min_capacity)
            for k in range(0, self._size): B[k] = self._A[k]
            self._A = B

    # Membership.
    def index_of(self, v: int) -> int:
        """Return the index of an instance of v in the list, or -1 if there are none."""
        k: int = 0
        while (k < self._size) and (v != self._A[k]): k += 1
        if k == self._size: return -1
        else: return k

    def contains(self, v: int) -> bool:
        """Return True iff the list contains (one or more copies of) v."""
        return self.index_of(v) != -1

    # Bounds Checking.
    def _check_bound_exclusive(self, k: int) -> None:
        """Raise IndexError if k is not the index of one of the list's items."""
        if (k < 0) or (k >= self._size): raise IndexError("index out of bounds")

    def _check_bound_inclusive(self, k: int) -> None:
        """
        Raise IndexError if k is not the index of one of the list's items
        or the next available index for an item to be added.
        """

        if (k < 0) or (k > self._size): raise IndexError("index out of bounds")