"""CSC111 Lecture 9 Examples"""

class BinarySearchTree:
    """Binary Search Tree class.

    Representation Invariants:
      - (self._root is None) == (self._left is None)
      - (self._root is None) == (self._right is None)
      - (BST Property) if self._root is not None, then
          all items in self._left are <= self._root, and
          all items in self._right are >= self._root

    Note that duplicates of the root can appear in *either* the left or right subtrees.
    """
    # Private Instance Attributes:
    #   - _root:
    #       The item stored at the root of this tree, or None if this tree is empty.
    #   - _left:
    #       The left subtree, or None if this tree is empty.
    #   - _right:
    #       The right subtree, or None if this tree is empty.
    _root: Optional[Any]
    _left: Optional[BinarySearchTree]
    _right: Optional[BinarySearchTree]

    def __init__(self, root: Optional[Any]) -> None:
        """Initialize a new BST containing only the given root value.

        If <root> is None, initialize an empty tree.
        """
        if root is None:
            self._root = None
            self._left = None
            self._right = None
        else:
            self._root = root
            self._left = BinarySearchTree(None)
            self._right = BinarySearchTree(None)

    def is_empty(self) -> bool:
        """Return whether this BST is empty.

        >>> bst = BinarySearchTree(None)
        >>> bst.is_empty()
        True
        >>> bst = BinarySearchTree(10)
        >>> bst.is_empty()
        False
        """
        return self._root is None

    def __contains__(self, item: Any) -> bool:
        """Return whether <item> is in this BST.

        >>> bst = BinarySearchTree(3)
        >>> bst._left = BinarySearchTree(2)
        >>> bst._right = BinarySearchTree(5)
        >>> bst.__contains__(3)  # or, 3 in bst
        True
        >>> bst.__contains__(5)
        True
        >>> bst.__contains__(2)
        True
        >>> bst.__contains__(4)
        False
        """
        if self.is_empty():
            return False
        elif item == self._root:
            return True
        elif item < self._root:
            return self._left.__contains__(item)  # or, item in self._left
        else:
            return self._right.__contains__(item)  # or, item in self._right

    def __str__(self) -> str:
        """Return a string representation of this BST.

        This string uses indentation to show depth.

        We've provided this method for debugging purposes, if you choose to print a BST.
        """
        return self._str_indented(0)

    def _str_indented(self, depth: int) -> str:
        """Return an indented string representation of this BST.

        The indentation level is specified by the <depth> parameter.

        Preconditions:
            - depth >= 0
        """
        if self.is_empty():
            return ''
        else:
            return (
                depth * '  ' + f'{self._root}\n'
                + self._left._str_indented(depth + 1)
                + self._right._str_indented(depth + 1)
            )

    def insert(self, item: Any) -> None:
        """Insert <item> into this tree.

        Do not change positions of any other values.
        """
        if self.is_empty():
            self._root = item
            # NEED TO UPDATE self._left and self._right so that they aren't None
            self._left = BinarySearchTree(None)
            self._right = BinarySearchTree(None)

            # Note: the following doesn't work (reassigns variable, doesn't mutate the BST object)
            # self = BinarySearchTree(item)
        elif item == self._root:
            # Could insert into self._left OR self._right
            self._left.insert(item)
        elif item < self._root:
            self._left.insert(item)
        else:  # item > self._root
            self._right.insert(item)

    def remove(self, item: Any) -> None:
        """Remove *one* occurrence of the given item from this BST.

        Do nothing if the item is not in this BST.
        """
        if self.is_empty():
            pass  # Could have also used "return" or "return None"
        elif item == self._root:
            self._delete_root()
        elif item < self._root:
            self._left.remove(item)
        else:  # item > self._root
            self._right.remove(item)

    def _delete_root(self) -> None:
        """Remove the root of this tree.

        Note: there are many different ways of simplifying/reorganizing the cases in this method,
        combining the "promote a subtree" and "extract min/max" strategies. As you're reviewing,
        we encourage you to experiment with different implementations of this method.

        Preconditions:
            - not self.is_empty()
        """
        # Case 1: this BST is a leaf
        if self._left.is_empty() and self._right.is_empty():
            self._root = None
            self._left = None    # Remember to preserve representation invariants!
            self._right = None

        # Case 2a: empty left subtree, non-empty right subtree
        elif self._left.is_empty() and not self._right.is_empty():
            # "Promote" the right subtree
            # Version 1
            to_promote = self._right
            self._root, self._left, self._right = to_promote._root, to_promote._left, to_promote._right

            # Version 2
            # self._root, self._left, self._right = self._right._root, self._right._left, self._right._right

            # Version 3 (INCORRECT)
            # self = self._right

        # Case 2b: non-empty left subtree, empty right subtree
        elif not self._left.is_empty() and self._right.is_empty():
            # "Promote" the left
            to_promote = self._left
            self._root, self._left, self._right = to_promote._root, to_promote._left, to_promote._right

        # Case 3: non-empty left and right subtrees
        else:
            # Replace self._root with the maximum of the left subtree
            self._root = self._left._extract_max()

    def _extract_max(self) -> Any:
        """Remove and return the maximum item stored in this tree.

        Note the similarity to BinarySearchTree.maximum from this week's prep!

        Preconditions:
            - not self.is_empty()
        """
        if self._right.is_empty():
            root = self._root

            # Version 1: Promote the left subtree (same as above)
            to_promote = self._left
            self._root, self._left, self._right = to_promote._root, to_promote._left, to_promote._right

            # Version 2: Reuse self._delete_root
            # Some students asked about this after lecture. Definitely possible (and good thing to
            # notice about function reuse!), but technically a form of *mutual recursion*, having two
            # different functions call each other. We aren't really covering mutual recursion in CSC111,
            # since it's a more complex form of recursion.
            # self._delete_root()

            return root

        else:
            # Just extract the max from the right subtree
            return self._right._extract_max()

