Lab 12: Exceptions & Iteration

Before You Begin

Pull the files from GitHub and create a new IntelliJ project out of them.

Learning Goals

In this lab, we’ll be exploring the concept of delegation and exploring different methods for how we can delegate work to other classes and methods. To delegate work means to pass it off to someone or something else.

We’ll first consider what happens when an error occurs, like an ArrayIndexOutOfBoundsException. Instead of crashing immediately and printing out a long stack trace, we’ll learn how we can hand over control of the program to the method which called us, allowing the programmer to handle the crash and take alternate action. The mechanism that enables this ability is called an exception.

An exception can be thrown—passed to another part of the program to handle—or caught—handled on its own. We’ll consider examples of each kind of use in the upcoming lab exercises.

Then, we’ll see how exceptions can be used to build iterators, objects that control iteration through the items in a collection via three methods: a constructor, hasNext (“Are there any more items left?”), and next (“Return the next item.”). Iterators and iterables are a core component of the Java standard library, and we’ll see how iterators, as a form of delegation, can be used to write better and more performant code.

Error-Handling

So far in this course, we have not dealt much with error-handling. You were allowed to assume that the arguments given to methods were formatted or structured appropriately. However, this is not always the case due to program bugs and incorrect user input. Here are a few examples of this:

Bugs in your programs might create inconsistent structures or erroneous method calls (e.g. division by zero, indexing out of bounds, dereferencing a null pointer).
Users cannot be trusted to give valid input (e.g. non-numeric input where a number is required or search failures where a command or keyword was misspelled).

We assume in the following discussion that we can detect the occurrence of an error and at least print an error message about it.

A big challenge in dealing with the error is to provide information about it at the right level of detail. For instance, consider the error of running off the end of an array or list. If the contents of a list are inconsistent with the number of elements supposedly contained in the list, a “reference through a null pointer” or “index out of bounds” error may result. The programmer may wish to pass information about the error back to the calling method with the hope that the caller can provide more appropriate and useful information about the root cause of the error and perhaps be able to deal with the error.

Discussion: Error Handling

Here are three approaches to error handling:

Don’t try to pass back any information to the caller at all. Just print an error message and halt the program.
Detect the error and set some global error indicator (like a public static variable in Java) to indicate its cause.
Require that the method where the error occurred (and every method that directly or indirectly calls it) to pass back its value or to take an extra argument object that can be set to indicate the error.

Different languages geared towards solving different types of problems take different approaches to error handling. The increasingly popular Go programming language, for example, chooses a design similar to the third option.

Which seems most reasonable? Discuss with your partner, and defend your answer. If none, justify why all the options are bad.

Exceptions

There is a fourth option for handling errors, called an exception. Provided by Java and other modern programming languages, an exception signals that an error of some sort has occurred. Java allows both the signaling of an error and selective handling of the error. Methods called between the signaling method and the handling method need not be aware of the possibility of the error.

An exception is thrown by the code that detects the exceptional situation, and caught by the code that handles the problem. These two definitions are helpful in discussing exceptions.

Read Chapter 6.1 and 6.2 of the online textbook to learn more about exceptions.

An extension to the try catch block construct that often comes in handy is the finally block. A finally block comes after the last catch block and is used to do any cleanup that might be necessary, such as releasing resources the try block was using. This is very common when working with input-output like opening files on your computer.

Scanner scanner = new Scanner(System.in);
int k;
try {
    k = scanner.nextInt();
} catch (NoSuchElementException e) {
    // Ran out of input
} catch (InputMismatchException e) {
    // Token isn't an integer
} finally {
    // finally will be executed as long as JVM does not exit early
    scanner.close();
}

This use of the finally block so common that the Java language developers introduced the try-with-resources block. It allows you to declare resources being used as part of the try block, and automatically release those resources after the block finishes executing. The code below is equivalent to the snippet above, but it doesn’t use the finally block.

int k;
try (Scanner scanner = new Scanner(System.in)) {
    k = scanner.nextInt();
} catch (NoSuchElementException e) {
    // ran out of input
} catch (InputMismatchException e) {
    // token isn't an integer
}

Worksheet: 1. Exceptions

