Iterators

Here is a video lecture for the material outlined below. If you prefer (or want supplemental) textbook readings, Bailey Chapter 8 covers this topic.

The video contains sections on

1. Motivation (0:01)
2. Analyzing a quadratic time operation (4:38)
3. Iterator interface (8:50)
4. Fibonacci Iterator (10:21)
5. Iterating over structures (16:02)
6. Inner classes (19:08)
7. SinglyLinkedListIterator (22:06)
8. SkipIterator (26:13)
9. ReverseIterator (28:25)
10. Iterators and for-each loops (29:46)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=7bb540f7-0278-4c5b-b811-acb60122bfd2

• The problem: Efficient and uniform dispensing of values from data structures
• The solution: The Iterator interface
  • Iterators as dispensers
  • Iterators as generators
  • Iterators as filters
• Iterators that iterate over other Iterators?!
  • Yep, it's a thing
• Iterators and for loops: The Iterable interface
  • Allows use of iterators with for-each

Here's a method (count) that counts the number of times a particular Object appears in a List. List is an interface provided by Java that specifies methods for a list-like structure. Both ArrayList and LinkedList implement this interface.

public static int count(List<Object> data, Object elem) { 
    int count = 0;
    for (int i = 0; i < data.size(); i++) { 
        Object obj = data.get(i);
        if (obj.equals(elem))  // <-- Curly brackets can be omitted from an if, for, or while
            count++;           // <-- when the body consists of a single line
    }
    return count;
}

(All Objects in Java have a default equals method (or define their own).) Does this count on all structures (that we have studied so far)?

Every data structure we've studies has provided some form of these common operations

• size()
• isEmpty()
• add()
• remove()

They also all provide a method for efficient data traversal: public Iterator<E> iterator(). Iterator<E> is an interface for classes that provide support for efficiently visiting all elements of a data structure. The common methods it defines can serve to dispense values for

• Traversal of elements: Iteration
• Production of values: Generation
• Selection of values: Filtering

By providing a simple, minimal interface, the Iterator interface abstracts away details of how to access elements. This must be part of the customized implementation for each data structure.

public interface Iterator<E> {
    boolean hasNext(); // are there more elements in iteration?
    E next();          // return next element
}

Here's a simple example of an iterator that generates values belonging to the sequence of numbers known as the Fibonacci Sequence. This sequence begins with two 1s, and then each subsequent number is the sum of the previous two numbers in the sequence. Thus, we have 1, 1, 2, 3, 5, …

Here's an iterator that effcienctly generates this sequence

import java.util.Iterator;
public class FibonacciNumbers implements Iterator<Integer> { 
    private int next;
    private int current;
    private int length;

    public FibonacciNumbers(int n) {
        length = n;
        next = 1;
        current = 1;
    } 

    public boolean hasNext() { 
        return length >= 0;
    }

    public Integer next() {
        length--;
        int temp = current; 
        current = next;
        next = temp + current; 
        return temp;
    }
}

Why Is This Cool? (it is)

• We could calculate the \(i\)th Fibonacci number each time, but that would be slow
• Observation: to find the \(n\)th Fibonacci number, we need to calculate the previous \(n-1\) Fib numbers…
• But by storing some state, we can easily generate the next Fibonacci number in constant time
• Knowledge about the structure of the problem helps us traverse the Fibonacci space efficiently one element at a time
• We can do the same for data structures

Goal: Have a data structure produce an iterator that return the values of the structure in some order. How can we accomplish this?

• Define an iterator class for the structure, for example

  class ArrayListIterator<E> implements Iterator<E> { ... }
  class SinglyLinkedListIterator<E> implements Iterator<E> { ... }
  

• Provide a method in the data structure that returns an iterator

  public Iterator<E> iterator() { ... }
  

The details of hasNext() and next() often depend on the specific data structure. For example, our SinglyLinkedListIterator will hold a reference to the next node whose value it will return. In contrast our ArrayListIterator will hold the index of next element to return.

Given these two pieces, we rewrite count to use an iterator instead of repeated calls to get:

public int count (List<Object> data, Object elem) { 
    int count = 0;
    Iterator<Object> iter = data.iterator(); 
    while (iter.hasNext()) {
        if(elem.equals(iter.next())) 
            count++; 
    }
    return count;
}

Why do we need an iterator method in the data structure that returns an iterator? Why not just pass the data structure to the constructor for the iterator like this?

public SinglyLinkedListIterator<E>(SinglyLinkedList<E> list) {
      // code to construct the iterator
}

In this case we would only have access to list's public methods. We would be prevented from using the private instance variables of the data structure to efficiently implement our iterator. From within the data structure, however, we can access the instance variables of the structure and use them in the implementation of the iterator.

One way we can give iterators the privileged access to a data structure's internal data we need is to implement them as an inner class of the data structure. In Java, we can nest one class definition within another. We have used this already in our linked list implementations—our ListNode has been an inner class of the SinglyLinkedList class:

public class SinglyLinkedList<E> {
    private class ListNode {
        E data;
        ListNode next;
    }
    ...
}