"""CSC111 Lecture 7 examples"""

class Tree:
    """A recursive tree data structure.

    Representation Invariants:
        - self._root is not None or self._subtrees == []
    """
    # Private Instance Attributes:
    #   - _root:
    #       The item stored at this tree's root, or None if the tree is empty.
    #   - _subtrees:
    #       The list of subtrees of this tree. This attribute is empty when
    #       self._root is None (representing an empty tree). However, this attribute
    #       may be empty when self._root is not None, which represents a tree consisting
    #       of just one item.
    _root: Optional[Any]
    _subtrees: list[Tree]

    def __init__(self, root: Optional[Any], subtrees: list[Tree]) -> None:
        """Initialize a new Tree with the given root value and subtrees.

        If root is None, the tree is empty.

        Preconditions:
            - root is not none or subtrees == []
        """
        self._root = root
        self._subtrees = subtrees

    def is_empty(self) -> bool:
        """Return whether this tree is empty.
        """
        return self._root is None

    def __len__(self) -> int:
        """Return the number of items contained in this tree.

        >>> t1 = Tree(None, [])
        >>> len(t1)
        0
        >>> t2 = Tree(3, [Tree(4, []), Tree(1, [])])
        >>> len(t2)
        3
        """
        if self.is_empty():
            return 0
        else:
            return 1 + sum(subtree.__len__() for subtree in self._subtrees)

    def first_at_depth(self, d: int) -> Optional[Any]:
        """Return the leftmost value at depth d in this tree.

        Return None if there are NO items at depth d in this tree.

        Preconditions:
            - d >= 0  # depth 0 is the root of the tree

        >>> empty = Tree(None, [])
        >>> empty.first_at_depth(0) is None
        True
        >>> empty.first_at_depth(10) is None
        True
        >>> single = Tree(111, [])
        >>> single.first_at_depth(0)
        111
        >>> single.first_at_depth(3) is None
        True
        >>> tree = Tree(5, [
        ...    Tree(8, [Tree(3, []), Tree(2, []), Tree(6, [])]),
        ...    Tree(10, []),
        ...    Tree(7, [Tree(0, [Tree(111, [])])])
        ... ])
        >>> tree.first_at_depth(0)
        5
        >>> tree.first_at_depth(1)
        8
        >>> tree.first_at_depth(3)
        111
        """
        # Homework: try rewriting this code using a single flat if statement
        # (instead of nested if statements). Also, consider whether you can
        # merge the "elif" and "else" branches.
        if self.is_empty():
            return None
        elif self._subtrees == []:
            if d == 0:
                return self._root
            else:
                return None
        else:
            if d == 0:
                return self._root
            else:
                for subtree in self._subtrees:
                    possible_first = subtree.first_at_depth(d - 1)
                    if possible_first is not None:
                        return possible_first

                # Not necessary, but explicit:
                return None

    def __str__(self) -> str:
        """Return a string representation of this tree.
        """
        return self._str_indented(0)

    def _str_indented(self, depth: int) -> str:
        """Return an indented string representation of this tree.

        The string representation
        """
        if self.is_empty():
            return ''
        else:
            # This version doesn't use indentation, but illustrates how the
            # depth parameter changes across recursive calls.
            # str_so_far = f'(depth: {depth}) {self._root}\n'

            # This version uses string repetition to create indentation.
            str_so_far = ('  ' * depth) + f'{self._root}\n'
            for subtree in self._subtrees:
                str_so_far += subtree._str_indented(depth + 1)
            return str_so_far

    def average(self) -> float:
        """Return the average of the numbers in this tree.

        Return 0.0 if this tree is empty.

        Preconditions:
            - this tree contains only numbers
        """
        if self.is_empty():
            return 0.0
        else:
            # Homework: complete this method by defining
            # a recursive helper function average_helper below
            sum_items, num_items = self.average_helper()

            return sum_items / num_items

    def average_helper(self) -> tuple[int, int]:
        """Return (sum of self, size of self)."""
        if self.is_empty():
            return ...
        else:
            ...

    ###########################################################################
    # Deletion
    ###########################################################################
    def __contains__(self, item: Any) -> bool:
        """Return whether the given item is in this tree."""
        if self.is_empty():
            return False
        elif self._root == item:
            return True
        else:
            for subtree in self._subtrees:
                if subtree.__contains__(item):
                    return True

            return False

    def remove(self, item: Any) -> bool:
        """Delete *one* occurrence of the given item from this tree.

        Do nothing if the item is not in this tree.
        Return whether the given item was deleted.
        """
        if self.is_empty():
            return False
        elif self._root == item:
            # Need to remove self._root!
            # self._root = None  # <-- Doesn't work if self._subtrees is non-empty!
            self._delete_root()

            return True
        else:
            for subtree in self._subtrees:
                if subtree.remove(item):
                    return True

            return False

    def _delete_root(self) -> None:
        """Remove the root of this tree.

        Preconditions:
            - not self.is_empty()
        """
        if self._subtrees == []:
            self._root = None  # If self has size one, we turn it into an empty tree
        else:
            # Strategy 1: "Promote" the last subtree
            last_subtree = self._subtrees.pop()
            self._root = last_subtree._root
            self._subtrees.extend(last_subtree._subtrees)

            # Strategy 2: Move a leaf
            # Need to update this method as well to preserve the "no empty
            # subtrees" representation invariant!
            self._root = self._extract_leaf()

    def _extract_leaf(self) -> Any:
        """Remove and return the leftmost leaf in this tree.

        Preconditions:
            - not self.is_empty()
        """
        if self._subtrees == []:   # Similar to _delete_root, but also returns the root value
            root = self._root
            self._root = None
            return root
        else:
            return self._subtrees[0]._extract_leaf()  # Recurse on leftmost subtree

