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

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?

• I don't think you can. Java's generics doesn't allow compound types such as Iterator<T | RecursiveElement<T>>. – David Harkness Apr 16 '14 at 17:39

## 2 Answers

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.

• 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). – David Harkness Apr 16 '14 at 17:34

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.