How to Merge Two Sorted Streams Into One Sorted Stream, Part II (Java 8 Edition)

Previously, we merged two sorted iterators into one sorted iterator. One might reasonably ask, can we do the same thing with Java 8’s Streams? One might reasonably answer: Yes, we can!

The Data Structure

The Stream object has the same qualities as java.util.Iterator (allowing you to iterate over data without exposing storage), but it also offers a lot more functionality. Stream is a central component of Java 8 Lambdas, designed from the ground up to work with lambda expressions.

Given the prevalence of Stream, it would be nice to convert our Iterator solution into a Stream solution.

It’s All About Leverage

A Stream is backed by a Spliterator. A look at the API shows that a Stream can produce an Iterator and be constructed by a Spliterator, so with a simple Adapter (to make an Iterator look like a Spliterator) we can essentially convert Streams and Iterators back and forth to each other. This will allow us to leverage the existing iterator-merging code that we already wrote in the last post.
Our approach might look like this:

  1. accept two incoming Streams
  2. extract iterators from each one
  3. merge the iterators using our existing iterator-merging code
  4. use the newly merged iterator to create a Spliterator
  5. use the Spliterator to construct a new Stream

Embodied in code, the above description looks like so:

public class StreamMerger<T> {

    public Stream merge(Stream stream1, Stream stream2) {
        Iterator<T> iterator = new MergedIterator<>(stream1.iterator(), stream2.iterator());
        Spliterator<T> spliterator = new SpliteratorAdapter<>(iterator);
        return StreamSupport.stream(spliterator, false);
    }
}

With the SpliteratorAdapter being equally simple:

/**
 * Recommend using with StreamSupport.stream(iteratorStream, false);
 */
public class SpliteratorAdapter<T> extends Spliterators.AbstractSpliterator <T>{

    private final Iterator<T> iterator;

    public SpliteratorAdapter(Iterator<T> iter) {
        super(Long.MAX_VALUE, 0);
        iterator = iter;
    }

    @Override
    public synchronized boolean tryAdvance(Consumer<? super T> action) {
        if(iterator.hasNext()) {
            action.accept(iterator.next());
            return true;
        }
        return false;
    }
}

At this point we can simply use our new StreamMerger to merge as many sorted streams as we want.

The Test

The unit test would be pretty similar to the one for the iterator. In fact we can use the same test data for both tests since the Parameterized test runner requires a public static data provider.

@RunWith(Parameterized.class)
public class StreamMergerTest {

    private final List<Integer> expectedMerge;
    private final StreamMerger<Integer> streamMerger = new StreamMerger<>();
    private final Stream<Integer> mergedStream;

    public StreamMergerTest(List<Integer> list1, List<Integer> list2, List<Integer> expected) {
        expectedMerge = expected;
        mergedStream = streamMerger.merge(list1.stream(), list2.stream());
    }

    @Test
    public void testStream() throws Exception {
        List<Integer> merged = mergedStream.collect(Collectors.<Integer>toList());
        assertEquals(expectedMerge, merged);
    }

    @Parameters
    public static List<Object[]> data() {
        return MergedIteratorTest.data();
    }
}

And there we have it! Now we can merge sorted Java 8 Streams.

Advertisements

4 Comments

Filed under Software Engineering

4 responses to “How to Merge Two Sorted Streams Into One Sorted Stream, Part II (Java 8 Edition)

  1. Where can I find the MergedIterator?

  2. Ihor

    Thanks, but how to do it for more than 2 streams? Like public Stream merge(Set stream)

  3. Out of interest… why are you using your own SpliteratorAdapter rather than just using Spliterators.spliteratorUnknownSize(Iterator, int)?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s