if __name__ == '__main__':
    import doctest
    doctest.testmod(verbose=True)

    # This variable is just used for testing purposes
    my_tree = Tree(5, [
        Tree(8, [Tree(3, []), Tree(2, []), Tree(6, [])]),
        Tree(10, []),
        Tree(7, [Tree(0, [Tree(111, [])])])
    ])

"""CSC111 Lecture 6 examples"""

@check_contracts
def items_at_depth(nested_list: int | list, d: int) -> list[int]:
    """Return the list of all integers in nested_list that have depth d.

    Preconditions:
        - d >= 0

    >>> items_at_depth(10, 0)
    [10]
    >>> items_at_depth(10, 3)
    []

    >>> items_at_depth([10, [[20]], [[30], 40]], 0)
    []
    >>> items_at_depth([10, [[20]], [[30], 40]], 3)
    [20, 30]
    """
    # Exercise: try rewriting this code without using nested if statements,
    # and instead using compound if/elif conditions.
    if isinstance(nested_list, int):
        if d == 0:
            return [nested_list]
        else:
            return []
    else:
        if d == 0:
            return []
        else:
            result_so_far = []
            for sublist in nested_list:
                result_so_far.extend(items_at_depth(sublist, d - 1))

            return result_so_far


@check_contracts
class RecursiveList:
    """A recursive implementation of the List ADT.

    Note: this list can't store None values! (Because None is used as a special value
    for its attributes.)

    """
    # Private Instance Attributes:
    #   - _first: The first item in the list, or None if this list is empty.
    #   - _rest: A list containing the items that come after the first one,
    #            or None if this list is empty.
    _first: Optional[Any]
    _rest: Optional[RecursiveList]

    def __init__(self, first: Optional[Any], rest: Optional[RecursiveList]) -> None:
        """Initialize a new recursive list."""
        self._first = first
        self._rest = rest

    def sum(self) -> int:
        """Return the sum of the elements in this list.

        Preconditions:
            - every element in this list is an int

        >>> empty = RecursiveList(None, None)
        >>> empty.sum()
        0
        >>> single = RecursiveList(111, empty)
        >>> single.sum()
        111
        >>> four_items = RecursiveList(1,
        ...                            RecursiveList(2,
        ...                                          RecursiveList(3,
        ...                                                        RecursiveList(4, empty))))
        >>> four_items.sum()
        10
        """
        if self._first is None:  # Base case: this list is empty
            return 0
        else:
            return self._first + self._rest.sum()

