19. Iterators

• It is often necessary to access every element in some thing

  • Like an array, Stack, Queue, or Bag

• This is called iterating over the things

• This has already been done countless times with arrays

for (int i = 0; i < someArray.length; i++) {
    process(someArray[i]);
}

• However, not everything one may want to iterate over is an array

• Trying to use a for loop for iterating over a linked structure doesn’t work as nicely

• Instead, a while loop is typically used

while (currentNode != null) {
    process(currentNode.getData());
    currentNode = currentNode.getNext();
}

19.1. Iterators

• Java provides a common uniform way to iterate over things

• Iterators are objects that allow iterating over something one element at a time

  • Get each element in an array

  • Get each element from a Bag

• There are two important relevant interfaces:

  • Iterator — used when creating an iterator object

  • Iterable — used when creating something one may want to iterate over

19.2. Iterator Interface

• Iterator objects are typically very simple

• To define an iterator for a class, define the class such that it implements Iterator<T>

  • Uses the Iterator interface

• There are two abstract methods included in the interface to focus on

  • T next() — retrieve the next element

  • boolean hasNext() — checks if another element exists

• With these, it becomes possible to iterate over elements without needing to worry about the underlying container

Iterator<T> iterator = arbitraryIterableThing.iterator();

while (iterator.hasNext()) {
    process(iterator.next());
}

19.2.1. Array Iterator

• Although it is not required to know what the underlying container is when using the iterator

• It is required to define an iterator for the underlying container

• For example, if defining a collection that makes use of an array, an ArrayIterator will need to be defined

public class ArrayIterator<T> implements Iterator<T> {

    private final int size;
    private final T[] elements;
    private int index;

• The fields only include

  • size — number of elements in the collection

  • elements — the array of elements to iterate over

  • index — the current index the iterator is at

    public ArrayIterator(T[] elements, int size) {
        if (size > elements.length) {
            throw new IllegalArgumentException("size exceeds array length.");
        }
        this.elements = elements;
        this.size = size;
        this.index = 0;
    }

• Constructor sets the iterator up to start at the beginning of the array

    @Override
    public boolean hasNext() {
        return index < size;
    }

• hasNext returns a boolean indicating if there is an element to retrieve

• Simply check if the current index (index) is less than the number of elements in the array (size)

    @Override
    public T next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        T returnElement = elements[index];
        index++;
        return returnElement;
    }

• next returns the next element and updates index

  • It returns the element and sets the iterator up to return the subsequent element when needed

• The way this is written, if next is called when there are no more elements to retrieve, an exception is thrown

• Notice that

  • This iterator can only go in one direction

  • Once the iterator object hits the end of the collection, it does not reset

  • To start iterating again, a new iterator would need to be created

Note

There is nothing preventing someone from writing an iterator class that returns the element in some other order. For example, reverse order.

Warning

Consider that the ArrayIterator has reference to the underlying array container. Generally, iterators should not modify the collections they are iterating over. Side effects like this are a recipe for disaster.

19.2.2. Linked Iterator

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedIterator<T> implements Iterator<T> {

    private Node<T> current;

    public LinkedIterator(Node<T> head) {
        current = head;
    }

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

    @Override
    public T next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        T returnElement = current.getData();
        current = current.getNext();
        return returnElement;
    }
}

• For the LinkedIterator, all that is needed is a reference to the current node

• The constructor sets the current node to reference the head of the linked structure

• hasNext just checks if current references null

• next returns the next element and sets the iterator up to return the subsequent element when needed

• Just like the ArrayIterator

  • The iterator only goes in one direction

  • Once an element is retrieved with next(), it is not possible to retrieve it again unless creating a new iterator

Warning

If the Node class is an internal class, then the LinkedIterator will need to be internal too.

19.2.3. Collection Iterators

• Consider a SortedBag

• If using an ArraySortedBag implementation, the iterator method would need to return an ArrayIterator

      @Override
      public Iterator<T> iterator() {
          return new ArrayIterator<>(bag, size());
      }
  

• Similarly, the iterator method for a LinkedSortedBag would need to return a LinkedIterator

      @Override
      public Iterator<T> iterator() {
          return new LinkedIterator<>(head);
      }
  

• Since both versions of the SortedBag return an Iterator

• And since the iterator provides a common way to iterate over the container