Complete this exercise on your worksheet.

Iteration

In CS 61BL, we’ve encountered a variety of different data structures, such as linked lists like SLList, multiple types of Deques like LinkedListDeque and ArrayDeque, and a few types of trees like BinaryTree and BTree. Later, we’ll see more complicated data structures such as hash tables, heaps, and graphs.

A common operation on a data structure is to process every item. But often, the code we need to write to setup and iterate through a data structure differs depending on the data structure’s implementation.

for (int i = 0; i < array.length; i += 1) {
    // Do something with array[i]
}

For SLList, the pattern significantly differs from above.

SLList list = ...
for (IntNode p = list.sentinel.next; p != null; p = p.next) {
    int item = p.item;
}

Evidently, we need to write two very different codes in order to do the exactly same thing. It would be nice if we can write one piece of code that we can reuse for different data structures. In other words, we wish to abstract away the internal implementation of data structures from the operations on them.

Furthermore, if we use a different data structure, a for loop like the one above may not make sense. For example, what would it mean to access the kth item of a set, where order of items is not defined? We need a more abstract notion of processing every item in a data structure, something that allows us to check every item regardless of how they’re organized. To do that, we’re going to use something called an iterator.

Enhanced `for` Loop

It turns out that we’ve already been using iterators this summer! When Java executes an enhanced for loop, it does a bit of work to convert it into iterators and iterables.

Under the surface, this code:

List<Integer> friends = new ArrayList<>();
friends.add(5);
friends.add(23);
friends.add(42);
for (int x : friends) {
    System.out.println(x);
}

Is converted to something like this:

List<Integer> friends = new ArrayList<>();
friends.add(5);
friends.add(23);
friends.add(42);

Iterator<Integer> seer = friends.iterator();
while (seer.hasNext()) {
    int x = seer.next();
    System.out.println(x);
}

`Iterable`

How does this work? List is an interface which extends the Iterable interface. An iterable is something which can be iterated over, so all Collections implement Iterable.

public interface Iterable<T> {
    Iterator<T> iterator();
}

Implementing the Iterable interface requires a class to have an iterator() method. This method intializes an iterator by returning an object of type Iterator, which can then be used to iterate (which is definitely not confusing at all, right?).

What is Iterator? It turns out this is another interface!

`Iterator`

package java.util;

public interface Iterator<T> {
    boolean hasNext();
    T next();
}

hasNext: hasNext is a boolean method that says whether there are any more remaining items in the data structure to return.
next: next successively returns items in the data structure one by one. The first call to next returns the first value, the second call to next returns the second value, and so on. If you’re iterating over a set—a data structure that is not supposed to have an order—we might not necessarily guarantee that next returns items in any specific order. However, what we do need to guarantee is that it returns each item exactly once. If we were iterating over a data structure that does have an ordering, like a list, then we would also like to guarantee that next returns items in the right order.

I find it useful to come up with an analogy when trying to separate the ideas of Iterables and Iterators. One such analogy is that of reading a book. Since a book has many pages to flip through, we can think of it as an Iterable, while one could use a bookmark to keep track of the current page, acting as the Iterator in this analogy. What is important to remember is that an Iterable is an object that can be “moved through”, while an Iterator is the object which “moves through” its respective Iterable.

Why design two separate interfaces, one for iterator and one for iterable? Why not just have the iterable do both?

The idea is similar to Comparable and Comparator. By separating the design, we can provide a ‘default’ iterator, but also allow for programmers to implement different iterators with different behaviors. While the SLList class might, by default, provide an efficient SLListIterator implementation, this design opens up the possibility of defining an SLListReverseIterator that can iterate over an SLList in reverse, all without modifying any of the code in SLList!

`SLListIterator`

Here’s an example of inserting the iterator methods into a modified version of the SLList class from lab 06, which can now hold any generic object, rather than just Integers. Don’t worry if you don’t get it all right away.

import java.util.Iterator;

public class SLList<Item> implements Iterable<Item> {

    private ListNode<Item> sentinel;
    private int size;

    // SLList constructors and methods would normally appear here.

    public Iterator<Item> iterator() {
        return new SLListIterator();
    }