"""CSC111 Lecture 5 Examples"""


def sum_n(n: int) -> int:
    """Return the sum of the numbers between 0 and n, inclusive.

    Preconditions:
        - n >= 0

    >>> sum_n(4)
    10
    """
    if n == 0:
        return 0
    else:
        return sum_n(n - 1) + n


def euclidean_gcd(a: int, b: int) -> int:
    """Return the gcd of a and b.

    Preconditions:
        - a >= 0 and b >= 0
    """
    x = a
    y = b
    while y != 0:
        print(x, y)
        x, y = y, x % y
    return x


def euclidean_gcd_rec(a: int, b: int) -> int:
    """Return the gcd of a and b (using recursion!).

    Preconditions:
        - a >= 0 and b >= 0
    """
    print(a, b)
    if b == 0:
        return a
    else:
        return euclidean_gcd_rec(b, a % b)


def sum_list(numbers: list[int]) -> int:
    """Return the sum of the numbers in the given list.

    >>> sum_list([1, 2, 3])
    6
    """
    sum_so_far = 0
    for num in numbers:
        sum_so_far += num
    return sum_so_far


def sum_list2(lists_of_numbers: list[list[int]]) -> int:
    """Return the sum of the numbers in the given list of lists.

    >>> sum_list2([[1], [10, 20], [1, 2, 3]])
    37
    """
    sum_so_far = 0
    for numbers in lists_of_numbers:
        # numbers is a list[int]
        sum_so_far += sum_list(numbers)
    return sum_so_far


def sum_list3(lists_of_lists_of_numbers: list[list[list[int]]]) -> int:
    """Return the sum of the numbers in the given list of lists of lists.

    >>> sum_list3([[[1], [10, 20], [1, 2, 3]], [[2, 3], [4, 5]]])
    51
    """
    sum_so_far = 0
    for lists_of_numbers in lists_of_lists_of_numbers:
        # lists_of_numbers is a list[list[int]]
        sum_so_far += sum_list2(lists_of_numbers)
    return sum_so_far