• It is possible to iterate over an array and linked structure the exact same way

    Iterator<Integer> iterator = myBag.iterator();

    while (iterator.hasNext()) {
        process(iterator.next());
    }

• In the end, the actual underlying container has no impact on the code used to iterate

19.2.3.1. toString

• Consider the following toString for some collection

    public String toString() {
        StringBuilder builder = new StringBuilder();
        Iterator<T> iterator = this.iterator();
        while(iterator.hasNext()) {
            builder.append(iterator.next());
            builder.append(", ");
        }
        return builder.toString();
    }

• By looking at the above code, it is not possible to know if this is for an array or linked implementation

  • This is a fantastic example of abstraction

  • It is possible to iterate over something (what) without needing to worry about the implementation details (how)

19.3. Iterable Interface

• The Iterator interface is used for creating an iterator object to iterate over something

• If making a class that is to be iterated over, then that class will implement Iterable<T>

  • For example, asking the collection for an iterator

    • myBag.iterator()

• Within the Iterable interface there is one abstract method — iterator()

• If this interface is implemented correctly, the collection is guaranteed to be iterable

19.3.1. For Each

• For things that are iterable, enhanced for loop can be used — for each loop

• In general, it looks like this

for (type refVar: iterableThing) {
    process(refVar);
}

• An example for our SortedBag<Integer> may look like this

for (Integer x: myBag) {
    process(x);
}

• Revisiting the toString() example from above with an enhanced for loop

    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (T element : this) {     // 'this' is the iterable thing
            builder.append(element);
            builder.append(", ");
        }
        return builder.toString();
    }

Note

The enhanced for loop is just syntactic sugar for what was already shown above. The enhanced for loop example

for (Integer x: myBag) {
    process(x);
}

means the same thing as

Iterator<Integer> iterator = myBag.iterator();
while (iterator.hasNext()) {
    process(iterator.next());
}

19.4. Equality of Stacks (and Queues)

• Consider the equals methods from ArrayStack and LinkedStack

    @Override
    public final boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        ArrayStack<?> that = (ArrayStack<?>) o;
        return Arrays.equals(this.stack, 0, this.size(), that.stack, 0, that.size());
    }

    @Override
    public final int hashCode() {
        int result = Objects.hash(top);
        for (int i = 0; i < size(); i++) {
            result = result * 97 + Objects.hashCode(stack[i]);
        }
        return result;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        LinkedStack<?> that = (LinkedStack<?>) o;
        if (this.size() != that.size()) {
            return false;
        }
        Node<?> thisCurrent = this.top;
        Node<?> thatCurrent = that.top;
        while (thisCurrent != null && thatCurrent != null) {
            if (!Objects.equals(thisCurrent.getData(), thatCurrent.getData())) {
                return false;
            }
            thisCurrent = thisCurrent.getNext();
            thatCurrent = thatCurrent.getNext();
        }
        return true;
    }

    @Override
    public int hashCode() {
        int result = Objects.hashCode(size);
        Node<?> current = top;
        while (current != null) {
            result = result * 97 + Objects.hashCode(current.getData());
            current = current.getNext();
        }
        return result;
    }

• It should be possible to check equality between Stack objects, regardless of their implementation

• However, with the current implementation, it’s not possible to compare an ArrayStack and LinkedStack

• A solution to this problem is to make Stacks implement iterable

• If this is done, there is a common way to iterate over the Stack independent of the underlying implementation

@Override
public final boolean equals(Object o) {
    if (this == o) {
        return true;
    }
    if (o == null) {
        return false;
    }
    if (!(o instanceof Stack)) {
        return false;
    }
    Stack<?> that = (Stack<?>) o;
    if (this.size() != that.size()) {
        return false;
    }
    Iterator<T> thisIterator = this.iterator();
    Iterator<?> thatIterator = that.iterator();
    while (thisIterator.hasNext()) {
        if (!Objects.equals(thisIterator.next(), thatIterator.next())) {
            return false;
        }
    }
    return true;
}

19.5. For Next Time

• Consider how the Stack and Queue could be made iterable

• Read Chapter 7

  • 12 pages

19.5.1. Playing Code

• Download and play with

  • ArrayIterator

  • ArrayIteratorTest

  • LinkedIterator

  • LinkedIteratorTest