DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Flattening Iterator

02.14.2007
| 7441 views |
  • submit to reddit
        A trivial utility class for iterating through a collection of objects in a 'flat' manner, descending into any collections (in this case defined as iterators, iterables or arrays, rather than elements of the Collection interface ) it finds and iterating through their elements. This preserves order, so {a, b, {c, d, {e}}} will be iterated through as a, b, c, d, e.

It's not very complicated, but the implementation amused me so I thought I'd share it.

package playground.library.functional.iterator;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;

/**
 * An iterator that 'flattens out' collections, iterators, arrays, etc. 
 *
 * That is it will iterate out their contents in order, descending into any 
 * iterators, iterables or arrays provided to it.
 *
 * An example (not valid Java for brevity - some type declarations are ommitted):
 *
 * new FlattingIterator({1, 2, 3}, {{1, 2}, {3}}, new ArrayList({1, 2, 3}))
 *
 * Will iterate through the sequence 1, 2, 3, 1, 2, 3, 1, 2, 3.
 *
 * Note that this implements a non-generic version of the Iterator interface so
 * may be cast appropriately - it's very hard to give this class an appropriate 
 * generic type.
 *
 * @author david
 */
public class FlatteningIterator implements Iterator
{
    // Marker object. This is never exposed outside this class, so can be guaranteed
    // to be != anything else. We use it to indicate an absense of any other object.
    private final Object blank = new Object();
    
    /* This stack stores all the iterators found so far. The head of the stack is
     * the iterator which we are currently progressing through */
    private final Stack<Iterator<?>> iterators = new Stack<Iterator<?>>();
    
    // Storage field for the next element to be returned. blank when the next element
    // is currently unknown.
    private Object next = blank;
        
    public FlatteningIterator(Object... objects){
        this.iterators.push(Arrays.asList(objects).iterator());}
    
    public void remove(){
        /* Not implemented */}
    
    private void moveToNext(){
        if ((next == blank) && !this.iterators.empty() ) {
            if (!iterators.peek().hasNext()){
                iterators.pop();
                moveToNext();}
                else{
                    final Object next = iterators.peek().next();
                    if (next instanceof Iterator){
                      iterators.push((Iterator<?>)next);
                      moveToNext();}
                    else if (next instanceof Iterable){
                       iterators.push(((Iterable)next).iterator());
                       moveToNext();}
                    else if (next instanceof Array){
                        iterators.push(Arrays.asList((Array)next).iterator());
                        moveToNext();}
                    else this.next = next;}}}
    
    /**
     * Returns the next element in our iteration, throwing a NoSuchElementException
     * if none is found. 
     */
    public Object next() {
        moveToNext();
        
        if (this.next == blank) throw new NoSuchElementException();
        else{
            Object next = this.next;
            this.next = blank;
            return next;
        }}
    
    /**
     * Returns if there are any objects left to iterate over. This method 
     * can change the internal state of the object when it is called, but repeated
     * calls to it will not have any additional side effects.
     */
    public boolean hasNext(){
        moveToNext();
        return (this.next != blank);}    
}
    

Comments

Snippets Manager replied on Wed, 2007/02/14 - 2:44pm

Note that the previous version had an error in it. It wasn't able to detect a stack full of exhausted iterators and so incorrectly reported more elements when there were none. I've now updated my unit tests to include this case.