def sum_list8(x: list[list[list[list[list[list[list[list[int]]]]]]]]) -> int:
    ...


def sum_nested(nested_list: int | list) -> int:
    """Return the sum of the integers in nested_list.
    nested_list is a nested list of integers (using our definition from lecture).
    """
    if isinstance(nested_list, int):
        return nested_list
    else:
        # Note: could use a for loop instead of a comprehension
        return sum(sum_nested(sublist) for sublist in nested_list)


def flatten(nested_list: int | list) -> list[int]:
    """Return a (non-nested) list of the integers in nested_list.

    The integers are returned in the left-to-right order they appear in
    nested_list.
    """
    if isinstance(nested_list, int):
        return [nested_list]
    else:
        result_so_far = []
        for sublist in nested_list:
            result_so_far.extend(flatten(sublist))
        return result_so_far


def depth(nested_list: int | list) -> int:
    """Return the depth of this nested list."""
    if isinstance(nested_list, int):  # Our "normal" base case
        return 0
    elif nested_list == []:  # An additional base case!
        return 1
    else:
        # Note: could use a for loop instead of a comprehension
        return 1 + max(depth(sublist) for sublist in nested_list)


def nested_list_contains(nested_list: int | list, item: int) -> bool:
    """Return whether the given item appears in nested_list.

    If nested_list is an integer, return whether it is equal to item.

    >>> nested_list_contains(10, 10)
    True
    >>> nested_list_contains(10, 5)
    False

    >>> nested_list_contains([[1, [30], 40], [], 77], 50)
    False
    >>> nested_list_contains([[1, [30], 40], [], 77], 40)
    True
    """
    if isinstance(nested_list, int):
        return nested_list == item
    else:
        # Version 1 (comprehension and any)
        return any(nested_list_contains(sublist, item) for sublist in nested_list)

        # Version 2 (loop and early return)
        # for sublist in nested_list:
        #     if nested_list_contains(sublist, item):
        #         return True
        #
        # return False

"""CSC111 Winter 2021: Lecture 4 code
(also includes code from Lecture 3)
"""

@dataclass
class _Node:
    """A node in a linked list.

    Instance Attributes:
      - item: The data stored in this node.
      - next: The next node in the list, if any.
    """
    item: Any
    next: Optional[_Node] = None  # By default, this node does not link to any other node