    private class SLListIterator implements Iterator<Item> {

        private ListNode<Item> bookmark = sentinel.next;

        public Item next() {
            Item toReturn = bookmark.item;
            bookmark = bookmark.next;
            return toReturn;
        }

        public boolean hasNext() {
            return bookmark != sentinel;
        }
    }
}

The code maintains an important invariant: prior to any call to next, bookmark points to the IntListNode which contains the next value in the list to return.

Notice also that we don’t need a generic type in the SLListIterator class declaration. Since it’s a non-static nested class (called an inner class), the SLList generic type still applies. The implication of SLListIterator being non-static means that an SLListIterator cannot be created without an existing SLList instance: the SLListIterator needs to know its outer SLList’s generic type Item in order to function correctly.

We can then use our SLList class exactly like in the earlier examples, and even in an enhanced for loop.

SLList<Integer> friends = new SLList<>();
friends.addFirst(5);
friends.addFirst(23);
friends.addFirst(42);

Iterator<Integer> seer = friends.iterator();
while (seer.hasNext()) {
    int x = seer.next();
    System.out.println(x);
}

SLList<Integer> moreFriends = new SLList<>();
moreFriends.addFirst(5);
moreFriends.addFirst(23);
moreFriends.addFirst(42);
for (int x : moreFriends) {
    System.out.println(x);
}

Defining Iterators

Often, when writing our own iterators, we’ll follow a similar pattern of doing most of the work in next.

We save the next item with Item toReturn = bookmark.item.
Move the bookmark to the next item with bookmark = bookmark.next.
Return the item we saved earlier.

An important feature of the code is that hasNext doesn’t change any state. It only examines existing state by comparing the progress of the iteration to the number of list elements. hasNext can then be called twice in a row and nothing should change, or it could be called not at all and the iteration should still work as long as there are elements left to be returned.

Discussion: Iterator Invariants

Consider the following SLListIterator, slightly different from those we just encountered.

private class SLListIterator implements Iterator<Item> {

    private ListNode<Item> bookmark = sentinel;

    public Item next() {
        bookmark = bookmark.next;
        return bookmark.item;
    }

    public boolean hasNext() {
        return bookmark.next != sentinel;
    }
}

Now, discuss the following questions with your partner:

What’s the invariant relation that’s true between calls to next?
In general, most experienced programmers prefer the organization introduced first over this organization. What might explain this preference?

Worksheet: 2. Iterators

Complete this exercise on your worksheet.

What if someone calls next when hasNext returns false?: This violates the iterator contract so the behavior for next is undefined. Crashing the program is acceptable. However, a common convention is to throw a NoSuchElementException.
Will hasNext always be called before next?: Not necessarily. This is sometimes the case when someone using the iterator knows exactly how many elements are in the sequence. For this reason, we can’t depend on the user calling hasNext when implementing next.

Exercise: `SpaceListIterator`

As mentioned before, it is standard practice to use a separate iterator object (and therefore a separate, typically nested class) as the actual Iterator. This separates the Iterator from the underlying data structure or iterable.

Modify the provided SpaceList class so that it implements Iterable<Item>. Then, add a nested SpaceListIterator class which implements Iterator<Item>.

Note that SpaceList itself does not implement Iterator. This is why we need a separate, nested, private class to be the iterator. Typically, this class is nested inside the data structure class itself so that it can access the internals of the object that instantiated the instance of the nested class.

Make sure that you’ve completed the following checklist.

Does your SpaceList object know anything about its SpaceListIterator’s state? Information about iteration (index of the next item to return) should be confined to Iterator alone.

Are multiple Iterators for the same SpaceList object independent of each other? There can be multiple Iterators for a single SpaceList object, and one iterator’s operation should not affect the state of another.

Does hasNext alter the state of your Iterator? It should not change state.

After you have modified your SpaceList class, write some test code to see if Java’s enhanced for loop works as expected on your SpaceList.

Discussion: Concurrent Modification

For our lab, we regarded our data structure to be “frozen,” while the Iterator was at work. In other words, we assumed that while we were operating on the iterators, the data structure would remain as is. However, this is not generally true in the real world.

