6
\$\begingroup\$

This class combines multiple instances of Iterable into one and iterates through them in the order they are given to CombinedIterable.

CombinedIterable.java:

package net.coderodde.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * This class implements an {@code Iterable} combining multiple 
 * {@code Iterable}s into one.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 11, 2016)
 * @param <T> the actual type of elements being iterated.
 */
public class CombinedIterable<T> implements Iterable<T> {

    private final Iterator<T>[] iterators;

    public static <T> Iterable<T> combine(Iterable<T>... iterables) {
        return new CombinedIterable(iterables);
    }

    private CombinedIterable(Iterable<T>... iterables) {
        this.iterators = new Iterator[iterables.length];

        for (int i = 0; i < iterables.length; ++i) {
            this.iterators[i] = iterables[i].iterator();
        }
    }

    @Override
    public Iterator<T> iterator() {
        return new MultiIterator();
    }

    private final class MultiIterator<T> implements Iterator<T> {

        private int index;
        private Iterator<T> lastReadIterator;

        MultiIterator() {
            if (iterators.length > 0) {
                this.lastReadIterator = (Iterator<T>) iterators[0];
            }
        }

        @Override
        public boolean hasNext() {
            while (index < iterators.length) {
                if (iterators[index].hasNext()) {
                    return true;
                }

                ++index;
            }

            return false;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException(
                        "No elements to iterate left.");
            }

            lastReadIterator = (Iterator<T>) iterators[index];
            T element = lastReadIterator.next();

            if (!iterators[index].hasNext()) {
                ++index;
            }

            return element;
        }

        @Override
        public void remove() {
            lastReadIterator.remove();
        }
    }

    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new LinkedList<>();
        Set<Integer> set = new LinkedHashSet<>();

        for (int i = 10; i < 15; ++i) {
            list1.add(i);
        }

        for (int i = 0; i < 3; ++i) {
            set.add(i);
        }

        for (int i = 20; i < 24; ++i) {
            list2.add(i);
        }

        Set<Integer> emptySet   = Collections.<Integer>emptySet();
        List<Integer> emptyList = Collections.<Integer>emptyList();

        CombinedIterable.<Integer>combine(emptySet,
                                          list1,
                                          emptyList,
                                          set,
                                          emptyList,
                                          emptySet,
                                          list2,
                                          emptySet)
                     .forEach((i) -> { System.out.print(i + " "); });

        System.out.println();
    }
}

CombinedIterableTest.java:

package net.coderodde.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;
import org.junit.Test;
import static org.junit.Assert.*;

public class CombinedIterableTest {

    @Test
    public void testEmptyIterator() {
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();

        Iterator<Integer> iterator1 = list.iterator();
        Iterator<Integer> iterator2 = set.iterator();

        assertFalse(iterator1.hasNext());
        assertFalse(iterator2.hasNext());

        try {
            iterator1.next();
            fail("List iterator1 should have thrown an exception upon " +
                 "the call to next().");
        } catch (NoSuchElementException ex) {

        }

        try {
            iterator1.remove();
            fail("List iterator1 should have thrown an exception.upon " +
                 "the call to remove().");
        } catch (IllegalStateException ex) {

        }

        try {
            iterator2.next();
            fail("Set iterator2 should have thrown an exception upon " + 
                 "the call to next().");
        } catch (NoSuchElementException ex) {

        }

        try {
            iterator2.remove();
            fail("Set iterator2 should have thrown an exception upon " + 
                 "the call to next().");
        } catch (IllegalStateException ex) {

        }

        Iterable<Integer> combined = CombinedIterable.combine(list, set);

        assertFalse(combined.iterator().hasNext());

        try {
            combined.iterator().next();
            fail("Combined iterator should have thrown an exception upon " + 
                 "the call to next().");
        } catch (NoSuchElementException ex) {

        }

        try {
            combined.iterator().remove();
            fail("Combined iterator should have thrown an exception upon " + 
                 "the call to next().");
        } catch (IllegalStateException ex) {

        }
    }