class LinkedList:
    """A linked list implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first node in this linked list, or None if this list is empty.
    _first: Optional[_Node]

    def __init__(self, items: Iterable) -> None:
        """Initialize a new linked list containing the given items.
        """
        self._first = None
        for item in items:
            self.append(item)

    def to_list(self) -> list:
        """Return a built-in Python list containing the items of this linked list.

        The items in this linked list appear in the same order in the returned list.
        """
        items_so_far = []

        curr = self._first
        while curr is not None:
            items_so_far.append(curr.item)
            curr = curr.next

        return items_so_far

    def __getitem__(self, i: int) -> Any:
        # Version 1
        curr = self._first
        curr_index = 0

        while curr is not None:
            if curr_index == i:
                return curr.item

            curr = curr.next
            curr_index = curr_index + 1

        raise IndexError

        # Version 2
        # curr = self._first
        # curr_index = 0
        #
        # while not (curr is None or curr_index == i):
        #     curr = curr.next
        #     curr_index = curr_index + 1
        #
        # assert curr is None or curr_index == i
        #
        # if curr is None:
        #     raise IndexError
        # else:
        #     return curr.item

    def append(self, item: Any) -> None:
        """Append item to the end of this list.

        >>> lst = LinkedList([1, 2, 3])
        >>> lst.append(4)
        >>> lst.to_list()
        [1, 2, 3, 4]
        """
        new_node = _Node(item)

        if self._first is None:
            self._first = new_node
        else:
            curr = self._first
            while curr.next is not None:
                curr = curr.next

            # After the loop, curr is the last node in the LinkedList.
            assert curr is not None and curr.next is None
            curr.next = new_node

    def insert(self, i: int, item: Any) -> None:
        """Insert the given item at index i in this list.

        Raise IndexError if i > len(self).
        Note that adding to the end of the list (i == len(self)) is okay.

        Preconditions:
            - i >= 0

        >>> lst = LinkedList([1, 2, 10, 200])
        >>> lst.insert(2, 300)
        >>> lst.to_list()
        [1, 2, 300, 10, 200]
        """
        # Create the new node to add (this occurs in all cases)
        new_node = _Node(item)

        if i == 0:
            # Need to reassign self._first to add new_node at the front
            # new_node.next = self._first
            # self._first = new_node

            self._first, new_node.next = new_node, self._first
        else:
            # Need to mutate the (i-1)-th node to add new_node
            curr = self._first
            curr_index = 0

            while curr is not None:
                if curr_index == i - 1:
                    # curr refers to the (i-1)-th node
                    curr.next, new_node.next = new_node, curr.next
                    return

                curr = curr.next
                curr_index += 1

            # At this point, i - 1 is not a valid index,
            # therefore i > len(self), and so we raise an IndexError
            raise IndexError

    def pop(self, i: int) -> Any:
        """Remove and return the item at index i.

        Raise IndexError if i >= len(self).

        Preconditions:
            - i >= 0

        >>> lst = LinkedList([1, 2, 10, 200])
        >>> lst.pop(1)
        2
        >>> lst.to_list()
        [1, 10, 200]
        """
        if self._first is None:
            raise IndexError
        elif i == 0:
            # Remove and return the first node (need to update self._first)
            # This is close but subtly wrong (FIXED by adding a separate check for empty list)
            item = self._first.item
            self._first = self._first.next
            return item
        else:
            # Remove and return the i-th node
            # (need to iterate to the (i-1)-th node!)
            curr = self._first
            curr_index = 0

            # Compound loop condition version (for practice!)
            # NOTE: it is possible to use curr.next is None in the condition instead,
            # though there is a subtletly that I didn't want to get into during lecture.
            # Using "curr.next is None" will also ensure that curr is not None,
            # since curr = curr.next in the loop.
            while not (curr is None or curr_index == i - 1):
                curr = curr.next
                curr_index += 1

            # After the loop ends, the following is True:
            assert curr is None or curr_index == i - 1

            if curr is None or curr.next is None:
                raise IndexError
            else:
                item = curr.next.item
                curr.next = curr.next.next
                return item

            # Alternate version using a second "previous node" loop variable.
            # prev, curr = None, self._first
            # curr_index = 0
            #
            # # Now, iterate to the i-th node
            # while not (curr is None or curr_index == i):
            #     # Update both curr and prev in the loop
            #     prev, curr = curr, curr.next
            #     curr_index += 1
            #
            # # After the loop ends, the following is True:
            # assert curr is None or curr_index == i
            #
            # if curr is None:
            #     raise IndexError
            # else:
            #     # Return curr's item and update prev's "next" link.
            #     item = curr.item
            #     prev.next = curr.next
            #     return item

    def remove(self, item: Any) -> None:
        """Remove the first occurrence of item from the list.

        Raise ValueError if the item is not found in the list.

        >>> lst = LinkedList([10, 20, 30, 20])
        >>> lst.remove(20)
        >>> lst.to_list()
        [10, 30, 20]
        """
        prev, curr = None, self._first

        while not (curr is None or curr.item == item):
            prev, curr = curr, curr.next

        # Assert what we know after the loop ends
        assert curr is None or curr.item == item

        if curr is None:
            raise ValueError
        else:  # curr.item == item  (the item was found)
            if prev is None:  # curr is the first node in the list
                self._first = curr.next

                # Alternate:
                # self._first = self._first.next
            else:
                prev.next = curr.next

        # Alternate (flattening the nested if statement using "elif")
        # if curr is None:
        #     raise ValueError
        # elif prev is None:  # curr is the first node in the list
        #     self._first = curr.next
        # else:
        #     prev.next = curr.next

"""David Lecture 1 code"""

@dataclass
class _Node:
    """A node in a linked list.

    Note that this is considered a "private class", one which is only meant
    to be used in this module by the LinkedList class, but not by client code.

    Instance Attributes:
      - item: The data stored in this node.
      - next: The next node in the list, if any.
    """
    item: Any
    next: Optional[_Node] = None  # By default, this node does not link to any other node


class LinkedList:
    """A linked list implementation of the List ADT.
    """
    # Private Instance Attributes:
    #   - _first: The first node in this linked list, or None if this list is empty.
    _first: Optional[_Node]

    def __init__(self) -> None:
        """Initialize an empty linked list.
        """
        self._first = None

    def sum_items(self) -> int:
        """Return the sum of the items in this linked list.

        Preconditions:
            - all items in this linked list are ints
        """
        sum_so_far = 0

        curr = self._first

        while curr is not None:  # or, while not (curr is None):
            sum_so_far = sum_so_far + curr.item
            curr = curr.next

        # Contrast with:
        # i = 0
        # while i < len(self):
        #     sum_so_far = sum_so_far + self[i]
        #     i = i + 1

        return sum_so_far

    ###########################################################################
    # Exercise 1: Linked List Traversal
    ###########################################################################
    def maximum(self) -> float:
        """Return the maximum element in this linked list.

        Preconditions:
            - every element in this linked list is a float
            - this linked list is not empty

        >>> linky = LinkedList()
        >>> node3 = _Node(30.0)
        >>> node2 = _Node(-20.5, node3)
        >>> node1 = _Node(10.1, node2)
        >>> linky._first = node1
        >>> linky.maximum()
        30.0
        """
        # Implementation note: as usual for compute maximums,
        # import the math module and initialize your accumulator
        # to -math.inf (negative infinity).
        max_so_far = -math.inf  # Comment: could also initialize to self._first.item
        curr = self._first

        while curr is not None:  # or, while not (curr is None):
            if curr.item > max_so_far:
                max_so_far = curr.item

            # Or,
            # max_so_far = max(max_so_far, curr.item)

            curr = curr.next

        return max_so_far

    def __contains__(self, item: Any) -> bool:
        """Return whether item is in this list.

        >>> linky = LinkedList()
        >>> linky.__contains__(10)
        False
        >>> node2 = _Node(20)
        >>> node1 = _Node(10, node2)
        >>> linky._first = node1
        >>> linky.__contains__(20)
        True
        """
        curr = self._first

        while curr is not None:
            # We should be comparing the node's item with item, not the node itself.
            # As written, this comparison will always be False (assuming item isn't a _Node).
            # if curr.item == item:
            if curr == item:
                # We've found the item and can return early.
                return True

            curr = curr.next

        # If we reach the end of the loop without finding the item,
        # it's not in the linked list.
        return False

    def __getitem__(self, i: int) -> Any:
        """Return the item stored at index i in this linked list.

        Raise an IndexError if index i is out of bounds.

        Preconditions:
            - i >= 0
        """
        curr = self._first
        curr_index = 0

        while curr is not None:
            if curr_index == i:
                return curr.item

            curr = curr.next
            curr_index += 1

        raise IndexError

        # Version 2: not using an early return, but using a "compound loop condition"
        # HOMEWORK: read about this in 13.2
        # curr = self._first
        # curr_index = 0  # the index of the current node
        #
        # # Idea: modify the loop condition so that we stop when EITHER:
        # #  1. we reach the end of the list (curr is None)
        # #  2. we reach the right index (curr_index == i)
        # while not (... or ...):
        #     curr = curr.next
        #     curr_index = curr_index + 1
        #
        # # Now, detect which of the two cases we're in (1 or 2)
        # # and handle each case separately.
        # if ...:
        #     ...
        # else:
        #     ...