Simplify writing custom iterators in Java

Question

Writing iterators for custom collections in Java is quite difficult, because instead of writing direct code that provides one element after another, you essentially need to write a state machine:

public class CustomCollection<T> implements Iterable<T> { private T[] data; private int size; @Override public Iterator<T> iterator() { return new Iterator<T>() { private int cursor = 0; @Override public boolean hasNext() { return cursor < size; } @Override public T next() { return data[cursor++]; } @Override public void remove() { throw new UnsupportedOperationException(); } }; } // ... } 

For collections more complex than a list of arrays or a linked list, getting these machine states correctly is a difficult task. In fact, the C # development team felt that writing custom iterators was difficult enough to implement special language support ( yield return ), allowing the compiler to create state machines.

Something like yield return is included in the next version of Java? Or are there any library solutions that make my life easier when it comes to writing my own iterators in Java?

Answer 1

Java has always provided a mechanism for maintaining state and continuing execution at a later point in time: threads. The main idea for my library solution is to allow ConcurrentIterable create elements in one thread, and a ConcurrentIterator consume them in another, exchanging through a limited queue. (This is commonly known as a producer / consumer pattern.)

Firstly, this is a demonstration of simplified use:

 public class CustomCollection<T> extends ConcurrentIterable<T> { private T[] data; private int size; @Override protected void provideElements() { for (int i = 0; i < size; ++i) { provideElement(data[i]); } } // ... } 

Pay attention to the complete absence of state machines. All you have to do is get the ConcurrentIterable and implement the provideElements method. Inside this method, you write straightforward code that calls provideElement for each element in the collection.

Sometimes the client does not iterate the entire collection, for example, in a linear search. You can stop providing items immediately after abortion detection by checking iterationAborted() :

  @Override protected void provideElements() { for (int i = 0; i < size && !iterationAborted(); ++i) { provideElement(data[i]); } } 

It is perfectly normal not to check iterationAborted() unless you need additional generated elements. With infinite sequences, checking iterationAborted() required.

How can a producer discover that a consumer has stopped iterating? This is realized due to the strong reference to the consumer token and the weak reference to the same token in the manufacturer. When the consumer stops the iteration, the token becomes suitable for garbage collection, and ultimately it will become invisible to the producer. From now on, all new items will simply be discarded.

(Without this precaution, under certain circumstances, a limited queue might end up filling up, the manufacturer will enter an endless loop, and the items contained will never be garbage collected.)

And now for implementation details:

ConcurrentIterable.java

 import java.util.Iterator; import java.util.concurrent.ArrayBlockingQueue; import java.util.concurrent.BlockingQueue; import java.util.concurrent.TimeUnit; public abstract class ConcurrentIterable<T> implements Iterable<T> { private static final int CAP = 1000; private final ThreadLocal<CommunicationChannel<T>> channels = new ThreadLocal<CommunicationChannel<T>>(); @Override public Iterator<T> iterator() { BlockingQueue<Option<T>> queue = new ArrayBlockingQueue<Option<T>>(CAP); Object token = new Object(); final CommunicationChannel<T> channel = new CommunicationChannel<T>(queue, token); new Thread(new Runnable() { @Override public void run() { channels.set(channel); provideElements(); enqueueSentinel(); } }).start(); return new ConcurrentIterator<T>(queue, token); } protected abstract void provideElements(); protected final boolean iterationAborted() { return channels.get().iterationAborted(); } protected final void provideElement(T element) { enqueue(Option.some(element)); } private void enqueueSentinel() { enqueue(Option.<T> none()); } private void enqueue(Option<T> element) { try { while (!offer(element)) { System.gc(); } } catch (InterruptedException ignore) { ignore.printStackTrace(); } } private boolean offer(Option<T> element) throws InterruptedException { CommunicationChannel<T> channel = channels.get(); return channel.iterationAborted() || channel.queue.offer(element, 1, TimeUnit.SECONDS); } } 

CommunicationChannel.java

 import java.lang.ref.WeakReference; import java.util.concurrent.BlockingQueue; public class CommunicationChannel<T> { public final BlockingQueue<Option<T>> queue; private final WeakReference<Object> token; public CommunicationChannel(BlockingQueue<Option<T>> queue, Object token) { this.queue = queue; this.token = new WeakReference<Object>(token); } public boolean iterationAborted() { return token.get() == null; } } 

ConcurrentIterator.java

 import java.util.Iterator; import java.util.NoSuchElementException; import java.util.concurrent.BlockingQueue; public class ConcurrentIterator<T> implements Iterator<T> { private final BlockingQueue<Option<T>> queue; @SuppressWarnings("unused") private final Object token; private Option<T> next; public ConcurrentIterator(BlockingQueue<Option<T>> queue, Object token) { this.queue = queue; this.token = token; } @Override public boolean hasNext() { if (next == null) { try { next = queue.take(); } catch (InterruptedException ignore) { ignore.printStackTrace(); } } return next.present; } @Override public T next() { if (!hasNext()) throw new NoSuchElementException(); T result = next.value; next = null; return result; } @Override public void remove() { throw new UnsupportedOperationException(); } } 

Option.java

 public class Option<T> { public final T value; public final boolean present; private Option(T value, boolean present) { this.value = value; this.present = present; } public static <T> Option<T> some(T value) { return new Option<T>(value, true); } @SuppressWarnings("unchecked") public static <T> Option<T> none() { return none; } @SuppressWarnings({ "rawtypes", "unchecked" }) private static final Option none = new Option(null, false); } 

Let me know what you think!

Answer 2

No, Java has nothing like yield . As for libraries, Guava contains several useful classes that make it easy to write certain types of iterators:

• AbstractIterator simply requires you to implement the T computeNext() method.
• AbstractLinkedIterator is required to execute T computeNext(T previous) .

AbstractIterator can be used for this as follows:

 return new AbstractIterator<T>() { private int index = 0; protected T computeNext() { return index == size ? endOfData() : data[index++]; } }; 

You can also use Arrays.asList , as Amir suggested, or even do something like this:

 private final List<T> listView = new AbstractList<T>() { public int size() { return data.length; } public T get(int index) { return data[index]; } }; public Iterator<T> iterator() { return listView.iterator(); } 

Answer 3

Perhaps I just do not understand your questions. You cannot do return Arrays.asList(data).iterator()

Answer 4

if you don't mind starting a new thread using SynchronousQueue

 public class InternalIterator<T> implements Iterator<T>{ private SynchronousQueue<T> queue = new SynchronousQueue<T>(); private volatile boolean empty = false; private T current =null; private Object lock = new Object(); private Runner implements Runnable{//run in deamon public void run(){ //iterate and call synchronized()(lock){ try{ queue.offer(t); lock.wait(); }catch(InteruptedException e){ empty=true; throw new RuntimeException(e); } } //for each element to insert this will be the yield return emtpy=true; } } public boolean hasNext(){ if(current!=null)return true; while(!empty){ if( (current=queue.poll(100,TimeUnit.MILLISECONDS))!=null){//avoid deadlock when last element is already returned but empty wasn't written yet return true; } } return false; } public boolean next(){ if(!hasNext())throw new NoSuchElementException(); T tmp = current; current=null; return tmp; } public void remove(){ throw new UnsupportedOperationException(); } }