# Principled Programming / Tim Teitelbaum / Chapter 12.

def list_context() -> None:
    """
    This function provides a catalog of code snippets that implement the various
    operations of a collection implemented as a list. The collection is assumed
    to be stored in the <A, size, n> data structure below. The function body doesn't
    do anything in particular. It's just a catalog. Sometimes when the code is left
    unfinished, a "pass" statement is needed to make the unfinished whole syntactically
    correct.
    """
    A: list[int] = []  # The list for containing items of the collection.
    size: int = 0      # The number of items in the collection.
    n: int = len(A)    # The length of A.

    v: int = 17        # A value of interest.
    k: int = 13        # An index of interest.

    def ensure_capacity(A: list[int]) -> list[int]:
        """ Return a reference to a copy of A in an object that is twice as long."""
        B: list[int] = [0] * len(A)
        for k in range(len(A)): B[k] = A[k];
        return B

    # Lists. Just syntax checks.
    def index_of(v: int, A: list[int], size: int, n: int) -> int:
        """Return k, a location of v in A, or return size, if no v in A."""
        k: int = 0
        while k < size and A[k] != v: k += 1
        return k

    """Add v to A. # Ensure the capacity of A for another element."""
    if size == n: A = ensure_capacity(A); n = len(A)
    A[size] = v
    size += 1

    """
    Remove v from A. This version of remove does not maintain the order of items.
    It just plugs the hole being created by the removal of v with whatever item is 
    currently last in the list.
    """
    k = index_of(v, A, size, n)
    if k == size:  pass # v is not in A. Sound an alarm, or whatever.
    else: size -= 1; A[k] = A[size]

    """Membership of v in A. Set b to true if v is in A, and false otherwise."""
    k: int = index_of(v, A, size, n)
    b: bool = (k != n)

    """Set b to true if v is in A, and false otherwise."""
    k: int = index_of(v, A, size, n)
    b: bool = (k != n)

    """Set m to the multiplicity of v in A."""
    m: int = 0
    for k in range(size):
        if A[k] == v: m += 1

    """Enumerate the elements of A."""
    for k in range(size): pass # Do whatever for A[k].

    """"Add v at position k of A."""
    if k > size: pass  # Alert: Bad index. ;
    if size == n: pass # Make room for more values.
    for j in range(size, k, -1): A[j] = A[j-1]
    A[k] = v
    size += 1

    """Remove v from position k of A."""
    if k < 0 or k >= size: pass # Alert: Bad index.
    size -= 1
    for j in range(k, size): A[j] = A[j+1]

# Histograms.
def histogram_context():
    """
    This function provides a catalog of code snippets that implement the various
    operations of a collection as a histogram. The collection is assumed to be stored
    in the <H, maxvalue> data structure below. The function body doesn't do anything
    in particular. It's just a catalog.
    """
    maxvalue: int = 100
    H: list[int] = [0] * maxvalue
    v: int = 17  # A value of interest.

    """Add v to H."""
    H[v] += 1

    """Remove v from H."""
    if H[v] == 0: pass # Alarm: attempt to remove a value not in H.
    else: H[v] -= 1

    """Set b to True iff v is in H."""
    b: bool = (H[v] > 0)

    """Set m to the multiplicity of v in A."""
    m: int = H[v]

    """Enumerate elements of H."""
    for k in range(0, maxvalue +1):
       for j in range(0, H[k]): pass # Enumerate k

def e12_3_2() -> None:
        """
        Confirm Ramanujan’s claim that 1729 is the smallest number that is the
        sum of two positive cubes in two different ways. This is an excellent use
        of a histogram.
        """
    # Create histogram
        N = 12*12*12+11*11*11+1   # (Max r)^3+(max c)^3+1, for r!=c in [0..12].
        H: list[int] = [0] * N    # H[k] = # of {r,c}, r!=c, s.t. k=r^3+c^3.
    # Let H be a histogram of r^3+c^3, for each set {r,c} of distinct
    #   nonnegative integers that are no larger than 12.
        for r in range(1, 13):
            for c in range(0, r):
                H[(r*r*r) + (c*c*c)] += 1
    # Let k be smallest index s.t. H[k]>1.
        k=0
        while H[k] < 2: k += 1
    # Output confirmation message.
        if (H[k] == 2) and (k == 1729):
            print("Confirmed that 1729 is the smallest number that is the sum of cubes in two ways.")
        else:
            print("Ramanujan’s claim disproved.")

# Uncomment out to run.
# e12_3_2()