IteratorPattern.md

Iterator pattern

The iterator pattern is a design pattern that is useful for when you want to loop through arrays or similar data structures. It provides a common access methodology for these items.

In essence you have to implement two interfaces. The first is the thing which you want to be able to iterate through - that must implement the Iterable interface. Secondly, you must have an iterator object which handles the moving through - you can have multiple iterators in use simultaneously, as the state of where you currently are is stored within the iterator object. The iterator object must implement - surprise surprise - the Iterator interface.

An implementation of the two interfaces can be seen below:

public interface Iterable<T> {
    //It must be able to create a new iterator
    public Iterator<T> iterator();
}

public interface Iterator<T> {
    //Return the current element, and move onto the next one
    public T next();

    //Check whether there are any left.
    public bool hasNext();
}

In this, we will create a generic array implementation called MyArray. At first we will just write enough for a generic array.

package iterator;

public class MyArray<T> {

    //Due to type erasure, this has to be Object (can't be T)
    private Object[] arr;

    public MyArray(int size) {
        arr = new Object[size];
    }

    public  MyArray(T[] arrIn) {
        arr = new Object[arrIn.length];
        for(int i = 0; i < arr.length; i++)
            arr[i] = arrIn[i];
    }

    public void set(int index, T val) {
        arr[index] = val;
    }

    public T get(int index) {
        return (T)arr[index];
    }
}

From this, we can then then make it iterable, first by implementing the Iterable and then creating an Iterator-implementing class for it.

The class definition is changed to

public class MyArray<T> implements Iterable<T> {

and then the iterator is implemented as an inner class (so it can access the private arr object.)

public Iterator<T> iterator() {
    return this.new MyArrayIterator();
}

private class MyArrayIterator implements Iterator<T> {

    int index = 0;

    public boolean hasNext() {
        return index < arr.length;
    }

    public T next() {
        return (T)arr[index++];
    }
}

We could then write code to use this:

package iterator;

import java.util.Iterator;

public class Main {
    public static void main(String[] args) {
        MyArray<String> arr1 = new MyArray<>(4);
        arr1.set(0, "This");
        arr1.set(1, "Is");
        arr1.set(2, "A");
        arr1.set(3, "Test");

        Iterator<String> myIter = arr1.iterator();

        while (myIter.hasNext()) { //Look at sum for more efficient method
            System.out.println(myIter.next());
        }

        MyArray<Integer> arr2 = new MyArray<>(new Integer[]{1,2,3,4,5});
        System.out.println("Sum: " + sum(arr2));
    }

    private static int sum(Iterable<Integer> a) {
        int total = 0;

        for(int i : a) //A builtin way of looping through array
            total += i;

        return total;
    }
}

Iterators can also be used when it is easier to generate the data on the fly rather than store it all, just by writing a slightly more complex iterable and iterator. Let's take as an example the python range function, which generates all the numbers in a range. We can implement it in an iterator and therefore not need to store all of the numbers.

An implementation of a range iterator is as follows:

package iterator;

import java.util.Iterator;

public class Range implements Iterable<Integer> {

    private int stop, start, step;

    public Range(int stop, int start, int step) {
        this.stop = stop;
        this.start = start;
        this.step = step;
    }

    public Range(int stop, int start) { this (stop, start, 1); }

    public Range(int stop) { this (stop, 0);  }

    public Iterator<Integer> iterator() {
        return this.new RangeIterator();
    }

    private class RangeIterator implements Iterator<Integer> {

        private int curr = start;

        public boolean hasNext() {
            return curr < stop;
        }

        public Integer next() {
            int out = curr;
            curr += step;
            return out;
        }
    }
}