9
\$\begingroup\$

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?

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

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.

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

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.