We could make ListNode an entirely separate class implemented in its own .java file, but there are some good reason to make it an inner class:

• It simplifies the SinglyLinkedList implementation somewhat if it can directly manipulate the fields of the nodes. If ListNode was a separate class with private fields, we'd need to define getters and setters for SinglyLinkedList to use.
• Logically, a ListNode isn't an object that should exist on its own. A ListNode should only exist as part of a SinglyLinkedList. By making it a private inner class, we ensure it's something that can only be used internally by SinglyLinkedList.
• In general, anytime it would be useful to have a new type of object as part of a data structure's implementation, we'll create an inner class for that purpose.

This same idea applies to iterators! If we define our SinglyLinkedListIterator as an inner class within the SinglyLinkedList class, we can use the head field and directly access the next and data fields of the ListNode inner class:

import java.util.Iterator;
public class SinglyLinkedList<E> {
    private class ListNode {
        E data;
        ListNode next;
    }

    private ListNode head;
    private int count;

    ...

    private class SinglyLinkedListIterator<E> implements Iterator<E> {
        private ListNode current;

        public SinglyLinkedListIterator() {
            current = head;
        }

        public boolean hasNext() {
            return current != null;
        }

        public E next() {
            E value = current.data;
            current = current.next;
            return value;
        }
    }

    public Iterator<E> iterator() {
        return new SingleLinkedListIterator();
    }
}

Because this iterator keeps track of the current node it's on, it can return the value at the next node in constant time. This is a big improvement over repeated calls to the linear time get method (where we have to re-find the current node each time).

We can also make iterators that filter the output of other iterators.

• SkipIterator: Skips over a given value
• ReverseIterator: Dispenses elements in the reverse order given by another iterator

Recall that with arrays, we saw we can use a simplified form of the for loop (called a for-each loop):

String[] arr = new String[] {"All", "the", "world's", "a", "stage"};
for( String s : arr) {
    System.out.println(s);
}

We could also rewrite out count method from before to use a for-each loop:

public int count (List<Object> data, Object elem) { 
    int count = 0;
    for (Object obj : data) {
        if(elem.equals(obj)) 
            count++; 
    }
    return count;
}

Why does this work?? Because the List interface provides an iterator() method and we can use the for-each construct…

for( E elem : boxOfStuff ) { ... }

…as long as boxOfStuff implements the Iterable interface:

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

All of the Java structures we've studied so far (ArrayList, LinkedList, Stack, Queue, and Deque) implement Iterable, and so can all be used with a for-each loop.

1. Suppose iter is an Iterator over some data structure. Write a loop using iter to print all the values of the data structure.
2. Suppose that a is an ArrayList of Integer values (ArrayList<Integer>). Write a loop that will use an Iterator to print those Integer values that are even. Try to see if you can write two ways: using a while loop and using a for-each loop.
3. This code attemps to use an iterator to find and return the longest string in a linked list, but is has a bug. What is the problem and how would you fix it?

   // returns the longest string in the list (does not work!)
   public static String longest(LinkedList<String> list) {
       Iterator<String> itr = list.iterator();
       String longest = itr.next(); // initialize to first element
       while (itr.hasNext()) {
           if (itr.next().length() > longest.length()) {
               longest = itr.next();
           }
       }
       return longest;
   }
   

4. What is one benefit of making the list iterator into an inner class?
5. Write a CharacterIterator class that iterates over the characters in a String. It should implement the Iterator<Character> interface, and next should return type Character. The constructor should take the String that the instance will iterate over. It may be useful to refer to the Java String documentation.

• Lab 2
  • Lots of great questions on the check-in forum, make sure to check it out!
  • Adding dummy nodes does not change the efficiency of the list, but serves to greatly simplify some of the code
    • By eliminating edge cases for many of the add and remove methods (see preparatory exercises for examples of these edge cases)
    • Simpler code is easier to write correctly, easier to debug, easier to maintain/modify
  • In what sense are the dummy nodes transparent?
    • internally the list accounts for the dummy nodes, interacts with them, etc.
      • the head and tail fields always refer to the dummy nodes, and they are always the first and last nodes in the list
    • the effects of and values returned by public methods (i.e., the externally observable behavior of the list) are as if the dummy nodes don't exist
  • Method overloading
    • Joe asked a great question on the forum: why are there three removes?
      • private E remove(ListNode node)
      • public E remove(int index)
      • public E remove(E value)
      • We want all three because each does a different thing
      • But how does Java tell them apart?
        • The parameter types are part of a method's identity—two methods with the same name, but different parameter types are treated as entirely separate and don't conflict
        • When you call remove, you pass it a value. The type of this value tells Java which remove to use (the one that takes a value of that type)
    • This is called method overloading.
• Remember to fill out the partner survey for lab 3!
• Questions?
• Form question
• In pods: implement WordIterator
  • constructor takes a string
  • next returns the next word in the string
  • words are separated by spaces
  • s.split(" ") returns a String[] of parts of s separated by spaces
• In pods: share lab progress