How can I avoid unchecked cast warning in my generic recursive Iterator?

Question

It's somewhat odd that Java's collection framework has no iterator for recursive data structures. Since I needed something like this, I wrote my own. First off, I need recursive elements:

public interface RecursiveElement<T>
{
 public Iterator<T> getChildrenIterator();
}

And then an Iterator:

public class RecursiveIterator<T> implements Iterator<T>
{
 private Deque<Iterator<T>> stack;
 private Iterator<T> currentStackItem;
 /**
 * Creates a new instance
 * 
 * @param root
 * all children of this node are iterated. The root node itself
 * is not returned
 * @throws NullPointerException
 * if root is null
 */
 public RecursiveIterator(final RecursiveElement<T> root)
 {
 if (root == null)
 throw new NullPointerException(
 "root argument to this iterator must not be null");
 stack = new LinkedList<Iterator<T>>();
 currentStackItem = root.getChildrenIterator();
 }
 @Override
 public boolean hasNext()
 {
 return currentStackItem != null;
 }
 @Override
 public T next()
 {
 final T result = currentStackItem.next();
 if (result instanceof RecursiveElement)
 {
 stack.addLast(currentStackItem);
 // Here is the warning:
 currentStackItem = ((RecursiveElement<T>)result).getChildrenIterator();
 }
 while (currentStackItem != null && !currentStackItem.hasNext())
 currentStackItem = stack.pollLast();
 return result;
 }
 @Override
 public void remove()
 {
 currentStackItem.remove();
 }
}

That code works very well, but I do get a warning from the compiler in the next() method in the line I marked. It is clear to me why this warning occurs, but I have not come up with any solution on how to solve the problem without this warning (save suppressing the warning). Any ideas?

• David Harkness: I don't think you can. Java's generics doesn't allow compound types such as Iterator<T | RecursiveElement<T>>.

Answer 1

I don't think you can do anything about this. You have to cast here, and in the process you lose all information about the type parameter: The compiler can't know that if you have a RecursiveElement, it's always a RecursiveElement<T>, and "thanks" to type erasure it can't check the runtime type.

• David Harkness: As @JvR points out, the problem isn't type erasure but the fact that each collection may contain both items and other collections. This necessitates a cast from T to RecursiveElement<T> which the compiler does not like (rightly so).

Answer 2

The type checker is marking a real issue here. To visualise this, replace your RecursiveElement<T> with a generic Iterable<T>, which provides identical type guarantees.

When different layers mix different types, RecursiveIterator unfortunately breaks down. Here is an example:

public class Main {
 public static void main(String[] args) {
 final RecursiveIterator<IntElem> itr = new RecursiveIterator<IntElem>(new MixedRecursiveElem());
 while ( itr.hasNext() ) {
 IntElem elm = itr.next();
 }
 }
}
class IntElem implements RecursiveElement<Integer> {
 public Iterator<Integer> getChildrenIterator() {
 return Arrays.asList(1, 2, 3).iterator();
 }
}
class MixedRecursiveElem implements RecursiveElement<IntElem> {
 public Iterator<IntElem> getChildrenIterator() {
 return Arrays.asList(new IntElem(), new IntElem()).iterator();
 }
}
Output:
Exception in thread "main" java.lang.ClassCastException: java.lang.Integer cannot be cast to IntElem
 at Main.main(Main.java:7)

Your options are:

• try to push the responsibility of recursing to your actual elements;
• try some wizardry to accept a finite amount of recursion by adding type variables;
• drop type safety and wrap in a filtering iterator.