Interview: Collections Iterator

Question

Hi guys i got this as an interview question and was having trouble with it. I am familiar with generics/collections & iterator but the manner i which the Collection is declared completely threw me.

Heres the question: Contained in the provided workspace is cocI, the start of a class that implements an Iterator that can be used to iterate a Collection of Collections. The Collection of Collections is passed into the constructor of the class. The Iterator should iterate through the contents depth-first.

For example, if the Collection of Collections looks like the following:

[0] – [“A”, “B”, “C”] 
[1] – [“D”] 
[2] – [“E”, “F”] 

The iterator should then return the contents in the following order: “A”, “B”, “C”, “D”, “E”, “F”

Q.Provide implementations for the hasNext() and next() methods in cocI

Thanks

import java.util.Collection;
import java.util.Iterator;

public class cocI implements Iterator<Object> {

    private Collection<Collection<Object>> _collOfColl = null;

    public cocI(Collection<Collection<Object>> collofColl) {
        _collOfColl = collofColl;
    }

    public boolean hasNext() {
        // TODO implement this method
        return false;
    }


    public Object next() {
        // TODO implement this method
        return null;
    }


    public void remove() {
        throw new UnsupportedOperationException();
    }

}

Answer 1

All you need to do is keep track of the current collection's iterator within the collection of collections. The hasnext() method, which is the tricky part, will then do one of two things: return true if the current iterator has more elements, if not search until we find a collection that has elements. If we exhaust all the collections, return false.

public class Cocl implements Iterator<Object> {

    private Collection<Collection<Object>> _collOfColl = null;
    private final Iterator<Collection<Object>> coClIterator;
    private Iterator<Object> currentColIterator;

    public Cocl(Collection<Collection<Object>> collofColl) {
        _collOfColl = collofColl;
        coClIterator = collofColl.iterator();
        if (coClIterator.hasNext()) {
            currentColIterator = coClIterator.next().iterator();
        }
    }

    public boolean hasNext() {
        if (currentColIterator == null) {
            return false;
        }
        if (!currentColIterator.hasNext()) {
            while (coClIterator.hasNext()) {
                currentColIterator = coClIterator.next().iterator();
                if (currentColIterator.hasNext()) {
                    return true;
                }
            }
            return false;
        } else {
            return true;
        }
    }

    public Object next() {
        if (hasNext()) {
            return currentColIterator.next();
        }
        throw new NoSuchElementException();
    }


    public void remove() {
        throw new UnsupportedOperationException();
    }

    public static void main(String[] args) {
        Collection<Object> one = Arrays.asList((Object) "A", (Object) "B", (Object) "C");
        Collection<Object> two = Arrays.asList((Object) "D", (Object) "E");
        Cocl cocl = new Cocl(Arrays.asList(one, two));
        while (cocl.hasNext()) {
            Object a = cocl.next();
            System.out.println(a);
        }
    }

}

Answer 2

A couple of introductory remarks:

• cocI is an odd class name; it should start with a capital letter.
• The interface you are supposed to implement doesn't use generics effectively. You should be able to use a data type more specific than Object.
• It is good practice to use the @Override annotation.

The solution involves an iterator for the outer collection and an iterator for the inner collection. When the inner iterator runs out of elements, it needs to be replaced with an iterator for the next collection. However, considering that a collection could be empty, the advancement needs to be done in a loop, which I've put in an advanceCollection() helper.

import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class cocI<T> implements Iterator<T> {

    private Iterator<Collection<T>> outerIterator;
    private Iterator<T> innerIterator;

    public cocI(Collection<Collection<T>> collofColl) {
        this.outerIterator = collofColl.iterator();
        advanceCollection();
    }

    @Override
    public boolean hasNext() {
        return this.innerIterator != null && this.innerIterator.hasNext();
    }

    @Override
    public T next() {
        if (this.innerIterator == null) {
            throw new NoSuchElementException();
        }
        try {
            return this.innerIterator.next();
        } finally {
            advanceCollection();
        }
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }

    private void advanceCollection() {
        while ((this.innerIterator == null || !this.innerIterator.hasNext())
               && this.outerIterator.hasNext()) {
            this.innerIterator = this.outerIterator.next().iterator();
        }
    }

}

---

There is one slightly tricky piece of code I used:

    try {
        return this.innerIterator.next();
    } finally {
        advanceCollection();
    }

It is roughly equivalent to:

    T result = this.innerIterator.next();
    advanceCollection();
    return result;