5
\$\begingroup\$

Given a list of objects, return an iterator for such a list. Looking for code-review, optimizations and best practices. Verifying complexity to be O(n) where n is sum of all objects, including elements of collections if contained. previously solved here.

public class FlattenIterator implements Iterator<Object> {

    private final Stack<Iterator<?>> iteratorStack;
    private Object next;

    public FlattenIterator(Iterable<?> list) {
        if (list == null) {
            throw new NullPointerException();
        }

        iteratorStack = new Stack<Iterator<?>>();
        iteratorStack.push(list.iterator());
    }


    private void moveToNext() {
       while ((next == null) && !iteratorStack.empty()) {
            Iterator<?> itr = iteratorStack.peek();

            // if iterator is empty, then pop it from stack.
            if (!itr.hasNext()) {
                iteratorStack.pop();
            } else {
                final Object next = itr.next();
                if (next instanceof Iterable) {
                    iteratorStack.push(((Iterable<?>) next).iterator());
                    moveToNext();
                } else {
                    this.next = 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 next != null;
    }

    /**
     * Returns the next element in our iteration, throwing a NoSuchElementException
     * if none is found. 
     */
    public Object next() {
        moveToNext();
        if (next == null) {
            throw new NoSuchElementException(); 
        }

        Object objectToReturn = next;
        next = null;
        return objectToReturn;
    }

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

public class FlattenIteratorTest {

    @Test
    public void testIterator() {
        /**
         *  < <1, 2>, <"abc", "xyz">  <<1, 2>, <"abc", "xyz">> , a, 10 >
         */
        List<Object> genericList = new ArrayList<Object>();

        // integer list
        List<Integer> listInteger = new ArrayList<Integer>(Arrays.asList(1, 2));

        // string list
        List<String> listString = new ArrayList<String>(Arrays.asList("abc", "xyz"));

        // nested lists.
        List<Object> nestedList = new ArrayList<Object>();
        nestedList.add(listInteger);
        nestedList.add(listString);

        genericList.add(listInteger);
        genericList.add(listString);
        genericList.add(nestedList);
        genericList.add('a');
        genericList.add(10);

        /**
         * A very simple test case.
         */
        FlattenIterator fi = new FlattenIterator(genericList); 
        final List<Object> listExpected = new ArrayList<>(Arrays.asList(1, 2, "abc", "xyz", 1, 2, "abc", "xyz", 'a', 10));
        final List<Object> listActual = new ArrayList<>();
        while (fi.hasNext()) {
           listActual.add(fi.next());
        }    
        assertTrue(listExpected.equals(listActual));
    }

    @Test
    public void testEmpty() {
        List<Integer> list = new ArrayList<>();
        list.addAll(list);
        FlattenIterator fi = new FlattenIterator(list);
        assertFalse(fi.hasNext());
    }

}
\$\endgroup\$
  • 2
    \$\begingroup\$ I so want this to be named Flatterator! \$\endgroup\$ – David Harkness Jul 9 '14 at 2:19
5
\$\begingroup\$

I'm going to hit the high notes on my phone and swing back later with details unless someone beats me to it.

Allow null

Add a separate boolean field to track when next holds the actual next element rather than using null as a signal that it needs to be populated so that null elements can be supported.

Avoid Recursion

In this case, there's no reason for moveToNext to call itself. Continuing the loop should have the same effect.

Use Generics

Even though you're stuck using Object for variables which may hold an element or an iterable, you can still add a generic type T to the class and specify it as the return type from next. At least, I think you can. :)

Testing

When using the @Test annotation, you don't have to prefix each test method name with test. However, you really need more descriptive method names, and each test should validate one specific condition.

Burn this into your brain: Arrange, Act, Assert. Arrange the test fixture in the initial state, perform the action being tested, and assert the results. It can become tedious to setup the fixture each time, but helper methods can ease the pain and promote DRYness.

\$\endgroup\$
4
\$\begingroup\$

You have the general right idea, I think.

Naming

FlattenIterator is slightly off, since it is a Verb+Noun. I suggest FlatteningIterator, which is an Adjective+Noun.

Generics

I agree with @DavidHarkness. Even if the Iterables you pass in are non-homogeneous, your class should still be some kind of Iterator<T> rather than just an Iterator.

moveToNext()

Of course, this is where the main challenge is.

The fact that hasNext() calls moveToNext() is weird, since hasNext() should have no visible side-effects. Therefore, either it's wrong for hasNext() to call moveToNext(), or moveToNext() is lying and doesn't always advance. In fact, the latter is true: moveToNext() is "disabled" unless next is null, which happens either when the FlattenIterator is freshly constructed or after you clear next at the end of next(). So, just call moveToNext() at the end of the constructor and at the end of next(), but not in hasNext(). Problem solved — no more lying.

As @DavidHarkness points out, encountering a null value among the iterables causes premature termination. You don't want to test whether next is null. Rather, I propose that you test whether the iteratorStack is empty to know when to terminate.

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

    private final Stack<Iterator<?>> iteratorStack;
    private T next;

    public FlatteningIterator(Iterable<?> list) {
        if (list == null) {
            throw new NullPointerException();
        }

        iteratorStack = new Stack<Iterator<?>>();
        iteratorStack.push(list.iterator());
        moveToNext();
    }

    @SuppressWarnings("unchecked")    // Needed for this.next = (T)next
    private void moveToNext() {
       this.next = null;              // Avoid lingering memory reference
       do {
            Iterator<?> itr = iteratorStack.peek();

            // if iterator is empty, then pop it from stack.
            if (!itr.hasNext()) {
                iteratorStack.pop();
            } else {
                final Object next = itr.next();
                if (next instanceof Iterable) {
                    iteratorStack.push(((Iterable<?>)next).iterator());
                } else {
                    this.next = (T)next;
                    break;
                }
            }
        } while (!this.iteratorStack.isEmpty());
    }

    /**
     * Returns if there are any objects left to iterate over.
     */
    public boolean hasNext() {
        return !this.iteratorStack.isEmpty();
    }

    /**
     * Returns the next element in our iteration, throwing a NoSuchElementException
     * if none is found. 
     */
    public T next() {
        if (this.iteratorStack.isEmpty()) {
            throw new NoSuchElementException();
        }
        try {
            return this.next;
        } finally {
            moveToNext();
        }
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}
\$\endgroup\$
1
\$\begingroup\$

The null check in the constructor seems pointless to me:

public FlattenIterator(Iterable<?> list) {
    if (list == null) {
        throw new NullPointerException();
    }
    iteratorStack = new Stack<Iterator<?>>();
    iteratorStack.push(list.iterator());
}

Without that check, the list.iterator() call will have the same effect anyway.

Unit testing

Especially for a utility class that's kind of tricky, it's good to test more thoroughly with more unit tests. Here are some ideas. (@200_success' proposed solution passes all the tests below.)


This is pretty much the same as yours, but slightly simpler and shorter:

@Test
public void testEmpty() {
    FlatIterator<Object> iter = new FlatIterator<>(Arrays.asList());
    assertFalse(iter.hasNext());
}

A simple, short and sweet sanity check:

@Test
public void testSingletonList() {
    FlatIterator<Integer> iter = new FlatIterator<>(Arrays.asList(3));
    assertTrue(iter.hasNext());
    iter.next();
    assertFalse(iter.hasNext());
}

Test that going beyond the end will throw the expected exception:

@Test(expected = NoSuchElementException.class)
public void testAccessBeyond() {
    new FlatIterator<>(Arrays.asList()).next();
}

The typical pattern of iteration is like this:

while (iter.hasNext()) {
    iter.next();
}

That is, alternating hasNext() and next() calls. It's good to make sure that the implementation can work without hasNext() too:

@Test
public void testAdvanceWithoutHasNext() {
    Integer num = 3;
    List<Integer> list = Arrays.asList(num);
    FlatIterator<Integer> iter = new FlatIterator<>(list);
    assertEquals(num, iter.next());
    assertFalse(iter.hasNext());
}

A simple test to confirm that null elements are handled correctly:

@Test
public void testNullElements() {
    Integer num = 3;
    List<Integer> listWithNull = Arrays.asList(num, null);
    FlatIterator<Integer> iter = new FlatIterator<>(listWithNull);
    assertEquals(num, iter.next());
    assertNull(iter.next());
    assertFalse(iter.hasNext());
}

Test the length of the iterator matches the length of the underlying iterable:

@Test
public void testIteratorCount() {
    List<Integer> list = Arrays.asList(3, null, 4, 5);
    FlatIterator<Integer> iter = new FlatIterator<>(list);
    int count = 0;
    while (iter.hasNext()) {
        ++count;
        iter.next();
    }
    assertEquals(list.size(), count);
}

Sanity test with mixed types:

@Test
public void testMixedElements() {
    List<Object> mixed = new ArrayList<>();
    mixed.add(3);
    mixed.add("hello");
    mixed.add(null);
    FlatIterator<Object> iter = new FlatIterator<>(mixed);
    iter.next();
    iter.next();
    iter.next();
    assertFalse(iter.hasNext());
}

A more complex test with nested lists of several levels deep:

@Test
public void testDeeplyNestedList() {
    List<Object> nested = Arrays.asList(
            1, 2,
            Arrays.asList(3, 4),
            Arrays.asList(5, Arrays.asList(6, 7, 8, Arrays.asList(Arrays.asList(9), 10))),
            Arrays.asList(Arrays.asList(), Arrays.asList(), Arrays.asList(11)),
            Arrays.asList(Arrays.asList(), Arrays.asList(), Arrays.asList()),
            Arrays.asList(Arrays.asList(Arrays.asList())),
            12,
            Arrays.asList(),
            Arrays.asList(13, 14)
    );
    FlatIterator<Object> iter = new FlatIterator<>(nested);
    for (int i = 1; i <= 14; ++i) {
        assertTrue(iter.hasNext());
        assertEquals(i, iter.next());
    }
    assertFalse(iter.hasNext());
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.