# Principled Programming / Tim Teitelbaum / Chapter 18.
from typing import Optional, cast
class ArrayList[E]:
    _A: list[E]     # ArrayList elements are in A[0..size-1].
    _size: int      # The default value is 0.

    # Constructors.
    def __init__(self, m: int = 20) -> None:          # Default capacity of 20.
        if m < 0: raise ValueError("Capacity must be non-negative int")
        self._A = [cast(E,object()) for _ in range(m)]
        self._size = 0

    # Iteration
    def __iter__(self):
        self._index = 0
        return self
    def __next__(self):
        if self._index < self._size:
            value = self._A[self._index]
            self._index += 1
            return value
        else:
            raise StopIteration
    # Size.
    def size(self)    -> int:  return self._size
    def is_empty(self) -> bool: return self._size == 0

    # Access.
    def get(self, k: int) -> E:
        self._check_bound_exclusive(k)
        return self._A[k]
    def set(self, k: int, v: E) -> E:
        self._check_bound_exclusive(k)
        old  = self._A[k]
        self._A[k] = v
        return old

    # Utility 
    def _check_bound_exclusive(self, k: int) -> None:
         if (k < 0) or (k >= self._size): raise IndexError("≥size")
        
    def _check_bound_inclusive(self, k: int) -> None:
         if (k < 0) or (k > self._size): raise IndexError(">size")

    # Insertion / Deletion.        
    def add(self, v: E, k: int = -1) -> None:
        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:
        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:
        k = self.index_of(v)
        if k != -1: self.remove(k); return True 
        else: self.remove(k); return False  


     # Capacity.
    def ensure_capacity(self, min_capacity: int) -> None:
        current_length: int = len(self._A)
        if min_capacity > current_length:
            B: list[E] = [cast(E,object())] * 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:
        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 self.index_of(v) != -1