Thursday, October 1, 2009

Fun with Iterators - UnionIterator

The problem
You want to create an iterator for a union of iterators. For example, you have 5 iterators and you want to create an iterator so that it represents elements in all 5 of them in linear fashion.

Solution
(For brevity and simplicity, the UnionIterator is a readonly iterator.)


1 import java.util.ArrayList;
2 import java.util.Arrays;
3 import java.util.Iterator;
4 import java.util.List;
5 import java.util.NoSuchElementException;
6
7 public class ReadonlyUnionIterator<E> implements Iterator<E> {
8
9 private final Iterator<? extends Iterator<E>> parts;
10
11 private Iterator<E> current = null;
12
13 public ReadonlyUnionIterator(final Iterator<? extends Iterator<E>> parts) {
14 this.parts = parts;
15 alignForwardCurrent();
16 }
17
18 public static <E>ReadonlyUnionIterator<E> fromIterables(
19 final Iterable<? extends Iterable<E>> iterableParts) {
20 final List<Iterator<E>> itlist = new ArrayList<Iterator<E>>();
21 for (final Iterable<E> each: iterableParts) {
22 itlist.add(each.iterator());
23 }
24 return new ReadonlyUnionIterator<E>(itlist.iterator());
25 }
26
27 public static <E>ReadonlyUnionIterator<E> fromIterables(
28 final Iterable<E>... parts) {
29 return fromIterables(Arrays.asList(parts));
30 }
31
32 /**
33 * Aligns 'current' by advancing to a non-empty element.
34 * @return true if current has next element, false otherwise
35 */

36 private synchronized boolean alignForwardCurrent() {
37 while (parts.hasNext()) { // parts has next, but they may be empty!
38 current = parts.next();
39 if (current.hasNext()) { return true; }
40 }
41 current = null;
42 return false;
43 }
44
45 public synchronized boolean hasNext() {
46 // NULL is end-of-union marker for 'current'
47 if (current == null) { return false; }
48 if (current.hasNext()) { return true; }
49 // control reached here means current does not have next
50 return alignForwardCurrent();
51 }
52
53 public synchronized E next() {
54 if (hasNext()) { return current.next(); }
55 throw new NoSuchElementException("No more element available");
56 }
57
58 public void remove() {
59 throw new UnsupportedOperationException(
60 "Readonly iterator -- remove() is not supported");
61 }
62
63 }

2 comments:

  1. You probably should use Iterator[Iterator[? extends E]] instead of Iterator[? extends Iterator[E]] so that this class could be used to iterate collections that do not have exactly the same generic types.

    What is more a constructor taking (Collection[? extends E]... collections) would be more useful.

    (sorry for using square brackets - your blog confuses generics with html injection :D )

    ReplyDelete
  2. <E> is a generic parameter by itself -- I am not sure how "? extends E" can be useful.

    Var-args factory method is a good idea. (Item #1 in "Effective Java" by Joshua Bloch says consider using factory methods instead of constructors, which applies here because Collections are not the only iterable things.)

    I have updated the code. Thanks.

    ReplyDelete

Disqus for Char Sequence