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

    # Constructors.
    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 = [cast(E,None) 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) -> E:
        """
        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: E) -> E:
        """
        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  = self._A[k]
        self._A[k] = v
        return old

    # Insertion / Deletion.        
    def add(self, v: E, k: int = -1) -> None:
        """
        If no k is provided, append v to the end of the list, else right shift items with
        indices k to the end of the list one place, and insert v into the list 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) -> E:
        """
        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: E = 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: E) -> bool:
        """Return False if v is not in the list, else remove (one copy of) it 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[E] = [cast(E,None)] * 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: E) -> 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: E) -> 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("≥size")

    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(">size")