    @Test
    public void testNonEmpty() {
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        // LinkedHashSet iterates the contents in the order it was added to it.
        Set<Integer> set = new LinkedHashSet<>();

        list1.add(0);
        list1.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        list2.add(5);

        Iterable<Integer> combined = CombinedIterable.combine(list1, set, list2);
        Iterator<Integer> iterator = combined.iterator();

        for (int i = 0; i < 6; ++i) {
            assertTrue(iterator.hasNext());
            assertEquals(Integer.valueOf(i), iterator.next());
        }

        assertFalse(iterator.hasNext());

        set.clear();

        iterator = CombinedIterable.<Integer>combine(list1, set, list2).iterator();

        assertTrue(iterator.hasNext());
        assertEquals(Integer.valueOf(0), iterator.next());

        assertTrue(iterator.hasNext());
        assertEquals(Integer.valueOf(1), iterator.next());

        assertTrue(iterator.hasNext());
        assertEquals(Integer.valueOf(5), iterator.next());

        iterator = CombinedIterable.<Integer>combine(list1, set, list2).iterator();

        assertTrue(iterator.hasNext());
        assertEquals(Integer.valueOf(0), iterator.next());

        assertTrue(iterator.hasNext());
        assertEquals(Integer.valueOf(1), iterator.next());

        // Remove 1 from the first list.
        iterator.remove();

        assertEquals(list1, Arrays.asList(0));
        assertEquals(list2, Arrays.asList(5));
        assertTrue(set.isEmpty());

        try {
            iterator.remove();
            fail("Removed the same element twice, but IllegalStateException " +
                 "was not thrown.");
        } catch (IllegalStateException ex) {

        }
    }
}

Is there anything I could improve?

\$\endgroup\$
  • \$\begingroup\$ @Tunaki has commented helpfully that if CombinedIterable is not meant to to be re-iterable, then you should handle that explicitly. In addition, if the underlying Iterable implementations have been modified, should that affect your CombinedIterable? In other words, is it desirable for CombinedIterable to materialize the elements to iterate first? These should be quite important design decisions... \$\endgroup\$ – h.j.k. Feb 12 '16 at 3:07
4
\$\begingroup\$

Your code has a lot of warnings that can be avoided.

  1. You should never use raw types, like in the following

    return new CombinedIterable(iterables); // use CombinedIterable<> instead
    

    and

    return new MultiIterator(); // use MultiIterator<> instead
    
  2. You should not create array of a generic type but prefer to use a List.

    this.iterators = new Iterator[iterables.length];
    

    This is fragile and leads to a lot of unnecessary warnings in your code, because you need to explicitely cast afterwards, like in:

    lastReadIterator = (Iterator<T>) iterators[index];
    

    Instead, what you want is to declare iterators as a List<Iterator<T>>. This way, you can use an enhanced for loop to loop through the iterable to add each of their iterator to the list.

    private final List<Iterator<T>> iterators;
    
    private CombinedIterable(Iterable<T>... iterables) {
        this.iterators = new ArrayList<>(iterables.length);
        for (Iterable<T> iterable : iterables) {
            this.iterators.add(iterable.iterator());
        }
    }
    

    also you can retrieve an iterator from that list with just

    lastReadIterator = iterators.get(index);
    
  3. The type T of MultiIterator is hiding the type T of CombinedIterable. Since MultiIterator is an internal helper class, it actually does not need to be typed: it can reuse the type of the enclosing CombinedIterable, with:

    private final class MultiIterator implements Iterator<T> { /* ... */ }
    
  4. The method combine and the constructor CombinedIterable both take a vararg of a generic type, which leads a warning because of a potential heap pollution. If you know this won't happen, you can annotate the method with @SafeVarargs and remove the warning. It also documents that the method does not perform potentially unsafe operation on the varargs parameter.


A side-note in your next() method: the following block of code

if (!iterators.get(index).hasNext()) {
    ++index;
}

is not necessary since the method hasNext() will have already set the index to the next iterator to read from. As such, you can safely remove it.

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

Others have already given excellent reviews of the implementation code. I thought it would be worth giving some review comments on your test code, as you posted it.

Very large tests

You have two very large tests; each contains many assertions and can fail for many reasons.

Smaller, more granular tests (each with approximately one assertion) are easier to read, and provide more useful feedback when they fail.

To manage the initialization code for such a large number of tests, you probably want to use the @Before annotation to define common setup code. Used well, that approach makes tests sufficiently "cheap" that each one doesn't have to do very much.

Verifying the standard library

