join multiple iterators in java

Question

Does anybody know how to join multiple iterators in Java? The solution I found iterate through one iterator first, and then move on to the next one. However, what I want is when next() gets called, it first returns the first element from the first iterator. Next time when next() gets called, it returns the first element from the second iterator, and so on.

Thanks

Answer 1

Using Guava's AbstractIterator for simplicity:

final List<Iterator<E>> theIterators;
return new AbstractIterator<E>() {
  private Queue<Iterator<E>> queue = new LinkedList<Iterator<E>>(theIterators);
  @Override protected E computeNext() {
    while(!queue.isEmpty()) {
      Iterator<E> topIter = queue.poll();
      if(topIter.hasNext()) {
        E result = topIter.next();
        queue.offer(topIter);
        return result;
      }
    }
    return endOfData();
  }
};

This will give you the desired "interleaved" order, it's smart enough to deal with the collections having different sizes, and it's quite compact. (You may wish to use ArrayDeque in place of LinkedList for speed, assuming you're on Java 6+.)

If you really, really can't tolerate another third-party library, you can more or less do the same thing with some additional work, like so:

return new Iterator<E>() {
  private Queue<Iterator<E>> queue = new LinkedList<Iterator<E>>(theIterators);
  public boolean hasNext() {
    // If this returns true, the head of the queue will have a next element
    while(!queue.isEmpty()) {
      if(queue.peek().hasNext()) {
        return true;
      }
      queue.poll();
    }
    return false;
  }
  public E next() {
    if(!hasNext()) throw new NoSuchElementException();
    Iterator<E> iter = queue.poll();
    E result = iter.next();
    queue.offer(iter);
    return result;
  }
  public void remove() { throw new UnsupportedOperationException(); }
};

For reference, the "all of iter1, all of iter2, etc" behavior can also be obtained using Iterators.concat(Iterator<Iterator>) and its overloads.