Iterator<BankAccount> it = accounts.iterator();
while (it.hasNext()) {
    // Remove the next account!
    checkValidity(it.next()); // This code breaks since the account was removed.
}

If all clients of the data structure were to only read, there would be no problem. However, if any were to modify the data structure while others are reading, this could break the fundamental invariant that next returns the next item if hasNext returns true!

To handle such situations, many Java iterators throw ConcurrentModificationException if they detect that the data structure has been externally modified during the iterator’s lifetime. This is called a “fail-fast” behavior.

List<String> friends = new ArrayList<>();
friends.add("Ervin");
friends.add("Gigi");
friends.add("Lucas");
for (String friend : friends) {
    friends.remove(1);
    System.out.println("friend=" + friend);
}

Discuss with your partner about how to implement this “fail-fast” property for a data structure. How can we propagate the modification to all existing iterators?

If you want to see the Java standard library solution, run the above code, see the error message and click on the link in the stack trace ArrayList.java:937 to see where the fail-fast happened. You can even see how Java implements their nested Iterator.

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:937)

Delegation

The key advantage of using iterators over, say, the old fashioned way of getting items from a list lies in programming cost and execution cost.

Programming cost: How long it takes to develop, modify, and maintain code.
Execution cost: How long or how much space it takes to execute code on a computer.

Iterators are a powerful abstraction that allow us to reduce both programming cost and execution cost.

Let’s compare and contrast all the different ways to iterate over all the elements in an SLList.

Direct pointer manipulation: While this has a good execution cost as it runs in \(\Theta(N)\) time, it increases programming cost as the developer needs to know exactly how linked lists work, not to mention it’s a violation of abstraction barriers! Forgetting to include p = p.next is a very easy way to get stuck in an infinite loop. Moreover, the programmer need to know the exact details of the implementation like the fact that SLList uses a single, circular sentinel node structure, while SpaceList uses an array with spaces between items. As our data structures and our problems get increasingly complex, it will get harder and harder to maintain programs written in this way.

SLList<Integer> list = SLList.of(1, 2, 3, 4, 5);
IntNode p = list.sentinel.next;
while (p != sentinel) {
  int item = p.item;
  System.out.println(item);
  p = p.next;
}

Abstract data type methods: Using our provided ADT methods reduces programming costs significantly since we no longer need to worry about how the linked list works (and the code now works more generally as well), but our execution cost increases as the get operation isn’t optimized for sequential access! The following code runs in \(\Theta(N^2)\) time where \(N\) is the size of the list.

SLList<Integer> list = SLList.of(1, 2, 3, 4, 5);
int i = 0;
while (i < list.size()) {
  int item = list.get(i);
  System.out.println(item);
  i += 1;
}

Iterators: Iterators provide the best of both worlds by creating an abstraction for sequential access. The programming cost is incurred once by the SLList programmer, not the client using SLList! The client only has to understand how the iterator interface works to use the class.

SLList<Integer> list = SLList.of(1, 2, 3, 4, 5);
Iterator<Integer> seer = list.iterator();
while (seer.hasNext()) {
  int item = seer.next();
  System.out.println(item);
}

Java provides the enhanced for loop to make this even easier to use.

SLList<Integer> list = SLList.of(1, 2, 3, 4, 5);
for (int item : list) {
  System.out.println(item);
}

By delegating work to the implementation, we can reduce both programming cost by writing code that adheres to a universally-accepted standard interface while gaining all the execution cost benefits of specialization thanks to dynamic method selection.

In this way, delegation is a form of abstraction. Just like we saw with the idea of encapsulation earlier in the course, delegation makes it much easier to compose efficient programs.

Generate and Test

So far, we have been using our Iterators to obtain values from different data structures we have encountered. However, there are more ways to use Iterators than just listing items present. Say, for instance, you are attempting to get to class, but you find that there is construction blocking your preferred route. You probably don’t carry with you a list of every single possible way to get to class, but you’re still able to think for a moment about the alternative routes (generating possible routes) before deciding on which one to take (“testing” mentally to see if it is optimal). In a similar vein, Iterables in Java aren’t limited to containers which are able to iterate through discrete objects, but are able to iterate through the possibilities available.