In some project contexts, it makes sense to check that the language and standard library are behaving as expected, and to assertEquals(2, 1+1). I don't think this is one of those contexts.

The first half of testEmptyIterator (up to the creation of the combined iterator) is just testing the behaviour of the iterators for HashSet and ArrayList; it's probably reasonable to assume that those work as intended.

Checking for thrown exceptions

The pattern:

try {
    doStuffThatShouldFail();
    fail("Where's my exception?");
} catch (UnhappyException e) {
    // do nothing
}

is quite a common one when using test suites that don't support expected exceptions, and it isn't particularly unpleasant.

On the other hand, JUnit 4 does support expected exceptions, so you can just write that test as:

@Test(expected=UnhappyException.class)
public void testFailingStuff() {
    doStuffThatShouldFail();
}

This is shorter and clearer, and lets JUnit both easily verify that the correct exception was thrown and give you a useful error message if it wasn't.

\$\endgroup\$
3
\$\begingroup\$

Iterator not reiterable

The Iterable returned by CombinedIterable.combine cannot be re-iterated, example:

List<String> l = Arrays.asList("hi");
Iterable<String> s = CombinedIterable.combine(l);
s.iterator().forEach(SYstem.out::println); // prints hi
s.iterator().forEach(SYstem.out::println); // doesn't print

Use empty collections instead of new lists/sets

   List<Integer> list = new ArrayList<>();
   Set<Integer> set = new HashSet<>();

EMpty sets/lists returned by Collections are by nature read only, meaning you cannot accidentally modify them. By using those instead of new objects, you can protect the test against modification of the objects

   List<Integer> list = Collections.emptyList();
   Set<Integer> set = Collections.empySet();
\$\endgroup\$
  • 2
    \$\begingroup\$ An iterator that is not reiterable could potentially be wanted: DirectoryStream, for example, only supports a single iterator and throws an exception if an attempt is made to obtain a second iterator. Since this class wraps a list of iterables, you could argue that, since it's possible for an iterator not to be reiterable, we make the wrapper as such. Although, if this is the intent, I guess it should throw an IllegalStateException if iterator() is called a second time and be documented as such. \$\endgroup\$ – Tunaki Feb 11 '16 at 14:08
2
\$\begingroup\$
  1. Store the Iterables, not the iterators, so iteration can be performed repeatedly.
  2. Don't use arrays - they work badly with generics. (Although you need them for varargs.)
  3. Iterate over the Iterables using an iterator, which has a nice symmetry, is simplest, and doesn't incur a large upfront cost and unnecessary storage.
  4. Accept Iterable<? extends T>... so that iterables of different types can be combined, so long as all elements are of type T.

Here is a simple implementation:

    class CombinedIterable<T> implements Iterable<T> {

        private final Iterable<Iterable<? extends T>> iterables;

        CombinedIterable(final Iterable<? extends T>... iterables) {
            this.iterables = Arrays.asList(iterables);
        }

        @Override
        public Iterator<T> iterator() {
            return new Iterator<T>() {

                final Iterator<Iterable<? extends T>> iterableIterator = iterables.iterator();
                Iterator<? extends T> lastIterator, nextIterator;

                @Override
                public boolean hasNext() {
                    while (nextIterator == null || !nextIterator.hasNext()) {
                        if (!iterableIterator.hasNext())
                            return false;
                        nextIterator = iterableIterator.next().iterator();
                    }
                    return true;
                }

                @Override
                public T next() {
                    if (!hasNext()) // if true, sets nextIterator
                        throw new NoSuchElementException();
                    final T next = nextIterator.next();
                    lastIterator = nextIterator;
                    return next;
                }

                @Override
                public void remove() {
                    if (lastIterator == null)
                        throw new IllegalStateException();
                    lastIterator.remove();
                }
            }
        }
    }
\$\endgroup\$
1
\$\begingroup\$

Excellent points by the other responses. One more: If you until the iterator() method is called to call the underlying iterators' iterator() methods, you will maintain the expected behaviors of the iterators that you pass in.

The reason this is important is that you may construct iterators with network, database or other I/O connections - these iterators are created with enough information to perform iteration, but don't necessarily consume resources until you actually call the iterator() method. This isn't always the situation, but in cases where it is the CombinedIterable will maintain the predicted behavior.

\$\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.