Iterator pattern/iterator class

Question

I have implemented a simple iterator. Just want to check if I have missed anything.

interface iterator<E>
 {
 boolean hasNext();
 E next();
 }
 class Iterator<E> implements iterator
 {
 E[] arr;
 int curPos = 0;
 @Override
 public boolean hasNext()
 {
 if (curPos >= arr.length || arr[curPos] == null) 
 {
 return false;
 }
 else
 {
 return true;
 }
 }
 @Override
 public E next()
 {
 if(hasNext())
 {
 E res = arr[curPos];
 curPos++;
 return arr[curPos+1];
 }
 else
 {
 throw new runtimeException("No next element available !");
 }
 }
 }

Questions:

1. Why should I not use Object instead of E/template everywhere ?
2. How do I make an iterator for a binary tree.

I assume apart from the above, I would have to implement a traversal algorithm and try to find if the next "traversal" successor exist?

• CheatEx: It is not very clear what is asked in the second question. Could you clarify it or (what probably would be better) move it to a separate question?

Answer 1

I would write an iterator for arrays that way:

import java.util.Iterator;
import java.util.NoSuchElementException;
public class ArrayIterator<E> implements Iterator<E> {
 private final E[] arr;
 private int currentIndex = 0;
 public ArrayIterator(E... arr) {
 if(arr == null) {
 throw new IllegalArgumentException("Array is null");
 }
 this.arr = arr;
 }
 public boolean hasNext() {
 return currentIndex < arr.length;
 }
 public E next() {
 if (! hasNext()) {
 throw new NoSuchElementException();
 }
 return arr[currentIndex++];
 }
 public void remove() {
 throw new UnsupportedOperationException("Not supported.");
 }
}

To your second question: I assume you want to traverse the tree in-order, and that the nodes have no link to the parent, only to the children. Then you need a node list from the root node to the current node, which can store if a node was already visited or not, too.

Then you go left as deep as possible, storing the path in the node list. This is your first current node. When you need the next one, take its parent (from the node list). Next would be the right children of that node (if there are any) or its own parent. The best way to understand this is to take a sheet of paper, draw different trees, and look how the traversal must work.

• Matt Ball: Note, this will not be usable for arrays of primitives, e.g. int[], boolean[], ...
• Landei: @Matt: Yes, you would need specialized versions of that class, but this is a consequence from the insane way Java handles primitive arrays. You have that problem for all other collection stuff as well. On the other hand it's very easy to fix E to a wrapper like Integer and to adapt array and the constructor accordingly.

Answer 2

Because then the consumer of that code could write something like:

Iterator<Foo> iterator = new Iterator<Foo>();
//...
Foo theFoo = iterator.next();

instead of having to cast the object of type Object to type Foo like

Foo theFoo = (Foo)iterator.next();

It avoids potential confusion by being strict about what type of object to expect.

• p101: Thanks, I also see that being strict would also enforce that people dont start equating arrays to trees !!

Answer 3

The next method should throw an exception in case iterator reach the end. It is neither safe nor convenient to get an NPE after the iterator was used improperly.

Answer 4

If you don't define your own iterator, but use java.util.Iterator, you get this error from the compiler:

Iterator.java:9: Iterator is not abstract and does not override abstract method remove() in java.util.Iterator

To use it, where an Iterator is expected, you have to use the java.util.Iterator, which will not be too easy - removing from an array - but you could probably look up, how it is done in the Java source.

But then the compiler is your friend, and tells you, what is wrong.

For a tree, you could write implement multiple iterators - for depth-first traversal, or top-down.