To help solidify this example, consider the following snippet of code:

import java.util.Iterator;
import java.util.List;

public class NameGenerator implements Iterable<String> {

    private List<String> firstNames;
    private List<String> lastNames;

    // NameGenerator constructors and methods would normally appear here.

    public Iterator<String> iterator() {
        return new NameIterator();
    }

    private class NameIterator implements Iterator<String> {

        private Iterator<String> firsts;
        private String currFirst;
        private Iterator<String> lasts;

        public NameIterator() {
            firsts = firstNames.iterator();
            prepNext();
        }

        public String next() {
            String result = currFirst + " " + lasts.next();
            prepNext();
            return result;
        }

        public boolean hasNext() {
            return lasts == null || lasts.hasNext();
        }

        private void prepNext() {
            while (true) {
                if (lasts != null && lasts.hasNext()) {
                    break;
                } else if (firsts.hasNext()) {
                    currFirst = firsts.next();
                    lasts = lastNames.iterator();
                } else {
                    break;
                }
            }
        }
    }
}

Here, we can see that when a NameGenerator is iterated over, it will generate pairings of first and last names “on the fly”, without having to store every possible pairing. In this way, we are able to iterate over the possibilities that this object represents, rather than just the values that are explicitly present.

Exercise: `Lockdown`

As mentioned above, we are able to use Iterators to iterate through possiblities that are represented by objects. For the following exercise, you will fill in iterator() and MoveIterator within the Lockdown class in order to iterate through valid moves by generate possible moves and testing if they are valid.

Lockdown is a relatively simple board game played on a square grid in which two players are each attempting to win by preventing the other player from being able to move. The rules are simple:

The X player goes first, then turns alternate until one player loses.
Players may only move to a position adjacent to them that is not currently occupied.
After moving, players must place a “block” in an adjacent, unoccupied position, which then remains for the rest of the game.
If a play cannot move, they lose.

To get an idea of how the game is played, simply run the main method provided. It will (mostly) work, even without the code you need to fill in, which can help you get a feel for the game. When you run the main method, try typing in A1 B2 before returning; you should see the X player move and block a position. Next, try out D4 C3; you should see a similar situation for the O player. Play around with this for a bit so you can familiarize yourself with how the game works.

Most of this code is already completed for you. All you have to do is get Lockdown to iterate through the possible moves available for the current player. This means that the next() method should return a length 2 String[] where the first item is the location that is being moved to and the last item is the location which is being blocked. Remember that you shouldn’t actually make these moves; just iterate through the possible moves available for the current player.

Some of the following will likely be useful to you:

from can be used as a length 2 int[] where the first item is the row and the last item is the column of a given position. Remember that each player only has one piece and the iterator is only checking the moves of the current player.
moveDir and blockDir can be used to keep track of the current directions that are being considered for moves and blocks (since you have to consider each direction that can be blocked for each direction that can be moved to). Remember that checking for which directions can be blocked will require you to somehow obtain the position that you are considering moving to before you can use it.
nextPos() is intended to be a helper method which prepares the next pairing to be returned, similar to prepNext() in the example above. This way, your hasNext() can simply return a check on whether there are any directions left to go, rather than doing considerably more work.
getDirection() will return one of the 8 spots adjacent to a given position. This method takes in a length 2 int[] which represents the current position and returns a length 2 int[] which represents the adjacent position.
moveAvailable() will return whether an input move is allowed on the current game board. As before, inputs are in int[] format, with the inputs being the desired location to move from, the desired location to move to, and a space to treat as though it were empty, respectively. You may be wondering why we would ever treat a space as empty, but consider the case in which you want to move and then block the place you just moved from. If we are checking to see whether we can block that space and don’t treat it as empty, we will think that we cannot place a block there and will report fewer moves than are possible.
getPosition() will take in an int[] position on the board and convert it into the proper String format, so don’t have to worry about converting the board positions into Strings.

Deliverables

Here’s a quick recap of what you need to do to complete this lab.

Make SpaceList.java iterable.
Fill in Lockdown.java so that its moves are iterable.
Submit the worksheet to your lab TA by the end of your section.